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