1.1 --- a/src/work/edmonds_karp.hh Wed Feb 04 12:45:32 2004 +0000
1.2 +++ b/src/work/edmonds_karp.hh Wed Feb 04 12:46:33 2004 +0000
1.3 @@ -1,5 +1,5 @@
1.4 -#ifndef MARCI_MAX_FLOW_HH
1.5 -#define MARCI_MAX_FLOW_HH
1.6 +#ifndef EDMONDS_KARP_HH
1.7 +#define EDMONDS_KARP_HH
1.8
1.9 #include <algorithm>
1.10
1.11 @@ -7,17 +7,17 @@
1.12
1.13 namespace marci {
1.14
1.15 - template<typename Graph, typename T>
1.16 + template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
1.17 class ResGraph {
1.18 typedef typename Graph::NodeIt NodeIt;
1.19 typedef typename Graph::EachNodeIt EachNodeIt;
1.20 typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.21 const Graph& G;
1.22 - typename Graph::EdgeMap<T>& flow;
1.23 - const typename Graph::EdgeMap<T>& capacity;
1.24 + FlowMap& flow;
1.25 + const CapacityMap& capacity;
1.26 public:
1.27 - ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow,
1.28 - const typename Graph::EdgeMap<T>& _capacity) :
1.29 + ResGraph(const Graph& _G, FlowMap& _flow,
1.30 + const CapacityMap& _capacity) :
1.31 G(_G), flow(_flow), capacity(_capacity) { }
1.32
1.33 class EdgeIt;
1.34 @@ -26,9 +26,9 @@
1.35 friend class OutEdgeIt;
1.36
1.37 class EdgeIt {
1.38 - friend class ResGraph<Graph, T>;
1.39 + friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
1.40 protected:
1.41 - const ResGraph<Graph, T>* resG;
1.42 + const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
1.43 OldSymEdgeIt sym;
1.44 public:
1.45 EdgeIt() { }
1.46 @@ -51,12 +51,12 @@
1.47 };
1.48
1.49 class OutEdgeIt : public EdgeIt {
1.50 - friend class ResGraph<Graph, T>;
1.51 + friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
1.52 public:
1.53 OutEdgeIt() { }
1.54 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.55 private:
1.56 - OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) {
1.57 + OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) {
1.58 resG=&_resG;
1.59 sym=resG->G.template first<OldSymEdgeIt>(v);
1.60 while( sym.valid() && !(free()>0) ) { ++sym; }
1.61 @@ -98,109 +98,106 @@
1.62
1.63 template <typename ValueType>
1.64 class NodeMap {
1.65 - //const ResGraph<Graph, T>& G;
1.66 typename Graph::NodeMap<ValueType> node_map;
1.67 public:
1.68 - NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
1.69 - NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
1.70 + NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.71 + NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
1.72 void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
1.73 ValueType get(const NodeIt nit) const { return node_map.get(nit); }
1.74 };
1.75
1.76 };
1.77
1.78 - template <typename Graph, typename T>
1.79 - struct max_flow_type {
1.80 + template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
1.81 + class MaxFlow {
1.82 typedef typename Graph::NodeIt NodeIt;
1.83 typedef typename Graph::EdgeIt EdgeIt;
1.84 typedef typename Graph::EachEdgeIt EachEdgeIt;
1.85 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.86 typedef typename Graph::InEdgeIt InEdgeIt;
1.87 const Graph& G;
1.88 - NodeIt s;
1.89 - NodeIt t;
1.90 - typename Graph::EdgeMap<T> flow;
1.91 - const typename Graph::EdgeMap<T>& capacity;
1.92 + const NodeIt s;
1.93 + const NodeIt t;
1.94 + FlowMap& flow;
1.95 + const CapacityMap& capacity;
1.96 + typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
1.97 + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.98 + typedef typename AugGraph::EdgeIt AugEdgeIt;
1.99 + public:
1.100 + 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) { }
1.101 + bool augment() {
1.102 + AugGraph res_graph(G, flow, capacity);
1.103 + bool _augment=false;
1.104 +
1.105 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.106 + BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.107 + res_bfs.pushAndSetReached(s);
1.108 +
1.109 + typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.110 + //filled with invalid iterators
1.111 +
1.112 + typename AugGraph::NodeMap<int> free(res_graph);
1.113 +
1.114 + //searching for augmenting path
1.115 + while ( !res_bfs.finished() ) {
1.116 + //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
1.117 + //while (!bfs_copy.empty()) {
1.118 + // AugOutEdgeIt e=bfs_copy.front();
1.119 + // bfs_copy.pop();
1.120 + // if (e.valid()) {
1.121 + // std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
1.122 + // } else {
1.123 + // std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
1.124 + // }
1.125 + //}
1.126 + //std::cout<<std::endl;
1.127 + AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
1.128 + //if (e.valid()) {
1.129 + // std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
1.130 + //} else {
1.131 + // std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
1.132 + //}
1.133 + if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.134 + NodeIt v=res_graph.tail(e);
1.135 + NodeIt w=res_graph.head(e);
1.136 + //std::cout<<v<<"->"<<w<<std::endl;
1.137 + pred.set(w, e);
1.138 + if (pred.get(v).valid()) {
1.139 + free.set(w, std::min(free.get(v), e.free()));
1.140 + } else {
1.141 + free.set(w, e.free());
1.142 + }
1.143 + if (res_graph.head(e)==t) { _augment=true; break; }
1.144 + }
1.145 +
1.146 + ++res_bfs;
1.147 + } //end of searching augmenting path
1.148
1.149 - max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
1.150 + if (_augment) {
1.151 + NodeIt n=t;
1.152 + T augment_value=free.get(t);
1.153 + //std::cout<<"augmentation: ";
1.154 + while (pred.get(n).valid()) {
1.155 + AugEdgeIt e=pred.get(n);
1.156 + e.augment(augment_value);
1.157 + //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
1.158 + n=res_graph.tail(e);
1.159 + }
1.160 + //std::cout<<std::endl;
1.161 + }
1.162 + //std::cout << "actual flow: "<< std::endl;
1.163 + //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
1.164 + //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.165 + //}
1.166 + //std::cout<<std::endl;
1.167 +
1.168 + return _augment;
1.169 + }
1.170 void run() {
1.171 - typedef ResGraph<Graph, T> AugGraph;
1.172 - AugGraph res_graph(G, flow, capacity);
1.173 -
1.174 - bool augment;
1.175 - do {
1.176 - augment=false;
1.177 -
1.178 - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.179 - typedef typename AugGraph::EdgeIt AugEdgeIt;
1.180 - typedef std::queue<AugOutEdgeIt> BfsQueue;
1.181 - BfsQueue bfs_queue;
1.182 - bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
1.183 -
1.184 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.185 - ReachedMap reached(res_graph, false);
1.186 - reached.set(s, true);
1.187 -
1.188 - bfs_iterator1< AugGraph, ReachedMap >
1.189 - res_bfs(res_graph, bfs_queue, reached);
1.190 -
1.191 - typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
1.192 - PredMap pred(res_graph);
1.193 - //typename AugGraph::EdgeIt a; //invalid
1.194 - //a.makeInvalid();
1.195 - //pred.set(s, a);
1.196 -
1.197 - typedef typename AugGraph::NodeMap<int> FreeMap;
1.198 - FreeMap free(res_graph);
1.199 -
1.200 - //searching for augmenting path
1.201 - while ( res_bfs.valid() ) {
1.202 - //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
1.203 - if (res_bfs.newly_reached()) {
1.204 - AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
1.205 - NodeIt v=res_graph.tail(e);
1.206 - NodeIt w=res_graph.head(e);
1.207 - //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
1.208 - pred.set(w, e);
1.209 - if (pred.get(v).valid()) {
1.210 - free.set(w, std::min(free.get(v), e.free()));
1.211 - //std::cout <<" nem elso csucs: ";
1.212 - //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.213 - } else {
1.214 - free.set(w, e.free());
1.215 - //std::cout <<" elso csucs: ";
1.216 - //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
1.217 - }
1.218 - //std::cout<<std::endl;
1.219 - }
1.220 -
1.221 - if (res_graph.head(res_bfs)==t) break;
1.222 - ++res_bfs;
1.223 - } //end searching augmenting path
1.224 - if (reached.get(t)) {
1.225 - augment=true;
1.226 - NodeIt n=t;
1.227 - T augment_value=free.get(t);
1.228 - std::cout<<"augmentation: ";
1.229 - while (pred.get(n).valid()) {
1.230 - AugEdgeIt e=pred.get(n);
1.231 - e.augment(augment_value);
1.232 - std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
1.233 - n=res_graph.tail(e);
1.234 - }
1.235 - std::cout<<std::endl;
1.236 - }
1.237 -
1.238 - std::cout << "actual flow: "<< std::endl;
1.239 - for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
1.240 - std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
1.241 - }
1.242 - std::cout<<std::endl;
1.243 -
1.244 - } while (augment);
1.245 + while (augment()) { }
1.246 }
1.247 };
1.248
1.249 } // namespace marci
1.250
1.251 -#endif //MARCI_MAX_FLOW_HH
1.252 +#endif //EDMONDS_KARP_HH
2.1 --- a/src/work/iterator_bfs_dfs_demo.cc Wed Feb 04 12:45:32 2004 +0000
2.2 +++ b/src/work/iterator_bfs_dfs_demo.cc Wed Feb 04 12:46:33 2004 +0000
2.3 @@ -181,6 +181,41 @@
2.4 }
2.5 }
2.6
2.7 + {
2.8 + std::cout << "iterator bfs demo 2 ..." << std::endl;
2.9 + //ListGraph::NodeMap<bool> reached(G, false);
2.10 + //reached.set(s, true);
2.11 + //std::queue<ListGraph::OutEdgeIt> bfs_queue;
2.12 + //bfs_queue.push(G.first<OutEdgeIt>(s));
2.13 + BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
2.14 + bfs.pushAndSetReached(s);
2.15 + while (!bfs.finished()) {
2.16 + if (OutEdgeIt(bfs).valid()) {
2.17 + std::cout << "OutEdgeIt: " << bfs;
2.18 + std::cout << " aNode: " << G.aNode(bfs);
2.19 + std::cout << " bNode: " << G.bNode(bfs) << " ";
2.20 + } else {
2.21 + std::cout << "OutEdgeIt: " << "invalid";
2.22 + std::cout << " aNode: " << G.aNode(bfs);
2.23 + std::cout << " bNode: " << "invalid" << " ";
2.24 + }
2.25 + if (bfs.isBNodeNewlyReached()) {
2.26 + std::cout << "bNodeIsNewlyReached ";
2.27 + } else {
2.28 + std::cout << "bNodeIsNotNewlyReached ";
2.29 + }
2.30 + if (bfs.isANodeExamined()) {
2.31 + std::cout << "aNodeIsExamined ";
2.32 + } else {
2.33 + std::cout << "aNodeIsNotExamined ";
2.34 + }
2.35 + std::cout<<std::endl;
2.36 + ++bfs;
2.37 + }
2.38 + }
2.39 +
2.40 +
2.41 +
2.42
2.43 {
2.44 std::cout << "iterator dfs demo 1..." << std::endl;
3.1 --- a/src/work/list_graph.hh Wed Feb 04 12:45:32 2004 +0000
3.2 +++ b/src/work/list_graph.hh Wed Feb 04 12:46:33 2004 +0000
3.3 @@ -1,18 +1,11 @@
3.4 -#ifndef MARCI_LIST_GRAPH_HH
3.5 -#define MARCI_LIST_GRAPH_HH
3.6 +#ifndef LIST_GRAPH_HH
3.7 +#define LIST_GRAPH_HH
3.8
3.9 #include <iostream>
3.10
3.11 namespace marci {
3.12
3.13 template <typename It>
3.14 - int number_of(It _it) {
3.15 - int i=0;
3.16 - for( ; _it.valid(); ++_it) { ++i; }
3.17 - return i;
3.18 - }
3.19 -
3.20 - template <typename It>
3.21 int count(It it) {
3.22 int i=0;
3.23 for( ; it.valid(); ++it) { ++i; }
3.24 @@ -20,9 +13,12 @@
3.25 }
3.26
3.27 class ListGraph {
3.28 +
3.29 class node_item;
3.30 class edge_item;
3.31 +
3.32 public:
3.33 +
3.34 class NodeIt;
3.35 class EachNodeIt;
3.36 class EdgeIt;
3.37 @@ -30,70 +26,38 @@
3.38 class OutEdgeIt;
3.39 class InEdgeIt;
3.40 class SymEdgeIt;
3.41 + template <typename ValueType> class NodeMap;
3.42 + template <typename ValueType> class EdgeMap;
3.43 +
3.44 + private:
3.45 +
3.46 + template <typename ValueType> friend class NodeMap;
3.47 + template <typename ValueType> friend class EdgeMap;
3.48
3.49 - template <typename T>
3.50 + template <typename ValueType>
3.51 class NodeMap {
3.52 - //typedef typename Graph::NodeIt NodeIt;
3.53 - //typedef typename Graph::EachNodeIt EachNodeIt;
3.54 const ListGraph& G;
3.55 - std::vector<T> container;
3.56 + std::vector<ValueType> container;
3.57 public:
3.58 - NodeMap(const ListGraph& _G) : G(_G) {
3.59 - int i=0;
3.60 - for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i;
3.61 - container.resize(i);
3.62 - }
3.63 - NodeMap(const ListGraph& _G, const T a) : G(_G) {
3.64 - for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) {
3.65 - container.push_back(a);
3.66 - }
3.67 - }
3.68 - void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; }
3.69 - T get(const NodeIt nit) const { return container[G.id(nit)]; }
3.70 + NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
3.71 + NodeMap(const ListGraph& _G, const ValueType a) :
3.72 + G(_G), container(_G.node_id, a) { }
3.73 + void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
3.74 + ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
3.75 };
3.76
3.77 - template <typename T>
3.78 + template <typename ValueType>
3.79 class EdgeMap {
3.80 - //typedef typename Graph::EdgeIt EdgeIt;
3.81 - //typedef typename Graph::EachEdgeIt EachEdgeIt;
3.82 const ListGraph& G;
3.83 - std::vector<T> container;
3.84 + std::vector<ValueType> container;
3.85 public:
3.86 - EdgeMap(const ListGraph& _G) : G(_G) {
3.87 - int i=0;
3.88 - for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i;
3.89 - container.resize(i);
3.90 - }
3.91 - EdgeMap(const ListGraph& _G, const T a) : G(_G) {
3.92 - for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) {
3.93 - container.push_back(a);
3.94 - }
3.95 - }
3.96 - void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; }
3.97 - T get(const EdgeIt eit) const { return container[G.id(eit)]; }
3.98 + EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
3.99 + EdgeMap(const ListGraph& _G, const ValueType a) :
3.100 + G(_G), container(_G.edge_id, a) { }
3.101 + void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
3.102 + ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
3.103 };
3.104
3.105 - //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap;
3.106 - //template <typename T>
3.107 - //typedef NodePropertyVector<ListGraph, T> NodeMap;
3.108 - //template <typename T>
3.109 - //typedef typename NodePropertyVector<ListGraph, T> NodeMap;
3.110 - //template <typename T>
3.111 - //typedef NodePropertyVector<typename ListGraph, T> NodeMap;
3.112 - //template <typename T>
3.113 - //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap;
3.114 - //template <typename T>
3.115 - //typedef template NodePropertyVector<ListGraph, T> NodeMap;
3.116 - //template <typename T>
3.117 - //typedef template typename NodePropertyVector<ListGraph, T> NodeMap;
3.118 - //template <typename T>
3.119 - //typedef template NodePropertyVector<typename ListGraph, T> NodeMap;
3.120 - //template <typename T>
3.121 - //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap;
3.122 - //template <typename T>
3.123 - //typedef EdgePropertyVector<ListGraph, T> EdgeMap;
3.124 -
3.125 - private:
3.126 int node_id;
3.127 int edge_id;
3.128 int _node_num;
3.129 @@ -113,7 +77,7 @@
3.130 friend class SymEdgeIt;
3.131 friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
3.132 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
3.133 - ListGraph* G;
3.134 + //ListGraph* G;
3.135 int id;
3.136 edge_item* _first_out_edge;
3.137 edge_item* _last_out_edge;
3.138 @@ -135,7 +99,7 @@
3.139 friend class InEdgeIt;
3.140 friend class SymEdgeIt;
3.141 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
3.142 - ListGraph* G;
3.143 + //ListGraph* G;
3.144 int id;
3.145 node_item* _tail;
3.146 node_item* _head;
3.147 @@ -256,17 +220,12 @@
3.148
3.149 /* functions to construct iterators from the graph, or from each other */
3.150
3.151 - EachNodeIt firstNode() const { return EachNodeIt(_first_node); }
3.152 - EachEdgeIt firstEdge() const {
3.153 - node_item* v=_first_node;
3.154 - edge_item* edge=v->_first_out_edge;
3.155 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
3.156 - return EachEdgeIt(v, edge);
3.157 - }
3.158 + //EachNodeIt firstNode() const { return EachNodeIt(*this); }
3.159 + //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); }
3.160
3.161 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
3.162 - InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
3.163 - SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
3.164 + //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
3.165 + //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
3.166 NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
3.167 NodeIt head(const EdgeIt e) const { return e.headNode(); }
3.168
3.169 @@ -287,8 +246,8 @@
3.170 /* same methods in other style */
3.171 /* for experimental purpose */
3.172
3.173 - void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); }
3.174 - void getFirst(EachEdgeIt& e) const { e=firstEdge(); }
3.175 + void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
3.176 + void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
3.177 void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
3.178 void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
3.179 void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); }
3.180 @@ -386,10 +345,11 @@
3.181
3.182 class EachNodeIt : public NodeIt {
3.183 friend class ListGraph;
3.184 + protected:
3.185 + EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
3.186 public:
3.187 EachNodeIt() : NodeIt() { }
3.188 EachNodeIt(node_item* v) : NodeIt(v) { }
3.189 - EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
3.190 EachNodeIt& operator++() { node=node->_next_node; return *this; }
3.191 };
3.192
3.193 @@ -422,16 +382,17 @@
3.194
3.195 class EachEdgeIt : public EdgeIt {
3.196 friend class ListGraph;
3.197 - node_item* v;
3.198 - public:
3.199 - EachEdgeIt() : EdgeIt(), v(0) { }
3.200 - EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { }
3.201 + protected:
3.202 EachEdgeIt(const ListGraph& G) {
3.203 - v=G._first_node;
3.204 - edge=v->_first_out_edge;
3.205 + node_item* v=G._first_node;
3.206 + if (v) edge=v->_first_out_edge; else edge=0;
3.207 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
3.208 }
3.209 + public:
3.210 + EachEdgeIt() : EdgeIt() { }
3.211 + EachEdgeIt(edge_item* _e) : EdgeIt(_e) { }
3.212 EachEdgeIt& operator++() {
3.213 + node_item* v=edge->_tail;
3.214 edge=edge->_next_out;
3.215 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
3.216 return *this;
3.217 @@ -441,11 +402,10 @@
3.218 class OutEdgeIt : public EdgeIt {
3.219 friend class ListGraph;
3.220 node_item* v;
3.221 - public:
3.222 - OutEdgeIt() : EdgeIt(), v(0) { }
3.223 protected:
3.224 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
3.225 public:
3.226 + OutEdgeIt() : EdgeIt(), v(0) { }
3.227 OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
3.228 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
3.229 protected:
3.230 @@ -457,13 +417,10 @@
3.231 class InEdgeIt : public EdgeIt {
3.232 friend class ListGraph;
3.233 node_item* v;
3.234 + protected:
3.235 + InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
3.236 public:
3.237 InEdgeIt() : EdgeIt(), v(0) { }
3.238 - protected:
3.239 - InEdgeIt(const NodeIt& _v) : v(_v.node) {
3.240 - edge=v->_first_in_edge;
3.241 - }
3.242 - public:
3.243 InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
3.244 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
3.245 protected:
3.246 @@ -476,8 +433,6 @@
3.247 friend class ListGraph;
3.248 bool out_or_in; //1 iff out, 0 iff in
3.249 node_item* v;
3.250 - public:
3.251 - SymEdgeIt() : EdgeIt(), v(0) { }
3.252 protected:
3.253 SymEdgeIt(const NodeIt& _v) : v(_v.node) {
3.254 out_or_in=1;
3.255 @@ -485,6 +440,7 @@
3.256 if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
3.257 }
3.258 public:
3.259 + SymEdgeIt() : EdgeIt(), v(0) { }
3.260 SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) {
3.261 out_or_in=1;
3.262 edge=v->_first_out_edge;
3.263 @@ -549,4 +505,4 @@
3.264
3.265 } //namespace marci
3.266
3.267 -#endif //MARCI_LIST_GRAPH_HH
3.268 +#endif //LIST_GRAPH_HH