La tarea es tarea y se me pidio hacer nuestra propia implementación de una clase Grafo, a la que iriamos añadiendo métodos como Dijkstra, floyd, dfprint, ...

De momento he implementado Dijkstra:[Enlace externo eliminado para invitados], basicamente sirve para calcular la ruta de coste mínimo entre dos nodos (A,B).

Mostrar/Ocultar

y Aqui dejo las JUNIT de todos los métodos, si se os ocurren más casos sois bienvenidos a dejar un comentario y eso que me ayudais a completar del todo las pruebas, a más exhaustivas pues mejor vaya.

Mostrar/Ocultar

Ejemplo:
[Enlace externo eliminado para invitados]

Me pase a postearlo por si a alguien le interesaba (hace tiempo no que no me logueo!) y nada, según vaya añadiendole algoritmos pues iré comentando el snipet, que perteneceria a la propia clase Graph.

Saludos
Se me olvido comentar:

PD: Se utiliza una implementación basada en matrices puesto que suponemos que queremos trabajar con grafos densos, la manera más eficiente de hacerlo en caso contrario(grafos ligeros) sería utilizando linkedlists.

PD2: Tal vez estos dias haga otra implementación de dijkstra usando colas de prioridad donde se verá reducido el coste temporal.
Se mejorarón las JUnit y los algoritmos que ya se habian implementado para hacerlos más robustos, se añadio:
- public double[][] floyd()

- public double path(T origen, T destino)
- private boolean existeCamino(int i, int j)
- private double printPath(int i, int j)

- public int recorridoProfundidad(T node)
- private void recProf(int index, boolean[] v)

- public boolean esNodoFuente(T node)
- public boolean esNodoSumidero(T node)
- public boolean esNodoAislado(T node)
- public int[] inaccesiblesDesdeUnNodo(T node)
- public int[] accesiblesDesdeUnNodo(T node)
- public T getMoreEccentricNode()
- protected double excentricidad(T nodo)

- public int gradoSalida(T nodo)
- public int gradoEntrada(T nodo)
Graph.java

Mostrar/Ocultar

Y dejo aqui tambien las JUNIT por si a alguien le interesa:

Pruebas básicas:

Mostrar/Ocultar

Pruebas Exhaustivas y Casos especiales:

Mostrar/Ocultar

Mostrar/Ocultar

Mostrar/Ocultar

Bro decídete es ingles o español...

por otra parte excelente clase. (gracias por aportar algo diferente en el foro como muy pocos.)

Saludos
Imagen
Responder

Volver a “Fuentes”