1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi16.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,329 @@
1.4 +/* glpapi16.c (graph and network analysis routines) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#include "glpapi.h"
1.29 +#include "glpnet.h"
1.30 +
1.31 +/***********************************************************************
1.32 +* NAME
1.33 +*
1.34 +* glp_weak_comp - find all weakly connected components of graph
1.35 +*
1.36 +* SYNOPSIS
1.37 +*
1.38 +* int glp_weak_comp(glp_graph *G, int v_num);
1.39 +*
1.40 +* DESCRIPTION
1.41 +*
1.42 +* The routine glp_weak_comp finds all weakly connected components of
1.43 +* the specified graph.
1.44 +*
1.45 +* The parameter v_num specifies an offset of the field of type int
1.46 +* in the vertex data block, to which the routine stores the number of
1.47 +* a (weakly) connected component containing that vertex. If v_num < 0,
1.48 +* no component numbers are stored.
1.49 +*
1.50 +* The components are numbered in arbitrary order from 1 to nc, where
1.51 +* nc is the total number of components found, 0 <= nc <= |V|.
1.52 +*
1.53 +* RETURNS
1.54 +*
1.55 +* The routine returns nc, the total number of components found. */
1.56 +
1.57 +int glp_weak_comp(glp_graph *G, int v_num)
1.58 +{ glp_vertex *v;
1.59 + glp_arc *a;
1.60 + int f, i, j, nc, nv, pos1, pos2, *prev, *next, *list;
1.61 + if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
1.62 + xerror("glp_weak_comp: v_num = %d; invalid offset\n", v_num);
1.63 + nv = G->nv;
1.64 + if (nv == 0)
1.65 + { nc = 0;
1.66 + goto done;
1.67 + }
1.68 + /* allocate working arrays */
1.69 + prev = xcalloc(1+nv, sizeof(int));
1.70 + next = xcalloc(1+nv, sizeof(int));
1.71 + list = xcalloc(1+nv, sizeof(int));
1.72 + /* if vertex i is unlabelled, prev[i] is the index of previous
1.73 + unlabelled vertex, and next[i] is the index of next unlabelled
1.74 + vertex; if vertex i is labelled, then prev[i] < 0, and next[i]
1.75 + is the connected component number */
1.76 + /* initially all vertices are unlabelled */
1.77 + f = 1;
1.78 + for (i = 1; i <= nv; i++)
1.79 + prev[i] = i - 1, next[i] = i + 1;
1.80 + next[nv] = 0;
1.81 + /* main loop (until all vertices have been labelled) */
1.82 + nc = 0;
1.83 + while (f != 0)
1.84 + { /* take an unlabelled vertex */
1.85 + i = f;
1.86 + /* and remove it from the list of unlabelled vertices */
1.87 + f = next[i];
1.88 + if (f != 0) prev[f] = 0;
1.89 + /* label the vertex; it begins a new component */
1.90 + prev[i] = -1, next[i] = ++nc;
1.91 + /* breadth first search */
1.92 + list[1] = i, pos1 = pos2 = 1;
1.93 + while (pos1 <= pos2)
1.94 + { /* dequeue vertex i */
1.95 + i = list[pos1++];
1.96 + /* consider all arcs incoming to vertex i */
1.97 + for (a = G->v[i]->in; a != NULL; a = a->h_next)
1.98 + { /* vertex j is adjacent to vertex i */
1.99 + j = a->tail->i;
1.100 + if (prev[j] >= 0)
1.101 + { /* vertex j is unlabelled */
1.102 + /* remove it from the list of unlabelled vertices */
1.103 + if (prev[j] == 0)
1.104 + f = next[j];
1.105 + else
1.106 + next[prev[j]] = next[j];
1.107 + if (next[j] == 0)
1.108 + ;
1.109 + else
1.110 + prev[next[j]] = prev[j];
1.111 + /* label the vertex */
1.112 + prev[j] = -1, next[j] = nc;
1.113 + /* and enqueue it for further consideration */
1.114 + list[++pos2] = j;
1.115 + }
1.116 + }
1.117 + /* consider all arcs outgoing from vertex i */
1.118 + for (a = G->v[i]->out; a != NULL; a = a->t_next)
1.119 + { /* vertex j is adjacent to vertex i */
1.120 + j = a->head->i;
1.121 + if (prev[j] >= 0)
1.122 + { /* vertex j is unlabelled */
1.123 + /* remove it from the list of unlabelled vertices */
1.124 + if (prev[j] == 0)
1.125 + f = next[j];
1.126 + else
1.127 + next[prev[j]] = next[j];
1.128 + if (next[j] == 0)
1.129 + ;
1.130 + else
1.131 + prev[next[j]] = prev[j];
1.132 + /* label the vertex */
1.133 + prev[j] = -1, next[j] = nc;
1.134 + /* and enqueue it for further consideration */
1.135 + list[++pos2] = j;
1.136 + }
1.137 + }
1.138 + }
1.139 + }
1.140 + /* store component numbers */
1.141 + if (v_num >= 0)
1.142 + { for (i = 1; i <= nv; i++)
1.143 + { v = G->v[i];
1.144 + memcpy((char *)v->data + v_num, &next[i], sizeof(int));
1.145 + }
1.146 + }
1.147 + /* free working arrays */
1.148 + xfree(prev);
1.149 + xfree(next);
1.150 + xfree(list);
1.151 +done: return nc;
1.152 +}
1.153 +
1.154 +/***********************************************************************
1.155 +* NAME
1.156 +*
1.157 +* glp_strong_comp - find all strongly connected components of graph
1.158 +*
1.159 +* SYNOPSIS
1.160 +*
1.161 +* int glp_strong_comp(glp_graph *G, int v_num);
1.162 +*
1.163 +* DESCRIPTION
1.164 +*
1.165 +* The routine glp_strong_comp finds all strongly connected components
1.166 +* of the specified graph.
1.167 +*
1.168 +* The parameter v_num specifies an offset of the field of type int
1.169 +* in the vertex data block, to which the routine stores the number of
1.170 +* a strongly connected component containing that vertex. If v_num < 0,
1.171 +* no component numbers are stored.
1.172 +*
1.173 +* The components are numbered in arbitrary order from 1 to nc, where
1.174 +* nc is the total number of components found, 0 <= nc <= |V|. However,
1.175 +* the component numbering has the property that for every arc (i->j)
1.176 +* in the graph the condition num(i) >= num(j) holds.
1.177 +*
1.178 +* RETURNS
1.179 +*
1.180 +* The routine returns nc, the total number of components found. */
1.181 +
1.182 +int glp_strong_comp(glp_graph *G, int v_num)
1.183 +{ glp_vertex *v;
1.184 + glp_arc *a;
1.185 + int i, k, last, n, na, nc, *icn, *ip, *lenr, *ior, *ib, *lowl,
1.186 + *numb, *prev;
1.187 + if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
1.188 + xerror("glp_strong_comp: v_num = %d; invalid offset\n",
1.189 + v_num);
1.190 + n = G->nv;
1.191 + if (n == 0)
1.192 + { nc = 0;
1.193 + goto done;
1.194 + }
1.195 + na = G->na;
1.196 + icn = xcalloc(1+na, sizeof(int));
1.197 + ip = xcalloc(1+n, sizeof(int));
1.198 + lenr = xcalloc(1+n, sizeof(int));
1.199 + ior = xcalloc(1+n, sizeof(int));
1.200 + ib = xcalloc(1+n, sizeof(int));
1.201 + lowl = xcalloc(1+n, sizeof(int));
1.202 + numb = xcalloc(1+n, sizeof(int));
1.203 + prev = xcalloc(1+n, sizeof(int));
1.204 + k = 1;
1.205 + for (i = 1; i <= n; i++)
1.206 + { v = G->v[i];
1.207 + ip[i] = k;
1.208 + for (a = v->out; a != NULL; a = a->t_next)
1.209 + icn[k++] = a->head->i;
1.210 + lenr[i] = k - ip[i];
1.211 + }
1.212 + xassert(na == k-1);
1.213 + nc = mc13d(n, icn, ip, lenr, ior, ib, lowl, numb, prev);
1.214 + if (v_num >= 0)
1.215 + { xassert(ib[1] == 1);
1.216 + for (k = 1; k <= nc; k++)
1.217 + { last = (k < nc ? ib[k+1] : n+1);
1.218 + xassert(ib[k] < last);
1.219 + for (i = ib[k]; i < last; i++)
1.220 + { v = G->v[ior[i]];
1.221 + memcpy((char *)v->data + v_num, &k, sizeof(int));
1.222 + }
1.223 + }
1.224 + }
1.225 + xfree(icn);
1.226 + xfree(ip);
1.227 + xfree(lenr);
1.228 + xfree(ior);
1.229 + xfree(ib);
1.230 + xfree(lowl);
1.231 + xfree(numb);
1.232 + xfree(prev);
1.233 +done: return nc;
1.234 +}
1.235 +
1.236 +/***********************************************************************
1.237 +* NAME
1.238 +*
1.239 +* glp_top_sort - topological sorting of acyclic digraph
1.240 +*
1.241 +* SYNOPSIS
1.242 +*
1.243 +* int glp_top_sort(glp_graph *G, int v_num);
1.244 +*
1.245 +* DESCRIPTION
1.246 +*
1.247 +* The routine glp_top_sort performs topological sorting of vertices of
1.248 +* the specified acyclic digraph.
1.249 +*
1.250 +* The parameter v_num specifies an offset of the field of type int in
1.251 +* the vertex data block, to which the routine stores the vertex number
1.252 +* assigned. If v_num < 0, vertex numbers are not stored.
1.253 +*
1.254 +* The vertices are numbered from 1 to n, where n is the total number
1.255 +* of vertices in the graph. The vertex numbering has the property that
1.256 +* for every arc (i->j) in the graph the condition num(i) < num(j)
1.257 +* holds. Special case num(i) = 0 means that vertex i is not assigned a
1.258 +* number, because the graph is *not* acyclic.
1.259 +*
1.260 +* RETURNS
1.261 +*
1.262 +* If the graph is acyclic and therefore all the vertices have been
1.263 +* assigned numbers, the routine glp_top_sort returns zero. Otherwise,
1.264 +* if the graph is not acyclic, the routine returns the number of
1.265 +* vertices which have not been numbered, i.e. for which num(i) = 0. */
1.266 +
1.267 +static int top_sort(glp_graph *G, int num[])
1.268 +{ glp_arc *a;
1.269 + int i, j, cnt, top, *stack, *indeg;
1.270 + /* allocate working arrays */
1.271 + indeg = xcalloc(1+G->nv, sizeof(int));
1.272 + stack = xcalloc(1+G->nv, sizeof(int));
1.273 + /* determine initial indegree of each vertex; push into the stack
1.274 + the vertices having zero indegree */
1.275 + top = 0;
1.276 + for (i = 1; i <= G->nv; i++)
1.277 + { num[i] = indeg[i] = 0;
1.278 + for (a = G->v[i]->in; a != NULL; a = a->h_next)
1.279 + indeg[i]++;
1.280 + if (indeg[i] == 0)
1.281 + stack[++top] = i;
1.282 + }
1.283 + /* assign numbers to vertices in the sorted order */
1.284 + cnt = 0;
1.285 + while (top > 0)
1.286 + { /* pull vertex i from the stack */
1.287 + i = stack[top--];
1.288 + /* it has zero indegree in the current graph */
1.289 + xassert(indeg[i] == 0);
1.290 + /* so assign it a next number */
1.291 + xassert(num[i] == 0);
1.292 + num[i] = ++cnt;
1.293 + /* remove vertex i from the current graph, update indegree of
1.294 + its adjacent vertices, and push into the stack new vertices
1.295 + whose indegree becomes zero */
1.296 + for (a = G->v[i]->out; a != NULL; a = a->t_next)
1.297 + { j = a->head->i;
1.298 + /* there exists arc (i->j) in the graph */
1.299 + xassert(indeg[j] > 0);
1.300 + indeg[j]--;
1.301 + if (indeg[j] == 0)
1.302 + stack[++top] = j;
1.303 + }
1.304 + }
1.305 + /* free working arrays */
1.306 + xfree(indeg);
1.307 + xfree(stack);
1.308 + return G->nv - cnt;
1.309 +}
1.310 +
1.311 +int glp_top_sort(glp_graph *G, int v_num)
1.312 +{ glp_vertex *v;
1.313 + int i, cnt, *num;
1.314 + if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
1.315 + xerror("glp_top_sort: v_num = %d; invalid offset\n", v_num);
1.316 + if (G->nv == 0)
1.317 + { cnt = 0;
1.318 + goto done;
1.319 + }
1.320 + num = xcalloc(1+G->nv, sizeof(int));
1.321 + cnt = top_sort(G, num);
1.322 + if (v_num >= 0)
1.323 + { for (i = 1; i <= G->nv; i++)
1.324 + { v = G->v[i];
1.325 + memcpy((char *)v->data + v_num, &num[i], sizeof(int));
1.326 + }
1.327 + }
1.328 + xfree(num);
1.329 +done: return cnt;
1.330 +}
1.331 +
1.332 +/* eof */