/* Copyright (c) 1997-2004
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ident "$Project: polymake $$Id: connectivity.cc 4714 2004-06-22 16:23:15Z gawrilow $"

#include <Bitset.h>
#include <Poly.h>
#include <Graph.h>

namespace polymake { namespace graph {

namespace {

typedef Graph<nothing, bool, directed> graph;

int FF_rec (int n, int t, Bitset& visited, graph& G)
{
   // DFS to find augmenting path, augmenting is done backwards once t is reached
   // return value is t if t is reached, n otherwise

   if (n==t)     // augmenting path is found
      return t;

   // traversing the outgoing edges (in the original graph)
   for (Entire<graph::out_edge_list>::iterator e=entire(G.out_edges(n)); !e.at_end(); ++e) {
      int nn=e.to_node();
      if ( !visited.contains(nn) && !(G.edge(n,nn)) ) {   // nn has not been visited and the arc (n,nn) is not saturated
	 visited+=nn;
	 int return_node = FF_rec (nn, t, visited, G);
	 if (return_node == t) {      // augmenting path is found: augment (original) edge
	    G.edge(n,nn) ^= 1;
	    return t;
	 }
      }
   }

   // traversing the ingoing edges (= reversed edges in the residual graph)
   for (Entire<graph::in_edge_list>::iterator e=entire(G.in_edges(n)); !e.at_end(); ++e) {
      int nn=e.from_node();
      if ( !visited.contains(nn) && G.edge(nn,n) ) {   // nn has not been visited and the arc (nn,n) is saturated, therefore it exists in the res graph
	 visited+=nn;
	 int return_node = FF_rec (nn, t, visited, G);
	 if (return_node == t) {      // augmenting path is found: augment (reverse) edge
	       G.edge(nn,n) ^= 1;
	       return t;
	 }
      }
   }

   return n;        // t has not been reached
}

int FF (int s, int t, graph& G)
{
   std::fill(entire(edges(G)), false);
   int maxflow=0;

   while (true) {
      Bitset visited(G.nodes());
      visited+=s;

      int end_node = FF_rec (s, t, visited, G);

      if (end_node == t)        // t is reached
	 ++maxflow;
      else                      // t wasn't reached -> no augmenting path found
	 break;
   }

   return maxflow;
}

}  // end unnamed namespace

void connectivity(Poly& p, const char* graph_section, const char* result_section)
{
   graph G;
   p.give(graph_section) >> neighborhood_matrix(G);

   /* Alter the graph G:
    * each node n is split in n_in and n_out with an arc (n_in, n_out).
    * the arcs (x,n) are replaced by (x,n_in) and the arcs (n,y) by (n_out,y).
    * all edges are assumed to have capacity c=1.
    *
    * n_in will be represented as n and n_out as n+nodes
    * the edge label reads saturated:
    * if there is "something" flowing over an edge e, than e is immediately saturated,
    * since all edges have capacity c=1 and we are computing an integer flow. 
    */
   const int nodes=G.nodes();
   G.resize(2*nodes);
   for (int i=0; i<nodes; ++i) {
      G.out_edges(i+nodes)=G.out_edges(i);
      G.out_edges(i).clear();
      G.edge(i,i+nodes);
   }

   // compute min maxflow from node 0+nodes to node n for n=1,...,nodes-1
   // using Ford-Fulkerson
   int minmaxflow = nodes;
     
   for (int i=1; i<nodes; ++i) {
      int maxflow=FF(nodes,i,G);
      if (maxflow < minmaxflow)
	 minmaxflow=maxflow;
   }
     
   p.take(result_section) << minmaxflow;
}

} }

using namespace polymake;

/** @file connectivity
 *
 *  Compute the connectivity of a given graph using the Ford-Fulkerson flow algorithm.
 *
 *  @synopsis connectivity <file> <graph_section> <connectivity_section>
 *
 *  @reading  <graph_section>
 *  @writing  <connectivity_section>
 *
 *  @author Nikolaus Witte <witte@math.tu-berlin.de>
 */

int main(int argc, const char *argv[])
{
   if (argc!=4) {
      cerr << "usage: " << argv[0] << " <file> <graph_section> <connectivity_section> " << endl;
      return 1;
   }
   try {
      Poly p(argv[1], ios::in | ios::out);
      graph::connectivity(p, argv[2], argv[3]);
   }
   catch (const std::exception& e) {
      cerr << e.what() << "\n" << endl;
      return 1;
   }
   return 0;
}