Changeset 615:b6b31b75b522 in lemon-0.x for src/work

Timestamp:

05/11/04 21:50:21 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@800

Message:

docs, max_flow improvments

Location:

src/work

Files:

• Doxyfile (modified) (1 diff)
• jacint/max_flow.h (modified) (53 diffs)
• marci/bfs_dfs.h (modified) (10 diffs)
• marci/bfs_dfs_misc.h (modified) (4 diffs)
• marci/makefile (modified) (1 diff)
• marci/max_bipartite_matching.h (modified) (1 diff)
• marci/max_flow_1.cc (added)

src/work/Doxyfile

@@ -395 +395 @@
                          ../hugo/skeletons \
                          ../test/test_tools.h \
-                         athos/minlengthpaths.h \
                          klao/path.h \
                          jacint/max_flow.h \

src/work/jacint/max_flow.h

@@ -2 +2 @@
 
 /*
-  Heuristics: 
+  Heuristics:
   2 phase
   gap
@@ -9 +9 @@
   runs heuristic 'highest label' for H1*n relabels
   runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
- 
+
   Parameters H0 and H1 are initialized to 20 and 1.
 
   Constructors:
 
-  Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if 
+  Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
   FlowMap is not constant zero, and should be true if it is
 
@@ -23 +23 @@
   Num flowValue() : returns the value of a maximum flow
 
-  void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
+  void minMinCut(CutMap& M) : sets M to the characteristic vector of the
   minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
 
-  void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
+  void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
   maximum min cut. M should be a map of bools initialized to false.
 
-  void minCut(CutMap& M) : sets M to the characteristic vector of 
+  void minCut(CutMap& M) : sets M to the characteristic vector of
   a min cut. M should be a map of bools initialized to false.
 
@@ -36 +36 @@
 #ifndef HUGO_MAX_FLOW_H
 #define HUGO_MAX_FLOW_H
-
-#define H0 20
-#define H1 1
 
 #include <vector>
@@ -51 +48 @@
 
 /// \file
-/// \brief Dimacs file format reader.
+/// \brief Maximum flows.
+/// \ingroup galgs
 
 namespace hugo {
@@ -58 +56 @@
   //  ///\author Marton Makai, Jacint Szabo
   /// A class for computing max flows and related quantities.
-  template <typename Graph, typename Num, 
-            typename CapMap=typename Graph::template EdgeMap<Num>, 
+  /// \ingroup galgs
+  template <typename Graph, typename Num,
+            typename CapMap=typename Graph::template EdgeMap<Num>,
             typename FlowMap=typename Graph::template EdgeMap<Num> >
   class MaxFlow {
-    
+  protected:
     typedef typename Graph::Node Node;
     typedef typename Graph::NodeIt NodeIt;
@@ -75 +74 @@
     Node s;
     Node t;
-    const CapMap* capacity;  
+    const CapMap* capacity;
     FlowMap* flow;
     int n;      //the number of nodes of G
@@ -84 +83 @@
     typedef typename Graph::template NodeMap<int> ReachedMap;
     ReachedMap level;
-    //level works as a bool map in augmenting path algorithms 
+    //level works as a bool map in augmenting path algorithms
     //and is used by bfs for storing reached information.
     //In preflow, it shows levels of nodes.
-    //typename Graph::template NodeMap<int> level;    
-    typename Graph::template NodeMap<Num> excess; 
+    //typename Graph::template NodeMap<int> level;
+    typename Graph::template NodeMap<Num> excess;
     //   protected:
     //     MaxFlow() { }
-    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
-    //       FlowMap& _flow) 
+    //     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
+    //       FlowMap& _flow)
     //       {
-    //  g=&_G; 
-    //  s=_s; 
-    //  t=_t; 
+    //  g=&_G;
+    //  s=_s;
+    //  t=_t;
     //  capacity=&_capacity;
     //  flow=&_flow;
     //  n=_G.nodeNum;
-    //  level.set (_G); //kellene vmi ilyesmi fv 
+    //  level.set (_G); //kellene vmi ilyesmi fv
     //  excess(_G,0); //itt is
     //       }
 
+    // constants used for heuristics
+    static const int H0=20;
+    static const int H1=1;
+
   public:
- 
+
     ///\todo Document this.
     ///\todo Maybe, it should be PRE_FLOW instead.
+    ///- \c NO_FLOW means nothing,
     ///- \c ZERO_FLOW means something,
     ///- \c GEN_FLOW means something else,
-    ///- \c PREFLOW is something different.
+    ///- \c PRE_FLOW is something different.
     enum flowEnum{
-      ZERO_FLOW=0,
-      GEN_FLOW=1,
-      PREFLOW=2
+      ZERO_FLOW,
+      GEN_FLOW,
+      PRE_FLOW,
+      NO_FLOW
     };
 
-    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
+    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
             FlowMap& _flow) :
-      g(&_G), s(_s), t(_t), capacity(&_capacity), 
+      g(&_G), s(_s), t(_t), capacity(&_capacity),
       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
 
     /// A max flow algorithm is run.
-    ///\pre the flow have to be 0 at the beginning.
-    void run() {
-      preflow(ZERO_FLOW);
-    }
-    
-    /// A preflow algorithm is run. 
-    ///\pre The initial edge-map have to be a 
+    /// \pre The flow have to satisfy the requirements
+    /// stated in fe.
+    void run(flowEnum fe=ZERO_FLOW) {
+      preflow(fe);
+    }
+
+    /// A preflow algorithm is run.
+    /// \pre The initial edge-map have to be a
     /// zero flow if \c fe is \c ZERO_FLOW,
-    /// a flow if \c fe is \c GEN_FLOW, 
-    /// and a pre-flow it is \c PREFLOW.
+    /// a flow if \c fe is \c GEN_FLOW,
+    /// a pre-flow if fe is \c PRE_FLOW and
+    /// anything if fe is NO_FLOW.
     void preflow(flowEnum fe) {
       preflowPhase0(fe);
@@ -138 +145 @@
     }
 
-    /// Run the first phase of preflow, starting from a 0 flow, from a flow, 
-    /// or from a preflow, according to \c fe.
-    void preflowPhase0( flowEnum fe );
+    /// Run the first phase of preflow, starting from a 0 flow, from a flow,
+    /// or from a preflow, of from undefined value according to \c fe.
+    void preflowPhase0(flowEnum fe);
 
     /// Second phase of preflow.
     void preflowPhase1();
 
-    /// Starting from a flow, this method searches for an augmenting path 
-    /// according to the Edmonds-Karp algorithm 
-    /// and augments the flow on if any. 
+    /// Starting from a flow, this method searches for an augmenting path
+    /// according to the Edmonds-Karp algorithm
+    /// and augments the flow on if any.
     /// The return value shows if the augmentation was succesful.
     bool augmentOnShortestPath();
 
-    /// Starting from a flow, this method searches for an augmenting blockin 
-    /// flow according to Dinits' algorithm and augments the flow on if any. 
-    /// The blocking flow is computed in a physically constructed 
+    /// Starting from a flow, this method searches for an augmenting blocking
+    /// flow according to Dinits' algorithm and augments the flow on if any.
+    /// The blocking flow is computed in a physically constructed
     /// residual graph of type \c Mutablegraph.
     /// The return value show sif the augmentation was succesful.
     template<typename MutableGraph> bool augmentOnBlockingFlow();
 
-    /// The same as \c augmentOnBlockingFlow<MutableGraph> but the 
+    /// The same as \c augmentOnBlockingFlow<MutableGraph> but the
     /// residual graph is not constructed physically.
     /// The return value shows if the augmentation was succesful.
@@ -164 +171 @@
 
     /// Returns the actual flow value.
-    /// More precisely, it returns the negative excess of s, thus 
+    /// More precisely, it returns the negative excess of s, thus
     /// this works also for preflows.
-    Num flowValue() { 
+    Num flowValue() {
       Num a=0;
-      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, s) a+=(*flow)[e];
-      FOR_EACH_INC_LOC(InEdgeIt, e, *g, s) a-=(*flow)[e];
+      FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
+      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
       return a;
     }
 
     /// Should be used between preflowPhase0 and preflowPhase1.
-    ///\todo We have to make some status variable which shows the actual state 
-    /// of the class. This enables us to determine which methods are valid 
+    /// \todo We have to make some status variable which shows the
+    /// actual state
+    /// of the class. This enables us to determine which methods are valid
     /// for MinCut computation
     template<typename _CutMap>
@@ -189 +197 @@
     }
 
-    /// The unique inclusionwise minimum cut is computed by 
+    /// The unique inclusionwise minimum cut is computed by
     /// processing a bfs from s in the residual graph.
-    ///\pre flow have to be a max flow otherwise it will the whole node-set.
+    /// \pre flow have to be a max flow otherwise it will the whole node-set.
     template<typename _CutMap>
     void minMinCut(_CutMap& M) {
-    
+
       std::queue<Node> queue;
-      
-      M.set(s,true);      
+
+      M.set(s,true);
       queue.push(s);
 
@@ -211 +219 @@
             M.set(v, true);
           }
-        } 
+        }
 
         InEdgeIt f;
@@ -220 +228 @@
             M.set(v, true);
           }
-        } 
-      }
-    }
-
-
-    /// The unique inclusionwise maximum cut is computed by 
+        }
+      }
+    }
+
+
+    /// The unique inclusionwise maximum cut is computed by
     /// processing a reverse bfs from t in the residual graph.
-    ///\pre flow have to be a max flow otherwise it will be empty.
+    /// \pre flow have to be a max flow otherwise it will be empty.
     template<typename _CutMap>
     void maxMinCut(_CutMap& M) {
@@ -237 +245 @@
 
       std::queue<Node> queue;
-      
-      M.set(t,false);        
+
+      M.set(t,false);
       queue.push(t);
 
@@ -244 +252 @@
         Node w=queue.front();
         queue.pop();
-
 
         InEdgeIt e;
@@ -254 +261 @@
           }
         }
-        
+
         OutEdgeIt f;
         for(g->first(f,w) ; g->valid(f); g->next(f)) {
@@ -275 +282 @@
     ///
     void resetTarget(Node _t) { t=_t; }
-   
+
     /// capacity-map is changed.
     void resetCap(const CapMap& _cap) { capacity=&_cap; }
-    
-    /// flow-map is changed. 
+
+    /// flow-map is changed.
     void resetFlow(FlowMap& _flow) { flow=&_flow; }
 
@@ -286 +293 @@
 
     int push(Node w, VecStack& active) {
-      
+
       int lev=level[w];
       Num exc=excess[w];
       int newlevel=n;       //bound on the next level of w
-          
+
       OutEdgeIt e;
       for(g->first(e,w); g->valid(e); g->next(e)) {
-            
-        if ( (*flow)[e] >= (*capacity)[e] ) continue; 
-        Node v=g->head(e);            
-            
+
+        if ( (*flow)[e] >= (*capacity)[e] ) continue;
+        Node v=g->head(e);
+
         if( lev > level[v] ) { //Push is allowed now
-          
+
           if ( excess[v]<=0 && v!=t && v!=s ) {
             int lev_v=level[v];
             active[lev_v].push(v);
           }
-          
+
           Num cap=(*capacity)[e];
           Num flo=(*flow)[e];
           Num remcap=cap-flo;
-          
+
           if ( remcap >= exc ) { //A nonsaturating push.
-            
+
             flow->set(e, flo+exc);
             excess.set(v, excess[v]+exc);
             exc=0;
-            break; 
-            
+            break;
+
           } else { //A saturating push.
             flow->set(e, cap);
@@ -321 +328 @@
           }
         } else if ( newlevel > level[v] ) newlevel = level[v];
-      } //for out edges wv 
-      
-      if ( exc > 0 ) {  
+      } //for out edges wv
+
+      if ( exc > 0 ) {
         InEdgeIt e;
         for(g->first(e,w); g->valid(e); g->next(e)) {
-          
-          if( (*flow)[e] <= 0 ) continue; 
-          Node v=g->tail(e); 
-          
+
+          if( (*flow)[e] <= 0 ) continue;
+          Node v=g->tail(e);
+
           if( lev > level[v] ) { //Push is allowed now
-            
+
             if ( excess[v]<=0 && v!=t && v!=s ) {
               int lev_v=level[v];
               active[lev_v].push(v);
             }
-            
+
             Num flo=(*flow)[e];
-            
+
             if ( flo >= exc ) { //A nonsaturating push.
-              
+
               flow->set(e, flo-exc);
               excess.set(v, excess[v]+exc);
               exc=0;
-              break; 
+              break;
             } else {  //A saturating push.
-              
+
               excess.set(v, excess[v]+flo);
               exc-=flo;
               flow->set(e,0);
-            }  
+            }
           } else if ( newlevel > level[v] ) newlevel = level[v];
         } //for in edges vw
-        
+
       } // if w still has excess after the out edge for cycle
-      
+
       excess.set(w, exc);
-      
+
       return newlevel;
     }
 
 
-    void preflowPreproc ( flowEnum fe, VecStack& active, 
-                          VecNode& level_list, NNMap& left, NNMap& right ) 
+    void preflowPreproc(flowEnum fe, VecStack& active,
+                        VecNode& level_list, NNMap& left, NNMap& right)
     {
-
       std::queue<Node> bfs_queue;
-      
-      switch ( fe ) {
-      case ZERO_FLOW: 
+
+      switch (fe) {
+      case ZERO_FLOW:
         {
           //Reverse_bfs from t, to find the starting level.
           level.set(t,0);
           bfs_queue.push(t);
-        
+
           while (!bfs_queue.empty()) {
-            
-            Node v=bfs_queue.front();   
+
+            Node v=bfs_queue.front();
             bfs_queue.pop();
             int l=level[v]+1;
-            
+
             InEdgeIt e;
             for(g->first(e,v); g->valid(e); g->next(e)) {
@@ -394 +400 @@
             }
           }
-          
+
           //the starting flow
           OutEdgeIt e;
-          for(g->first(e,s); g->valid(e); g->next(e)) 
+          for(g->first(e,s); g->valid(e); g->next(e))
             {
               Num c=(*capacity)[e];
               if ( c <= 0 ) continue;
               Node w=g->head(e);
-              if ( level[w] < n ) {       
+              if ( level[w] < n ) {
                 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-                flow->set(e, c); 
+                flow->set(e, c);
                 excess.set(w, excess[w]+c);
               }
@@ -410 +416 @@
           break;
         }
-        
+
       case GEN_FLOW:
-      case PREFLOW:
+      case PRE_FLOW:
         {
-          //Reverse_bfs from t in the residual graph, 
+          //Reverse_bfs from t in the residual graph,
           //to find the starting level.
           level.set(t,0);
           bfs_queue.push(t);
-          
+
           while (!bfs_queue.empty()) {
-            
-            Node v=bfs_queue.front();   
+
+            Node v=bfs_queue.front();
             bfs_queue.pop();
             int l=level[v]+1;
-            
+
             InEdgeIt e;
             for(g->first(e,v); g->valid(e); g->next(e)) {
@@ -438 +444 @@
               }
             }
-            
+
             OutEdgeIt f;
             for(g->first(f,v); g->valid(f); g->next(f)) {
@@ -453 +459 @@
             }
           }
-          
-          
+
+
           //the starting flow
           OutEdgeIt e;
-          for(g->first(e,s); g->valid(e); g->next(e)) 
+          for(g->first(e,s); g->valid(e); g->next(e))
             {
               Num rem=(*capacity)[e]-(*flow)[e];
               if ( rem <= 0 ) continue;
               Node w=g->head(e);
-              if ( level[w] < n ) {       
+              if ( level[w] < n ) {
                 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
-                flow->set(e, (*capacity)[e]); 
+                flow->set(e, (*capacity)[e]);
                 excess.set(w, excess[w]+rem);
               }
             }
-          
+
           InEdgeIt f;
-          for(g->first(f,s); g->valid(f); g->next(f)) 
+          for(g->first(f,s); g->valid(f); g->next(f))
             {
               if ( (*flow)[f] <= 0 ) continue;
               Node w=g->tail(f);
-              if ( level[w] < n ) {       
+              if ( level[w] < n ) {
                 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
                 excess.set(w, excess[w]+(*flow)[f]);
-                flow->set(f, 0); 
+                flow->set(f, 0);
               }
-            }  
+            }
           break;
-        } //case PREFLOW
+        } //case PRE_FLOW
       }
     } //preflowPreproc
@@ -487 +493 @@
 
 
-    void relabel(Node w, int newlevel, VecStack& active,  
-                 VecNode& level_list, NNMap& left, 
-                 NNMap& right, int& b, int& k, bool what_heur ) 
+    void relabel(Node w, int newlevel, VecStack& active,
+                 VecNode& level_list, NNMap& left,
+                 NNMap& right, int& b, int& k, bool what_heur )
     {
 
-      Num lev=level[w]; 
-      
+      Num lev=level[w];
+
       Node right_n=right[w];
       Node left_n=left[w];
-      
+
       //unlacing starts
       if ( g->valid(right_n) ) {
@@ -503 +509 @@
           left.set(right_n, left_n);
         } else {
-          level_list[lev]=right_n;   
+          level_list[lev]=right_n;
           left.set(right_n, INVALID);
-        } 
+        }
       } else {
         if ( g->valid(left_n) ) {
           right.set(left_n, INVALID);
-        } else { 
-          level_list[lev]=INVALID;   
-        } 
-      } 
+        } else {
+          level_list[lev]=INVALID;
+        }
+      }
       //unlacing ends
-                
+
       if ( !g->valid(level_list[lev]) ) {
-              
+
         //gapping starts
         for (int i=lev; i!=k ; ) {
@@ -529 +535 @@
               active[i].pop();    //FIXME: ezt szebben kene
             }
-          }          
-        }
-        
+          }
+        }
+
         level.set(w,n);
         b=lev-1;
         k=b;
         //gapping ends
-        
+
       } else {
-        
-        if ( newlevel == n ) level.set(w,n); 
+
+        if ( newlevel == n ) level.set(w,n);
         else {
           level.set(w,++newlevel);
@@ -552 +558 @@
         }
       }
-      
+
     } //relabel
 
 
-    template<typename MapGraphWrapper> 
+    template<typename MapGraphWrapper>
     class DistanceMap {
     protected:
       const MapGraphWrapper* g;
-      typename MapGraphWrapper::template NodeMap<int> dist; 
+      typename MapGraphWrapper::template NodeMap<int> dist;
     public:
       DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
-      void set(const typename MapGraphWrapper::Node& n, int a) { 
-        dist.set(n, a); 
-      }
-      int operator[](const typename MapGraphWrapper::Node& n) 
+      void set(const typename MapGraphWrapper::Node& n, int a) {
+        dist.set(n, a);
+      }
+      int operator[](const typename MapGraphWrapper::Node& n)
       { return dist[n]; }
-      //       int get(const typename MapGraphWrapper::Node& n) const { 
+      //       int get(const typename MapGraphWrapper::Node& n) const {
       //        return dist[n]; }
-      //       bool get(const typename MapGraphWrapper::Edge& e) const { 
+      //       bool get(const typename MapGraphWrapper::Edge& e) const {
       //        return (dist.get(g->tail(e))<dist.get(g->head(e))); }
-      bool operator[](const typename MapGraphWrapper::Edge& e) const { 
-        return (dist[g->tail(e)]<dist[g->head(e)]); 
+      bool operator[](const typename MapGraphWrapper::Edge& e) const {
+        return (dist[g->tail(e)]<dist[g->head(e)]);
       }
     };
-    
+
   };
 
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
   {
-      
-    int heur0=(int)(H0*n);  //time while running 'bound decrease' 
+
+    int heur0=(int)(H0*n);  //time while running 'bound decrease'
     int heur1=(int)(H1*n);  //time while running 'highest label'
     int heur=heur1;         //starting time interval (#of relabels)
     int numrelabel=0;
-     
-    bool what_heur=1;       
+
+    bool what_heur=1;
     //It is 0 in case 'bound decrease' and 1 in case 'highest label'
 
-    bool end=false;     
-    //Needed for 'bound decrease', true means no active nodes are above bound b.
+    bool end=false;
+    //Needed for 'bound decrease', true means no active nodes are above bound
+    //b.
 
     int k=n-2;  //bound on the highest level under n containing a node
     int b=k;    //bound on the highest level under n of an active node
-      
+
     VecStack active(n);
-      
+
     NNMap left(*g, INVALID);
     NNMap right(*g, INVALID);
@@ -608 +615 @@
     for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
     //setting each node to level n
-      
-    switch ( fe ) {
-    case PREFLOW:
+
+    switch (fe) {
+    case PRE_FLOW:
       {
-        //counting the excess
+        //computing the excess
         NodeIt v;
         for(g->first(v); g->valid(v); g->next(v)) {
           Num exc=0;
-          
+
           InEdgeIt e;
           for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
           OutEdgeIt f;
           for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
-            
-          excess.set(v,exc);      
-            
+
+          excess.set(v,exc);
+
           //putting the active nodes into the stack
           int lev=level[v];
@@ -632 +639 @@
     case GEN_FLOW:
       {
-        //Counting the excess of t
+        //computing the excess of t
         Num exc=0;
-          
+
         InEdgeIt e;
         for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
         OutEdgeIt f;
         for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
-          
-        excess.set(t,exc);      
-          
+
+        excess.set(t,exc);
+
         break;
       }
-    default:
-      break;
-    }
-      
-    preflowPreproc( fe, active, level_list, left, right );
-    //End of preprocessing 
-      
-      
+    default:;
+    }
+
+    preflowPreproc(fe, active, level_list, left, right);
+    //End of preprocessing
+
+
     //Push/relabel on the highest level active nodes.
     while ( true ) {
@@ -660 +666 @@
         } else break;
       }
-        
-      if ( active[b].empty() ) --b; 
+
+      if ( active[b].empty() ) --b;
       else {
-        end=false;  
+        end=false;
         Node w=active[b].top();
         active[b].pop();
         int newlevel=push(w,active);
-        if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 
+        if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
                                      left, right, b, k, what_heur);
-          
-        ++numrelabel; 
+
+        ++numrelabel;
         if ( numrelabel >= heur ) {
           numrelabel=0;
@@ -680 +686 @@
             what_heur=1;
             heur=heur1;
-            b=k; 
-          }
-        }
-      } 
-    } 
+            b=k;
+          }
+        }
+      }
+    }
   }
 
@@ -690 +696 @@
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
+  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
   {
-      
+
     int k=n-2;  //bound on the highest level under n containing a node
     int b=k;    //bound on the highest level under n of an active node
-      
+
     VecStack active(n);
     level.set(s,0);
     std::queue<Node> bfs_queue;
     bfs_queue.push(s);
-            
+
     while (!bfs_queue.empty()) {
-        
-      Node v=bfs_queue.front(); 
+
+      Node v=bfs_queue.front();
       bfs_queue.pop();
       int l=level[v]+1;
-              
+
       InEdgeIt e;
       for(g->first(e,v); g->valid(e); g->next(e)) {
         if ( (*capacity)[e] <= (*flow)[e] ) continue;
         Node u=g->tail(e);
-        if ( level[u] >= n ) { 
+        if ( level[u] >= n ) {
           bfs_queue.push(u);
           level.set(u, l);
@@ -717 +723 @@
         }
       }
-        
+
       OutEdgeIt f;
       for(g->first(f,v); g->valid(f); g->next(f)) {
         if ( 0 >= (*flow)[f] ) continue;
         Node u=g->head(f);
-        if ( level[u] >= n ) { 
+        if ( level[u] >= n ) {
           bfs_queue.push(u);
           level.set(u, l);
@@ -732 +738 @@
 
     while ( true ) {
-        
+
       if ( b == 0 ) break;
 
-      if ( active[b].empty() ) --b; 
+      if ( active[b].empty() ) --b;
       else {
         Node w=active[b].top();
         active[b].pop();
-        int newlevel=push(w,active);      
+        int newlevel=push(w,active);
 
         //relabel
@@ -754 +760 @@
 
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
   {
     ResGW res_graph(*g, *capacity, *flow);
     bool _augment=false;
-      
+
     //ReachedMap level(res_graph);
     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     bfs.pushAndSetReached(s);
-        
-    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 
+
+    typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
     pred.set(s, INVALID);
-      
+
     typename ResGW::template NodeMap<Num> free(res_graph);
-        
+
     //searching for augmenting path
-    while ( !bfs.finished() ) { 
+    while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
@@ -779 +785 @@
           free.set(w, std::min(free[v], res_graph.resCap(e)));
         } else {
-          free.set(w, res_graph.resCap(e)); 
+          free.set(w, res_graph.resCap(e));
         }
         if (res_graph.head(e)==t) { _augment=true; break; }
       }
-        
+
       ++bfs;
     } //end of searching augmenting path
@@ -790 +796 @@
       Node n=t;
       Num augment_value=free[t];
-      while (res_graph.valid(pred[n])) { 
+      while (res_graph.valid(pred[n])) {
         ResGWEdge e=pred[n];
-        res_graph.augment(e, augment_value); 
+        res_graph.augment(e, augment_value);
         n=res_graph.tail(e);
       }
@@ -806 +812 @@
 
 
-
-
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  template<typename MutableGraph> 
-  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow() 
-  {      
+  template<typename MutableGraph>
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
+  {
     typedef MutableGraph MG;
     bool _augment=false;
@@ -822 +826 @@
     BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     bfs.pushAndSetReached(s);
-    typename ResGW::template NodeMap<int> 
+    typename ResGW::template NodeMap<int>
       dist(res_graph); //filled up with 0's
 
@@ -828 +832 @@
     //with the set of edges which are on shortest paths
     MG F;
-    typename ResGW::template NodeMap<typename MG::Node> 
+    typename ResGW::template NodeMap<typename MG::Node>
       res_graph_to_F(res_graph);
     {
@@ -842 +846 @@
     typename MG::template EdgeMap<Num> residual_capacity(F);
 
-    while ( !bfs.finished() ) { 
+    while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
       if (res_graph.valid(e)) {
         if (bfs.isBNodeNewlyReached()) {
           dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
-          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
+          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
+                                        res_graph_to_F[res_graph.head(e)]);
           original_edge.update();
           original_edge.set(f, e);
@@ -854 +859 @@
         } else {
           if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
-            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
+            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
+                                          res_graph_to_F[res_graph.head(e)]);
             original_edge.update();
             original_edge.set(f, e);
@@ -877 +883 @@
       typename MG::template NodeMap<Num> free(F);
 
-      dfs.pushAndSetReached(sF);      
+      dfs.pushAndSetReached(sF);
       while (!dfs.finished()) {
         ++dfs;
@@ -888 +894 @@
               free.set(w, std::min(free[v], residual_capacity[dfs]));
             } else {
-              free.set(w, residual_capacity[dfs]); 
-            }
-            if (w==tF) { 
-              __augment=true; 
+              free.set(w, residual_capacity[dfs]);
+            }
+            if (w==tF) {
+              __augment=true;
               _augment=true;
-              break; 
-            }
-              
+              break;
+            }
+
           } else {
             F.erase(/*typename MG::OutEdgeIt*/(dfs));
           }
-        } 
+        }
       }
 
@@ -905 +911 @@
         typename MG::Node n=tF;
         Num augment_value=free[tF];
-        while (F.valid(pred[n])) { 
+        while (F.valid(pred[n])) {
           typename MG::Edge e=pred[n];
-          res_graph.augment(original_edge[e], augment_value); 
+          res_graph.augment(original_edge[e], augment_value);
           n=F.tail(e);
-          if (residual_capacity[e]==augment_value) 
-            F.erase(e); 
-          else 
+          if (residual_capacity[e]==augment_value)
+            F.erase(e);
+          else
             residual_capacity.set(e, residual_capacity[e]-augment_value);
         }
       }
-        
-    }
-            
+
+    }
+
     return _augment;
   }
@@ -924 +930 @@
 
 
-
-
   template <typename Graph, typename Num, typename CapMap, typename FlowMap>
-  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() 
+  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
   {
     bool _augment=false;
 
     ResGW res_graph(*g, *capacity, *flow);
-      
+
     //ReachedMap level(res_graph);
     FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
@@ -939 +943 @@
     bfs.pushAndSetReached(s);
     DistanceMap<ResGW> dist(res_graph);
-    while ( !bfs.finished() ) { 
+    while ( !bfs.finished() ) {
       ResGWOutEdgeIt e=bfs;
       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
@@ -949 +953 @@
       //Subgraph containing the edges on some shortest paths
     ConstMap<typename ResGW::Node, bool> true_map(true);
-    typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>, 
+    typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
       DistanceMap<ResGW> > FilterResGW;
     FilterResGW filter_res_graph(res_graph, true_map, dist);
 
-    //Subgraph, which is able to delete edges which are already 
+    //Subgraph, which is able to delete edges which are already
     //met by the dfs
-    typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt> 
+    typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
       first_out_edges(filter_res_graph);
     typename FilterResGW::NodeIt v;
-    for(filter_res_graph.first(v); filter_res_graph.valid(v); 
-        filter_res_graph.next(v)) 
+    for(filter_res_graph.first(v); filter_res_graph.valid(v);
+        filter_res_graph.next(v))
       {
         typename FilterResGW::OutEdgeIt e;
@@ -975 +979 @@
       __augment=false;
       //computing blocking flow with dfs
-      DfsIterator< ErasingResGW, 
-        typename ErasingResGW::template NodeMap<bool> > 
+      DfsIterator< ErasingResGW,
+        typename ErasingResGW::template NodeMap<bool> >
         dfs(erasing_res_graph);
       typename ErasingResGW::
-        template NodeMap<typename ErasingResGW::OutEdgeIt> 
-        pred(erasing_res_graph); 
+        template NodeMap<typename ErasingResGW::OutEdgeIt>
+        pred(erasing_res_graph);
       pred.set(s, INVALID);
       //invalid iterators for sources
 
-      typename ErasingResGW::template NodeMap<Num> 
+      typename ErasingResGW::template NodeMap<Num>
         free1(erasing_res_graph);
 
-      dfs.pushAndSetReached(
-                            typename ErasingResGW::Node(
-                                                        typename FilterResGW::Node(
-                                                                                   typename ResGW::Node(s)
-                                                                                   )
-                                                        )
-                            );
+      dfs.pushAndSetReached
+        ///\bug hugo 0.2
+        (typename ErasingResGW::Node
+         (typename FilterResGW::Node
+          (typename ResGW::Node(s)
+           )
+          )
+         );
       while (!dfs.finished()) {
         ++dfs;
-        if (erasing_res_graph.valid(
-                                    typename ErasingResGW::OutEdgeIt(dfs))) 
-          { 
+        if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
+          {
             if (dfs.isBNodeNewlyReached()) {
-          
+
               typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
               typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
@@ -1006 +1010 @@
               pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
               if (erasing_res_graph.valid(pred[v])) {
-                free1.set(w, std::min(free1[v], res_graph.resCap(
-                                                                 typename ErasingResGW::OutEdgeIt(dfs))));
+                free1.set
+                  (w, std::min(free1[v], res_graph.resCap
+                               (typename ErasingResGW::OutEdgeIt(dfs))));
               } else {
-                free1.set(w, res_graph.resCap(
-                                              typename ErasingResGW::OutEdgeIt(dfs))); 
+                free1.set
+                  (w, res_graph.resCap
+                   (typename ErasingResGW::OutEdgeIt(dfs)));
               }
-              
-              if (w==t) { 
-                __augment=true; 
+
+              if (w==t) {
+                __augment=true;
                 _augment=true;
-                break; 
+                break;
               }
             } else {
@@ -1022 +1028 @@
             }
           }
-      } 
+      }
 
       if (__augment) {
-        typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
+        typename ErasingResGW::Node
+          n=typename FilterResGW::Node(typename ResGW::Node(t));
         //        typename ResGW::NodeMap<Num> a(res_graph);
         //        typename ResGW::Node b;
@@ -1036 +1043 @@
         //        Num j2=a2[b2];
         Num augment_value=free1[n];
-        while (erasing_res_graph.valid(pred[n])) { 
+        while (erasing_res_graph.valid(pred[n])) {
           typename ErasingResGW::OutEdgeIt e=pred[n];
           res_graph.augment(e, augment_value);
@@ -1044 +1051 @@
         }
       }
-      
-    } //while (__augment) 
-            
+
+    } //while (__augment)
+
     return _augment;
   }
 
 
-
-
 } //namespace hugo
 

src/work/marci/bfs_dfs.h

@@ -3 +3 @@
 #define HUGO_BFS_DFS_H
 
-// ///\ingroup gwrappers
-///\file
-///\brief Bfs and dfs iterators.
+/// \ingroup galgs
+/// \file
+/// \brief Bfs and dfs iterators.
 ///
-///This file contains bfs and dfs iterator classes.
+/// This file contains bfs and dfs iterator classes.
 ///
-// ///\author Marton Makai
+// /// \author Marton Makai
 
 #include <queue>
@@ -22 +22 @@
   /// \c reached_map
   /// Reached have to work as read-write bool Node-map.
+  /// \ingroup galgs
   template <typename Graph, /*typename OutEdgeIt,*/ 
             typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
@@ -106 +107 @@
       return *this;
     }
-    ///
+    /// Guess what?
     bool finished() const { return bfs_queue.empty(); }
     /// The conversion operator makes for converting the bfs-iterator 
@@ -112 +113 @@
     ///\bug Edge have to be in HUGO 0.2
     operator OutEdgeIt() const { return actual_edge; }
-    ///
+    /// Guess what?
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    ///
+    /// Guess what?
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    ///
+    /// Guess what?
     Node aNode() const { return bfs_queue.front(); }
-    ///
+    /// Guess what?
     Node bNode() const { return graph->bNode(actual_edge); }
-    ///
+    /// Guess what?
     const ReachedMap& getReachedMap() const { return reached; }
-    ///
+    /// Guess what?
     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
-  };  
+  };
 
   /// Bfs searches for the nodes wich are not marked in 
@@ -130 +131 @@
   /// Reached have to work as a read-write bool Node-map, 
   /// Pred is a write Edge Node-map and
-  /// Dist is a read-write int Node-map, have to be. 
-  ///\todo In fact onsly simple operations requirement are needed for 
-  /// Dist::Value.
+  /// Dist is a read-write Node-map of integral value, have to be. 
+  /// \ingroup galgs
   template <typename Graph, 
             typename ReachedMap=typename Graph::template NodeMap<bool>, 
@@ -179 +179 @@
       return *this;
     }
-    ///
+    /// Guess what?
     const PredMap& getPredMap() const { return pred; }
-    ///
+    /// Guess what?
     const DistMap& getDistMap() const { return dist; }
   };
@@ -188 +188 @@
   /// \c reached_map
   /// Reached have to be a read-write bool Node-map.
+  /// \ingroup galgs
   template <typename Graph, /*typename OutEdgeIt,*/ 
             typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
@@ -249 +250 @@
       return *this;
     }
-    ///
+    /// Guess what?
     bool finished() const { return dfs_stack.empty(); }
-    ///
+    /// Guess what?
     operator OutEdgeIt() const { return actual_edge; }
-    ///
+    /// Guess what?
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    ///
+    /// Guess what?
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    ///
+    /// Guess what?
     Node aNode() const { return actual_node; /*FIXME*/}
-    ///
+    /// Guess what?
     Node bNode() const { return graph->bNode(actual_edge); }
-    ///
+    /// Guess what?
     const ReachedMap& getReachedMap() const { return reached; }
-    ///
+    /// Guess what?
     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   };
@@ -271 +272 @@
   /// Reached is a read-write bool Node-map, 
   /// Pred is a write Node-map, have to be.
+  /// \ingroup galgs
   template <typename Graph, 
             typename ReachedMap=typename Graph::template NodeMap<bool>, 
@@ -313 +315 @@
       return *this;
     }
-    ///
+    /// Guess what?
     const PredMap& getPredMap() const { return pred; }
   };

src/work/marci/bfs_dfs_misc.h

@@ -3 +3 @@
 #define HUGO_BFS_DFS_MISC_H
 
-// ///\ingroup gwrappers
-///\file
-///\brief Miscellaneous algorithms using bfs and dfs.
+/// \ingroup galgs
+/// \file
+/// \brief Miscellaneous algorithms using bfs and dfs.
 ///
-///This file contains several algorithms using bfs and dfs.
+/// This file contains several algorithms using bfs and dfs.
 ///
 // ///\author Marton Makai
@@ -16 +16 @@
 namespace hugo {
 
-  /// This function eat a read-write \c BoolMap& bool_map, 
+  /// This function eats a read-write \c BoolMap& bool_map, 
   /// which have to work well up 
   /// to its \c set and \c operator[]() method. Thus we have to deal 
   /// very carefully with an uninitialized \c IterableBoolMap.
+  /// \ingroup galgs
   template<typename Graph, typename BoolMap> 
   bool isBipartite(const Graph& g, BoolMap& bool_map) {
@@ -53 +54 @@
   /// then going back from the returned node via the pred information, a 
   /// cycle is obtained.
+  /// \ingroup galgs
   template<typename Graph, typename PredMap> 
   typename Graph::Node 
@@ -90 +92 @@
     return INVALID;
   }
+
 } //namespace hugo
 

src/work/marci/makefile

@@ -5 +5 @@
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test
+BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
 

src/work/marci/max_bipartite_matching.h

@@ -2 +2 @@
 #ifndef HUGO_MAX_BIPARTITE_MATCHING_H
 #define HUGO_MAX_BIPARTITE_MATCHING_H
+
+/// \ingroup galgs
+/// \file
+/// \brief Maximum bipartite matchings, b-matchings and 
+/// capacitated b-matchings.
+///
+/// This file contains a class for bipartite maximum matching, b-matchings 
+/// and capacitated b-matching computations.
+///
+// /// \author Marton Makai
 
 //#include <for_each_macros.h>