Mercurial > projects > dil
annotate src/docgen/graphutils/primitives.d @ 806:bcb74c9b895c
Moved out files in the trunk folder to the root.
| author | Aziz K?ksal <aziz.koeksal@gmail.com> |
|---|---|
| date | Sun, 09 Mar 2008 00:12:19 +0100 |
| parents | trunk/src/docgen/graphutils/primitives.d@ec8dd7b8bf0c |
| children |
| rev | line source |
|---|---|
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
1 /** |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
2 * Author: Aziz Köksal & Jari-Matti Mäkelä |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
3 * License: GPL3 |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
4 */ |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
5 module docgen.graphutils.primitives; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
6 |
| 729 | 7 /** |
| 8 * Extendible graph class. Should support separation of concerns now better with mixins. | |
| 9 * Provides a method for cycle marking. | |
| 10 */ | |
| 11 class Graph(alias V, alias E, int capacity = 1) { | |
| 12 static class Edge { | |
| 13 Vertex outgoing, incoming; | |
| 14 //bool cyclic = true; | |
|
462
b7503e02fbe7
Docgen code for handling public imports.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
453
diff
changeset
|
15 |
| 729 | 16 this(Vertex o, Vertex i) { |
| 17 outgoing = o; | |
| 18 incoming = i; | |
| 19 o.outgoingEdges ~= this; | |
| 20 i.incomingEdges ~= this; | |
| 21 } | |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
22 |
| 729 | 23 bool cyclic() { |
| 24 return outgoing.cyclic && incoming.cyclic; | |
| 25 } | |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
26 |
| 729 | 27 mixin E; |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
28 } |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
29 |
| 729 | 30 static class Vertex { |
| 31 Edge[] incomingEdges; | |
| 32 Edge[] outgoingEdges; | |
| 33 bool cyclic = true; | |
| 34 | |
| 35 Edge addChild(Vertex v) { | |
| 36 return new Edge(v, this); | |
| 37 } | |
| 38 | |
| 39 Edge addParent(Vertex v) { | |
| 40 return v.addChild(this); | |
| 41 } | |
| 42 | |
| 43 Vertex[] incoming() { | |
| 44 Vertex[] tmp; | |
| 45 | |
| 46 foreach(edge; incomingEdges) | |
| 47 tmp ~= edge.outgoing; | |
| 48 | |
| 49 return tmp; | |
| 50 } | |
| 51 | |
| 52 Vertex[] outgoing() { | |
| 53 Vertex[] tmp; | |
| 54 | |
| 55 foreach(edge; outgoingEdges) | |
| 56 tmp ~= edge.incoming; | |
| 57 | |
| 58 return tmp; | |
| 59 } | |
| 60 | |
| 61 mixin V; | |
| 62 } | |
| 63 | |
| 64 Vertex[] vertices; | |
| 65 Edge[] edges; | |
| 66 | |
| 67 this() { | |
| 68 vertices.length = capacity; | |
| 69 vertices.length = 0; | |
| 70 edges.length = capacity; | |
| 71 edges.length = 0; | |
| 72 } | |
| 73 | |
| 74 void add(Vertex vertex) { vertices ~= vertex; } | |
| 75 | |
| 76 void add(Edge edge) { edges ~= edge; } | |
| 77 | |
| 78 void connect(Vertex from, Vertex to) { edges ~= from.addParent(to); } | |
| 79 | |
| 80 void connect(int from, int to) { connect(vertices[from], vertices[to]); } | |
| 81 | |
| 82 /** | |
| 83 * Starts from non-cyclic nodes and propagates two both directions. | |
| 84 * Bugs: marks non-cyclic imports between two cycles as cyclic. Could be fixed later if it's really needed (slow) | |
| 85 */ | |
| 86 void markCycles() { | |
| 87 void mark(Vertex v) { | |
| 88 v.cyclic = false; | |
| 89 foreach(o; v.outgoing) { | |
| 90 if (!o.cyclic) continue; | |
| 91 | |
| 92 // propagate | |
| 93 bool cyclic = false; | |
| 94 foreach(p; o.incoming) if (p.cyclic) { cyclic = true; break; } | |
| 95 if (!cyclic) mark(o); | |
| 96 } | |
| 97 } | |
| 98 | |
| 99 void mark2(Vertex v) { | |
| 100 v.cyclic = false; | |
| 101 foreach(o; v.incoming) { | |
| 102 if (!o.cyclic) continue; | |
| 103 | |
| 104 // propagate | |
| 105 bool cyclic = false; | |
| 106 foreach(p; o.outgoing) if (p.cyclic) { cyclic = true; break; } | |
| 107 if (!cyclic) mark2(o); | |
| 108 } | |
| 109 } | |
| 110 | |
| 111 foreach(e; vertices) | |
| 112 if (e.cyclic) { | |
| 113 if (!e.incoming.length) mark(e); | |
| 114 if (!e.outgoing.length) mark2(e); | |
| 115 } | |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
116 } |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
117 } |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
118 |
| 729 | 119 template Empty() {} |
| 120 | |
| 121 | |
| 122 // graph elements used in dep graphs | |
| 123 | |
| 124 | |
| 125 template DepEdge() { | |
| 126 bool isPublic; /// Public import. | |
| 127 bool isStatic; /// Static import. | |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
128 } |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
129 |
| 729 | 130 template DepVertex() { |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
131 char[] name; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
132 char[] location; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
133 uint id; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
134 |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
135 this(char[] name, char[] location, uint id = 0) { |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
136 this.name = name; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
137 this.location = location; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
138 this.id = id; |
|
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
139 } |
| 729 | 140 } |
|
395
ac9cd48151b6
Added couple of docgen modules.
Jari-Matti M?kel? <jmjm@iki.fi>
parents:
diff
changeset
|
141 |
| 729 | 142 alias Graph!(DepVertex, DepEdge, 100) DepGraph; |