Hello Andrew,
the tsp example results in warnings
mincut.c:52:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
52 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/])
| ^~~
mincut.c:225:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
225 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/])
|
In file included from main.c:83:
mincut.h:9:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
9 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/]);
| ^~~
mincut.h:18:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
18 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/]);
| ^~~
In file included from mincut.c:8:
mincut.h:9:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
9 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/]);
| ^~~
mincut.h:18:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
18 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/]);
| ^~~
mincut.c:52:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
52 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/])
| ^~~
mincut.c:225:38: warning: type defaults to ‘int’ in declaration of ‘cap’
[-Wimplicit-int]
225 | const int end[/*1+ne*/], const cap[/*1+ne*/], int
cut[/*1+nn*/])
Please, replace the files according to the appendix.
Best regards
Heinrich
/* mincut.c */
/* Written by Andrew Makhorin <[email protected]>, October 2015. */
#include <limits.h>
#include "maxflow.h"
#include "mincut.h"
#include "misc.h"
/***********************************************************************
* NAME
*
* min_cut - find min cut in undirected capacitated network
*
* SYNOPSIS
*
* #include "mincut.h"
* int min_cut(int nn, int ne, const int beg[], const int end[],
* const cap[], int cut[]);
*
* DESCRIPTION
*
* This routine finds min cut in a given undirected network.
*
* The undirected capacitated network is specified by the parameters
* nn, ne, beg, end, and cap. The parameter nn specifies the number of
* vertices (nodes), nn >= 2, and the parameter ne specifies the number
* of edges, ne >= 0. The network edges are specified by triplets
* (beg[k], end[k], cap[k]) for k = 1, ..., ne, where beg[k] < end[k]
* are numbers of the first and second nodes of k-th edge, and
* cap[k] > 0 is a capacity of k-th edge. Loops and multiple edges are
* not allowed.
*
* Let V be the set of nodes of the network and let W be an arbitrary
* non-empty proper subset of V. A cut associated with the subset W is
* a subset of all the edges, one node of which belongs to W and other
* node belongs to V \ W. The capacity of a cut (W, V \ W) is the sum
* of the capacities of all the edges, which belong to the cut. Minimal
* cut is a cut, whose capacity is minimal.
*
* On exit the routine stores flags of nodes v[i], i = 1, ..., nn, to
* locations cut[i], where cut[i] = 1 means that v[i] belongs to W and
* cut[i] = 0 means that v[i] belongs to V \ W, where W corresponds to
* the minimal cut found.
*
* RETURNS
*
* The routine returns the capacity of the min cut found. */
int min_cut(int nn, int ne, const int beg[/*1+ne*/],
const int end[/*1+ne*/], const int cap[/*1+ne*/], int cut[/*1+nn*/])
{ int k;
/* sanity checks */
xassert(nn >= 2);
xassert(ne >= 0);
for (k = 1; k <= ne; k++)
{ xassert(1 <= beg[k] && beg[k] < end[k] && end[k] <= nn);
xassert(cap[k] > 0);
}
/* find min cut */
return min_cut_sw(nn, ne, beg, end, cap, cut);
}
/***********************************************************************
* NAME
*
* min_st_cut - find min (s,t)-cut for known max flow
*
* SYNOPSIS
*
* #include "mincut.h"
*
* DESCRIPTION
*
* This routine finds min (s,t)-cut in a given undirected network that
* corresponds to a known max flow from s to t in the network.
*
* Parameters nn, ne, beg, end, and cap specify the network in the same
* way as for the routine min_cut (see above).
*
* Parameters s and t specify, resp., the number of the source node
* and the number of the sink node, s != t, for which the min (s,t)-cut
* has to be found.
*
* Parameter x specifies the known max flow from s to t in the network,
* where locations x[1], ..., x[ne] contains elementary flow thru edges
* of the network (positive value of x[k] means that the elementary
* flow goes from node beg[k] to node end[k], and negative value means
* that the flow goes in opposite direction).
*
* This routine splits the set of nodes V of the network into two
* non-empty subsets V(s) and V(t) = V \ V(s), where the source node s
* belongs to V(s), the sink node t belongs to V(t), and all edges, one
* node of which belongs to V(s) and other one belongs to V(t), are
* saturated (that is, x[k] = +cap[k] or x[k] = -cap[k]).
*
* On exit the routine stores flags of the nodes v[i], i = 1, ..., nn,
* to locations cut[i], where cut[i] = 1 means that v[i] belongs to V(s)
* and cut[i] = 0 means that v[i] belongs to V(t) = V \ V(s).
*
* RETURNS
*
* The routine returns the capacity of min (s,t)-cut, which is the sum
* of the capacities of all the edges, which belong to the cut. (Note
* that due to theorem by Ford and Fulkerson this value is always equal
* to corresponding max flow.)
*
* ALGORITHM
*
* To determine the set V(s) the routine simply finds all nodes, which
* can be reached from the source node s via non-saturated edges. The
* set V(t) is determined as the complement V \ V(s). */
int min_st_cut(int nn, int ne, const int beg[/*1+ne*/],
const int end[/*1+ne*/], const int cap[/*1+ne*/], int s, int t,
const int x[/*1+ne*/], int cut[/*1+nn*/])
{ int i, j, k, p, q, temp, *head1, *next1, *head2, *next2, *list;
/* head1[i] points to the first edge with beg[k] = i
* next1[k] points to the next edge with the same beg[k]
* head2[i] points to the first edge with end[k] = i
* next2[k] points to the next edge with the same end[k] */
head1 = xalloc(1+nn, sizeof(int));
head2 = xalloc(1+nn, sizeof(int));
next1 = xalloc(1+ne, sizeof(int));
next2 = xalloc(1+ne, sizeof(int));
for (i = 1; i <= nn; i++)
head1[i] = head2[i] = 0;
for (k = 1; k <= ne; k++)
{ i = beg[k], next1[k] = head1[i], head1[i] = k;
j = end[k], next2[k] = head2[j], head2[j] = k;
}
/* on constructing the set V(s) list[1], ..., list[p-1] contain
* nodes, which can be reached from source node and have been
* visited, and list[p], ..., list[q] contain nodes, which can be
* reached from source node but havn't been visited yet */
list = xalloc(1+nn, sizeof(int));
for (i = 1; i <= nn; i++)
cut[i] = 0;
p = q = 1, list[1] = s, cut[s] = 1;
while (p <= q)
{ /* pick next node, which is reachable from the source node and
* has not visited yet, and visit it */
i = list[p++];
/* walk through edges with beg[k] = i */
for (k = head1[i]; k != 0; k = next1[k])
{ j = end[k];
xassert(beg[k] == i);
/* from v[i] we can reach v[j], if the elementary flow from
* v[i] to v[j] is non-saturated */
if (cut[j] == 0 && x[k] < +cap[k])
list[++q] = j, cut[j] = 1;
}
/* walk through edges with end[k] = i */
for (k = head2[i]; k != 0; k = next2[k])
{ j = beg[k];
xassert(end[k] == i);
/* from v[i] we can reach v[j], if the elementary flow from
* v[i] to v[j] is non-saturated */
if (cut[j] == 0 && x[k] > -cap[k])
list[++q] = j, cut[j] = 1;
}
}
/* sink cannot belong to V(s) */
xassert(!cut[t]);
/* free working arrays */
xfree(head1);
xfree(head2);
xfree(next1);
xfree(next2);
xfree(list);
/* compute capacity of the minimal (s,t)-cut found */
temp = 0;
for (k = 1; k <= ne; k++)
{ i = beg[k], j = end[k];
if (cut[i] && !cut[j] || !cut[i] && cut[j])
temp += cap[k];
}
/* return to the calling program */
return temp;
}
/***********************************************************************
* NAME
*
* min_cut_sw - find min cut with Stoer and Wagner algorithm
*
* SYNOPSIS
*
* #include "mincut.h"
* int min_cut_sw(int nn, int ne, const int beg[], const int end[],
* const cap[], int cut[]);
*
* DESCRIPTION
*
* This routine find min cut in a given undirected network with the
* algorithm proposed by Stoer and Wagner (see references below).
*
* Parameters of this routine have the same meaning as for the routine
* min_cut (see above).
*
* RETURNS
*
* The routine returns the capacity of the min cut found.
*
* ALGORITHM
*
* The basic idea of Stoer&Wagner algorithm is the following. Let G be
* a capacitated network, and G(s,t) be a network, in which the nodes s
* and t are merged into one new node, loops are deleted, but multiple
* edges are retained. It is obvious that a minimum cut in G is the
* minimum of two quantities: the minimum cut in G(s,t) and a minimum
* cut that separates s and t. This allows to find a minimum cut in the
* original network solving at most nn max flow problems.
*
* REFERENCES
*
* M. Stoer, F. Wagner. A Simple Min Cut Algorithm. Algorithms, ESA'94
* LNCS 855 (1994), pp. 141-47.
*
* J. Cheriyan, R. Ravi. Approximation Algorithms for Network Problems.
* Univ. of Waterloo (1998), p. 147. */
int min_cut_sw(int nn, int ne, const int beg[/*1+ne*/],
const int end[/*1+ne*/], const int cap[/*1+ne*/], int cut[/*1+nn*/])
{ int i, j, k, min_cut, flow, temp, *head1, *next1, *head2, *next2;
int I, J, K, S, T, DEG, NV, NE, *HEAD, *NEXT, *NUMB, *BEG, *END,
*CAP, *X, *ADJ, *SUM, *CUT;
/* head1[i] points to the first edge with beg[k] = i
* next1[k] points to the next edge with the same beg[k]
* head2[i] points to the first edge with end[k] = i
* next2[k] points to the next edge with the same end[k] */
head1 = xalloc(1+nn, sizeof(int));
head2 = xalloc(1+nn, sizeof(int));
next1 = xalloc(1+ne, sizeof(int));
next2 = xalloc(1+ne, sizeof(int));
for (i = 1; i <= nn; i++)
head1[i] = head2[i] = 0;
for (k = 1; k <= ne; k++)
{ i = beg[k], next1[k] = head1[i], head1[i] = k;
j = end[k], next2[k] = head2[j], head2[j] = k;
}
/* an auxiliary network used in the algorithm is resulted from
* the original network by merging some nodes into one supernode;
* all variables and arrays related to this auxiliary network are
* denoted in CAPS */
/* HEAD[I] points to the first node of the original network that
* belongs to the I-th supernode
* NEXT[i] points to the next node of the original network that
* belongs to the same supernode as the i-th node
* NUMB[i] is a supernode, which the i-th node belongs to */
/* initially the auxiliary network is equivalent to the original
* network, i.e. each supernode consists of one node */
NV = nn;
HEAD = xalloc(1+nn, sizeof(int));
NEXT = xalloc(1+nn, sizeof(int));
NUMB = xalloc(1+nn, sizeof(int));
for (i = 1; i <= nn; i++)
HEAD[i] = i, NEXT[i] = 0, NUMB[i] = i;
/* number of edges in the auxiliary network is never greater than
* in the original one */
BEG = xalloc(1+ne, sizeof(int));
END = xalloc(1+ne, sizeof(int));
CAP = xalloc(1+ne, sizeof(int));
X = xalloc(1+ne, sizeof(int));
/* allocate some auxiliary arrays */
ADJ = xalloc(1+nn, sizeof(int));
SUM = xalloc(1+nn, sizeof(int));
CUT = xalloc(1+nn, sizeof(int));
/* currently no min cut is found so far */
min_cut = INT_MAX;
/* main loop starts here */
while (NV > 1)
{ /* build the set of edges of the auxiliary network */
NE = 0;
/* multiple edges are not allowed in the max flow algorithm,
* so we can replace each multiple edge, which is the result
* of merging nodes into supernodes, by a single edge, whose
* capacity is the sum of capacities of particular edges;
* these summary capacities will be stored in the array SUM */
for (I = 1; I <= NV; I++)
SUM[I] = 0.0;
for (I = 1; I <= NV; I++)
{ /* DEG is number of single edges, which connects I-th
* supernode and some J-th supernode, where I < J */
DEG = 0;
/* walk thru nodes that belong to I-th supernode */
for (i = HEAD[I]; i != 0; i = NEXT[i])
{ /* i-th node belongs to I-th supernode */
/* walk through edges with beg[k] = i */
for (k = head1[i]; k != 0; k = next1[k])
{ j = end[k];
/* j-th node belongs to J-th supernode */
J = NUMB[j];
/* ignore loops and edges with I > J */
if (I >= J)
continue;
/* add an edge that connects I-th and J-th supernodes
* (if not added yet) */
if (SUM[J] == 0.0)
ADJ[++DEG] = J;
/* sum up the capacity of the original edge */
xassert(cap[k] > 0.0);
SUM[J] += cap[k];
}
/* walk through edges with end[k] = i */
for (k = head2[i]; k != 0; k = next2[k])
{ j = beg[k];
/* j-th node belongs to J-th supernode */
J = NUMB[j];
/* ignore loops and edges with I > J */
if (I >= J)
continue;
/* add an edge that connects I-th and J-th supernodes
* (if not added yet) */
if (SUM[J] == 0.0)
ADJ[++DEG] = J;
/* sum up the capacity of the original edge */
xassert(cap[k] > 0.0);
SUM[J] += cap[k];
}
}
/* add single edges connecting I-th supernode with other
* supernodes to the auxiliary network; restore the array
* SUM for subsequent use */
for (K = 1; K <= DEG; K++)
{ NE++;
xassert(NE <= ne);
J = ADJ[K];
BEG[NE] = I, END[NE] = J, CAP[NE] = SUM[J];
SUM[J] = 0.0;
}
}
/* choose two arbitrary supernodes of the auxiliary network,
* one of which is the source and other is the sink */
S = 1, T = NV;
/* determine max flow from S to T */
flow = max_flow(NV, NE, BEG, END, CAP, S, T, X);
/* if the min cut that separates supernodes S and T is less
* than the currently known, remember it */
if (min_cut > flow)
{ min_cut = flow;
/* find min (s,t)-cut in the auxiliary network */
temp = min_st_cut(NV, NE, BEG, END, CAP, S, T, X, CUT);
/* (Ford and Fulkerson insist on this) */
xassert(flow == temp);
/* build corresponding min cut in the original network */
for (i = 1; i <= nn; i++) cut[i] = CUT[NUMB[i]];
/* if the min cut capacity is zero (i.e. the network has
* unconnected components), the search can be prematurely
* terminated */
if (min_cut == 0)
break;
}
/* now merge all nodes of the original network, which belong
* to the supernodes S and T, into one new supernode; this is
* attained by carrying all nodes from T to S (for the sake of
* convenience T should be the last supernode) */
xassert(T == NV);
/* assign new references to nodes from T */
for (i = HEAD[T]; i != 0; i = NEXT[i])
NUMB[i] = S;
/* find last entry in the node list of S */
i = HEAD[S];
xassert(i != 0);
while (NEXT[i] != 0)
i = NEXT[i];
/* and attach to it the node list of T */
NEXT[i] = HEAD[T];
/* decrease number of nodes in the auxiliary network */
NV--;
}
/* free working arrays */
xfree(HEAD);
xfree(NEXT);
xfree(NUMB);
xfree(BEG);
xfree(END);
xfree(CAP);
xfree(X);
xfree(ADJ);
xfree(SUM);
xfree(CUT);
xfree(head1);
xfree(head2);
xfree(next1);
xfree(next2);
/* return to the calling program */
return min_cut;
}
/* eof */
/* mincut.c */
/* Written by Andrew Makhorin <[email protected]>, October 2015. */
#ifndef MINCUT_H
#define MINCUT_H
int min_cut(int nn, int ne, const int beg[/*1+ne*/],
const int end[/*1+ne*/], const int cap[/*1+ne*/], int cut[/*1+nn*/]);
/* find min cut in undirected capacitated network */
int min_st_cut(int nn, int ne, const int beg[/*1+ne*/],
const int end[/*1+ne*/], const int cap[/*1+ne*/], int s, int t,
const int x[/*1+ne*/], int cut[/*1+nn*/]);
/* find min (s,t)-cut for known max flow */
int min_cut_sw(int nn, int ne, const int beg[/*1+ne*/],
const int end[/*1+ne*/], const int cap[/*1+ne*/], int cut[/*1+nn*/]);
/* find min cut with Stoer and Wagner algorithm */
#endif
/* eof */
