# HG changeset patch
# User alpar
# Date 1171986813 0
# Node ID e30a0fdad0d7b3085d82d1290afb6f754513bc23
# Parent  b59a17034ffaa8383f4a4ce986ec8ffd3a174aea
A preflow based general network circulation algorithm and a simple demo

diff -r b59a17034ffa -r e30a0fdad0d7 demo/Makefile.am
--- a/demo/Makefile.am	Tue Feb 20 13:01:22 2007 +0000
+++ b/demo/Makefile.am	Tue Feb 20 15:53:33 2007 +0000
@@ -1,10 +1,23 @@
 EXTRA_DIST += \
 	demo/Makefile \
-	demo/sub_graph_adaptor_demo.dim
-
+	demo/sub_graph_adaptor_demo.dim \
+	demo/circulation-input.lgf \
+	demo/coloring.lgf \
+	demo/dir_components.lgf \
+	demo/disjoint_paths_demo.lgf \
+	demo/graph_orientation.lgf \
+	demo/partitions.lgf \
+	demo/route.lgf \
+	demo/sample.lgf \
+	demo/simann_maxcut_demo.lgf \
+	demo/strongly_connected_orientation.lgf \
+	demo/sub_gad_input.lgf \
+	demo/u_components.lgf
+	
 if WANT_DEMO
 
 noinst_PROGRAMS += \
+	demo/circulation_demo \
 	demo/csp_demo \
 	demo/dim_to_dot \
 	demo/dijkstra_demo \
@@ -39,6 +52,8 @@
 
 demo_csp_demo_SOURCES = demo/csp_demo.cc
 
+demo_circulation_demo_SOURCES = demo/circulation_demo.cc
+
 demo_dim_to_dot_SOURCES = demo/dim_to_dot.cc
 
 demo_dijkstra_demo_SOURCES = demo/dijkstra_demo.cc
diff -r b59a17034ffa -r e30a0fdad0d7 demo/circulation-input.lgf
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/circulation-input.lgf	Tue Feb 20 15:53:33 2007 +0000
@@ -0,0 +1,165 @@
+@nodeset 
+coordinates_x	coordinates_y	delta	label	
+-396.638	-311.798	0	0	
+154.409	-214.714	-13	1	
+-378.119	-135.808	0	2	
+-138.182	-58.0452	0	3	
+55	-76.1018	0	4	
+-167.302	169.88	0	5	
+71.6876	38.7452	0	6	
+-328.784	257.777	0	7	
+354.242	67.9628	13	8	
+147	266	0	9	
+@edgeset 
+		label	lo_cap	up_cap	
+0	1	0	0	20	
+0	2	1	0	0	
+1	1	2	0	3	
+1	2	3	0	8	
+1	3	4	0	8	
+2	5	5	0	5	
+3	2	6	0	5	
+3	5	7	0	5	
+3	6	8	0	5	
+4	3	9	0	3	
+5	7	10	0	3	
+5	6	11	0	10	
+5	8	12	0	10	
+6	8	13	0	8	
+8	9	14	0	20	
+8	1	15	0	5	
+9	5	16	0	5	
+@gui
+<arrow_pos>
+ <item>
+  <first>0</first>
+  <second>
+   <x>-121.114</x><y>-263.256</y>
+  </second>
+ </item>
+ <item>
+  <first>1</first>
+  <second>
+   <x>-387.378</x><y>-223.803</y>
+  </second>
+ </item>
+ <item>
+  <first>2</first>
+  <second>
+   <x>253.622</x><y>-301.284</y>
+  </second>
+ </item>
+ <item>
+  <first>3</first>
+  <second>
+   <x>-111.855</x><y>-175.261</y>
+  </second>
+ </item>
+ <item>
+  <first>4</first>
+  <second>
+   <x>8.1134</x><y>-136.379</y>
+  </second>
+ </item>
+ <item>
+  <first>5</first>
+  <second>
+   <x>-272.71</x><y>17.0361</y>
+  </second>
+ </item>
+ <item>
+  <first>6</first>
+  <second>
+   <x>-258.151</x><y>-96.9267</y>
+  </second>
+ </item>
+ <item>
+  <first>7</first>
+  <second>
+   <x>-152.742</x><y>55.9176</y>
+  </second>
+ </item>
+ <item>
+  <first>8</first>
+  <second>
+   <x>-33.2474</x><y>-9.64996</y>
+  </second>
+ </item>
+ <item>
+  <first>9</first>
+  <second>
+   <x>-41.5912</x><y>-67.0735</y>
+  </second>
+ </item>
+ <item>
+  <first>10</first>
+  <second>
+   <x>-248.043</x><y>213.829</y>
+  </second>
+ </item>
+ <item>
+  <first>11</first>
+  <second>
+   <x>-47.8072</x><y>104.313</y>
+  </second>
+ </item>
+ <item>
+  <first>12</first>
+  <second>
+   <x>93.4701</x><y>118.922</y>
+  </second>
+ </item>
+ <item>
+  <first>13</first>
+  <second>
+   <x>212.965</x><y>53.354</y>
+  </second>
+ </item>
+ <item>
+  <first>14</first>
+  <second>
+   <x>250.621</x><y>166.981</y>
+  </second>
+ </item>
+ <item>
+  <first>15</first>
+  <second>
+   <x>254.326</x><y>-73.3755</y>
+  </second>
+ </item>
+ <item>
+  <first>16</first>
+  <second>
+   <x>-10.1511</x><y>217.94</y>
+  </second>
+ </item>
+</arrow_pos>
+<active_nodemaps>
+ <item>
+  <first>0</first>
+  <second></second>
+ </item>
+ <item>
+  <first>1</first>
+  <second>delta</second>
+ </item>
+ <item>
+  <first>2</first>
+  <second>label</second>
+ </item>
+</active_nodemaps>
+<active_edgemaps>
+ <item>
+  <first>0</first>
+  <second>up_cap</second>
+ </item>
+ <item>
+  <first>1</first>
+  <second></second>
+ </item>
+ <item>
+  <first>2</first>
+  <second>up_cap</second>
+ </item>
+</active_edgemaps>
+@end
diff -r b59a17034ffa -r e30a0fdad0d7 demo/circulation_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/circulation_demo.cc	Tue Feb 20 15:53:33 2007 +0000
@@ -0,0 +1,108 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\ingroup demos
+///\file
+///\brief Demonstrating the usage of LEMON's General Flow algorithm
+///
+/// This demo program reads a general network circulation problem from the
+/// file 'circulation-input.lgf', runs the preflow based algorithm for
+/// finding a feasible solution and writes the output
+/// to 'circulation-input.lgf'
+///
+/// \include circulation_demo.cc
+
+#include <iostream>
+
+#include <lemon/list_graph.h>
+#include <lemon/circulation.h>
+#include <lemon/graph_reader.h>
+#include <lemon/graph_writer.h>
+
+using namespace lemon;
+
+
+int main (int, char*[])
+{
+
+    typedef ListGraph Graph;
+    typedef Graph::Node Node;
+    typedef Graph::NodeIt NodeIt;
+    typedef Graph::Edge Edge;
+    typedef Graph::EdgeIt EdgeIt;
+    typedef Graph::EdgeMap<int> EdgeMap;
+    typedef Graph::NodeMap<int> NodeMap;
+    typedef Graph::NodeMap<double> DNodeMap;
+
+    Graph g;
+    EdgeMap lo(g);
+    EdgeMap up(g);
+    EdgeMap x(g);
+    NodeMap delta(g);
+    NodeMap nid(g);
+    EdgeMap eid(g);
+    DNodeMap cx(g);
+    DNodeMap cy(g);
+    
+    GraphReader<Graph>("circulation-input.lgf", g).
+      readEdgeMap("lo_cap", lo).
+      readEdgeMap("up_cap", up).
+      readNodeMap("delta", delta).
+      readEdgeMap("label", eid).
+      readNodeMap("label", nid).
+      readNodeMap("coordinates_x", cx).
+      readNodeMap("coordinates_y", cy).
+      run();
+
+    Circulation<Graph,int> gen(g,lo,up,delta,x);
+    int ret=gen.run();
+    if(ret==-1)
+      {
+	std::cout << "\nA feasible flow has been found.\n";
+	if(!gen.checkX(x)) std::cerr << "Oops!!!\n";
+	GraphWriter<Graph>("circulation-output.lgf", g).
+	  writeEdgeMap("lo_cap", lo).
+	  writeEdgeMap("up_cap", up).
+	  writeEdgeMap("flow", x).
+	  writeNodeMap("delta", delta).
+	  writeEdgeMap("label", eid).
+	  writeNodeMap("label", nid).
+	  writeNodeMap("coordinates_x", cx).
+	  writeNodeMap("coordinates_y", cy).
+	  run();
+      }
+    else {
+      std::cout << "\nThere is no such a flow\n";
+      Graph::NodeMap<int> bar(g);
+      gen.barrier(bar,ret);
+      if(!gen.checkBarrier(bar)) std::cerr << "Dual Oops!!!\n";
+
+      GraphWriter<Graph>("circulation-output.lgf", g).
+	writeEdgeMap("lo_cap", lo).
+	writeEdgeMap("up_cap", up).
+	writeNodeMap("barrier", bar).
+	writeNodeMap("delta", delta).
+	writeEdgeMap("label", eid).
+	writeNodeMap("label", nid).
+	writeNodeMap("coordinates_x", cx).
+	writeNodeMap("coordinates_y", cy).
+	run();
+    }
+  std::cout << "The output is written to file 'circulation-output.lgf'\n\n";
+    
+}
diff -r b59a17034ffa -r e30a0fdad0d7 lemon/Makefile.am
--- a/lemon/Makefile.am	Tue Feb 20 13:01:22 2007 +0000
+++ b/lemon/Makefile.am	Tue Feb 20 15:53:33 2007 +0000
@@ -33,6 +33,7 @@
 endif
 
 lemon_HEADERS += \
+	lemon/circulation.h \
 	lemon/bellman_ford.h \
 	lemon/bfs.h \
 	lemon/bin_heap.h \
diff -r b59a17034ffa -r e30a0fdad0d7 lemon/circulation.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/circulation.h	Tue Feb 20 15:53:33 2007 +0000
@@ -0,0 +1,299 @@
+/* -*- C++ -*-
+ * lemon/preflow_matching.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_CIRCULATION_H
+#define LEMON_CIRCULATION_H
+
+#include <lemon/graph_utils.h>
+#include <iostream>
+#include <queue>
+#include <lemon/tolerance.h>
+#include <lemon/elevator.h>
+
+///\ingroup flowalgs
+///\file
+///\brief Push-prelabel algorithm for finding a feasible circulation.
+///
+namespace lemon {
+
+  ///Preflow algorithm for the Network Circulation Problem.
+  
+  ///\ingroup flowalgs
+  ///This class implements a preflow algorithm
+  ///for the Network Circulation Problem.
+  ///The exact formulation of this problem is the following.
+  /// \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq delta(v)\quad \forall v\in V \f]
+  /// \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f]
+  ///
+  template<class Graph,
+	   class Value,
+	   class FlowMap=typename Graph::template EdgeMap<Value>,
+	   class LCapMap=typename Graph::template EdgeMap<Value>,
+	   class UCapMap=LCapMap,
+	   class DeltaMap=typename Graph::template NodeMap<Value>
+	    >
+  class Circulation {
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+
+    const Graph &_g;
+    int _node_num;
+
+    const LCapMap &_lo;
+    const UCapMap &_up;
+    const DeltaMap &_delta;
+    FlowMap &_x;
+    Tolerance<Value> _tol;
+    Elevator<Graph,typename Graph::Node> _levels;
+    typename Graph::template NodeMap<Value> _excess;
+
+  public:
+    ///\e
+    Circulation(const Graph &g,const LCapMap &lo,const UCapMap &up,
+		const DeltaMap &delta,FlowMap &x) :
+      _g(g),
+      _node_num(countNodes(g)),
+      _lo(lo),_up(up),_delta(delta),_x(x),
+      _levels(g,_node_num),
+      _excess(g)
+    {
+    }
+    
+  private:
+
+    void addExcess(Node n,Value v)
+    {
+      if(_tol.positive(_excess[n]+=v))
+	{
+	  if(!_levels.active(n)) _levels.activate(n);
+	}
+      else if(_levels.active(n)) _levels.deactivate(n);
+    }
+    
+    void init() 
+    {
+     
+      _x=_lo;
+
+      for(NodeIt n(_g);n!=INVALID;++n) _excess[n]=-_delta[n];
+
+      for(EdgeIt e(_g);e!=INVALID;++e)
+	{
+	  _excess[_g.target(e)]+=_x[e];
+	  _excess[_g.source(e)]-=_x[e];
+	}
+     
+      _levels.initStart();
+      for(NodeIt n(_g);n!=INVALID;++n)
+	_levels.initAddItem(n);
+      _levels.initFinish();
+      for(NodeIt n(_g);n!=INVALID;++n)
+	if(_tol.positive(_excess[n]))
+	  _levels.activate(n);
+    }
+
+  public:
+    ///Check if \c x is a feasible circulation
+    template<class FT>
+    bool checkX(FT &x) {
+      for(EdgeIt e(_g);e!=INVALID;++e)
+	if(x[e]<_lo[e]||x[e]>_up[e]) return false;
+      for(NodeIt n(_g);n!=INVALID;++n)
+	{
+	  Value dif=_delta[n];
+	  for(InEdgeIt e(_g,n);e!=INVALID;++e) dif-=x[e];
+	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) dif+=x[e];
+	  if(_tol.negative(dif)) return false;
+	}
+      return true;
+    };
+    ///Check if the default \c x is a feasible circulation
+    bool checkX() { return checkX(_x); }
+
+    ///Chech if \c bar is a real barrier
+
+    ///Chech if \c bar is a real barrier
+    ///\sa barrier()
+    template<class GT>
+    bool checkBarrier(GT &bar) 
+    {
+      Value delta=0;
+      for(NodeIt n(_g);n!=INVALID;++n)
+	if(bar[n])
+	  delta+=_delta[n];
+      for(EdgeIt e(_g);e!=INVALID;++e)
+	{
+	  Node s=_g.source(e);
+	  Node t=_g.target(e);
+	  if(bar[s]&&!bar[t]) delta+=_up[e];
+	  else if(bar[t]&&!bar[s]) delta-=_lo[e];
+	}
+      return _tol.negative(delta);
+    }  
+    ///Chech whether or not the last execution provides a barrier
+
+    ///Chech whether or not the last execution provides a barrier
+    ///\sa barrier()
+    bool checkBarrier() 
+    {
+      typename Graph:: template NodeMap<bool> bar(_g);
+      barrier(bar);
+      return checkBarrier(bar);
+    }
+    ///Run the algorithm
+
+    ///This function runs the algorithm.
+    ///\return This function returns -1 if it found a feasible circulation.
+    /// nonnegative values (including 0) mean that no feasible solution is
+    /// found. In this case the return value means an "empty level".
+    ///
+    ///\sa barrier()
+    int run() 
+    {
+      init();
+      
+#ifdef LEMON_CIRCULATION_DEBUG
+      for(NodeIt n(_g);n!=INVALID;++n)
+	std::cerr<< _levels[n] << ' ';
+      std::cerr << std::endl;
+#endif      
+      Node act;
+      Node bact=INVALID;
+      Node last_activated=INVALID;
+      while((act=_levels.highestActive())!=INVALID) {
+	int actlevel=_levels[act];
+	int tlevel;
+	int mlevel=_node_num;
+	Value exc=_excess[act];
+	Value fc;
+	
+#ifdef LEMON_CIRCULATION_DEBUG
+	for(NodeIt n(_g);n!=INVALID;++n)
+	  std::cerr<< _levels[n] << ' ';
+	std::cerr << std::endl;
+	std::cerr << "Process node " << _g.id(act)
+		  << " on level " << actlevel
+		  << " with excess " << exc
+		  << std::endl;
+#endif
+	for(OutEdgeIt e(_g,act);e!=INVALID; ++e)
+	  if((fc=_up[e]-_x[e])>0)
+	    if((tlevel=_levels[_g.target(e)])<actlevel)
+	      if(fc<=exc) {
+		_x[e]=_up[e];
+		addExcess(_g.target(e),fc);
+		exc-=fc;
+#ifdef LEMON_CIRCULATION_DEBUG
+		std::cerr << "  Push " << fc
+			  << " toward " << _g.id(_g.target(e)) << std::endl;
+#endif
+	      }
+	      else {
+		_x[e]+=exc;
+		addExcess(_g.target(e),exc);
+		//exc=0;
+		_excess[act]=0;
+		_levels.deactivate(act);
+#ifdef LEMON_CIRCULATION_DEBUG
+		std::cerr << "  Push " << exc
+			  << " toward " << _g.id(_g.target(e)) << std::endl;
+		std::cerr << "  Deactivate\n";
+#endif
+		goto next_l;
+	      }
+	    else if(tlevel<mlevel) mlevel=tlevel;
+	
+	for(InEdgeIt e(_g,act);e!=INVALID; ++e)
+	  if((fc=_x[e]-_lo[e])>0)
+	    if((tlevel=_levels[_g.source(e)])<actlevel)
+	      if(fc<=exc) {
+		_x[e]=_lo[e];
+		addExcess(_g.source(e),fc);
+		exc-=fc;
+#ifdef LEMON_CIRCULATION_DEBUG
+		std::cerr << "  Push " << fc
+			  << " toward " << _g.id(_g.source(e)) << std::endl;
+#endif
+	      }
+	      else {
+		_x[e]-=exc;
+		addExcess(_g.source(e),exc);
+		//exc=0;
+		_excess[act]=0;
+		_levels.deactivate(act);
+#ifdef LEMON_CIRCULATION_DEBUG
+		std::cerr << "  Push " << exc
+			  << " toward " << _g.id(_g.source(e)) << std::endl;
+		std::cerr << "  Deactivate\n";
+#endif
+		goto next_l;
+              }
+	    else if(tlevel<mlevel) mlevel=tlevel;
+   
+	_excess[act]=exc;
+	if(!_tol.positive(exc)) _levels.deactivate(act);
+	else if(mlevel==_node_num) {
+	  _levels.liftHighestActiveTo(_node_num);
+#ifdef LEMON_CIRCULATION_DEBUG
+	  std::cerr << "  Lift to level " << _node_num << std::endl;
+#endif
+	  return _levels.onLevel(_node_num-1)==0?_node_num-1:actlevel;
+	}
+	else {
+	  _levels.liftHighestActiveTo(mlevel+1);
+#ifdef LEMON_CIRCULATION_DEBUG
+	  std::cerr << "  Lift to level " << mlevel+1 << std::endl;
+#endif
+	  if(_levels.onLevel(actlevel)==0)
+	    return actlevel;
+	}
+      next_l:
+	;
+      }
+#ifdef LEMON_CIRCULATION_DEBUG
+      std::cerr << "Feasible flow found.\n";
+#endif
+      return -1;
+    }
+    
+    ///Return a barrier
+    
+    ///Barrier is a set \e B of nodes for which
+    /// \f[ \sum_{v\in B}delta(v)<\sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f]
+    ///holds. The existence of a set with this property prooves that a feasible
+    ///flow cannot exists.
+    ///\pre The run() must have been executed, and its return value was -1.
+    ///\sa checkBarrier()
+    ///\sa run()
+    template<class GT>
+    void barrier(GT &bar,int empty_level=-1) 
+    {
+      if(empty_level==-1)
+	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
+      for(NodeIt n(_g);n!=INVALID;++n)
+	bar[n] = _levels[n]>empty_level;
+    }  
+
+  };
+  
+}
+
+#endif