lemon-project-template-glpk

annotate deps/glpk/src/glpapi16.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpapi16.c (graph and network analysis routines) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #include "glpapi.h"
alpar@9 26 #include "glpnet.h"
alpar@9 27
alpar@9 28 /***********************************************************************
alpar@9 29 * NAME
alpar@9 30 *
alpar@9 31 * glp_weak_comp - find all weakly connected components of graph
alpar@9 32 *
alpar@9 33 * SYNOPSIS
alpar@9 34 *
alpar@9 35 * int glp_weak_comp(glp_graph *G, int v_num);
alpar@9 36 *
alpar@9 37 * DESCRIPTION
alpar@9 38 *
alpar@9 39 * The routine glp_weak_comp finds all weakly connected components of
alpar@9 40 * the specified graph.
alpar@9 41 *
alpar@9 42 * The parameter v_num specifies an offset of the field of type int
alpar@9 43 * in the vertex data block, to which the routine stores the number of
alpar@9 44 * a (weakly) connected component containing that vertex. If v_num < 0,
alpar@9 45 * no component numbers are stored.
alpar@9 46 *
alpar@9 47 * The components are numbered in arbitrary order from 1 to nc, where
alpar@9 48 * nc is the total number of components found, 0 <= nc <= |V|.
alpar@9 49 *
alpar@9 50 * RETURNS
alpar@9 51 *
alpar@9 52 * The routine returns nc, the total number of components found. */
alpar@9 53
alpar@9 54 int glp_weak_comp(glp_graph *G, int v_num)
alpar@9 55 { glp_vertex *v;
alpar@9 56 glp_arc *a;
alpar@9 57 int f, i, j, nc, nv, pos1, pos2, *prev, *next, *list;
alpar@9 58 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
alpar@9 59 xerror("glp_weak_comp: v_num = %d; invalid offset\n", v_num);
alpar@9 60 nv = G->nv;
alpar@9 61 if (nv == 0)
alpar@9 62 { nc = 0;
alpar@9 63 goto done;
alpar@9 64 }
alpar@9 65 /* allocate working arrays */
alpar@9 66 prev = xcalloc(1+nv, sizeof(int));
alpar@9 67 next = xcalloc(1+nv, sizeof(int));
alpar@9 68 list = xcalloc(1+nv, sizeof(int));
alpar@9 69 /* if vertex i is unlabelled, prev[i] is the index of previous
alpar@9 70 unlabelled vertex, and next[i] is the index of next unlabelled
alpar@9 71 vertex; if vertex i is labelled, then prev[i] < 0, and next[i]
alpar@9 72 is the connected component number */
alpar@9 73 /* initially all vertices are unlabelled */
alpar@9 74 f = 1;
alpar@9 75 for (i = 1; i <= nv; i++)
alpar@9 76 prev[i] = i - 1, next[i] = i + 1;
alpar@9 77 next[nv] = 0;
alpar@9 78 /* main loop (until all vertices have been labelled) */
alpar@9 79 nc = 0;
alpar@9 80 while (f != 0)
alpar@9 81 { /* take an unlabelled vertex */
alpar@9 82 i = f;
alpar@9 83 /* and remove it from the list of unlabelled vertices */
alpar@9 84 f = next[i];
alpar@9 85 if (f != 0) prev[f] = 0;
alpar@9 86 /* label the vertex; it begins a new component */
alpar@9 87 prev[i] = -1, next[i] = ++nc;
alpar@9 88 /* breadth first search */
alpar@9 89 list[1] = i, pos1 = pos2 = 1;
alpar@9 90 while (pos1 <= pos2)
alpar@9 91 { /* dequeue vertex i */
alpar@9 92 i = list[pos1++];
alpar@9 93 /* consider all arcs incoming to vertex i */
alpar@9 94 for (a = G->v[i]->in; a != NULL; a = a->h_next)
alpar@9 95 { /* vertex j is adjacent to vertex i */
alpar@9 96 j = a->tail->i;
alpar@9 97 if (prev[j] >= 0)
alpar@9 98 { /* vertex j is unlabelled */
alpar@9 99 /* remove it from the list of unlabelled vertices */
alpar@9 100 if (prev[j] == 0)
alpar@9 101 f = next[j];
alpar@9 102 else
alpar@9 103 next[prev[j]] = next[j];
alpar@9 104 if (next[j] == 0)
alpar@9 105 ;
alpar@9 106 else
alpar@9 107 prev[next[j]] = prev[j];
alpar@9 108 /* label the vertex */
alpar@9 109 prev[j] = -1, next[j] = nc;
alpar@9 110 /* and enqueue it for further consideration */
alpar@9 111 list[++pos2] = j;
alpar@9 112 }
alpar@9 113 }
alpar@9 114 /* consider all arcs outgoing from vertex i */
alpar@9 115 for (a = G->v[i]->out; a != NULL; a = a->t_next)
alpar@9 116 { /* vertex j is adjacent to vertex i */
alpar@9 117 j = a->head->i;
alpar@9 118 if (prev[j] >= 0)
alpar@9 119 { /* vertex j is unlabelled */
alpar@9 120 /* remove it from the list of unlabelled vertices */
alpar@9 121 if (prev[j] == 0)
alpar@9 122 f = next[j];
alpar@9 123 else
alpar@9 124 next[prev[j]] = next[j];
alpar@9 125 if (next[j] == 0)
alpar@9 126 ;
alpar@9 127 else
alpar@9 128 prev[next[j]] = prev[j];
alpar@9 129 /* label the vertex */
alpar@9 130 prev[j] = -1, next[j] = nc;
alpar@9 131 /* and enqueue it for further consideration */
alpar@9 132 list[++pos2] = j;
alpar@9 133 }
alpar@9 134 }
alpar@9 135 }
alpar@9 136 }
alpar@9 137 /* store component numbers */
alpar@9 138 if (v_num >= 0)
alpar@9 139 { for (i = 1; i <= nv; i++)
alpar@9 140 { v = G->v[i];
alpar@9 141 memcpy((char *)v->data + v_num, &next[i], sizeof(int));
alpar@9 142 }
alpar@9 143 }
alpar@9 144 /* free working arrays */
alpar@9 145 xfree(prev);
alpar@9 146 xfree(next);
alpar@9 147 xfree(list);
alpar@9 148 done: return nc;
alpar@9 149 }
alpar@9 150
alpar@9 151 /***********************************************************************
alpar@9 152 * NAME
alpar@9 153 *
alpar@9 154 * glp_strong_comp - find all strongly connected components of graph
alpar@9 155 *
alpar@9 156 * SYNOPSIS
alpar@9 157 *
alpar@9 158 * int glp_strong_comp(glp_graph *G, int v_num);
alpar@9 159 *
alpar@9 160 * DESCRIPTION
alpar@9 161 *
alpar@9 162 * The routine glp_strong_comp finds all strongly connected components
alpar@9 163 * of the specified graph.
alpar@9 164 *
alpar@9 165 * The parameter v_num specifies an offset of the field of type int
alpar@9 166 * in the vertex data block, to which the routine stores the number of
alpar@9 167 * a strongly connected component containing that vertex. If v_num < 0,
alpar@9 168 * no component numbers are stored.
alpar@9 169 *
alpar@9 170 * The components are numbered in arbitrary order from 1 to nc, where
alpar@9 171 * nc is the total number of components found, 0 <= nc <= |V|. However,
alpar@9 172 * the component numbering has the property that for every arc (i->j)
alpar@9 173 * in the graph the condition num(i) >= num(j) holds.
alpar@9 174 *
alpar@9 175 * RETURNS
alpar@9 176 *
alpar@9 177 * The routine returns nc, the total number of components found. */
alpar@9 178
alpar@9 179 int glp_strong_comp(glp_graph *G, int v_num)
alpar@9 180 { glp_vertex *v;
alpar@9 181 glp_arc *a;
alpar@9 182 int i, k, last, n, na, nc, *icn, *ip, *lenr, *ior, *ib, *lowl,
alpar@9 183 *numb, *prev;
alpar@9 184 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
alpar@9 185 xerror("glp_strong_comp: v_num = %d; invalid offset\n",
alpar@9 186 v_num);
alpar@9 187 n = G->nv;
alpar@9 188 if (n == 0)
alpar@9 189 { nc = 0;
alpar@9 190 goto done;
alpar@9 191 }
alpar@9 192 na = G->na;
alpar@9 193 icn = xcalloc(1+na, sizeof(int));
alpar@9 194 ip = xcalloc(1+n, sizeof(int));
alpar@9 195 lenr = xcalloc(1+n, sizeof(int));
alpar@9 196 ior = xcalloc(1+n, sizeof(int));
alpar@9 197 ib = xcalloc(1+n, sizeof(int));
alpar@9 198 lowl = xcalloc(1+n, sizeof(int));
alpar@9 199 numb = xcalloc(1+n, sizeof(int));
alpar@9 200 prev = xcalloc(1+n, sizeof(int));
alpar@9 201 k = 1;
alpar@9 202 for (i = 1; i <= n; i++)
alpar@9 203 { v = G->v[i];
alpar@9 204 ip[i] = k;
alpar@9 205 for (a = v->out; a != NULL; a = a->t_next)
alpar@9 206 icn[k++] = a->head->i;
alpar@9 207 lenr[i] = k - ip[i];
alpar@9 208 }
alpar@9 209 xassert(na == k-1);
alpar@9 210 nc = mc13d(n, icn, ip, lenr, ior, ib, lowl, numb, prev);
alpar@9 211 if (v_num >= 0)
alpar@9 212 { xassert(ib[1] == 1);
alpar@9 213 for (k = 1; k <= nc; k++)
alpar@9 214 { last = (k < nc ? ib[k+1] : n+1);
alpar@9 215 xassert(ib[k] < last);
alpar@9 216 for (i = ib[k]; i < last; i++)
alpar@9 217 { v = G->v[ior[i]];
alpar@9 218 memcpy((char *)v->data + v_num, &k, sizeof(int));
alpar@9 219 }
alpar@9 220 }
alpar@9 221 }
alpar@9 222 xfree(icn);
alpar@9 223 xfree(ip);
alpar@9 224 xfree(lenr);
alpar@9 225 xfree(ior);
alpar@9 226 xfree(ib);
alpar@9 227 xfree(lowl);
alpar@9 228 xfree(numb);
alpar@9 229 xfree(prev);
alpar@9 230 done: return nc;
alpar@9 231 }
alpar@9 232
alpar@9 233 /***********************************************************************
alpar@9 234 * NAME
alpar@9 235 *
alpar@9 236 * glp_top_sort - topological sorting of acyclic digraph
alpar@9 237 *
alpar@9 238 * SYNOPSIS
alpar@9 239 *
alpar@9 240 * int glp_top_sort(glp_graph *G, int v_num);
alpar@9 241 *
alpar@9 242 * DESCRIPTION
alpar@9 243 *
alpar@9 244 * The routine glp_top_sort performs topological sorting of vertices of
alpar@9 245 * the specified acyclic digraph.
alpar@9 246 *
alpar@9 247 * The parameter v_num specifies an offset of the field of type int in
alpar@9 248 * the vertex data block, to which the routine stores the vertex number
alpar@9 249 * assigned. If v_num < 0, vertex numbers are not stored.
alpar@9 250 *
alpar@9 251 * The vertices are numbered from 1 to n, where n is the total number
alpar@9 252 * of vertices in the graph. The vertex numbering has the property that
alpar@9 253 * for every arc (i->j) in the graph the condition num(i) < num(j)
alpar@9 254 * holds. Special case num(i) = 0 means that vertex i is not assigned a
alpar@9 255 * number, because the graph is *not* acyclic.
alpar@9 256 *
alpar@9 257 * RETURNS
alpar@9 258 *
alpar@9 259 * If the graph is acyclic and therefore all the vertices have been
alpar@9 260 * assigned numbers, the routine glp_top_sort returns zero. Otherwise,
alpar@9 261 * if the graph is not acyclic, the routine returns the number of
alpar@9 262 * vertices which have not been numbered, i.e. for which num(i) = 0. */
alpar@9 263
alpar@9 264 static int top_sort(glp_graph *G, int num[])
alpar@9 265 { glp_arc *a;
alpar@9 266 int i, j, cnt, top, *stack, *indeg;
alpar@9 267 /* allocate working arrays */
alpar@9 268 indeg = xcalloc(1+G->nv, sizeof(int));
alpar@9 269 stack = xcalloc(1+G->nv, sizeof(int));
alpar@9 270 /* determine initial indegree of each vertex; push into the stack
alpar@9 271 the vertices having zero indegree */
alpar@9 272 top = 0;
alpar@9 273 for (i = 1; i <= G->nv; i++)
alpar@9 274 { num[i] = indeg[i] = 0;
alpar@9 275 for (a = G->v[i]->in; a != NULL; a = a->h_next)
alpar@9 276 indeg[i]++;
alpar@9 277 if (indeg[i] == 0)
alpar@9 278 stack[++top] = i;
alpar@9 279 }
alpar@9 280 /* assign numbers to vertices in the sorted order */
alpar@9 281 cnt = 0;
alpar@9 282 while (top > 0)
alpar@9 283 { /* pull vertex i from the stack */
alpar@9 284 i = stack[top--];
alpar@9 285 /* it has zero indegree in the current graph */
alpar@9 286 xassert(indeg[i] == 0);
alpar@9 287 /* so assign it a next number */
alpar@9 288 xassert(num[i] == 0);
alpar@9 289 num[i] = ++cnt;
alpar@9 290 /* remove vertex i from the current graph, update indegree of
alpar@9 291 its adjacent vertices, and push into the stack new vertices
alpar@9 292 whose indegree becomes zero */
alpar@9 293 for (a = G->v[i]->out; a != NULL; a = a->t_next)
alpar@9 294 { j = a->head->i;
alpar@9 295 /* there exists arc (i->j) in the graph */
alpar@9 296 xassert(indeg[j] > 0);
alpar@9 297 indeg[j]--;
alpar@9 298 if (indeg[j] == 0)
alpar@9 299 stack[++top] = j;
alpar@9 300 }
alpar@9 301 }
alpar@9 302 /* free working arrays */
alpar@9 303 xfree(indeg);
alpar@9 304 xfree(stack);
alpar@9 305 return G->nv - cnt;
alpar@9 306 }
alpar@9 307
alpar@9 308 int glp_top_sort(glp_graph *G, int v_num)
alpar@9 309 { glp_vertex *v;
alpar@9 310 int i, cnt, *num;
alpar@9 311 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
alpar@9 312 xerror("glp_top_sort: v_num = %d; invalid offset\n", v_num);
alpar@9 313 if (G->nv == 0)
alpar@9 314 { cnt = 0;
alpar@9 315 goto done;
alpar@9 316 }
alpar@9 317 num = xcalloc(1+G->nv, sizeof(int));
alpar@9 318 cnt = top_sort(G, num);
alpar@9 319 if (v_num >= 0)
alpar@9 320 { for (i = 1; i <= G->nv; i++)
alpar@9 321 { v = G->v[i];
alpar@9 322 memcpy((char *)v->data + v_num, &num[i], sizeof(int));
alpar@9 323 }
alpar@9 324 }
alpar@9 325 xfree(num);
alpar@9 326 done: return cnt;
alpar@9 327 }
alpar@9 328
alpar@9 329 /* eof */