• Fuentes

 #479332  por sanko
 12 Oct 2015, 21:34
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:[ Debe registrarse para ver este enlace ], basicamente sirve para calcular la ruta de coste mínimo entre dos nodos (A,B).
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.
Ejemplo:
[ Debe registrarse para ver este enlace ]

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
 #479335  por sanko
 12 Oct 2015, 21:49
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.
 #480090  por sanko
 29 Oct 2015, 15:55
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
Y dejo aqui tambien las JUNIT por si a alguien le interesa:

Pruebas básicas:
Pruebas Exhaustivas y Casos especiales:
 #480091  por Pink
 29 Oct 2015, 16:11
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