Mercurial > projects > dil

comparison trunk/src/cmd/ImportGraph.d @ 720:74cdbb25c7c8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Using old algo for cycle detection again.
author Aziz K?ksal <aziz.koeksal@gmail.com>
date Fri, 01 Feb 2008 15:40:32 +0100
parents 8f8c9ab3f3ba
children 90668b83ae5e
comparison
equal deleted inserted replaced
719:8f8c9ab3f3ba 720:74cdbb25c7c8
55 /// Walks the graph and marks cyclic vertices and edges. 55 /// Walks the graph and marks cyclic vertices and edges.
56 void detectCycles() 56 void detectCycles()
57 { // Cycles could also be detected in the GraphBuilder, 57 { // Cycles could also be detected in the GraphBuilder,
58 // but having the code here makes things much clearer. 58 // but having the code here makes things much clearer.
59 59
60 // Commented out because this algorithm doesn't work.
60 // Returns true if the vertex is in status Visiting. 61 // Returns true if the vertex is in status Visiting.
61 bool visit(Vertex vertex) 62 /+bool visit(Vertex vertex)
62 { 63 {
63 switch (vertex.status) 64 switch (vertex.status)
64 { 65 {
65 case Vertex.Status.Visiting: 66 case Vertex.Status.Visiting:
66 vertex.isCyclic = true; 67 vertex.isCyclic = true;
77 assert(0, "unknown vertex status"); 78 assert(0, "unknown vertex status");
78 } 79 }
79 return false; // return (vertex.status == Vertex.Status.Visiting); 80 return false; // return (vertex.status == Vertex.Status.Visiting);
80 } 81 }
81 // Start visiting vertices. 82 // Start visiting vertices.
82 visit(vertices[0]); 83 visit(vertices[0]);+/
83 84
84 foreach (edge; edges) 85 //foreach (edge; edges)
85 if (edge.from.isCyclic && edge.to.isCyclic) 86 // if (edge.from.isCyclic && edge.to.isCyclic)
86 edge.isCyclic = true; 87 // edge.isCyclic = true;
88
89 // Use functioning algorithm.
90 analyzeGraph(vertices, edges);
87 } 91 }
88 } 92 }
89 93
90 /// Represents a directed connection between two vertices. 94 /// Represents a directed connection between two vertices.
91 class Edge 95 class Edge
333 } 337 }
334 338
335 Stdout("}\n"); 339 Stdout("}\n");
336 } 340 }
337 341
338 /+
339 // This is the old algorithm that was used to detect cycles in a directed graph. 342 // This is the old algorithm that was used to detect cycles in a directed graph.
340 void analyzeGraph(Vertex[] vertices_init, Edge[] edges) 343 void analyzeGraph(Vertex[] vertices_init, Edge[] edges)
341 { 344 {
345 edges = edges.dup;
342 void recursive(Vertex[] vertices) 346 void recursive(Vertex[] vertices)
343 { 347 {
344 foreach (idx, vertex; vertices) 348 foreach (idx, vertex; vertices)
345 { 349 {
346 uint outgoing, incoming; 350 uint outgoing, incoming;
405 if (edge) 409 if (edge)
406 edge.isCyclic = true; 410 edge.isCyclic = true;
407 } 411 }
408 recursive(vertices_init); 412 recursive(vertices_init);
409 } 413 }
410 +/