¿Alguien sabe dónde puedo obtener una implementación de muestra de un gráfico dirigido y un código de muestra para realizar una clasificación topológica en un gráfico dirigido? (Preferiblemente en Java)Gráfico dirigido a la muestra y código de clasificación topológica
Respuesta
Aquí va una aplicación que hice hace algún tiempo:
/**
*
* Sorts a directed graph, obtaining a visiting sequence ("sorted" list)
* that respects the "Predecessors" (as in a job/task requirements list).
* (when there is freedom, the original ordering is preferred)
*
* The behaviour in case of loops (cycles) depends on the "mode":
* permitLoops == false : loops are detected, but result is UNDEFINED (simpler)
* permitLoops == true : loops are detected, result a "best effort" try, original ordering is privileged
*
* http://en.wikipedia.org/wiki/Topological_sort
*/
public class TopologicalSorter<T extends DirectedGraphNode> {
private final boolean permitLoops;
private final Collection<T> graph; // original graph. this is not touched.
private final List<T> sorted = new ArrayList<T>(); // result
private final Set<T> visited = new HashSet<T>(); // auxiliar list
private final Set<T> withLoops = new HashSet<T>();
// auxiliar: all succesors (also remote) of each node; this is only used if permitLoops==true
private HashMap<T, Set<T>> succesors = null;
public TopologicalSorter(Collection<T> graph, boolean permitLoops) {
this.graph = graph;
this.permitLoops = permitLoops;
}
public void sort() {
init();
for(T n : graph) {
if(permitLoops) visitLoopsPermitted(n);
else visitLoopsNoPermitted(n, new HashSet<T>());
}
}
private void init() {
sorted.clear();
visited.clear();
withLoops.clear();
// build succesors map: only it permitLoops == true
if(permitLoops) {
succesors = new HashMap<T, Set<T>>();
HashMap<T, Set<T>> addTo = new HashMap();
for(T n : graph) {
succesors.put(n, new HashSet<T>());
addTo.put(n, new HashSet<T>());
}
for(T n2 : graph) {
for(DirectedGraphNode n1 : n2.getPredecessors()) {
succesors.get(n1).add(n2);
}
}
boolean change = false;
do {
change = false;
for(T n : graph) {
addTo.get(n).clear();
for(T ns : succesors.get(n)) {
for(T ns2 : succesors.get(ns)) {
if(!succesors.get(n).contains(ns2)) {
change = true;
addTo.get(n).add(ns2);
}
}
}
}
for(DirectedGraphNode n : graph) {
succesors.get(n).addAll(addTo.get(n));
}
} while(change);
}
}
private void visitLoopsNoPermitted(T n, Set<T> visitedInThisCallStack) { // this is simpler than visitLoopsPermitted
if(visited.contains(n)) {
if(visitedInThisCallStack.contains(n)) {
withLoops.add(n); // loop!
}
return;
}
//System.out.println("visiting " + n.toString());
visited.add(n);
visitedInThisCallStack.add(n);
for(DirectedGraphNode n1 : n.getPredecessors()) {
visitLoopsNoPermitted((T) n1, visitedInThisCallStack);
}
sorted.add(n);
}
private void visitLoopsPermitted(T n) {
if(visited.contains(n)) return;
//System.out.println("visiting " + n.toString());
visited.add(n);
for(DirectedGraphNode n1 : n.getPredecessors()) {
if(succesors.get(n).contains(n1)) {
withLoops.add(n);
withLoops.add((T) n1);
continue;
} // loop!
visitLoopsPermitted((T) n1);
}
sorted.add(n);
}
public boolean hadLoops() {
return withLoops.size() > 0;
}
public List<T> getSorted() {
return sorted;
}
public Set<T> getWithLoops() {
return withLoops;
}
public void showResult() { // for debugging
for(DirectedGraphNode node : sorted) {
System.out.println(node.toString());
}
if(hadLoops()) {
System.out.println("LOOPS!:");
for(DirectedGraphNode node : withLoops) {
System.out.println(" " + node.toString());
}
}
}
}
/**
* Node that conform a DirectedGraph
* It is used by TopologicalSorter
*/
public interface DirectedGraphNode {
/**
* empty collection if no predecessors
* @return
*/
public Collection<DirectedGraphNode> getPredecessors();
}
Y aquí un ejemplo de uso:
public class TopologicalSorterExample {
public static class Node implements DirectedGraphNode {
public final String x;
public ArrayList<DirectedGraphNode> antec = new ArrayList<DirectedGraphNode>(); // immediate antecesors
public Node(String x) {this.x= x;}
public Collection<DirectedGraphNode> getPredecessors() {
return antec;
}
public String toString() {
return x;
}
}
public static void main(String[] args) {
List<DirectedGraphNode> graph = new ArrayList<DirectedGraphNode>();
Node na = new Node("A");
Node nb = new Node("B");
Node nc = new Node("C");
Node nd = new Node("D");
Node ne = new Node("E");
nc.antec.add(na);
nc.antec.add(nb);
nd.antec.add(ne);
ne.antec.add(na);
na.antec.add(nd);
graph.add(nc);
graph.add(na);
graph.add(nb);
graph.add(ne);
graph.add(nd);
TopologicalSorter ts = new TopologicalSorter(graph, false);
ts.sort();
ts.showResult();
}
}
Dos características adicionales (o complicaciones) en mi código : Necesitaba soportar bucles (ciclos) en mi caso, de modo que si el gráfico tiene bucles hace un pedido de "mejor esfuerzo". Este comportamiento está controlado por un indicador pasado al constructor. En cualquier caso, puede (debería) llamar al hadLoops()
para preguntar si se detectaron ciclos. Además, quería que el algoritmo de clasificación prefiriera el orden original en caso de libertad.
Aquí es una aplicación sencilla del primer algoritmo de la Wikipedia page on Topological Sort:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
public class Graph {
static class Node{
public final String name;
public final HashSet<Edge> inEdges;
public final HashSet<Edge> outEdges;
public Node(String name) {
this.name = name;
inEdges = new HashSet<Edge>();
outEdges = new HashSet<Edge>();
}
public Node addEdge(Node node){
Edge e = new Edge(this, node);
outEdges.add(e);
node.inEdges.add(e);
return this;
}
@Override
public String toString() {
return name;
}
}
static class Edge{
public final Node from;
public final Node to;
public Edge(Node from, Node to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object obj) {
Edge e = (Edge)obj;
return e.from == from && e.to == to;
}
}
public static void main(String[] args) {
Node seven = new Node("7");
Node five = new Node("5");
Node three = new Node("3");
Node eleven = new Node("11");
Node eight = new Node("8");
Node two = new Node("2");
Node nine = new Node("9");
Node ten = new Node("10");
seven.addEdge(eleven).addEdge(eight);
five.addEdge(eleven);
three.addEdge(eight).addEdge(ten);
eleven.addEdge(two).addEdge(nine).addEdge(ten);
eight.addEdge(nine).addEdge(ten);
Node[] allNodes = {seven, five, three, eleven, eight, two, nine, ten};
//L <- Empty list that will contain the sorted elements
ArrayList<Node> L = new ArrayList<Node>();
//S <- Set of all nodes with no incoming edges
HashSet<Node> S = new HashSet<Node>();
for(Node n : allNodes){
if(n.inEdges.size() == 0){
S.add(n);
}
}
//while S is non-empty do
while(!S.isEmpty()){
//remove a node n from S
Node n = S.iterator().next();
S.remove(n);
//insert n into L
L.add(n);
//for each node m with an edge e from n to m do
for(Iterator<Edge> it = n.outEdges.iterator();it.hasNext();){
//remove edge e from the graph
Edge e = it.next();
Node m = e.to;
it.remove();//Remove edge from n
m.inEdges.remove(e);//Remove edge from m
//if m has no other incoming edges then insert m into S
if(m.inEdges.isEmpty()){
S.add(m);
}
}
}
//Check to see if all edges are removed
boolean cycle = false;
for(Node n : allNodes){
if(!n.inEdges.isEmpty()){
cycle = true;
break;
}
}
if(cycle){
System.out.println("Cycle present, topological sort not possible");
}else{
System.out.println("Topological Sort: "+Arrays.toString(L.toArray()));
}
}
}
me salvó la vida! Gracias M. Jessup! – Aziz
¿Por qué eligió un hashSet? Sin anular equals() y hashCode() en Edges, este es * no * un conjunto. Intenta agregar el mismo borde dos veces. – bastaPasta
codifiqué this implementation hasta hace unas semanas. Está en Java y usa una clase de gráfico dirigido personalizado. ¡Espero que los comentarios sean útiles!
También puede utilizar proyectos de código abierto de terceros, como JGraphT. Proporciona muchas estructuras de gráficos simples y complicadas y su representación visual. Además, no tienes que lidiar con problemas estructurales de esta manera.
También debe sobrescribir la función hashCode()
ya que está utilizando HashSet
en los bordes.
De lo contrario, provocará errores inesperados.
EXP: Agregue dos instancias con el mismo desde y hacia el hashset
. El segundo no se sobrescribirá sin hashCode()
que se supone que debe sobrescribirse.
De acuerdo con jeremy.
Creo que aquí es una aplicación para hacer el código hash basado en Java efectiva: http://www.javapractices.com/topic/TopicAction.do?Id=28
Cómo a agregar a continuación el método para anular el código hash?
@Override
public int hashCode(){
if (fHashCode == 0) {
int result = HashCodeUtil.SEED;
result = HashCodeUtil.hash(result, from);
result = HashCodeUtil.hash(result, to);
}
return fHashCode;
}
Una aplicación que hice basado en la segunda alternativa en la página Wikipedia: http://en.wikipedia.org/wiki/Topological_sorting
public class Graph {
Hashtable<Node, ArrayList<Node>> adjList = new Hashtable<Node, ArrayList<Node>>();
ArrayList<Node> nodes = new ArrayList<Node>();
LinkedList<Node> topoSorted;
public Graph() {}
public void add(Node node) {
if (adjList.contains(node)) {
return;
} else {
adjList.put(node, new ArrayList<Node>());
nodes.add(node);
}
}
public void addNeighbor(Node from, ArrayList<Node> list) {
for (Node to: list) {
addNeighbor(from, to);
}
}
public void addNeighbor(Node from, Node to) {
if (!adjList.containsKey(from)) {
add(from);
}
if (!adjList.containsKey(to)) {
add(to);
}
adjList.get(from).add(to);
to.inDegree++;
to.inNodes.add(from);
}
public void remove(Node node) {
for (Node n: nodes) {
for (Node x: adjList.get(n)) {
if (x.equals(node)) removeNeighbor(n, x);
}
}
adjList.remove(node);
nodes.remove(node);
}
public void removeNeighbor(Node from, Node to) {
adjList.get(from).remove(to);
to.inDegree--;
to.inNodes.remove(from);
}
public void resetVisited() {
for (Node node: nodes) {
node.visited = false;
}
}
public boolean hasEdge(Node from, Node to) {
return adjList.get(from).contains(to) ? true : false;
}
/**
* for DAGS only
* @throws Exception
*/
public void topologicalSort() throws Exception {
/* L <-- Empty list that will contain the sorted elements */
topoSorted = new LinkedList<Node>();
/* Use set to keep track of permanently visited nodes
* in constant time. Does have pointer overhead */
HashSet<Node> visited = new HashSet<Node>();
/* while there are unmarked nodes do */
for (Node n: nodes) {
/* select an unmarked node n
* visit(n)
*/
if (!visited.contains(n)) visit(n, visited);
}
}
/* function: visit(node n) */
public void visit(Node node, HashSet<Node> set) throws Exception {
/* if n has a temporary mark then stop (not a DAG) */
if (node.visited) {
throw new Exception("graph cyclic");
/* if n is not marked (i.e. has not been visited) then... */
} else {
/* mark n temporarily [using boolean field in node]*/
node.visited = true;
/* for each node m with an edge n to m do... */
for (Node m: adjList.get(node)) {
/* visit(m) */
if (!set.contains(m)) visit(m, set);
}
/* mark n permanently */
set.add(node);
/* unmark n temporarily */
node.visited = false;
/* add n to head of L */
topoSorted.addFirst(node);
}
}
public void printGraph() {
for (Node node: nodes) {
System.out.print("from: " + node.value + " | to: ");
for (Node m: adjList.get(node)) {
System.out.print(m.value + " ");
}
System.out.println();
}
}
public void instantiateGraph() {
Node seven = new Node("7");
Node five = new Node("5");
Node three = new Node("3");
Node eleven = new Node("11");
Node eight = new Node("8");
Node two = new Node("2");
Node nine = new Node("9");
Node ten = new Node("10");
addNeighbor(seven, eleven);
addNeighbor(seven, eight);
addNeighbor(five, eleven);
addNeighbor(three, eight);
addNeighbor(three, ten);
addNeighbor(eleven, two);
addNeighbor(eleven, nine);
addNeighbor(eleven, ten);
addNeighbor(eight, nine);
try {
topologicalSort();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for (Node node: topoSorted) {
System.out.print(node.value + " ");
}
}
public class Node {
String value;
boolean visited = false;
int inDegree = 0;
ArrayList<Node> inNodes = new ArrayList<Node>();
public Node (String value) {
this.value = value;
}
}
public static void main(String[] args) {
Graph g = new Graph();
g.instantiateGraph();
}
}
Sólo para aumentar la gran solución por @templatetypedef un poco, he añadido algunas pruebas unitarias para dar alguna confianza añadida para mí y para otros para usar. Espero que esto ayude ...
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.util.List;
import org.junit.Test;
public class TestTopologicalSort {
@Test (expected=java.lang.NullPointerException.class)
public void testNullGraph() {
final List<String> orderedLayers = TopologicalSort.sort(null);
}
@Test
public void testEmptyGraph() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(0, orderedLayers.size());
}
@Test
public void testSingleVertex() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(1, orderedLayers.size());
assertTrue(orderedLayers.contains("a"));
}
@Test
public void testMultipleVertices() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
dag.addNode("b");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(2, orderedLayers.size());
assertTrue(orderedLayers.contains("a"));
assertTrue(orderedLayers.contains("b"));
}
@Test (expected=java.util.NoSuchElementException.class)
public void testBogusEdge() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
dag.addEdge("a", "b");
}
@Test
public void testSimpleDag() {
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("b");
dag.addNode("a");
dag.addEdge("a", "b");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(2, orderedLayers.size());
assertTrue(orderedLayers.get(0).equals("a"));
assertTrue(orderedLayers.get(1).equals("b"));
}
@Test
public void testComplexGraph() {
// node b has two incoming edges
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
dag.addNode("b");
dag.addNode("c");
dag.addNode("d");
dag.addNode("e");
dag.addNode("f");
dag.addNode("g");
dag.addNode("h");
dag.addEdge("a", "b");
dag.addEdge("a", "c");
dag.addEdge("c", "d");
dag.addEdge("d", "b");
dag.addEdge("c", "e");
dag.addEdge("f", "g");
final List<String> orderedLayers = TopologicalSort.sort(dag);
assertEquals(8, orderedLayers.size());
assertTrue(orderedLayers.indexOf("a") < orderedLayers.indexOf("b"));
assertTrue(orderedLayers.indexOf("a") < orderedLayers.indexOf("c"));
assertTrue(orderedLayers.indexOf("c") < orderedLayers.indexOf("d"));
assertTrue(orderedLayers.indexOf("c") < orderedLayers.indexOf("e"));
assertTrue(orderedLayers.indexOf("d") < orderedLayers.indexOf("b"));
assertTrue(orderedLayers.indexOf("f") < orderedLayers.indexOf("g"));
}
@Test (expected=java.lang.IllegalArgumentException.class)
public void testCycle() {
// cycle between a, c, and d
final DirectedGraph<String> dag = new DirectedGraph<String>();
dag.addNode("a");
dag.addNode("b");
dag.addNode("c");
dag.addNode("d");
dag.addNode("e");
dag.addNode("f");
dag.addNode("g");
dag.addNode("h");
dag.addEdge("a", "b");
dag.addEdge("a", "c");
dag.addEdge("c", "d");
dag.addEdge("d", "a");
dag.addEdge("c", "e");
dag.addEdge("f", "g");
final List<String> orderedLayers = TopologicalSort.sort(dag);
}
}
- 1. Clasificación topológica en OCaml
- 2. Clasificación Topológica con Agrupación
- 3. Clasificación topológica usando LINQ
- 4. ¿Cuál es la diferencia entre la clasificación y la clasificación topológica?
- 5. ¿Cómo transformo un gráfico no dirigido y muy cíclico en un gráfico acíclico dirigido?
- 6. Django gráfico no dirigido
- 7. Recorrido de gráfico cíclico dirigido
- 8. Cómo convertir el gráfico acíclico dirigido (DAG) al árbol
- 9. Redis: implementar gráfico dirigido ponderado
- 10. Encontrar un ciclo en un gráfico no dirigido versus encontrar uno en un gráfico dirigido
- 11. topológica Ordenar
- 12. ¿Modelar un gráfico no dirigido en Rails?
- 13. Ejemplos de ordenación topológica en grandes DAG
- 14. Implementando un gráfico dirigido en python
- 15. Flujo máximo - Ford-Fulkerson: gráfico no dirigido
- 16. Cómo almacenar un gran gráfico no ponderado dirigido con miles de millones de nodos y vértices
- 17. ¿La ordenación topológica intenta ordenar vértices o bordes?
- 18. Detectando ciclos de un gráfico (tal vez dirigido o no dirigido) en Haskell
- 19. ¿Encontrando las "mejores raíces" en un gráfico de árbol dirigido?
- 20. Un árbol de expansión mínimo bidireccional de un gráfico dirigido
- 21. Algoritmo de propósito general para triangular un gráfico no dirigido?
- 22. Almacenar un gráfico dirigido en google appengine datastore
- 23. Encontrar todas las rutas en un gráfico dirigido con ciclos
- 24. ¿Cómo implementar un gráfico no dirigido en Ruby on Rails?
- 25. Sugerencias para KSPA en el gráfico no dirigido
- 26. ¿Cómo se almacena un gráfico acíclico dirigido (DAG) como JSON?
- 27. ¿Hay un evento de tocar y tocar dos veces en el gráfico dirigido a la fuerza de d3.js
- 28. ¿Hay algún tipo de datos de Gráfico Acíclico Dirigido (DAG) en Java, y debería usarlo?
- 29. Visualizar gráfico no dirigido que es demasiado grande para GraphViz?
- 30. ¿Cómo puedo verificar si un gráfico dirigido es acíclico?
Lo curioso es que si se hiciera la misma pregunta ahora, se habría reducido y se habría cerrado. Y la gente habría comentado preguntando "¿qué has intentado hasta ahora?". – arunmoezhi
cerrado como no constructivo. Tal como está actualmente, esta pregunta no es adecuada para nuestro formato de preguntas y respuestas.Esperamos que las respuestas cuenten con el respaldo de hechos, referencias o experiencia, pero es probable que esta pregunta solicite debate, argumentos, encuestas o discusiones extensas. Si cree que esta pregunta se puede mejorar y posiblemente se vuelva a abrir, visite el centro de ayuda para obtener ayuda. =========================================== ========= Es una broma. Por supuesto, lo encontré inmensamente útil. –