![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag_start.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / cmd / dag|
Return to dag_start.c CVS log | Up to [Research Unix] / researchv10dc / cmd / dag |
1.1 root 1: #include "draw_dag.h"
2:
3:
4: /*
5: Routines to start and end draw_dag.
6: In the starting phase, make in/out edge lists with no self-loops,
7: multiple edges and cycles. This phase also makes sure that
8: constraints of the form 'this set of nodes must be at the same level'
9: can be later satisfied.
10: */
11: static int Clean_up; // 1 if things need cleaned up before starting
12:
13: static int multiple(int, edge_t*, int),
14: findroot(int);
15: static void dfs(int, edge_t**, edge_t**, int*, int*, int**),
16: setunion(int*);
17:
18:
19:
20: void dag_start(int n_nodes, node_t **nodes, edge_t **outedges, options_t options)
21: {
22: // clean up previous space
23: if(Clean_up)
24: {
25: if(Verbose)
26: fprintf(stderr,"Clean up space from last call\n");
27: Clean_up = 0;
28:
29: for(int v = 0; v < N_real_nodes; v++)
30: {
31: for(edge_t *e = Outedges[v]; e; e = e->next)
32: if(e->splinept)
33: delete e->splinept;
34: if(Noedges)
35: for(e = Noedges[v]; e; e = e->next)
36: if(e->splinept)
37: delete e->splinept;
38: }
39:
40: deledges(N_nodes,Inedges);
41: deledges(N_nodes,Outedges);
42: if(Noedges)
43: deledges(N_real_nodes,Noedges);
44: Outedges = Inedges = Noedges = NULL;
45: if(Istems)
46: {
47: delete Istems;
48: delete Ostems;
49: delete Stems;
50: Istems = Ostems = NULL;
51: Stems = NULL;
52: }
53:
54: for(v = 0; v <= Maxlevel; v++)
55: delete Rank[v];
56: delete Rank; Rank = NULL;
57:
58: delete Root; Root = NULL;
59: delete Level; Level = NULL;
60: delete N_level; N_level = NULL;
61: delete Width; Width = NULL;
62: delete Height; Height = NULL;
63: delete Levelheight; Levelheight = NULL;
64: delete Levelpos; Levelpos = NULL;
65: delete Nodepos; Nodepos = NULL;
66: delete Deleted; Deleted = NULL;
67: }
68:
69: if (n_nodes <= 0)
70: return;
71:
72: // copy node Widths/Heights
73: Width = new int[n_nodes];
74: Height = new int[n_nodes];
75: for(int n = 0; n < n_nodes; ++n) {
76: Width[n] = nodes[n]->width;
77: Height[n] = nodes[n]->height;
78: }
79: Nodesep = options.nodesep;
80: Levelsep = options.ranksep;
81: Xbound = options.xbound;
82: Ybound = options.ybound;
83:
84: // construct equivalence class indices for vertices at same levels
85: int *srcs = options.source_nodes;
86: int *sinks = options.sink_nodes;
87: int **same = options.same_nodes;
88: Root = new int[n_nodes];
89: for(n = 0; n < n_nodes; ++n)
90: Root[n] = n;
91: if(srcs && srcs[0] != -1)
92: setunion(srcs);
93: if(sinks && sinks[0] != -1)
94: setunion(sinks);
95: if(same)
96: for(n = 0; same[n]; ++n)
97: if(same[n][0] != -1)
98: setunion(same[n]);
99: // compress union trees
100: for(n = 0; n < n_nodes; ++n)
101: (void)findroot(n);
102:
103: // construct auxilliary lists of edges turned around by min/max nodes
104: int source = (srcs && srcs[0] != -1) ? Root[srcs[0]] : -1;
105: int sink = (sinks && sinks[0] != -1) ? Root[sinks[0]] : -1;
106: if(sink == source)
107: sink = -1;
108: edge_t **aux = (edge_t **)0;
109: if(source >= 0 || sink >= 0)
110: {
111: aux = new edge_t*[n_nodes];
112: for(n = 0; n < n_nodes; ++n)
113: {
114: if(Root[n] != source)
115: {
116: for(edge_t *e = outedges[n]; e; e = e->next)
117: if(Root[e->node] == source)
118: {
119: aux[e->node] = new edge_t(n,e->weight,
120: e->width,e->minlen,aux[e->node]);
121: aux[e->node]->chain = e;
122: e->chain = aux[e->node];
123: }
124: }
125:
126: if(Root[n] == sink)
127: {
128: for(edge_t *e = outedges[n]; e; e = e->next)
129: if(Root[e->node] != sink)
130: {
131: aux[e->node] = new edge_t(n,e->weight,
132: e->width,e->minlen,aux[e->node]);
133: aux[e->node]->chain = e;
134: e->chain = aux[e->node];
135: }
136: }
137: }
138: }
139:
140: // make space for edges
141: N_edges = N_self_edges = N_repeat_edges = N_revert_edges = 0;
142: N_nodes = N_real_nodes = n_nodes;
143: Inedges = new edge_t*[n_nodes];
144: Outedges = new edge_t*[n_nodes];
145:
146: // use depth-first search to construct edge lists
147: int *active = new int[n_nodes];
148: int *marked = new int[n_nodes];
149:
150: // compute the squashed trees of equi-level nodes
151: int **sets = new int*[N_nodes];
152: for(n = 0; n < N_nodes; ++n)
153: active[Root[n]]++;
154: for(n = 0; n < N_nodes; ++n)
155: if(active[n] > 0) {
156: sets[n] = new int[active[n]+1];
157: sets[n][active[n]] = -1;
158: active[n] = 0;
159: }
160: for(n = 0; n < N_nodes; ++n)
161: sets[Root[n]][active[Root[n]]++] = n;
162: for(n = 0; n < N_nodes; ++n)
163: active[n] = 0;
164:
165: for(n = 0; n < n_nodes; ++n)
166: if(n == Root[n] && !marked[n])
167: dfs(n,outedges,aux,active,marked,sets);
168: delete active;
169: delete marked;
170: for(n = 0; n < n_nodes; ++n)
171: if(sets[n])
172: delete sets[n];
173: delete sets;
174:
175: // restore space used by auxilliary edges
176: if(source >= 0 || sink >= 0)
177: {
178: for(n = 0; n < n_nodes; ++n)
179: {
180: edge_t *nexte;
181: for(edge_t *e = aux[n]; e; e = nexte)
182: {
183: nexte = e->next;
184: delete e;
185: }
186: }
187: delete aux;
188: }
189:
190: if (Verbose)
191: {
192: #ifdef TIMING
193: fprintf(stderr,"%d\t%d\t",N_nodes,N_edges);
194: #else
195: fprintf(stderr,"N_nodes = %d, N_edges=%d\n",N_nodes,N_edges);
196: fprintf(stderr,"N_self_edges = %d\n", N_self_edges);
197: fprintf(stderr,"N_flat_edges = %d\n", N_flat_edges);
198: fprintf(stderr,"N_repeat_edges = %d\n", N_repeat_edges);
199: fprintf(stderr,"N_revert_edges = %d\n", N_revert_edges);
200: #endif
201: }
202: }
203:
204:
205: void dag_end(node_t **nodes, edge_t **outedges)
206: {
207: // output node positions
208: for(int v = 0; v < N_real_nodes; v++)
209: {
210: nodes[v]->pos.x = Nodepos[v];
211: nodes[v]->pos.y = Levelpos[Level[v]];
212: }
213:
214: // output edge splines
215: for(v = 0; v < N_real_nodes; ++v)
216: for(edge_t *e = outedges[v]; e; e = e->next)
217: {
218: // copy the points
219: Point *sp = e->chain->splinept;
220: for(int n_points = 0; sp[n_points].x >= 0; ++n_points)
221: ;
222:
223: Point *pt;
224: if(e->chain->count > 1)
225: {
226: pt = new Point[n_points+1];
227: for(int n = 0; n <= n_points; ++n)
228: {
229: pt[n].x = sp[n].x;
230: pt[n].y = sp[n].y;
231: }
232: }
233: else
234: {
235: pt = sp;
236: e->chain->splinept = NULL;
237: }
238:
239: // reverse the order of inverted edges
240: if(Level[v] > Level[e->node])
241: {
242: int n = 0, m = n_points-1;
243: for(; n < m; ++n, --m)
244: {
245: swap(pt[n].x,pt[m].x);
246: swap(pt[n].y,pt[m].y);
247: }
248: }
249:
250: e->top.x = pt[1].x;
251: e->top.y = pt[1].y;
252: e->bottom.x = pt[n_points-2].x;
253: e->bottom.y = pt[n_points-2].y;
254:
255: // adjust for multiple edges
256: if(e->chain->count > 1)
257: {
258: int place = e->place;
259: int width = e->chain->width;
260: if(v == e->node)
261: {
262: place -= width/2;
263: pt[2].x += place;
264: pt[1].y -= place/2;
265: pt[3].y += place/2;
266: }
267: else if(Level[v] == Level[e->node])
268: {
269: if(e->chain->weight > 0)
270: place = -place;
271: int mx = iabs(pt[n_points/2].x - pt[0].x);
272: for(int n = 1; n < n_points-1; ++n)
273: {
274: int d = iabs(pt[n].x - pt[0].x);
275: d = min(d,iabs(pt[n].x - pt[n_points-1].x));
276: pt[n].y += (int)(place*(((double)d)/mx));
277: }
278: }
279: else
280: {
281: place -= width/2;
282: for(int n = 1; n < n_points-1; ++n)
283: pt[n].x += place;
284: }
285: }
286:
287: e->splinept = pt;
288: }
289:
290: // so we'll remember to clean up next time around
291: Clean_up = 1;
292: }
293:
294:
295: // search for the root of the union tree containing this vertex
296: static int findroot(int v)
297: {
298: // if this is root, return it
299: if(v == Root[v])
300: return v;
301: // search for root and compress the path
302: return (Root[v] = findroot(Root[v]));
303: }
304:
305: // union a set of nodes
306: static void setunion(int *set)
307: {
308: int root = findroot(set[0]);
309: for(int i = 0; set[i] != -1; ++i)
310: {
311: int r = findroot(set[i]);
312: if(r == set[i])
313: Root[set[i]] = root;
314: else
315: {
316: Root[root] = r;
317: root = r;
318: }
319: }
320: }
321:
322:
323:
324: // check for multiple edges
325: static int multiple(int node, edge_t *edge, int isaux)
326: {
327: for(int dohead = 0; dohead < 2; ++dohead)
328: {
329: /* check for forward multiple edges */
330: edge_t *e = dohead ? Outedges[edge->node] : Outedges[node];
331: int match = dohead ? node : edge->node;
332:
333: for(; e; e = e->next)
334: if(e->node == match)
335: {
336: e->count += 1;
337: e->weight += edge->weight;
338: e->width += 3*Nodesep/4 + edge->width;
339:
340: // identify user's edge with our edge and set its order
341: if(isaux)
342: {
343: edge->chain->chain = e;
344: edge->chain->place = e->width - edge->width;
345: }
346: else
347: {
348: edge->chain = e;
349: edge->place = e->width - edge->width;
350: }
351:
352: // update the corresponding version in Inedges
353: e = e->link;
354: e->count += 1;
355: e->weight += edge->weight;
356: e->width += Nodesep + edge->width;
357:
358: return 1;
359: }
360: }
361:
362: return 0;
363: }
364:
365:
366: // keep track of self and flat edges for position assignment
367: static void noedge(int tail, edge_t *edge)
368: {
369: if(!Noedges)
370: Noedges = new edge_t*[N_real_nodes];
371:
372: // check for multiple edge
373: for(edge_t *e = Noedges[tail]; e; e = e->next)
374: if(e->node == edge->node)
375: {
376: e->count += 1;
377: e->weight += edge->weight;
378: e->width += Nodesep/2 + edge->width;
379: edge->chain = e;
380: edge->place = e->width - edge->width;
381: return;
382: }
383:
384: // making a new edge
385: Noedges[tail] = new edge_t(edge->node,edge->weight,edge->width,0,Noedges[tail]);
386: edge->chain = Noedges[tail];
387: }
388:
389:
390:
391: // construct new edge lists ensuring no cycles, multiple edges and self edges.
392: static void dfs(int node, edge_t **outedges, edge_t **auxedges,
393: int *active, int *marked, int **sets)
394: {
395: if(marked[node])
396: return;
397: marked[node] = 1;
398:
399: // mark this node as being on the search stack
400: active[node] = 1;
401:
402: for(int *set = sets[node]; *set != -1; ++set)
403: {
404: int tail = *set;
405:
406: for(int isaux = 0; isaux < 2; ++isaux)
407: {
408: if(isaux && !auxedges)
409: continue;
410:
411: edge_t *e = isaux ? auxedges[tail] : outedges[tail];
412: for(; e; e = e->next)
413: {
414: // there is a corresponding aux edge
415: if(!isaux && e->chain)
416: continue;
417:
418: // ignore self-edges or squashed edges
419: if(e->node == tail || Root[e->node] == node)
420: {
421: if(e->node == tail)
422: N_self_edges++;
423: else N_flat_edges++;
424: noedge(tail,e);
425: continue;
426: }
427:
428: // check for multiple edges
429: if(multiple(tail,e,isaux))
430: {
431: N_repeat_edges++;
432: continue;
433: }
434:
435: // a new edge is to be constructed
436: N_edges++;
437:
438: // a cycle is detected, reverse the edge
439: if(active[Root[e->node]])
440: {
441: N_revert_edges++;
442:
443: Outedges[e->node] =
444: new edge_t(tail,e->weight,e->width,e->minlen,
445: Outedges[e->node]);
446: Inedges[tail] =
447: new edge_t(e->node,e->weight,e->width,e->minlen,
448: Inedges[tail]);
449: Outedges[e->node]->link = Inedges[tail];
450: Inedges[tail]->link = Outedges[e->node];
451:
452: // identify user's edge with our edge
453: if(isaux)
454: {
455: e->chain->chain = Outedges[e->node];
456: e->chain->place = 0;
457: }
458: else
459: {
460: e->chain = Outedges[e->node];
461: e->place = 0;
462: }
463:
464: continue;
465: }
466:
467: // forward or cross-edges
468: Outedges[tail] = new edge_t(e->node,e->weight,e->width,e->minlen,
469: Outedges[tail]);
470: Inedges[e->node] = new edge_t(tail,e->weight,e->width,e->minlen,
471: Inedges[e->node]);
472: Outedges[tail]->link = Inedges[e->node];
473: Inedges[e->node]->link = Outedges[tail];
474:
475: // identify user's edge with our edge
476: if(isaux)
477: {
478: N_revert_edges++;
479: e->chain->chain = Outedges[tail];
480: e->chain->place = 0;
481: }
482: else
483: {
484: e->chain = Outedges[tail];
485: e->place = 0;
486: }
487:
488: // recursion
489: if(!marked[Root[e->node]])
490: dfs(Root[e->node],outedges,auxedges,
491: active,marked,sets);
492: }
493: }
494: }
495:
496: // this node is now off the search stack
497: active[node] = 0;
498: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.