![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to draw_dag.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / dag|
Return to draw_dag.c CVS log | Up to [Research Unix] / researchv10no / cmd / dag |
1.1 root 1: #include "draw_dag.h"
2:
3: #include <sys/types.h>
4: #include <sys/times.h>
5: #define TIC 60
6:
7: int N_real_nodes, // actual number of input nodes
8: N_nodes, // number of nodes at various phases
9: N_edges, // total number of edges
10: N_self_edges, // # of loops detected
11: N_flat_edges, // # of edges whose ends are at the same level
12: N_repeat_edges, // # of multi-edges deleted
13: N_revert_edges, // # of edges whose direction is reverted
14: N_component; // # of connected components
15: edge_t **Inedges, // in-edges for each node
16: **Outedges, // out-edges
17: **Noedges, // self-edges and flat edges
18: **Istems, // stem edges
19: **Ostems;
20: int *Stems;
21: int *Root, // space to store union trees of vertices at same ranks
22: *Component, // connected component numbers
23: *Invert, // inversion of nodes in their ranks
24: *Level, // level assignment of nodes
25: Maxlevel, // maximum level assigned to any node
26: *N_level, // number of nodes at each level
27: **Rank; // array of ordered lists of nodes
28: int *Nodepos, // node positions
29: *Deleted, // virtual nodes that were deleted
30: *Width, // widths of nodes
31: Nodesep, // minimum separation between nodes
32: *Height, // height of nodes
33: Levelsep, // separation between levels
34: *Levelheight, // height of layers
35: *Levelpos; // position of levels
36:
37: int Xbound,Ybound; // if "fill" then size of box to fill, else 0
38:
39: int Verbose; // say lots of things
40:
41: /*
42: Draw any directed graphs.
43: This function works best with directed acyclic graphs.
44: Cycles are broken using a depth-first search.
45: */
46:
47: void draw_dag(int n_nodes, node_t **nodes, edge_t **edges, options_t options)
48: {
49: struct tms begtm, endtm;
50: Verbose = options.verbose;
51:
52: if(options.verbose)
53: {
54: #ifndef TIMING
55: fprintf(stderr,"Start graph drawing\n");
56: #endif
57: times(&begtm);
58: }
59:
60: // Create Inedges[], Outedges[], Width[], N_nodes, and N_edges
61: dag_start(n_nodes,nodes,edges,options);
62:
63: // remove stem edges
64: if(N_flat_edges <= 0)
65: dag_delstem();
66:
67: // Create Level[], Maxlevel
68: int *srcs = options.source_nodes;
69: int source = (srcs && srcs[0] != -1) ? Root[srcs[0]] : -1;
70: int *sinks = options.sink_nodes;
71: int sink = (sinks && sinks[0] != -1) ? Root[sinks[0]] : -1;
72: if(sink == source)
73: sink = -1;
74: int **same = options.same_nodes;
75: dag_levels(source,sink,same ? 1 : 0);
76:
77: // Make long edges into short edges by inserting dummy nodes
78: dag_unitedges();
79:
80: // Create N_level[], Rank[][]
81: dag_ranks();
82:
83: // reinsert stems
84: if(N_flat_edges <= 0)
85: dag_insstem();
86:
87: // Create Positions[], Maxpos
88: dag_positions(options.ranksep,!options.quick);
89:
90: // Create splines
91: dag_spline();
92:
93: // Return values to user
94: dag_end(nodes,edges);
95:
96: if(Verbose)
97: {
98: times(&endtm);
99: int total = (endtm.tms_utime-begtm.tms_utime) +
100: (endtm.tms_stime-begtm.tms_stime);
101: int percent = (total - (total/TIC)*TIC)*100/TIC;
102: #ifdef TIMING
103: fprintf(stderr,"%d.%02d\n",total/TIC, percent);
104: #else
105: fprintf(stderr,"Total time in graph drawing: %d.%02ds\n",
106: total/TIC, percent);
107: #endif
108: }
109: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.