lemon-project-template-glpk

annotate deps/glpk/src/glpnet07.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 /* glpnet07.c (Ford-Fulkerson algorithm) */
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 "glpenv.h"
alpar@9 26 #include "glpnet.h"
alpar@9 27
alpar@9 28 /***********************************************************************
alpar@9 29 * NAME
alpar@9 30 *
alpar@9 31 * ffalg - Ford-Fulkerson algorithm
alpar@9 32 *
alpar@9 33 * SYNOPSIS
alpar@9 34 *
alpar@9 35 * #include "glpnet.h"
alpar@9 36 * void ffalg(int nv, int na, const int tail[], const int head[],
alpar@9 37 * int s, int t, const int cap[], int x[], char cut[]);
alpar@9 38 *
alpar@9 39 * DESCRIPTION
alpar@9 40 *
alpar@9 41 * The routine ffalg implements the Ford-Fulkerson algorithm to find a
alpar@9 42 * maximal flow in the specified flow network.
alpar@9 43 *
alpar@9 44 * INPUT PARAMETERS
alpar@9 45 *
alpar@9 46 * nv is the number of nodes, nv >= 2.
alpar@9 47 *
alpar@9 48 * na is the number of arcs, na >= 0.
alpar@9 49 *
alpar@9 50 * tail[a], a = 1,...,na, is the index of tail node of arc a.
alpar@9 51 *
alpar@9 52 * head[a], a = 1,...,na, is the index of head node of arc a.
alpar@9 53 *
alpar@9 54 * s is the source node index, 1 <= s <= nv.
alpar@9 55 *
alpar@9 56 * t is the sink node index, 1 <= t <= nv, t != s.
alpar@9 57 *
alpar@9 58 * cap[a], a = 1,...,na, is the capacity of arc a, cap[a] >= 0.
alpar@9 59 *
alpar@9 60 * NOTE: Multiple arcs are allowed, but self-loops are not allowed.
alpar@9 61 *
alpar@9 62 * OUTPUT PARAMETERS
alpar@9 63 *
alpar@9 64 * x[a], a = 1,...,na, is optimal value of the flow through arc a.
alpar@9 65 *
alpar@9 66 * cut[i], i = 1,...,nv, is 1 if node i is labelled, and 0 otherwise.
alpar@9 67 * The set of arcs, whose one endpoint is labelled and other is not,
alpar@9 68 * defines the minimal cut corresponding to the maximal flow found.
alpar@9 69 * If the parameter cut is NULL, the cut information are not stored.
alpar@9 70 *
alpar@9 71 * REFERENCES
alpar@9 72 *
alpar@9 73 * L.R.Ford, Jr., and D.R.Fulkerson, "Flows in Networks," The RAND
alpar@9 74 * Corp., Report R-375-PR (August 1962), Chap. I "Static Maximal Flow,"
alpar@9 75 * pp.30-33. */
alpar@9 76
alpar@9 77 void ffalg(int nv, int na, const int tail[], const int head[],
alpar@9 78 int s, int t, const int cap[], int x[], char cut[])
alpar@9 79 { int a, delta, i, j, k, pos1, pos2, temp,
alpar@9 80 *ptr, *arc, *link, *list;
alpar@9 81 /* sanity checks */
alpar@9 82 xassert(nv >= 2);
alpar@9 83 xassert(na >= 0);
alpar@9 84 xassert(1 <= s && s <= nv);
alpar@9 85 xassert(1 <= t && t <= nv);
alpar@9 86 xassert(s != t);
alpar@9 87 for (a = 1; a <= na; a++)
alpar@9 88 { i = tail[a], j = head[a];
alpar@9 89 xassert(1 <= i && i <= nv);
alpar@9 90 xassert(1 <= j && j <= nv);
alpar@9 91 xassert(i != j);
alpar@9 92 xassert(cap[a] >= 0);
alpar@9 93 }
alpar@9 94 /* allocate working arrays */
alpar@9 95 ptr = xcalloc(1+nv+1, sizeof(int));
alpar@9 96 arc = xcalloc(1+na+na, sizeof(int));
alpar@9 97 link = xcalloc(1+nv, sizeof(int));
alpar@9 98 list = xcalloc(1+nv, sizeof(int));
alpar@9 99 /* ptr[i] := (degree of node i) */
alpar@9 100 for (i = 1; i <= nv; i++)
alpar@9 101 ptr[i] = 0;
alpar@9 102 for (a = 1; a <= na; a++)
alpar@9 103 { ptr[tail[a]]++;
alpar@9 104 ptr[head[a]]++;
alpar@9 105 }
alpar@9 106 /* initialize arc pointers */
alpar@9 107 ptr[1]++;
alpar@9 108 for (i = 1; i < nv; i++)
alpar@9 109 ptr[i+1] += ptr[i];
alpar@9 110 ptr[nv+1] = ptr[nv];
alpar@9 111 /* build arc lists */
alpar@9 112 for (a = 1; a <= na; a++)
alpar@9 113 { arc[--ptr[tail[a]]] = a;
alpar@9 114 arc[--ptr[head[a]]] = a;
alpar@9 115 }
alpar@9 116 xassert(ptr[1] == 1);
alpar@9 117 xassert(ptr[nv+1] == na+na+1);
alpar@9 118 /* now the indices of arcs incident to node i are stored in
alpar@9 119 locations arc[ptr[i]], arc[ptr[i]+1], ..., arc[ptr[i+1]-1] */
alpar@9 120 /* initialize arc flows */
alpar@9 121 for (a = 1; a <= na; a++)
alpar@9 122 x[a] = 0;
alpar@9 123 loop: /* main loop starts here */
alpar@9 124 /* build augmenting tree rooted at s */
alpar@9 125 /* link[i] = 0 means that node i is not labelled yet;
alpar@9 126 link[i] = a means that arc a immediately precedes node i */
alpar@9 127 /* initially node s is labelled as the root */
alpar@9 128 for (i = 1; i <= nv; i++)
alpar@9 129 link[i] = 0;
alpar@9 130 link[s] = -1, list[1] = s, pos1 = pos2 = 1;
alpar@9 131 /* breadth first search */
alpar@9 132 while (pos1 <= pos2)
alpar@9 133 { /* dequeue node i */
alpar@9 134 i = list[pos1++];
alpar@9 135 /* consider all arcs incident to node i */
alpar@9 136 for (k = ptr[i]; k < ptr[i+1]; k++)
alpar@9 137 { a = arc[k];
alpar@9 138 if (tail[a] == i)
alpar@9 139 { /* a = i->j is a forward arc from s to t */
alpar@9 140 j = head[a];
alpar@9 141 /* if node j has been labelled, skip the arc */
alpar@9 142 if (link[j] != 0) continue;
alpar@9 143 /* if the arc does not allow increasing the flow through
alpar@9 144 it, skip the arc */
alpar@9 145 if (x[a] == cap[a]) continue;
alpar@9 146 }
alpar@9 147 else if (head[a] == i)
alpar@9 148 { /* a = i<-j is a backward arc from s to t */
alpar@9 149 j = tail[a];
alpar@9 150 /* if node j has been labelled, skip the arc */
alpar@9 151 if (link[j] != 0) continue;
alpar@9 152 /* if the arc does not allow decreasing the flow through
alpar@9 153 it, skip the arc */
alpar@9 154 if (x[a] == 0) continue;
alpar@9 155 }
alpar@9 156 else
alpar@9 157 xassert(a != a);
alpar@9 158 /* label node j and enqueue it */
alpar@9 159 link[j] = a, list[++pos2] = j;
alpar@9 160 /* check for breakthrough */
alpar@9 161 if (j == t) goto brkt;
alpar@9 162 }
alpar@9 163 }
alpar@9 164 /* NONBREAKTHROUGH */
alpar@9 165 /* no augmenting path exists; current flow is maximal */
alpar@9 166 /* store minimal cut information, if necessary */
alpar@9 167 if (cut != NULL)
alpar@9 168 { for (i = 1; i <= nv; i++)
alpar@9 169 cut[i] = (char)(link[i] != 0);
alpar@9 170 }
alpar@9 171 goto done;
alpar@9 172 brkt: /* BREAKTHROUGH */
alpar@9 173 /* walk through arcs of the augmenting path (s, ..., t) found in
alpar@9 174 the reverse order and determine maximal change of the flow */
alpar@9 175 delta = 0;
alpar@9 176 for (j = t; j != s; j = i)
alpar@9 177 { /* arc a immediately precedes node j in the path */
alpar@9 178 a = link[j];
alpar@9 179 if (head[a] == j)
alpar@9 180 { /* a = i->j is a forward arc of the cycle */
alpar@9 181 i = tail[a];
alpar@9 182 /* x[a] may be increased until its upper bound */
alpar@9 183 temp = cap[a] - x[a];
alpar@9 184 }
alpar@9 185 else if (tail[a] == j)
alpar@9 186 { /* a = i<-j is a backward arc of the cycle */
alpar@9 187 i = head[a];
alpar@9 188 /* x[a] may be decreased until its lower bound */
alpar@9 189 temp = x[a];
alpar@9 190 }
alpar@9 191 else
alpar@9 192 xassert(a != a);
alpar@9 193 if (delta == 0 || delta > temp) delta = temp;
alpar@9 194 }
alpar@9 195 xassert(delta > 0);
alpar@9 196 /* increase the flow along the path */
alpar@9 197 for (j = t; j != s; j = i)
alpar@9 198 { /* arc a immediately precedes node j in the path */
alpar@9 199 a = link[j];
alpar@9 200 if (head[a] == j)
alpar@9 201 { /* a = i->j is a forward arc of the cycle */
alpar@9 202 i = tail[a];
alpar@9 203 x[a] += delta;
alpar@9 204 }
alpar@9 205 else if (tail[a] == j)
alpar@9 206 { /* a = i<-j is a backward arc of the cycle */
alpar@9 207 i = head[a];
alpar@9 208 x[a] -= delta;
alpar@9 209 }
alpar@9 210 else
alpar@9 211 xassert(a != a);
alpar@9 212 }
alpar@9 213 goto loop;
alpar@9 214 done: /* free working arrays */
alpar@9 215 xfree(ptr);
alpar@9 216 xfree(arc);
alpar@9 217 xfree(link);
alpar@9 218 xfree(list);
alpar@9 219 return;
alpar@9 220 }
alpar@9 221
alpar@9 222 /* eof */