Source code: com/port80/graph/dot/impl/DotEdge.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.*;
8 import com.port80.util.msg;
9 import com.port80.util.Debug;
10 import com.port80.graph.*;
11
12 /** Graph edge interface.
13 *
14 * @see com.port80.graph.IEdge
15 */
16 public class DotEdge {
17
18 // Static fields ///////////////////////////////////////////////////////
19 //
20
21 private static final String NAME = "DotEdge";
22 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
23 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
24 private static final int VERSION = 0x0001;
25 private static final String VERSIONNAME = "0.1";
26
27 private static final boolean DEBUG = false;
28 static {
29 Debug.add(CLASSNAME);
30 }
31
32 // Instance fields /////////////////////////////////////////////////////
33 //
34
35 protected DotVertex head = null;
36 protected DotVertex tail = null;
37 //
38 int minLength = 1; /** =2 if edge has label. */
39 int weight = 1;
40 //
41 IEdge original = null; /** The original IEdge this DotEdge represent.*/
42 DotEdge next = null; /** Edges that have merged into this one.*/
43 int cutValue = 0;
44 int treeIndex = -1; /** treeIndex>=0 if edge is on the ranking tree.*/
45 boolean reversed = false;
46 /**
47 * Critical edges are preserved as much as possible.
48 * Effort is spent to keep it from being reversed.
49 */
50 boolean fIsCritical = false;
51
52 // Constructors ////////////////////////////////////////////////////////
53 //
54
55 public DotEdge(DotVertex head, DotVertex tail, int minlen, int weight) {
56 this.head = head;
57 this.tail = tail;
58 this.minLength = minlen;
59 this.weight = weight;
60 }
61
62 public DotEdge(DotVertex head, DotVertex tail, IEdge e) {
63 if (head == null || tail == null || e == null) {
64 msg.err(
65 NAME
66 + ": head="
67 + ((head == null) ? "null" : head.getName())
68 + ", tail="
69 + ((tail == null) ? "null" : tail.getName())
70 + ", e="
71 + e);
72 }
73 this.head = head;
74 this.tail = tail;
75 if (e.getAttrString("label") != null)
76 this.minLength = 2;
77 else
78 this.minLength = 1;
79 weight = e.getAttrInt("weight", -1);
80 if (weight < 0) {
81 if (e.getAttrBool("critical"))
82 weight = e.getAttrInt("weight_critical");
83 else
84 weight = e.getAttrInt("weight_default");
85 }
86 original = e;
87 }
88
89 // Instance methods ////////////////////////////////////////////////////
90 //
91
92 /** Calcuate cut value, assuming cutValue of edges on the child
93 * side were already set.
94 */
95 public void initCutValue() {
96 DotVertex v;
97 boolean tailside;
98
99 /* set v to the node on the side of the edge already searched (the
100 * child side). */
101 if (tail.treeParent == this) {
102 // child side is the tail side.
103 v = tail;
104 tailside = true;
105 } else {
106 v = head;
107 tailside = false;
108 }
109 // Provided cutValue of all but the parent edge of v is known,
110 // cutValue of the parent edge can be determined by looking at
111 // only the edges connected to v.
112 // cutValue=sum(xValue(all edges))
113 cutValue = 0;
114 for (int i = 0, max = v.outSize(); i < max; ++i) {
115 cutValue += v.outs[i].xValue(v, tailside);
116 }
117 for (int i = 0, max = v.inSize(); i < max; ++i) {
118 cutValue += v.ins[i].xValue(v, tailside);
119 }
120 if (DEBUG)
121 msg.println(NAME + ".initCutValue(): cutValue=" + cutValue + ": e=" + this);
122 }
123
124 /** Determine xValue of an edge depending on its edge type.
125 *
126 * . xValue of an edge is determined by its direction and whether it
127 * is a tree edge or non-tree edge.
128 *
129 * . The sign of the xValue is determined by:
130 *
131 * child(v) other other
132 * tailside tailside childside sign
133 * (ct) (ot) (oc)
134 * ---------------------------------------
135 * 0 0 0 0 (-ve)
136 * 0 0 1 1 (+ve)
137 * 0 1 0 1
138 * 0 1 1 0
139 * ---------------------------------------
140 * 1 0 0 1
141 * 1 0 1 0
142 * 1 1 0 0
143 * 1 1 1 1
144 * ---------------------------------------
145 *
146 * ie. ct^ot^oc
147 *
148 * @param v The vertex on the child side of edge whose cutValue is
149 * to be determined.
150 * @param tailside v is on the tail side.
151 *
152 * --parent-edge--(v)--this--(other)
153 */
154 private int xValue(DotVertex v, boolean tailside) {
155 DotVertex other;
156 boolean ishead; // other is on the head side.
157 boolean ischild; // other is on the child side.
158 int rv;
159
160 if (v == tail) {
161 other = head;
162 ishead = true;
163 } else {
164 other = tail;
165 ishead = false;
166 }
167 if (other.isDecendent(v)) {
168 // other is on the child side.
169 ischild = true;
170 // By definition, cutValue(e)=(T->H)-(H->T), so e.weight
171 // is always +ve for cutValue(e). Thus contribution of
172 // other edges is always: cutValue(e)-e.weight.
173 if (treeIndex >= 0)
174 rv = cutValue - weight;
175 else
176 rv = -weight;
177 } else {
178 ischild = false;
179 rv = weight;
180 }
181 if (tailside ^ ishead ^ ischild)
182 rv = -rv;
183 if (DEBUG)
184 msg.println(NAME + ".xValue()" + ": xValue=" + rv + ": edge=" + this);
185 return rv;
186 /*
187 if(tailside) {
188 if (e.head == v) d = 1; else d = -1;
189 } else {
190 if (e.tail == v) d = 1; else d = -1;
191 }
192 if(!ischild) d = -d;
193 if(d<0) rv = -rv;
194 return rv;
195 */
196 }
197
198 ////////////////////////////////////////////////////////////////////////
199
200 public int length() {
201 return head.rank - tail.rank;
202 }
203 public int slack() {
204 return head.rank - tail.rank - minLength;
205 }
206 public boolean isReversed() {
207 return reversed;
208 }
209
210 /** Reverse this edge. */
211 public void reverse() {
212 if (DEBUG)
213 msg.println(NAME + ".reverse(): " + this);
214 head.removeIn(this);
215 tail.removeOut(this);
216 DotVertex v = tail;
217 tail = head;
218 head = v;
219 head.addIn(this);
220 tail.addOut(this);
221 reversed = !reversed;
222 }
223
224 /** Merge the specified edge into this one. */
225 public void merge(DotEdge e) {
226 if (DEBUG)
227 msg.println(NAME + ".merge(): this=" + this +", e=" + e);
228 DotEdge last = this;
229 while (last.next != null)
230 last = last.next;
231 last.next = e;
232 if (e.minLength > minLength)
233 minLength = e.minLength;
234 weight += e.weight;
235 e.head.removeIn(e);
236 e.tail.removeOut(e);
237 }
238
239 // IEdge interface /////////////////////////////////////////////////////
240 //
241 public String getName() {
242 return tail.getName() + "->" + head.getName();
243 }
244
245 public DotVertex getHead() {
246 return head;
247 }
248 public DotVertex getTail() {
249 return tail;
250 }
251
252 public DotVertex getOpposite(DotVertex v) {
253 if (v.equals(head))
254 return tail;
255 if (v.equals(tail))
256 return head;
257 msg.err(NAME + ".getOpposite(): vertex not edge end point: v=" + v);
258 return null;
259 }
260
261 public boolean isCritical() {
262 return fIsCritical;
263 }
264 public void setCritical(boolean critical) {
265 fIsCritical = critical;
266 }
267
268 /** @return edge in the reverse direction if one exists, null if not.
269 */
270 public DotEdge findReverseEdge() {
271 DotEdge e;
272 for (int i = 0; i < head.outSize(); ++i) {
273 e = head.outs[i];
274 if (e.getHead().equals(tail))
275 return e;
276 }
277 return null;
278 }
279
280 public String toString() {
281 return getName() + "(i=" + treeIndex + ",s=" + slack() + ",c=" + cutValue + ")";
282 }
283
284 ////////////////////////////////////////////////////////////////////////
285
286 }