Changeset 64:72bd463289a9 in lemon-0.x for src/work

Timestamp:

02/05/04 16:06:45 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work

Files:

• bfs_iterator.hh (modified) (3 diffs)
• edmonds_karp.hh (modified) (8 diffs)
• list_graph.hh (modified) (12 diffs)

src/work/bfs_iterator.hh

@@ -406 +406 @@
   public:
     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
-    void pushAndSetReached(const NodeIt s) { 
+    void pushAndSetReached(NodeIt s) { 
       reached.set(s, true);
       if (bfs_queue.empty()) {
@@ -445 +445 @@
         if (!bfs_queue.empty()) {
           actual_edge=bfs_queue.front();
-        } else {
-          actual_edge=OutEdgeIt();
-        }
-        if (actual_edge.valid()) {
-          NodeIt w=G.bNode(actual_edge);
-          if (!reached.get(w)) {
-            bfs_queue.push(G.template first<OutEdgeIt>(w));
-            reached.set(w, true);
-            b_node_newly_reached=true;
-          } else {
-            b_node_newly_reached=false;
+          if (actual_edge.valid()) {
+            NodeIt w=G.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(G.template first<OutEdgeIt>(w));
+              reached.set(w, true);
+              b_node_newly_reached=true;
+            } else {
+              b_node_newly_reached=false;
+            }
           }
         }
@@ -469 +467 @@
  };
 
-
 } // namespace marci
 

src/work/edmonds_karp.hh

@@ -42 +42 @@
       }
       bool valid() const { return sym.valid(); }
-      void augment(const T a) const {
+      void augment(T a) const {
         if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
           resG->flow.set(sym, resG->flow.get(sym)+a);
@@ -57 +57 @@
       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
     private:
-      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) { 
+      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) { 
         resG=&_resG;
         sym=resG->G.template first<OldSymEdgeIt>(v);
@@ -70 +70 @@
     };
 
-    void getFirst(OutEdgeIt& e, const NodeIt v) const { 
+    void getFirst(OutEdgeIt& e, NodeIt v) const { 
       e=OutEdgeIt(*this, v); 
     }
@@ -83 +83 @@
 
     template< typename It >
-    It first(const NodeIt v) const { 
+    It first(NodeIt v) const { 
       It e;
       getFirst(e, v);
@@ -89 +89 @@
     }
 
-    NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
-    NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }
-
-    NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
-    NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }
-
-    int id(const NodeIt v) const { return G.id(v); }
+    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
+    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
+
+    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
+    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
+
+    int id(NodeIt v) const { return G.id(v); }
 
     template <typename ValueType>
@@ -102 +102 @@
     public:
       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
-      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
-      void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
-      ValueType get(const NodeIt nit) const { return node_map.get(nit); }
+      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { }
+      void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
+      ValueType get(NodeIt nit) const { return node_map.get(nit); }
     };
 
@@ -117 +117 @@
     typedef typename Graph::InEdgeIt InEdgeIt;
     const Graph& G;
-    const NodeIt s;
-    const NodeIt t;
+    NodeIt s;
+    NodeIt t;
     FlowMap& flow;
     const CapacityMap& capacity;
@@ -125 +125 @@
     typedef typename AugGraph::EdgeIt AugEdgeIt;
   public:
-    MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
+    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
     bool augment() {
       AugGraph res_graph(G, flow, capacity);

src/work/list_graph.hh

@@ -41 +41 @@
     public:
       NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
-      NodeMap(const ListGraph& _G, const ValueType a) : 
+      NodeMap(const ListGraph& _G, ValueType a) : 
         G(_G), container(_G.node_id, a) { }
-      void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
-      ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
+      void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; }
+      ValueType get(NodeIt nit) const { return container[G.id(nit)]; }
     };
 
@@ -53 +53 @@
     public:
       EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
-      EdgeMap(const ListGraph& _G, const ValueType a) : 
+      EdgeMap(const ListGraph& _G, ValueType a) : 
         G(_G), container(_G.edge_id, a) { }
-      void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
-      ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
+      void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; }
+      ValueType get(EdgeIt eit) const { return container[G.id(eit)]; }
     };
 
@@ -227 +227 @@
     //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
     //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
-    NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
-    NodeIt head(const EdgeIt e) const { return e.headNode(); }
+    NodeIt tail(EdgeIt e) const { return e.tailNode(); }
+    NodeIt head(EdgeIt e) const { return e.headNode(); }
 
     NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); }
@@ -249 +249 @@
     void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
     void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
-    void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
-    void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
-    void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); }
-    void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
-    void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
-
-    void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
-    void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
-    void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
-    void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
-    void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
-    void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
+    void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); }
+    void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); }
+    void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); }
+    //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
+    //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
+
+    //void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
+    //void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
+    //void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
+    //void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
+    //void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
+    //void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
     //void get_invalid(NodeIt& n) { n=NodeIt(); }
     //void get_invalid(EdgeIt& e) { e=EdgeIt(); }
@@ -275 +275 @@
 
     template< typename It >
-    It first(const NodeIt v) const { 
+    It first(NodeIt v) const { 
       It e;
       getFirst(e, v);
@@ -284 +284 @@
     /* these are important for the implementation of property vectors */
 
-    int id(const NodeIt v) const { return v.node->id; }
-    int id(const EdgeIt e) const { return e.edge->id; }
+    int id(NodeIt v) const { return v.node->id; }
+    int id(EdgeIt e) const { return e.edge->id; }
 
     /* adding nodes and edges */
 
     NodeIt addNode() { return NodeIt(_add_node()); }
-    EdgeIt addEdge(const NodeIt u, const NodeIt v) {
+    EdgeIt addEdge(NodeIt u, NodeIt v) {
       return EdgeIt(_add_edge(u.node, v.node)); 
     }
 
-    void deleteNode(const NodeIt i) { 
+    void deleteNode(NodeIt i) { 
       while (first<OutEdgeIt>(i).valid()) deleteEdge(first<OutEdgeIt>(i));
       while (first<InEdgeIt>(i).valid()) deleteEdge(first<InEdgeIt>(i));
@@ -300 +300 @@
     }
   
-    void deleteEdge(const EdgeIt e) { _delete_edge(e.edge); }
-
-    void setTail(const EdgeIt e, const NodeIt tail) {
+    void deleteEdge(EdgeIt e) { _delete_edge(e.edge); }
+
+    void setTail(EdgeIt e, NodeIt tail) {
       _set_tail(e.edge, tail.node); 
     }
 
-    void setHead(const EdgeIt e, const NodeIt head) {
+    void setHead(EdgeIt e, NodeIt head) {
       _set_head(e.edge, head.node); 
     }
@@ -329 +329 @@
     protected:
       node_item* node;
-      friend int ListGraph::id(const NodeIt v) const; 
+      friend int ListGraph::id(NodeIt v) const; 
     public:
       NodeIt() : node(0) { }
@@ -361 +361 @@
     protected:
       edge_item* edge;
-      friend int ListGraph::id(const EdgeIt e) const;
+      friend int ListGraph::id(EdgeIt e) const;
     public:
       EdgeIt() : edge(0) { }
@@ -407 +407 @@
     public:
       OutEdgeIt() : EdgeIt(), v(0) { }
-      OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
+      OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
     protected:
@@ -422 +422 @@
     public:
       InEdgeIt() : EdgeIt(), v(0) { }
-      InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
+      InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
     protected:
@@ -442 +442 @@
     public:
       SymEdgeIt() : EdgeIt(), v(0) { }
-      SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { 
+      SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { 
         out_or_in=1;
         edge=v->_first_out_edge;