Debian Codegraph @

SYMPHONY/Applications/VRP/src/CutGen/biconnected.c

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
6 /* */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs ([email protected]) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 /* system include files */
17
18 /* SYMPHONY include files */
19 #include "sym_constants.h"
20
21 /* VRP include files */
22 #include "vrp_cg.h"
23
24 /*===========================================================================*\
25 * This file contains functions for finding biconnected components.
26 \*===========================================================================*/
27
28 /*===========================================================================*/
29
30 void depth_first_search(vertex *v, int *count1, int *count2)
31 {
32 register elist *e;
33 char has_child = FALSE, has_non_tree_edge = FALSE;
34 char is_art_point = TRUE;
35 int c, min;
36
37 v->scanned = TRUE;
38 min = v->dfnumber = ++(*count1);
39 for (e = v->first; e; e = e->next_edge){
40 if (!e->other_end) continue;
41 if (!e->other->scanned){
42 e->data->tree_edge = TRUE;
43 depth_first_search(e->other, count1, count2);
44 has_child = TRUE;
45 }
46 c = e->other->dfnumber;
47 if (e->data->tree_edge && (c > v->dfnumber)){
48 if (min > e->other->low)
49 min = e->other->low;
50 if (e->other->low < v->dfnumber)
51 is_art_point = FALSE;
52 }else if (!e->data->tree_edge){
53 has_non_tree_edge = TRUE;
54 if (c < v->dfnumber){
55 if (min > c){
56 min = c;
57 }
58 }
59 }
60 }
61 v->low = min;
62 if (!has_child && has_non_tree_edge) is_art_point = FALSE;
63 v->is_art_point = is_art_point;
64
65 return;
66 }
67
68 /*===========================================================================*/
69
70 int biconnected(network *n, int *compnodes, int *compdemands,
71 double *compcuts)
72 {
73 int i, vertnum = n->vertnum;
74 vertex *verts = n->verts;
75 elist *e;
76 int count1 = 0, count2 = 0;
77 int num_comps = 0;
78 char is_art_point;
79
80 verts[0].scanned = TRUE;
81 verts[0].comp = 0;
82 for (i=1; i<vertnum; i++)
83 verts[i].scanned = FALSE;
84
85 for(i = 1; i < vertnum; i++){
86 if (!verts[i].scanned){
87 is_art_point = FALSE;
88 verts[i].low = verts[i].dfnumber = ++count1;
89 verts[i].scanned = TRUE;
90 e = verts[i].first;
91 if (!e->other_end){
92 if (e->next_edge)
93 e = e->next_edge;
94 else
95 continue;
96 }
97 e->data->tree_edge = TRUE;
98 depth_first_search(e->other, &count1, &count2);
99 is_art_point = e->other->is_art_point;
100 for(e = e->next_edge; e; e = e->next_edge){
101 if (!e->other_end) continue;
102 if (!e->other->scanned){
103 is_art_point = TRUE;
104 e->data->tree_edge = TRUE;
105 depth_first_search(e->other, &count1, &count2);
106 }
107 }
108 verts[i].is_art_point = is_art_point;
109 }
110 }
111
112 for (i=1; i<vertnum; i++)
113 verts[i].scanned = FALSE;
114
115 for (i = 1; i < vertnum; i++){
116 if (!verts[i].scanned){
117 verts[i].scanned = TRUE;
118 verts[i].comp = ++num_comps;
119 for (e = verts[i].first;e; e = e->next_edge){
120 if (!e->other_end) continue;
121 if (!e->other->scanned)
122 compute_comp_nums(e->other, verts[i].comp, &num_comps,
123 verts[i].is_art_point);
124 }
125 }
126 }
127
128
129 for (i = 1; i < vertnum; i++){
130 compnodes[verts[i].comp]++;
131 compdemands[verts[i].comp] += verts[i].demand;
132 for (e = verts[i].first; e; e = e->next_edge){
133 if (e->other->comp != verts[i].comp)
134 compcuts[verts[i].comp] += e->data->weight;
135 }
136 }
137
138 return (num_comps);
139 }
140
141 /*===================================================================*/
142
143 void compute_comp_nums(vertex *v, int parent_comp, int *num_comps,
144 char parent_is_art_point)
145 {
146 elist *e;
147
148 v->scanned = TRUE;
149 if (parent_is_art_point && v->is_art_point)
150 v->comp = ++(*num_comps);
151 else
152 v->comp = parent_comp;
153 for (e = v->first;e ; e = e->next_edge){
154 if (!e->other_end) continue;
155 if (!e->other->scanned)
156 compute_comp_nums(e->other, v->comp, num_comps,
157 v->is_art_point);
158 }
159 }
160
161
162