1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpapi16.c	Sun Nov 06 20:59:10 2011 +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, 2011 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 */