1 /* Copyright (c) 1997-2021
2 Ewgenij Gawrilow, Michael Joswig, and the polymake team
3 Technische Universität Berlin, Germany
4 https://polymake.org
5
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version: http://www.gnu.org/licenses/gpl.txt.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15 --------------------------------------------------------------------------------
16 */
17
18 #include "polymake/client.h"
19 #include "polymake/Bitset.h"
20 #include "polymake/Graph.h"
21
22 namespace polymake { namespace graph {
23 namespace {
24
25 typedef Graph<Directed> dgraph;
26
FF_rec(Int n,Int t,Bitset & visited,dgraph & G,EdgeMap<Directed,bool> & saturated)27 Int FF_rec(Int n, Int t, Bitset& visited, dgraph& G, EdgeMap<Directed, bool>& saturated)
28 {
29 // DFS to find augmenting path, augmenting is done backwards once t is reached
30 // return value is t if t is reached, n otherwise
31
32 if (n==t) // augmenting path is found
33 return t;
34
35 // traversing the outgoing edges (in the original graph)
36 for (auto e = entire(G.out_edges(n)); !e.at_end(); ++e) {
37 Int nn = e.to_node();
38 if ( !visited.contains(nn) && !saturated[*e] ) { // nn has not been visited and the arc (n,nn) is not saturated
39 visited+=nn;
40 Int return_node = FF_rec(nn, t, visited, G, saturated);
41 if (return_node == t) { // augmenting path is found: augment (original) edge
42 saturated[*e] ^= 1;
43 return t;
44 }
45 }
46 }
47
48 // traversing the ingoing edges (= reversed edges in the residual graph)
49 for (auto e=entire(G.in_edges(n)); !e.at_end(); ++e) {
50 Int nn = e.from_node();
51 if ( !visited.contains(nn) && saturated[*e] ) { // nn has not been visited and the arc (nn,n) is saturated, therefore it exists in the res graph
52 visited+=nn;
53 Int return_node = FF_rec(nn, t, visited, G, saturated);
54 if (return_node == t) { // augmenting path is found: augment (reverse) edge
55 saturated[*e] ^= 1;
56 return t;
57 }
58 }
59 }
60
61 return n; // t has not been reached
62 }
63
FF(Int s,Int t,dgraph & G)64 Int FF(Int s, Int t, dgraph& G)
65 {
66 Int maxflow = 0;
67 EdgeMap<Directed, bool> saturated(G, false);
68
69 for (;;) {
70 Bitset visited(G.nodes());
71 visited+=s;
72 if (FF_rec(s, t, visited, G, saturated) != t) break; // t wasn't reached -> no augmenting path found
73 ++maxflow;
74 }
75
76 return maxflow;
77 }
78
79 } // end unnamed namespace
80
81 template <typename AnyGraph>
connectivity(const GenericGraph<AnyGraph,Undirected> & G_in)82 Int connectivity(const GenericGraph<AnyGraph, Undirected>& G_in)
83 {
84 /* Tranfsorm the graph:
85 * each node n is split in n_in and n_out with an arc (n_in, n_out).
86 * the arcs (x,n) are replaced by (x,n_in) and the arcs (n,y) by (n_out,y).
87 * all edges are assumed to have capacity c=1.
88 *
89 * n_in will be represented as n and n_out as n+nodes
90 *
91 * if there is "something" flowing over an edge e, than e is immediately saturated,
92 * since all edges have capacity c=1 and we are computing an integer flow.
93 */
94
95 const Int nodes = G_in.nodes();
96 dgraph G(2*nodes);
97 for (Int i = 0; i < nodes; ++i) {
98 G.out_adjacent_nodes(i+nodes) = G_in.top().adjacent_nodes(i);
99 G.edge(i, i+nodes);
100 }
101
102 // compute min maxflow from node 0+nodes to node n for n=1,...,nodes-1
103 // using Ford-Fulkerson
104 Int minmaxflow = nodes;
105 for (Int i = 1; i < nodes; ++i)
106 assign_min(minmaxflow, FF(nodes,i,G));
107
108 return minmaxflow;
109 }
110
111 UserFunctionTemplate4perl("# @category Combinatorics"
112 "# Compute the [[CONNECTIVITY]] of a given //graph// using the Ford-Fulkerson flow algorithm."
113 "# @param GraphAdjacency<Undirected> graph"
114 "# @return Int"
115 "# @example [application polytope]"
116 "# Compute the connectivity of the vertex-edge graph of the square:"
117 "# > print connectivity(cube(2)->GRAPH->ADJACENCY);"
118 "# | 2"
119 "# This means that at least two nodes or edges need to be removed in order"
120 "# for the resulting graph not to be connected anymore."
121 "# @author Nikolaus Witte",
122 "connectivity(GraphAdjacency<Undirected>)");
123 } }
124
125 // Local Variables:
126 // mode:C++
127 // c-basic-offset:3
128 // indent-tabs-mode:nil
129 // End:
130