1 /* set up data structures for weighted match */
2
3 void
4 SetUp(Graph gptr, int type);
5
6 void
7 SetStandard(Graph graph);
8
9 void
10 SetEuclid(EuclidGraph graph);
11
12 void
13 SetMatrix(MatrixGraph graph);
14
15 /* to add a new type, add new case in SetUp() and a Set_X() routine */
16
17 void
SetUp(Graph gptr,int type)18 SetUp(Graph gptr, int type)
19 { int i,allocsize;
20 Graph g;
21 EuclidGraph xy;
22 MatrixGraph matg;
23
24 if (type==1) {
25 g = (Graph) gptr;
26 U = Degree(g,0);
27 V = NumEdges(g);
28 }
29 else if (type==2) {
30 xy = (EuclidGraph) gptr;
31 U = xy[0][0];
32 V = U*(U-1)/2;
33 }
34 else if (type==3) {
35 matg = (MatrixGraph) gptr;
36 U = matg[0];
37 V = U*(U-1)/2;
38 }
39
40 allocsize = (U+2*V+2)*sizeof(int);
41 A = (int *) malloc(allocsize);
42 END = (int *) malloc(allocsize);
43 WEIGHT = (int *) malloc(allocsize);
44 for (i=0; i<U+2*V+2; i++)
45 A[i]=END[i]=WEIGHT[i]=0;
46
47 if (type == 1) SetStandard(g);
48 else if (type == 2) SetEuclid(xy);
49 else if (type == 3) SetMatrix(matg);
50 }
51
52
53 /* set up from Type 1 graph. */
54
55 void
SetStandard(Graph graph)56 SetStandard(Graph graph)
57 { int elabel, adj_node, i, j;
58 int u, v, currentedge;
59 Edge edge;
60
61 currentedge = U+2;
62 for (i=1; i<=U; ++i) {
63 edge = FirstEdge(graph,i);
64 for (j = 1; j <= Degree(graph,i); ++j) {
65 adj_node = EndPoint(edge);
66 if (i < adj_node) {
67 elabel = ELabel(edge)*2;
68 WEIGHT[currentedge-1] = WEIGHT[currentedge] = 2*elabel;
69 END[currentedge-1] = i;
70 END[currentedge] = adj_node;
71 if (A[i] == 0)
72 A[i] = currentedge;
73 else {
74 u = i;
75 v = A[i];
76 while (v != 0) {
77 if (END[v] > adj_node)
78 break;
79 u = v;
80 v = A[v];
81 }
82 A[u] = currentedge;
83 A[currentedge] = v;
84 }
85 u = adj_node;
86 v = A[u];
87 while (v != 0) {
88 u = v;
89 v = A[v];
90 }
91 A[u] = currentedge - 1;
92 currentedge += 2;
93 }
94 edge = NextEdge(edge);
95 }
96 }
97 }
98
99 /* set up from Euclidean graph */
100
101 void
SetEuclid(EuclidGraph graph)102 SetEuclid(EuclidGraph graph)
103 { int i,j,currentedge;
104
105 currentedge = U+2;
106
107 for (i=U; i>=1; --i)
108 for (j = i-1; j >= 1; --j) {
109 WEIGHT[currentedge-1] = WEIGHT[currentedge]
110 = 2*eucdist2(graph,i,j);
111 END[currentedge-1] = i;
112 END[currentedge] = j;
113 A[currentedge] = A[i];
114 A[i] = currentedge;
115 A[currentedge-1] = A[j];
116 A[j] = currentedge-1;
117 currentedge += 2;
118 }
119 }
120
121 void
SetMatrix(MatrixGraph graph)122 SetMatrix(MatrixGraph graph)
123 { int i,j,currentedge;
124
125 currentedge = U+2;
126
127 for (i=U; i>=1; --i)
128 for (j = i-1; j >= 1; --j) {
129 WEIGHT[currentedge-1] = WEIGHT[currentedge]
130 = 2*graph[j*U+i];
131 END[currentedge-1] = i;
132 END[currentedge] = j;
133 A[currentedge] = A[i];
134 A[i] = currentedge;
135 A[currentedge-1] = A[j];
136 A[j] = currentedge-1;
137 currentedge += 2;
138 }
139 }
140
141