Mercurial > projects > dil

comparison trunk/src/docgen/graphutils/primitives.d @ 729:ec8dd7b8bf0c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated graph type.
author Jari-Matti M?kel? <jmjm@iki.fi>
date Sun, 03 Feb 2008 19:43:53 +0200
parents b7503e02fbe7
children
comparison
equal deleted inserted replaced
728:41cad5ca4863 729:ec8dd7b8bf0c
2 * Author: Aziz Köksal & Jari-Matti Mäkelä 2 * Author: Aziz Köksal & Jari-Matti Mäkelä
3 * License: GPL3 3 * License: GPL3
4 */ 4 */
5 module docgen.graphutils.primitives; 5 module docgen.graphutils.primitives;
6 6
7 enum EdgeType { 7 /**
8 Unspecified, 8 * Extendible graph class. Should support separation of concerns now better with mixins.
9 Aggregation, 9 * Provides a method for cycle marking.
10 Association, 10 */
11 Composition, 11 class Graph(alias V, alias E, int capacity = 1) {
12 Dependency, 12 static class Edge {
13 Generalization, 13 Vertex outgoing, incoming;
14 Inheritance, 14 //bool cyclic = true;
15 PublicDependency
16 }
17 15
18 enum CycleType { 16 this(Vertex o, Vertex i) {
19 Unspecified, 17 outgoing = o;
20 Cyclefree, 18 incoming = i;
21 Cyclic, 19 o.outgoingEdges ~= this;
22 Reserved 20 i.incomingEdges ~= this;
23 } 21 }
24 22
25 class Edge { 23 bool cyclic() {
26 Vertex outgoing; 24 return outgoing.cyclic && incoming.cyclic;
27 Vertex incoming; 25 }
28 EdgeType type;
29 CycleType cycleType; // used by the cycle algorithm
30 26
31 this(Vertex o, Vertex i, EdgeType type = EdgeType.Unspecified) { 27 mixin E;
32 this.outgoing = o;
33 this.incoming = i;
34 this.type = type;
35 } 28 }
36 29
37 bool isCyclic() { 30 static class Vertex {
38 return cycleType == CycleType.Cyclic; 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 }
39 } 116 }
40 } 117 }
41 118
42 enum VertexType { 119 template Empty() {}
43 Module, 120
44 UnlocatableModule, 121
45 Package, 122 // graph elements used in dep graphs
46 Class, 123
47 Interface, 124
48 Trait 125 template DepEdge() {
126 bool isPublic; /// Public import.
127 bool isStatic; /// Static import.
49 } 128 }
50 129
51 class Vertex { 130 template DepVertex() {
52 char[] name; 131 char[] name;
53 char[] location; 132 char[] location;
54 uint id; 133 uint id;
55
56 Edge[] incomingEdges;
57 Edge[] outgoingEdges;
58 VertexType type;
59 134
60 this(char[] name, char[] location, uint id = 0) { 135 this(char[] name, char[] location, uint id = 0) {
61 this.name = name; 136 this.name = name;
62 this.location = location; 137 this.location = location;
63 this.id = id; 138 this.id = id;
64 } 139 }
140 }
65 141
66 Edge addChild(Vertex v, EdgeType type = EdgeType.Unspecified) { 142 alias Graph!(DepVertex, DepEdge, 100) DepGraph;
67 auto edge = new Edge(v, this, type);
68 incomingEdges ~= edge;
69 v.outgoingEdges ~= edge;
70 return edge;
71 }
72
73 Edge addParent(Vertex v, EdgeType type = EdgeType.Unspecified) {
74 return v.addChild(this, type);
75 }
76
77 Vertex[] incoming() {
78 Vertex[] tmp;
79
80 foreach(edge; incomingEdges)
81 tmp ~= edge.outgoing;
82
83 return tmp;
84 }
85
86 Vertex[] outgoing() {
87 Vertex[] tmp;
88
89 foreach(edge; outgoingEdges)
90 tmp ~= edge.incoming;
91
92 return tmp;
93 }
94
95 bool isCyclic() {
96 foreach(edge; outgoingEdges)
97 if (edge.isCyclic)
98 return true;
99
100 return false;
101 }
102 }