Changeset 768:a5e9303a5511 in lemon-0.x for src/work/marci/max_bipartite_matching.h

Timestamp:

08/23/04 13:06:00 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

stGraphWrapper modifications

File:

• src/work/marci/max_bipartite_matching.h (modified) (3 diffs)

src/work/marci/max_bipartite_matching.h

@@ -60 +60 @@
     //   EdgeFlow* edge_flow;
     //   NodeFlow* node_flow;
-    typedef  stGraphWrapper<Graph> stGW;
+    typedef  stBipartiteGraphWrapper<Graph> stGW;
     stGW stgw;
     typedef typename stGW::template EdgeMapWrapper<EdgeCap, NodeCap> CapMap; 
@@ -67 +67 @@
     typedef typename stGW::template EdgeMapWrapper<EdgeFlow, NodeFlow> FlowMap;
     FlowMap flow;
-    MaxFlow<stGW, int, CapMap, FlowMap> mf;
+    typedef MaxFlow<stGW, int, CapMap, FlowMap> MaxFlow;
+    MaxFlow mf;
     //graph* g;
     //EdgeCap* edge_cap;
     //EdgeFlow* edge_flow;
   public:
+    enum MatchingEnum{
+      ZERO_MATCHING,
+      GEN_MATCHING,
+      GEN_MATCHING_WITH_GOOD_NODE_FLOW,
+      NO_MATCHING
+    };
     /// For capacitated b-matchings, edge-caoacities and node-capacities 
     /// have to be given. After running \c run the matching is is given 
@@ -99 +106 @@
     ~MaxBipartiteMatching() { if (node_flow) delete node_flow; }
     /// run computes the max matching.
-    void run() { mf.run(); } 
+    void run(MatchingEnum me=ZERO_MATCHING) { 
+      switch (me) {
+        case ZERO_MATCHING:
+          mf.run(MaxFlow::ZERO_FLOW);
+          break;
+        case GEN_MATCHING:
+        {
+          typename stGW::OutEdgeIt e;
+          for (stgw.first(e, stgw.S_NODE); stgw.valid(e); stgw.next(e)) 
+            flow.set(e, cap[e]);
+        }
+        {
+          typename stGW::InEdgeIt e;
+          for (stgw.first(e, stgw.T_NODE); stgw.valid(e); stgw.next(e)) 
+            flow.set(e, 0);
+        }
+        mf.run(MaxFlow::PRE_FLOW);
+        break;
+        case GEN_MATCHING_WITH_GOOD_NODE_FLOW:
+          mf.run(MaxFlow::GEN_FLOW);
+          break;
+        case NO_MATCHING:
+          mf.run(MaxFlow::NO_FLOW);
+          break;
+      }
+    } 
     /// The matching value after running \c run.
-    int matchingValue() { return mf.flowValue(); }
+    int matchingValue() const { return mf.flowValue(); }
   };