| 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 |
|