Mercurial > projects > dwt-addons
comparison dwtx/draw2d/graph/GraphUtilities.d @ 98:95307ad235d9
Added Draw2d code, still work in progress
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Sun, 03 Aug 2008 00:52:14 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
96:b492ba44e44d | 98:95307ad235d9 |
---|---|
1 /******************************************************************************* | |
2 * Copyright (c) 2003, 2005 IBM Corporation and others. | |
3 * All rights reserved. This program and the accompanying materials | |
4 * are made available under the terms of the Eclipse Public License v1.0 | |
5 * which accompanies this distribution, and is available at | |
6 * http://www.eclipse.org/legal/epl-v10.html | |
7 * | |
8 * Contributors: | |
9 * IBM Corporation - initial API and implementation | |
10 * Port to the D programming language: | |
11 * Frank Benoit <benoit@tionex.de> | |
12 *******************************************************************************/ | |
13 module dwtx.draw2d.graph.GraphUtilities; | |
14 | |
15 import dwt.dwthelper.utils; | |
16 import dwtx.draw2d.graph.Subgraph; | |
17 import dwtx.draw2d.graph.Node; | |
18 import dwtx.draw2d.graph.NodeList; | |
19 import dwtx.draw2d.graph.DirectedGraph; | |
20 import dwtx.draw2d.graph.Rank; | |
21 import dwtx.draw2d.graph.Edge; | |
22 import dwtx.draw2d.graph.EdgeList; | |
23 | |
24 /** | |
25 * Some utility methods for graphs. | |
26 * @author Eric Bordeau | |
27 * @since 2.1.2 | |
28 */ | |
29 class GraphUtilities { | |
30 | |
31 static Subgraph getCommonAncestor(Node left, Node right) { | |
32 Subgraph parent; | |
33 if (auto p = cast(Subgraph)right ) | |
34 parent = p; | |
35 else | |
36 parent = right.getParent(); | |
37 while (parent !is null) { | |
38 if (parent.isNested(left)) | |
39 return parent; | |
40 parent = parent.getParent(); | |
41 } | |
42 return null; | |
43 } | |
44 | |
45 /** | |
46 * Returns <code>true</code> if the given graph contains at least one cycle. | |
47 * @param graph the graph to test | |
48 * @return whether the graph is cyclic | |
49 */ | |
50 public static bool isCyclic(DirectedGraph graph) { | |
51 return isCyclic(new NodeList(graph.nodes)); | |
52 } | |
53 | |
54 /** | |
55 * Recursively removes leaf nodes from the list until there are no nodes remaining (acyclic) | |
56 * or there are no leaf nodes but the list is not empty (cyclic), then returns the result. | |
57 * @param nodes the list of nodes to test | |
58 * @return whether the graph is cyclic | |
59 */ | |
60 public static bool isCyclic(NodeList nodes) { | |
61 if (nodes.isEmpty()) | |
62 return false; | |
63 int size = nodes.size(); | |
64 // remove all the leaf nodes from the graph | |
65 for (int i = 0; i < nodes.size(); i++) { | |
66 Node node = nodes.getNode(i); | |
67 if (node.outgoing is null || node.outgoing.isEmpty()) { // this is a leaf node | |
68 nodes.remove(node); | |
69 for (int j = 0; j < node.incoming.size(); j++) { | |
70 Edge e = node.incoming.getEdge(j); | |
71 e.source.outgoing.remove(e); | |
72 } | |
73 } | |
74 } | |
75 // if no nodes were removed, that means there are no leaf nodes and the graph is cyclic | |
76 if (nodes.size() is size) | |
77 return true; | |
78 // leaf nodes were removed, so recursively call this method with the new list | |
79 return isCyclic(nodes); | |
80 } | |
81 | |
82 /** | |
83 * Counts the number of edge crossings in a DirectedGraph | |
84 * @param graph the graph whose crossed edges are counted | |
85 * @return the number of edge crossings in the graph | |
86 */ | |
87 public static int numberOfCrossingsInGraph(DirectedGraph graph) { | |
88 int crossings = 0; | |
89 for (int i = 0; i < graph.ranks.size(); i++) { | |
90 Rank rank = graph.ranks.getRank(i); | |
91 crossings += numberOfCrossingsInRank(rank); | |
92 } | |
93 return crossings; | |
94 } | |
95 | |
96 /** | |
97 * Counts the number of edge crossings in a Rank | |
98 * @param rank the rank whose crossed edges are counted | |
99 * @return the number of edge crossings in the rank | |
100 */ | |
101 public static int numberOfCrossingsInRank(Rank rank) { | |
102 int crossings = 0; | |
103 for (int i = 0; i < rank.size() - 1; i++) { | |
104 Node currentNode = rank.getNode(i); | |
105 Node nextNode; | |
106 for (int j = i + 1; j < rank.size(); j++) { | |
107 nextNode = rank.getNode(j); | |
108 EdgeList currentOutgoing = currentNode.outgoing; | |
109 EdgeList nextOutgoing = nextNode.outgoing; | |
110 for (int k = 0; k < currentOutgoing.size(); k++) { | |
111 Edge currentEdge = currentOutgoing.getEdge(k); | |
112 for (int l = 0; l < nextOutgoing.size(); l++) { | |
113 if (nextOutgoing.getEdge(l).getIndexForRank(currentNode.rank + 1) | |
114 < currentEdge.getIndexForRank(currentNode.rank + 1)) | |
115 crossings++; | |
116 } | |
117 } | |
118 } | |
119 } | |
120 return crossings; | |
121 } | |
122 | |
123 private static NodeList search(Node node, NodeList list) { | |
124 if (node.flag) | |
125 return list; | |
126 node.flag = true; | |
127 list.add(node); | |
128 for (int i = 0; i < node.outgoing.size(); i++) | |
129 search(node.outgoing.getEdge(i).target, list); | |
130 return list; | |
131 } | |
132 | |
133 /** | |
134 * Returns <code>true</code> if adding an edge between the 2 given nodes will introduce a | |
135 * cycle in the containing graph. | |
136 * @param source the potential source node | |
137 * @param target the potential target node | |
138 * @return whether an edge between the 2 given nodes will introduce a cycle | |
139 */ | |
140 public static bool willCauseCycle(Node source, Node target) { | |
141 NodeList nodes = search(target, new NodeList()); | |
142 nodes.resetFlags(); | |
143 return nodes.contains(source); | |
144 } | |
145 | |
146 static bool isConstrained(Node left, Node right) { | |
147 Subgraph common = left.getParent(); | |
148 while (common !is null && !common.isNested(right)) { | |
149 left = left.getParent(); | |
150 common = left.getParent(); | |
151 } | |
152 while (right.getParent() !is common) | |
153 right = right.getParent(); | |
154 return (left.rowOrder !is -1 && right.rowOrder !is -1) | |
155 && left.rowOrder !is right.rowOrder; | |
156 } | |
157 | |
158 } |