1.1 --- a/src/work/bfs_iterator.hh Wed Feb 04 18:59:07 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Thu Feb 05 15:06:45 2004 +0000
1.3 @@ -405,7 +405,7 @@
1.4 OutEdgeIt actual_edge;
1.5 public:
1.6 BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
1.7 - void pushAndSetReached(const NodeIt s) {
1.8 + void pushAndSetReached(NodeIt s) {
1.9 reached.set(s, true);
1.10 if (bfs_queue.empty()) {
1.11 bfs_queue.push(G.template first<OutEdgeIt>(s));
1.12 @@ -444,17 +444,15 @@
1.13 bfs_queue.pop();
1.14 if (!bfs_queue.empty()) {
1.15 actual_edge=bfs_queue.front();
1.16 - } else {
1.17 - actual_edge=OutEdgeIt();
1.18 - }
1.19 - if (actual_edge.valid()) {
1.20 - NodeIt w=G.bNode(actual_edge);
1.21 - if (!reached.get(w)) {
1.22 - bfs_queue.push(G.template first<OutEdgeIt>(w));
1.23 - reached.set(w, true);
1.24 - b_node_newly_reached=true;
1.25 - } else {
1.26 - b_node_newly_reached=false;
1.27 + if (actual_edge.valid()) {
1.28 + NodeIt w=G.bNode(actual_edge);
1.29 + if (!reached.get(w)) {
1.30 + bfs_queue.push(G.template first<OutEdgeIt>(w));
1.31 + reached.set(w, true);
1.32 + b_node_newly_reached=true;
1.33 + } else {
1.34 + b_node_newly_reached=false;
1.35 + }
1.36 }
1.37 }
1.38 }
1.39 @@ -468,7 +466,6 @@
1.40 const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
1.41 };
1.42
1.43 -
1.44 } // namespace marci
1.45
1.46 #endif //BFS_ITERATOR_HH
2.1 --- a/src/work/edmonds_karp.hh Wed Feb 04 18:59:07 2004 +0000
2.2 +++ b/src/work/edmonds_karp.hh Thu Feb 05 15:06:45 2004 +0000
2.3 @@ -41,7 +41,7 @@
2.4 }
2.5 }
2.6 bool valid() const { return sym.valid(); }
2.7 - void augment(const T a) const {
2.8 + void augment(T a) const {
2.9 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.10 resG->flow.set(sym, resG->flow.get(sym)+a);
2.11 } else {
2.12 @@ -56,7 +56,7 @@
2.13 OutEdgeIt() { }
2.14 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
2.15 private:
2.16 - OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) {
2.17 + OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
2.18 resG=&_resG;
2.19 sym=resG->G.template first<OldSymEdgeIt>(v);
2.20 while( sym.valid() && !(free()>0) ) { ++sym; }
2.21 @@ -69,7 +69,7 @@
2.22 }
2.23 };
2.24
2.25 - void getFirst(OutEdgeIt& e, const NodeIt v) const {
2.26 + void getFirst(OutEdgeIt& e, NodeIt v) const {
2.27 e=OutEdgeIt(*this, v);
2.28 }
2.29 void getFirst(EachNodeIt& v) const { G.getFirst(v); }
2.30 @@ -82,28 +82,28 @@
2.31 }
2.32
2.33 template< typename It >
2.34 - It first(const NodeIt v) const {
2.35 + It first(NodeIt v) const {
2.36 It e;
2.37 getFirst(e, v);
2.38 return e;
2.39 }
2.40
2.41 - NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); }
2.42 - NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); }
2.43 + NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
2.44 + NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
2.45
2.46 - NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); }
2.47 - NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); }
2.48 + NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
2.49 + NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
2.50
2.51 - int id(const NodeIt v) const { return G.id(v); }
2.52 + int id(NodeIt v) const { return G.id(v); }
2.53
2.54 template <typename ValueType>
2.55 class NodeMap {
2.56 typename Graph::NodeMap<ValueType> node_map;
2.57 public:
2.58 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.59 - NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
2.60 - void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
2.61 - ValueType get(const NodeIt nit) const { return node_map.get(nit); }
2.62 + NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { }
2.63 + void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
2.64 + ValueType get(NodeIt nit) const { return node_map.get(nit); }
2.65 };
2.66
2.67 };
2.68 @@ -116,15 +116,15 @@
2.69 typedef typename Graph::OutEdgeIt OutEdgeIt;
2.70 typedef typename Graph::InEdgeIt InEdgeIt;
2.71 const Graph& G;
2.72 - const NodeIt s;
2.73 - const NodeIt t;
2.74 + NodeIt s;
2.75 + NodeIt t;
2.76 FlowMap& flow;
2.77 const CapacityMap& capacity;
2.78 typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
2.79 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.80 typedef typename AugGraph::EdgeIt AugEdgeIt;
2.81 public:
2.82 - 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) { }
2.83 + MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
2.84 bool augment() {
2.85 AugGraph res_graph(G, flow, capacity);
2.86 bool _augment=false;
3.1 --- a/src/work/list_graph.hh Wed Feb 04 18:59:07 2004 +0000
3.2 +++ b/src/work/list_graph.hh Thu Feb 05 15:06:45 2004 +0000
3.3 @@ -40,10 +40,10 @@
3.4 std::vector<ValueType> container;
3.5 public:
3.6 NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
3.7 - NodeMap(const ListGraph& _G, const ValueType a) :
3.8 + NodeMap(const ListGraph& _G, ValueType a) :
3.9 G(_G), container(_G.node_id, a) { }
3.10 - void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
3.11 - ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
3.12 + void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; }
3.13 + ValueType get(NodeIt nit) const { return container[G.id(nit)]; }
3.14 };
3.15
3.16 template <typename ValueType>
3.17 @@ -52,10 +52,10 @@
3.18 std::vector<ValueType> container;
3.19 public:
3.20 EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
3.21 - EdgeMap(const ListGraph& _G, const ValueType a) :
3.22 + EdgeMap(const ListGraph& _G, ValueType a) :
3.23 G(_G), container(_G.edge_id, a) { }
3.24 - void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
3.25 - ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
3.26 + void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; }
3.27 + ValueType get(EdgeIt eit) const { return container[G.id(eit)]; }
3.28 };
3.29
3.30 int node_id;
3.31 @@ -226,8 +226,8 @@
3.32 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
3.33 //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
3.34 //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
3.35 - NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
3.36 - NodeIt head(const EdgeIt e) const { return e.headNode(); }
3.37 + NodeIt tail(EdgeIt e) const { return e.tailNode(); }
3.38 + NodeIt head(EdgeIt e) const { return e.headNode(); }
3.39
3.40 NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); }
3.41 NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); }
3.42 @@ -248,18 +248,18 @@
3.43
3.44 void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
3.45 void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
3.46 - void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
3.47 - void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
3.48 - void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); }
3.49 - void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
3.50 - void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
3.51 + void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); }
3.52 + void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); }
3.53 + void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); }
3.54 + //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
3.55 + //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
3.56
3.57 - void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
3.58 - void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
3.59 - void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
3.60 - void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
3.61 - void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
3.62 - void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
3.63 + //void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); }
3.64 + //void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); }
3.65 + //void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); }
3.66 + //void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); }
3.67 + //void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); }
3.68 + //void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); }
3.69 //void get_invalid(NodeIt& n) { n=NodeIt(); }
3.70 //void get_invalid(EdgeIt& e) { e=EdgeIt(); }
3.71 //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
3.72 @@ -274,7 +274,7 @@
3.73 }
3.74
3.75 template< typename It >
3.76 - It first(const NodeIt v) const {
3.77 + It first(NodeIt v) const {
3.78 It e;
3.79 getFirst(e, v);
3.80 return e;
3.81 @@ -283,29 +283,29 @@
3.82 /* for getting id's of graph objects */
3.83 /* these are important for the implementation of property vectors */
3.84
3.85 - int id(const NodeIt v) const { return v.node->id; }
3.86 - int id(const EdgeIt e) const { return e.edge->id; }
3.87 + int id(NodeIt v) const { return v.node->id; }
3.88 + int id(EdgeIt e) const { return e.edge->id; }
3.89
3.90 /* adding nodes and edges */
3.91
3.92 NodeIt addNode() { return NodeIt(_add_node()); }
3.93 - EdgeIt addEdge(const NodeIt u, const NodeIt v) {
3.94 + EdgeIt addEdge(NodeIt u, NodeIt v) {
3.95 return EdgeIt(_add_edge(u.node, v.node));
3.96 }
3.97
3.98 - void deleteNode(const NodeIt i) {
3.99 + void deleteNode(NodeIt i) {
3.100 while (first<OutEdgeIt>(i).valid()) deleteEdge(first<OutEdgeIt>(i));
3.101 while (first<InEdgeIt>(i).valid()) deleteEdge(first<InEdgeIt>(i));
3.102 _delete_node(i.node);
3.103 }
3.104
3.105 - void deleteEdge(const EdgeIt e) { _delete_edge(e.edge); }
3.106 + void deleteEdge(EdgeIt e) { _delete_edge(e.edge); }
3.107
3.108 - void setTail(const EdgeIt e, const NodeIt tail) {
3.109 + void setTail(EdgeIt e, NodeIt tail) {
3.110 _set_tail(e.edge, tail.node);
3.111 }
3.112
3.113 - void setHead(const EdgeIt e, const NodeIt head) {
3.114 + void setHead(EdgeIt e, NodeIt head) {
3.115 _set_head(e.edge, head.node);
3.116 }
3.117
3.118 @@ -328,7 +328,7 @@
3.119 friend class SymEdgeIt;
3.120 protected:
3.121 node_item* node;
3.122 - friend int ListGraph::id(const NodeIt v) const;
3.123 + friend int ListGraph::id(NodeIt v) const;
3.124 public:
3.125 NodeIt() : node(0) { }
3.126 NodeIt(node_item* _node) : node(_node) { }
3.127 @@ -360,7 +360,7 @@
3.128 friend class EachNodeIt;
3.129 protected:
3.130 edge_item* edge;
3.131 - friend int ListGraph::id(const EdgeIt e) const;
3.132 + friend int ListGraph::id(EdgeIt e) const;
3.133 public:
3.134 EdgeIt() : edge(0) { }
3.135 //EdgeIt() { }
3.136 @@ -406,7 +406,7 @@
3.137 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
3.138 public:
3.139 OutEdgeIt() : EdgeIt(), v(0) { }
3.140 - OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
3.141 + OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
3.142 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
3.143 protected:
3.144 NodeIt aNode() const { return NodeIt(v); }
3.145 @@ -421,7 +421,7 @@
3.146 InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
3.147 public:
3.148 InEdgeIt() : EdgeIt(), v(0) { }
3.149 - InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
3.150 + InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
3.151 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
3.152 protected:
3.153 NodeIt aNode() const { return NodeIt(v); }
3.154 @@ -441,7 +441,7 @@
3.155 }
3.156 public:
3.157 SymEdgeIt() : EdgeIt(), v(0) { }
3.158 - SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) {
3.159 + SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) {
3.160 out_or_in=1;
3.161 edge=v->_first_out_edge;
3.162 if (!edge) { edge=v->_first_in_edge; out_or_in=0; }