# HG changeset patch # User marci # Date 1079083194 0 # Node ID 44700ed9ffaa5ded46bdba64f0f80ee83d4a2d7d # Parent de9849252e7834b8dd59d5072148d2e4c4c59033 towards on ListGraph, SmartGraph compatibility diff -r de9849252e78 -r 44700ed9ffaa src/work/alpar/emptygraph.h --- a/src/work/alpar/emptygraph.h Thu Mar 11 23:31:13 2004 +0000 +++ b/src/work/alpar/emptygraph.h Fri Mar 12 09:19:54 2004 +0000 @@ -1,4 +1,6 @@ -// -*-mode: c++; -*- +// -*- c++ -*- +#ifndef EMPTYGRAPH_H +#define EMPTYGRAPH_H #include @@ -34,7 +36,7 @@ /// to an undefined value. Node() {} //FIXME /// Initialize the iterator to be invalid - Node(Invalid) {}; + Node(Invalid) {} //Node(const Node &) {} bool operator==(Node n) const { return true; } //FIXME bool operator!=(Node n) const { return true; } //FIXME @@ -47,7 +49,7 @@ /// to an undefined value. NodeIt() {} //FIXME /// Initialize the iterator to be invalid - NodeIt(Invalid) {}; + NodeIt(Invalid) {} /// Sets the iterator to the first node of \c G. NodeIt(const EmptyGraph &G) {} NodeIt(const NodeIt &) {} //FIXME @@ -61,7 +63,7 @@ /// to an undefined value. Edge() {} //FIXME /// Initialize the iterator to be invalid - Edge(Invalid) {}; + Edge(Invalid) {} //Edge(const Edge &) {} bool operator==(Edge n) const { return true; } //FIXME bool operator!=(Edge n) const { return true; } //FIXME @@ -75,7 +77,7 @@ /// to an undefined value. OutEdgeIt() {} /// Initialize the iterator to be invalid - OutEdgeIt(Invalid) {}; + OutEdgeIt(Invalid) {} /// This constructor sets the iterator to first outgoing edge. /// This constructor set the iterator to the first outgoing edge of @@ -91,7 +93,7 @@ /// to an undefined value. InEdgeIt() {} /// Initialize the iterator to be invalid - InEdgeIt(Invalid) {}; + InEdgeIt(Invalid) {} InEdgeIt(const EmptyGraph &, Node) {} }; // class SymEdgeIt : public Edge {}; @@ -101,7 +103,7 @@ /// to an undefined value. EdgeIt() {} /// Initialize the iterator to be invalid - EdgeIt(Invalid) {}; + EdgeIt(Invalid) {} EdgeIt(const EmptyGraph &) {} }; @@ -149,14 +151,14 @@ // Node bNode(SymEdgeIt) const {} /// Checks if a node iterator is valid - bool valid(const Node) const { return true;}; + bool valid(const Node) const { return true;} /// Checks if an edge iterator is valid - bool valid(const Edge) const { return true;}; + bool valid(const Edge) const { return true;} ///Gives back the \e id of a node. - int id(const Node) const { return 0;}; + int id(const Node) const { return 0;} ///Gives back the \e id of an edge. - int id(const Edge) const { return 0;}; + int id(const Edge) const { return 0;} //void setInvalid(Node &) const {}; //void setInvalid(Edge &) const {}; @@ -172,8 +174,8 @@ int nodeNum() { return 0;} int edgeNum() { return 0;} - EmptyGraph() {}; - EmptyGraph(const EmptyGraph &G) {}; + EmptyGraph() {} + EmptyGraph(const EmptyGraph &G) {} @@ -217,7 +219,7 @@ // @} -}; +} //namespace hugo @@ -236,3 +238,5 @@ // NodeClass getClass(Node n) {} // } + +#endif // EMPTYGRAPH_H diff -r de9849252e78 -r 44700ed9ffaa src/work/alpar/smart_graph.h --- a/src/work/alpar/smart_graph.h Thu Mar 11 23:31:13 2004 +0000 +++ b/src/work/alpar/smart_graph.h Fri Mar 12 09:19:54 2004 +0000 @@ -96,12 +96,14 @@ Node tail(Edge e) const { return edges[e.n].tail; } Node head(Edge e) const { return edges[e.n].head; } -// Node aNode(const OutEdgeIt& e) const { return tail(e); } -// Node aNode(const InEdgeIt& e) const { return head(e); } + // Marci + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } + Node aNode(InEdgeIt e) const { return edges[e.n].head; } // //Node aNode(const SymEdge& e) const { return e.aNode(); } -// Node bNode(const OutEdgeIt& e) const { return head(e); } -// Node bNode(const InEdgeIt& e) const { return tail(e); } + // Marci + Node bNode(OutEdgeIt e) const { return edges[e.n].head; } + Node bNode(InEdgeIt e) const { return edges[e.n].tail; } // //Node bNode(const SymEdge& e) const { return e.bNode(); } NodeIt& first(NodeIt& v) const { @@ -116,14 +118,16 @@ template< typename It > It first() const { It e; - getFirst(e); + //Marci + /*getF*/first(e); return e; } template< typename It > It first(Node v) const { It e; - getFirst(e, v); + //Marci + /*getF*/first(e, v); return e; } @@ -138,7 +142,12 @@ { It tmp(it); return next(tmp); } //{ It tmp; tmp.n=it.n+1; return tmp; } - Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; } + //FIXME correction Marci: I changed to NodeIt from Node + //NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; } + NodeIt& next(NodeIt& it) const { + it.n=(it.n+2)%(nodes.size()+1)-1; + return it; + } OutEdgeIt& next(OutEdgeIt& it) const { it.n=edges[it.n].next_out; return it; } InEdgeIt& next(InEdgeIt& it) const @@ -216,7 +225,8 @@ Edge(int nn) {n=nn;} public: Edge() { } - Edge (Invalid i) { n=-1; } + // Marci: kiszedtem az Invalid i-bol az i-t + Edge (Invalid) { n=-1; } bool operator==(const Edge i) const {return n==i.n;} bool operator!=(const Edge i) const {return n!=i.n;} bool operator<(const Edge i) const {return n +#include +#include +#include + +namespace hugo { + + template + struct bfs { + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::OutEdgeIt OutEdgeIt; + Graph& G; + Node s; + typename Graph::NodeMap reached; + typename Graph::NodeMap pred; + typename Graph::NodeMap dist; + std::queue bfs_queue; + bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { + bfs_queue.push(s); + for(NodeIt i=G.template first(); i.valid(); ++i) + reached.set(i, false); + reached.set(s, true); + dist.set(s, 0); + } + + void run() { + while (!bfs_queue.empty()) { + Node v=bfs_queue.front(); + OutEdgeIt e=G.template first(v); + bfs_queue.pop(); + for( ; e.valid(); ++e) { + Node w=G.bNode(e); + std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; + if (!reached.get(w)) { + std::cout << G.id(w) << " is newly reached :-)" << std::endl; + bfs_queue.push(w); + dist.set(w, dist.get(v)+1); + pred.set(w, e); + reached.set(w, true); + } else { + std::cout << G.id(w) << " is already reached" << std::endl; + } + } + } + } + }; + +// template +// struct bfs_visitor { +// typedef typename Graph::Node Node; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::OutEdgeIt OutEdgeIt; +// Graph& G; +// bfs_visitor(Graph& _G) : G(_G) { } +// void at_previously_reached(OutEdgeIt& e) { +// //Node v=G.aNode(e); +// Node w=G.bNode(e); +// std::cout << G.id(w) << " is already reached" << std::endl; +// } +// void at_newly_reached(OutEdgeIt& e) { +// //Node v=G.aNode(e); +// Node w=G.bNode(e); +// std::cout << G.id(w) << " is newly reached :-)" << std::endl; +// } +// }; + +// template +// struct bfs_iterator { +// typedef typename Graph::Node Node; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::OutEdgeIt OutEdgeIt; +// Graph& G; +// std::queue& bfs_queue; +// ReachedMap& reached; +// visitor_type& visitor; +// void process() { +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// if (bfs_queue.empty()) return; +// OutEdgeIt e=bfs_queue.front(); +// //Node v=G.aNode(e); +// Node w=G.bNode(e); +// if (!reached.get(w)) { +// visitor.at_newly_reached(e); +// bfs_queue.push(G.template first(w)); +// reached.set(w, true); +// } else { +// visitor.at_previously_reached(e); +// } +// } +// bfs_iterator(Graph& _G, std::queue& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// valid(); +// } +// bfs_iterator& operator++() { +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// //if (bfs_queue.empty()) return *this; +// if (!valid()) return *this; +// ++(bfs_queue.front()); +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// valid(); +// return *this; +// } +// //void next() { +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// // if (bfs_queue.empty()) return; +// // ++(bfs_queue.front()); +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// //} +// bool valid() { +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// if (bfs_queue.empty()) return false; else return true; +// } +// //bool finished() { +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// // if (bfs_queue.empty()) return true; else return false; +// //} +// operator Edge () { return bfs_queue.front(); } + +// }; + +// template +// struct bfs_iterator1 { +// typedef typename Graph::Node Node; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::OutEdgeIt OutEdgeIt; +// Graph& G; +// std::queue& bfs_queue; +// ReachedMap& reached; +// bool _newly_reached; +// bfs_iterator1(Graph& _G, std::queue& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { +// valid(); +// if (!bfs_queue.empty() && bfs_queue.front().valid()) { +// OutEdgeIt e=bfs_queue.front(); +// Node w=G.bNode(e); +// if (!reached.get(w)) { +// bfs_queue.push(G.template first(w)); +// reached.set(w, true); +// _newly_reached=true; +// } else { +// _newly_reached=false; +// } +// } +// } +// bfs_iterator1& operator++() { +// if (!valid()) return *this; +// ++(bfs_queue.front()); +// valid(); +// if (!bfs_queue.empty() && bfs_queue.front().valid()) { +// OutEdgeIt e=bfs_queue.front(); +// Node w=G.bNode(e); +// if (!reached.get(w)) { +// bfs_queue.push(G.template first(w)); +// reached.set(w, true); +// _newly_reached=true; +// } else { +// _newly_reached=false; +// } +// } +// return *this; +// } +// bool valid() { +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } +// if (bfs_queue.empty()) return false; else return true; +// } +// operator OutEdgeIt() { return bfs_queue.front(); } +// //ize +// bool newly_reached() { return _newly_reached; } + +// }; + +// template +// struct BfsIterator { +// typedef typename Graph::Node Node; +// Graph& G; +// std::queue& bfs_queue; +// ReachedMap& reached; +// bool b_node_newly_reached; +// OutEdgeIt actual_edge; +// BfsIterator(Graph& _G, +// std::queue& _bfs_queue, +// ReachedMap& _reached) : +// G(_G), bfs_queue(_bfs_queue), reached(_reached) { +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.firstOutEdge(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } +// BfsIterator& +// operator++() { +// if (bfs_queue.front().valid()) { +// ++(bfs_queue.front()); +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.firstOutEdge(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } else { +// bfs_queue.pop(); +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.firstOutEdge(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } +// return *this; +// } +// bool finished() { return bfs_queue.empty(); } +// operator OutEdgeIt () { return actual_edge; } +// bool bNodeIsNewlyReached() { return b_node_newly_reached; } +// bool aNodeIsExamined() { return !(actual_edge.valid()); } +// }; + + +// template +// struct DfsIterator { +// typedef typename Graph::Node Node; +// Graph& G; +// std::stack& bfs_queue; +// ReachedMap& reached; +// bool b_node_newly_reached; +// OutEdgeIt actual_edge; +// DfsIterator(Graph& _G, +// std::stack& _bfs_queue, +// ReachedMap& _reached) : +// G(_G), bfs_queue(_bfs_queue), reached(_reached) { +// actual_edge=bfs_queue.top(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.firstOutEdge(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// ++(bfs_queue.top()); +// b_node_newly_reached=false; +// } +// } else { +// bfs_queue.pop(); +// } +// } +// DfsIterator& +// operator++() { +// actual_edge=bfs_queue.top(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.firstOutEdge(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// ++(bfs_queue.top()); +// b_node_newly_reached=false; +// } +// } else { +// bfs_queue.pop(); +// } +// return *this; +// } +// bool finished() { return bfs_queue.empty(); } +// operator OutEdgeIt () { return actual_edge; } +// bool bNodeIsNewlyReached() { return b_node_newly_reached; } +// bool aNodeIsExamined() { return !(actual_edge.valid()); } +// }; + +// template +// struct BfsIterator1 { +// typedef typename Graph::Node Node; +// Graph& G; +// std::queue& bfs_queue; +// ReachedMap& reached; +// bool b_node_newly_reached; +// OutEdgeIt actual_edge; +// BfsIterator1(Graph& _G, +// std::queue& _bfs_queue, +// ReachedMap& _reached) : +// G(_G), bfs_queue(_bfs_queue), reached(_reached) { +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(OutEdgeIt(G, w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } +// void next() { +// if (bfs_queue.front().valid()) { +// ++(bfs_queue.front()); +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(OutEdgeIt(G, w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } else { +// bfs_queue.pop(); +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(OutEdgeIt(G, w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } +// //return *this; +// } +// bool finished() { return bfs_queue.empty(); } +// operator OutEdgeIt () { return actual_edge; } +// bool bNodeIsNewlyReached() { return b_node_newly_reached; } +// bool aNodeIsExamined() { return !(actual_edge.valid()); } +// }; + + +// template +// struct DfsIterator1 { +// typedef typename Graph::Node Node; +// Graph& G; +// std::stack& bfs_queue; +// ReachedMap& reached; +// bool b_node_newly_reached; +// OutEdgeIt actual_edge; +// DfsIterator1(Graph& _G, +// std::stack& _bfs_queue, +// ReachedMap& _reached) : +// G(_G), bfs_queue(_bfs_queue), reached(_reached) { +// //actual_edge=bfs_queue.top(); +// //if (actual_edge.valid()) { +// // Node w=G.bNode(actual_edge); +// //if (!reached.get(w)) { +// // bfs_queue.push(OutEdgeIt(G, w)); +// // reached.set(w, true); +// // b_node_newly_reached=true; +// //} else { +// // ++(bfs_queue.top()); +// // b_node_newly_reached=false; +// //} +// //} else { +// // bfs_queue.pop(); +// //} +// } +// void next() { +// actual_edge=bfs_queue.top(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(OutEdgeIt(G, w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// ++(bfs_queue.top()); +// b_node_newly_reached=false; +// } +// } else { +// bfs_queue.pop(); +// } +// //return *this; +// } +// bool finished() { return bfs_queue.empty(); } +// operator OutEdgeIt () { return actual_edge; } +// bool bNodeIsNewlyReached() { return b_node_newly_reached; } +// bool aNodeIsLeaved() { return !(actual_edge.valid()); } +// }; + +// template +// class BfsIterator2 { +// typedef typename Graph::Node Node; +// const Graph& G; +// std::queue bfs_queue; +// ReachedMap reached; +// bool b_node_newly_reached; +// OutEdgeIt actual_edge; +// public: +// BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { } +// void pushAndSetReached(Node s) { +// reached.set(s, true); +// if (bfs_queue.empty()) { +// bfs_queue.push(G.template first(s)); +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.template first(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } //else { +// //} +// } else { +// bfs_queue.push(G.template first(s)); +// } +// } +// BfsIterator2& +// operator++() { +// if (bfs_queue.front().valid()) { +// ++(bfs_queue.front()); +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.template first(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } else { +// bfs_queue.pop(); +// if (!bfs_queue.empty()) { +// actual_edge=bfs_queue.front(); +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(G.template first(w)); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } +// } +// return *this; +// } +// bool finished() const { return bfs_queue.empty(); } +// operator OutEdgeIt () const { return actual_edge; } +// bool isBNodeNewlyReached() const { return b_node_newly_reached; } +// bool isANodeExamined() const { return !(actual_edge.valid()); } +// const ReachedMap& getReachedMap() const { return reached; } +// const std::queue& getBfsQueue() const { return bfs_queue; } +// }; + + +// template +// class BfsIterator3 { +// typedef typename Graph::Node Node; +// const Graph& G; +// std::queue< std::pair > bfs_queue; +// ReachedMap reached; +// bool b_node_newly_reached; +// OutEdgeIt actual_edge; +// public: +// BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { } +// void pushAndSetReached(Node s) { +// reached.set(s, true); +// if (bfs_queue.empty()) { +// bfs_queue.push(std::pair(s, G.template first(s))); +// actual_edge=bfs_queue.front().second; +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(std::pair(w, G.template first(w))); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } //else { +// //} +// } else { +// bfs_queue.push(std::pair(s, G.template first(s))); +// } +// } +// BfsIterator3& +// operator++() { +// if (bfs_queue.front().second.valid()) { +// ++(bfs_queue.front().second); +// actual_edge=bfs_queue.front().second; +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(std::pair(w, G.template first(w))); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } else { +// bfs_queue.pop(); +// if (!bfs_queue.empty()) { +// actual_edge=bfs_queue.front().second; +// if (actual_edge.valid()) { +// Node w=G.bNode(actual_edge); +// if (!reached.get(w)) { +// bfs_queue.push(std::pair(w, G.template first(w))); +// reached.set(w, true); +// b_node_newly_reached=true; +// } else { +// b_node_newly_reached=false; +// } +// } +// } +// } +// return *this; +// } +// bool finished() const { return bfs_queue.empty(); } +// operator OutEdgeIt () const { return actual_edge; } +// bool isBNodeNewlyReached() const { return b_node_newly_reached; } +// bool isANodeExamined() const { return !(actual_edge.valid()); } +// Node aNode() const { return bfs_queue.front().first; } +// Node bNode() const { return G.bNode(actual_edge); } +// const ReachedMap& getReachedMap() const { return reached; } +// //const std::queue< std::pair >& getBfsQueue() const { return bfs_queue; } +// }; + + + template */ > + class BfsIterator4 { + typedef typename Graph::Node Node; + const Graph& G; + std::queue bfs_queue; + ReachedMap& reached; + bool b_node_newly_reached; + OutEdgeIt actual_edge; + bool own_reached_map; + public: + BfsIterator4(const Graph& _G, ReachedMap& _reached) : + G(_G), reached(_reached), + own_reached_map(false) { } + BfsIterator4(const Graph& _G) : + G(_G), reached(*(new ReachedMap(G /*, false*/))), + own_reached_map(true) { } + ~BfsIterator4() { if (own_reached_map) delete &reached; } + void pushAndSetReached(Node s) { + //std::cout << "mimi" << &reached << std::endl; + reached.set(s, true); + //std::cout << "mumus" << std::endl; + if (bfs_queue.empty()) { + //std::cout << "bibi1" << std::endl; + bfs_queue.push(s); + //std::cout << "zizi" << std::endl; + G./*getF*/first(actual_edge, s); + //std::cout << "kiki" << std::endl; + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + if (!reached.get(w)) { + bfs_queue.push(w); + reached.set(w, true); + b_node_newly_reached=true; + } else { + b_node_newly_reached=false; + } + } + } else { + //std::cout << "bibi2" << std::endl; + bfs_queue.push(s); + } + } + BfsIterator4& + operator++() { + if (G.valid(actual_edge)/*.valid()*/) { + /*++*/G.next(actual_edge); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + if (!reached.get(w)) { + bfs_queue.push(w); + reached.set(w, true); + b_node_newly_reached=true; + } else { + b_node_newly_reached=false; + } + } + } else { + bfs_queue.pop(); + if (!bfs_queue.empty()) { + G./*getF*/first(actual_edge, bfs_queue.front()); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + if (!reached.get(w)) { + bfs_queue.push(w); + reached.set(w, true); + b_node_newly_reached=true; + } else { + b_node_newly_reached=false; + } + } + } + } + return *this; + } + bool finished() const { return bfs_queue.empty(); } + operator OutEdgeIt () const { return actual_edge; } + bool isBNodeNewlyReached() const { return b_node_newly_reached; } + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } + Node aNode() const { return bfs_queue.front(); } + Node bNode() const { return G.bNode(actual_edge); } + const ReachedMap& getReachedMap() const { return reached; } + const std::queue& getBfsQueue() const { return bfs_queue; } + }; + + + template */ > + class BfsIterator5 { + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; + GraphWrapper G; + std::queue bfs_queue; + ReachedMap& reached; + bool b_node_newly_reached; + OutEdgeIt actual_edge; + bool own_reached_map; + public: + BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : + G(_G), reached(_reached), + own_reached_map(false) { } + BfsIterator5(const GraphWrapper& _G) : + G(_G), reached(*(new ReachedMap(G /*, false*/))), + own_reached_map(true) { } +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G, +// ReachedMap& _reached) : +// G(_G), reached(_reached), +// own_reached_map(false) { } +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : +// G(_G), reached(*(new ReachedMap(G /*, false*/))), +// own_reached_map(true) { } + ~BfsIterator5() { if (own_reached_map) delete &reached; } + void pushAndSetReached(Node s) { + reached.set(s, true); + if (bfs_queue.empty()) { + bfs_queue.push(s); + G./*getF*/first(actual_edge, s); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + if (!reached.get(w)) { + bfs_queue.push(w); + reached.set(w, true); + b_node_newly_reached=true; + } else { + b_node_newly_reached=false; + } + } + } else { + bfs_queue.push(s); + } + } + BfsIterator5& + operator++() { + if (G.valid(actual_edge)/*.valid()*/) { + /*++*/G.next(actual_edge); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + if (!reached.get(w)) { + bfs_queue.push(w); + reached.set(w, true); + b_node_newly_reached=true; + } else { + b_node_newly_reached=false; + } + } + } else { + bfs_queue.pop(); + if (!bfs_queue.empty()) { + G./*getF*/first(actual_edge, bfs_queue.front()); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + if (!reached.get(w)) { + bfs_queue.push(w); + reached.set(w, true); + b_node_newly_reached=true; + } else { + b_node_newly_reached=false; + } + } + } + } + return *this; + } + bool finished() const { return bfs_queue.empty(); } + operator OutEdgeIt () const { return actual_edge; } + bool isBNodeNewlyReached() const { return b_node_newly_reached; } + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } + Node aNode() const { return bfs_queue.front(); } + Node bNode() const { return G.bNode(actual_edge); } + const ReachedMap& getReachedMap() const { return reached; } + const std::queue& getBfsQueue() const { return bfs_queue; } + }; + + template */ > + class DfsIterator4 { + typedef typename Graph::Node Node; + const Graph& G; + std::stack dfs_stack; + bool b_node_newly_reached; + OutEdgeIt actual_edge; + Node actual_node; + ReachedMap& reached; + bool own_reached_map; + public: + DfsIterator4(const Graph& _G, ReachedMap& _reached) : + G(_G), reached(_reached), + own_reached_map(false) { } + DfsIterator4(const Graph& _G) : + G(_G), reached(*(new ReachedMap(G /*, false*/))), + own_reached_map(true) { } + ~DfsIterator4() { if (own_reached_map) delete &reached; } + void pushAndSetReached(Node s) { + actual_node=s; + reached.set(s, true); + dfs_stack.push(G.template first(s)); + } + DfsIterator4& + operator++() { + actual_edge=dfs_stack.top(); + //actual_node=G.aNode(actual_edge); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + actual_node=w; + if (!reached.get(w)) { + dfs_stack.push(G.template first(w)); + reached.set(w, true); + b_node_newly_reached=true; + } else { + actual_node=G.aNode(actual_edge); + /*++*/G.next(dfs_stack.top()); + b_node_newly_reached=false; + } + } else { + //actual_node=G.aNode(dfs_stack.top()); + dfs_stack.pop(); + } + return *this; + } + bool finished() const { return dfs_stack.empty(); } + operator OutEdgeIt () const { return actual_edge; } + bool isBNodeNewlyReached() const { return b_node_newly_reached; } + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } + Node aNode() const { return actual_node; /*FIXME*/} + Node bNode() const { return G.bNode(actual_edge); } + const ReachedMap& getReachedMap() const { return reached; } + const std::stack& getDfsStack() const { return dfs_stack; } + }; + + template */ > + class DfsIterator5 { + typedef typename GraphWrapper::Node Node; + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; + GraphWrapper G; + std::stack dfs_stack; + bool b_node_newly_reached; + OutEdgeIt actual_edge; + Node actual_node; + ReachedMap& reached; + bool own_reached_map; + public: + DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : + G(_G), reached(_reached), + own_reached_map(false) { } + DfsIterator5(const GraphWrapper& _G) : + G(_G), reached(*(new ReachedMap(G /*, false*/))), + own_reached_map(true) { } + ~DfsIterator5() { if (own_reached_map) delete &reached; } + void pushAndSetReached(Node s) { + actual_node=s; + reached.set(s, true); + dfs_stack.push(G.template first(s)); + } + DfsIterator5& + operator++() { + actual_edge=dfs_stack.top(); + //actual_node=G.aNode(actual_edge); + if (G.valid(actual_edge)/*.valid()*/) { + Node w=G.bNode(actual_edge); + actual_node=w; + if (!reached.get(w)) { + dfs_stack.push(G.template first(w)); + reached.set(w, true); + b_node_newly_reached=true; + } else { + actual_node=G.aNode(actual_edge); + /*++*/G.next(dfs_stack.top()); + b_node_newly_reached=false; + } + } else { + //actual_node=G.aNode(dfs_stack.top()); + dfs_stack.pop(); + } + return *this; + } + bool finished() const { return dfs_stack.empty(); } + operator OutEdgeIt () const { return actual_edge; } + bool isBNodeNewlyReached() const { return b_node_newly_reached; } + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } + Node aNode() const { return actual_node; /*FIXME*/} + Node bNode() const { return G.bNode(actual_edge); } + const ReachedMap& getReachedMap() const { return reached; } + const std::stack& getDfsStack() const { return dfs_stack; } + }; + + + +} // namespace hugo + +#endif //BFS_ITERATOR_H diff -r de9849252e78 -r 44700ed9ffaa src/work/edmonds_karp.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/edmonds_karp.h Fri Mar 12 09:19:54 2004 +0000 @@ -0,0 +1,707 @@ +// -*- c++ -*- +#ifndef EDMONDS_KARP_H +#define EDMONDS_KARP_H + +#include +#include +#include + +#include +#include + +namespace hugo { + + template + class ResGraph { + public: + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + private: + typedef typename Graph::SymEdgeIt OldSymEdgeIt; + const Graph& G; + FlowMap& flow; + const CapacityMap& capacity; + public: + ResGraph(const Graph& _G, FlowMap& _flow, + const CapacityMap& _capacity) : + G(_G), flow(_flow), capacity(_capacity) { } + + class Edge; + class OutEdgeIt; + friend class Edge; + friend class OutEdgeIt; + + class Edge { + friend class ResGraph; + protected: + const ResGraph* resG; + OldSymEdgeIt sym; + public: + Edge() { } + //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } + Number free() const { + if (resG->G.aNode(sym)==resG->G.tail(sym)) { + return (resG->capacity.get(sym)-resG->flow.get(sym)); + } else { + return (resG->flow.get(sym)); + } + } + bool valid() const { return sym.valid(); } + void augment(Number a) const { + if (resG->G.aNode(sym)==resG->G.tail(sym)) { + resG->flow.set(sym, resG->flow.get(sym)+a); + //resG->flow[sym]+=a; + } else { + resG->flow.set(sym, resG->flow.get(sym)-a); + //resG->flow[sym]-=a; + } + } + }; + + class OutEdgeIt : public Edge { + friend class ResGraph; + public: + OutEdgeIt() { } + //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } + private: + OutEdgeIt(const ResGraph& _resG, Node v) { + resG=&_resG; + sym=resG->G.template first(v); + while( sym.valid() && !(free()>0) ) { ++sym; } + } + public: + OutEdgeIt& operator++() { + ++sym; + while( sym.valid() && !(free()>0) ) { ++sym; } + return *this; + } + }; + + void /*getF*/first(OutEdgeIt& e, Node v) const { + e=OutEdgeIt(*this, v); + } + void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } + + template< typename It > + It first() const { + It e; + /*getF*/first(e); + return e; + } + + template< typename It > + It first(Node v) const { + It e; + /*getF*/first(e, v); + return e; + } + + Node tail(Edge e) const { return G.aNode(e.sym); } + Node head(Edge e) const { return G.bNode(e.sym); } + + Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } + Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } + + int id(Node v) const { return G.id(v); } + + template + class NodeMap { + typename Graph::NodeMap node_map; + public: + NodeMap(const ResGraph& _G) : node_map(_G.G) { } + NodeMap(const ResGraph& _G, S a) : node_map(_G.G, a) { } + void set(Node nit, S a) { node_map.set(nit, a); } + S get(Node nit) const { return node_map.get(nit); } + S& operator[](Node nit) { return node_map[nit]; } + const S& operator[](Node nit) const { return node_map[nit]; } + }; + + }; + + + template + class ResGraph2 { + public: + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + private: + //typedef typename Graph::SymEdgeIt OldSymEdgeIt; + typedef typename Graph::OutEdgeIt OldOutEdgeIt; + typedef typename Graph::InEdgeIt OldInEdgeIt; + + const Graph& G; + FlowMap& flow; + const CapacityMap& capacity; + public: + ResGraph2(const Graph& _G, FlowMap& _flow, + const CapacityMap& _capacity) : + G(_G), flow(_flow), capacity(_capacity) { } + + class Edge; + class OutEdgeIt; + friend class Edge; + friend class OutEdgeIt; + + class Edge { + friend class ResGraph2; + protected: + const ResGraph2* resG; + //OldSymEdgeIt sym; + OldOutEdgeIt out; + OldInEdgeIt in; + bool out_or_in; //true, iff out + public: + Edge() : out_or_in(true) { } + Number free() const { + if (out_or_in) { + return (resG->capacity.get(out)-resG->flow.get(out)); + } else { + return (resG->flow.get(in)); + } + } + bool valid() const { + return out_or_in && out.valid() || in.valid(); } + void augment(Number a) const { + if (out_or_in) { + resG->flow.set(out, resG->flow.get(out)+a); + } else { + resG->flow.set(in, resG->flow.get(in)-a); + } + } + }; + + class OutEdgeIt : public Edge { + friend class ResGraph2; + public: + OutEdgeIt() { } + private: + OutEdgeIt(const ResGraph2& _resG, Node v) { + resG=&_resG; + out=resG->G.template first(v); + while( out.valid() && !(free()>0) ) { ++out; } + if (!out.valid()) { + out_or_in=0; + in=resG->G.template first(v); + while( in.valid() && !(free()>0) ) { ++in; } + } + } + public: + OutEdgeIt& operator++() { + if (out_or_in) { + Node v=resG->G.aNode(out); + ++out; + while( out.valid() && !(free()>0) ) { ++out; } + if (!out.valid()) { + out_or_in=0; + in=resG->G.template first(v); + while( in.valid() && !(free()>0) ) { ++in; } + } + } else { + ++in; + while( in.valid() && !(free()>0) ) { ++in; } + } + return *this; + } + }; + + void /*getF*/first(OutEdgeIt& e, Node v) const { + e=OutEdgeIt(*this, v); + } + void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } + + template< typename It > + It first() const { + It e; + /*getF*/first(e); + return e; + } + + template< typename It > + It first(Node v) const { + It e; + /*getF*/first(e, v); + return e; + } + + Node tail(Edge e) const { + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } + Node head(Edge e) const { + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } + + Node aNode(OutEdgeIt e) const { + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } + Node bNode(OutEdgeIt e) const { + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } + + int id(Node v) const { return G.id(v); } + + template + class NodeMap { + typename Graph::NodeMap node_map; + public: + NodeMap(const ResGraph2& _G) : node_map(_G.G) { } + NodeMap(const ResGraph2& _G, S a) : node_map(_G.G, a) { } + void set(Node nit, S a) { node_map.set(nit, a); } + S get(Node nit) const { return node_map.get(nit); } + }; + }; + + + template + class MaxFlow { + public: + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::OutEdgeIt OutEdgeIt; + typedef typename Graph::InEdgeIt InEdgeIt; + + private: + const Graph* G; + Node s; + Node t; + FlowMap* flow; + const CapacityMap* capacity; + typedef ResGraphWrapper AugGraph; + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; + typedef typename AugGraph::Edge AugEdge; + + //AugGraph res_graph; + //typedef typename AugGraph::NodeMap ReachedMap; + //typename AugGraph::NodeMap pred; + //typename AugGraph::NodeMap free; + public: + MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : + G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, + //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) + { } + bool augmentOnShortestPath() { + AugGraph res_graph(*G, *flow, *capacity); + bool _augment=false; + + typedef typename AugGraph::NodeMap ReachedMap; + BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); + res_bfs.pushAndSetReached(s); + + typename AugGraph::NodeMap pred(res_graph); + pred.set(s, AugEdge(INVALID)); + + typename AugGraph::NodeMap free(res_graph); + + //searching for augmenting path + while ( !res_bfs.finished() ) { + AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); + if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { + Node v=res_graph.tail(e); + Node w=res_graph.head(e); + pred.set(w, e); + if (res_graph.valid(pred.get(v))) { + free.set(w, std::min(free.get(v), res_graph.free(e))); + } else { + free.set(w, res_graph.free(e)); + } + if (res_graph.head(e)==t) { _augment=true; break; } + } + + ++res_bfs; + } //end of searching augmenting path + + if (_augment) { + Node n=t; + Number augment_value=free.get(t); + while (res_graph.valid(pred.get(n))) { + AugEdge e=pred.get(n); + res_graph.augment(e, augment_value); + //e.augment(augment_value); + n=res_graph.tail(e); + } + } + + return _augment; + } + + template bool augmentOnBlockingFlow() { + +// std::cout << "number of nodes: " << G->nodeNum() << std::endl; +// typename Graph::NodeIt n; +// G->first(n); +// for( ; G->valid(n); G->next(n)) { +// std::cout << G->id(n) << std::endl; +// } +// std::cout << "meg elek 1"; + +// for(typename Graph::NodeIt n=G->template first(); G->valid(n); G->next(n)) { +// std::cout << G->id(n) << std::endl; +// } +// std::cout << "meg elek 2"; + + bool _augment=false; + + AugGraph res_graph(*G, *flow, *capacity); + + typedef typename AugGraph::NodeMap ReachedMap; + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); + + bfs.pushAndSetReached(s); + typename AugGraph::NodeMap dist(res_graph); //filled up with 0's + while ( !bfs.finished() ) { + AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + } + + ++bfs; + } //computing distances from s in the residual graph + +// for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { +// std::cout << res_graph.id(n) << std::endl; +// } +// std::cout << "meg elek"; + + MutableGraph F; + typename AugGraph::NodeMap + res_graph_to_F(res_graph); + for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { + res_graph_to_F.set(n, F.addNode()); + } + + typename MutableGraph::Node sF=res_graph_to_F.get(s); + typename MutableGraph::Node tF=res_graph_to_F.get(t); + + typename MutableGraph::EdgeMap original_edge(F); + typename MutableGraph::EdgeMap residual_capacity(F); + + //Making F to the graph containing the edges of the residual graph + //which are in some shortest paths + for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { + if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { + typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); + original_edge.update(); + original_edge.set(f, e); + residual_capacity.update(); + residual_capacity.set(f, res_graph.free(e)); + } + } + +// for(typename MutableGraph::NodeIt n=F.template first(); F.valid(n); F.next(n)) { +// std::cout << F.id(n) << std::endl; +// } + + bool __augment=true; + + while (__augment) { + __augment=false; + //computing blocking flow with dfs + typedef typename MutableGraph::NodeMap BlockingReachedMap; + DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); + typename MutableGraph::NodeMap pred(F); + pred.set(sF, typename MutableGraph::Edge(INVALID)); + //invalid iterators for sources + + typename MutableGraph::NodeMap free(F); + + dfs.pushAndSetReached(sF); + while (!dfs.finished()) { + ++dfs; + if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { + if (dfs.isBNodeNewlyReached()) { +// std::cout << "OutEdgeIt: " << dfs; +// std::cout << " aNode: " << F.aNode(dfs); +// std::cout << " bNode: " << F.bNode(dfs) << " "; + + typename MutableGraph::Node v=F.aNode(dfs); + typename MutableGraph::Node w=F.bNode(dfs); + pred.set(w, dfs); + if (F.valid(pred.get(v))) { + free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); + } else { + free.set(w, residual_capacity.get(dfs)); + } + if (w==tF) { + //std::cout << "AUGMENTATION"< EAugGraph; + typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; + typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; + typedef typename EAugGraph::Edge EAugEdge; + + EAugGraph res_graph(*G, *flow, *capacity); + + //std::cout << "meg jo1" << std::endl; + + //typedef typename EAugGraph::NodeMap ReachedMap; + BfsIterator4< + ErasingResGraphWrapper, + ErasingResGraphWrapper::OutEdgeIt, + ErasingResGraphWrapper::NodeMap > bfs(res_graph); + + //std::cout << "meg jo2" << std::endl; + + bfs.pushAndSetReached(s); + //std::cout << "meg jo2.5" << std::endl; + + //typename EAugGraph::NodeMap dist(res_graph); //filled up with 0's + typename ErasingResGraphWrapper:: + NodeMap& dist=res_graph.dist; + //std::cout << "meg jo2.6" << std::endl; + + while ( !bfs.finished() ) { + ErasingResGraphWrapper::OutEdgeIt e=bfs; +// EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); + //if (res_graph.valid(e)) { + // std::cout<<"a:"<(); res_graph.valid(n); res_graph.next(n)) { +// std::cout << "dist: " << dist.get(n) << std::endl; +// } + + bool __augment=true; + + while (__augment) { +// std::cout << "new iteration"<< std::endl; + + __augment=false; + //computing blocking flow with dfs + typedef typename EAugGraph::NodeMap BlockingReachedMap; + DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > + dfs(res_graph); + typename EAugGraph::NodeMap pred(res_graph); + pred.set(s, EAugEdge(INVALID)); + //invalid iterators for sources + + typename EAugGraph::NodeMap free(res_graph); + + dfs.pushAndSetReached(s); + while (!dfs.finished()) { + ++dfs; + if (res_graph.valid(EAugOutEdgeIt(dfs))) { + if (dfs.isBNodeNewlyReached()) { +// std::cout << "OutEdgeIt: " << dfs; +// std::cout << " aNode: " << res_graph.aNode(dfs); +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); +// std::cout << " bNode: " << res_graph.bNode(dfs) << " "; + + typename EAugGraph::Node v=res_graph.aNode(dfs); + typename EAugGraph::Node w=res_graph.bNode(dfs); + + pred.set(w, EAugOutEdgeIt(dfs)); + + //std::cout << EAugOutEdgeIt(dfs).free() << std::endl; + if (res_graph.valid(pred.get(v))) { + free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs)))); + } else { + free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); + } + + if (w==t) { +// std::cout << "t is reached, AUGMENTATION"<> "; + + res_graph.erase(dfs); + } + } + + } + + if (__augment) { + typename EAugGraph::Node n=t; + Number augment_value=free.get(t); +// std::cout << "av:" << augment_value << std::endl; + while (res_graph.valid(pred.get(n))) { + EAugEdge e=pred.get(n); + res_graph.augment(e, augment_value); + //e.augment(augment_value); + n=res_graph.tail(e); + if (res_graph.free(e)==0) + res_graph.erase(e); + } + } + + } + + return _augment; + } + void run() { + //int num_of_augmentations=0; + while (augmentOnShortestPath()) { + //while (augmentOnBlockingFlow()) { + //std::cout << ++num_of_augmentations << " "; + //std::cout< void run() { + //int num_of_augmentations=0; + //while (augmentOnShortestPath()) { + while (augmentOnBlockingFlow()) { + //std::cout << ++num_of_augmentations << " "; + //std::cout</*getF*/first(e, s); G->valid(e); G->next(e)) { + a+=flow->get(e); + } + return a; + } + }; + + +// template +// class MaxFlow2 { +// public: +// typedef typename Graph::Node Node; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::EdgeIt EdgeIt; +// typedef typename Graph::OutEdgeIt OutEdgeIt; +// typedef typename Graph::InEdgeIt InEdgeIt; +// private: +// const Graph& G; +// std::list& S; +// std::list& T; +// FlowMap& flow; +// const CapacityMap& capacity; +// typedef ResGraphWrapper AugGraph; +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; +// typedef typename AugGraph::Edge AugEdge; +// typename Graph::NodeMap SMap; +// typename Graph::NodeMap TMap; +// public: +// MaxFlow2(const Graph& _G, std::list& _S, std::list& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { +// for(typename std::list::const_iterator i=S.begin(); +// i!=S.end(); ++i) { +// SMap.set(*i, true); +// } +// for (typename std::list::const_iterator i=T.begin(); +// i!=T.end(); ++i) { +// TMap.set(*i, true); +// } +// } +// bool augment() { +// AugGraph res_graph(G, flow, capacity); +// bool _augment=false; +// Node reached_t_node; + +// typedef typename AugGraph::NodeMap ReachedMap; +// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); +// for(typename std::list::const_iterator i=S.begin(); +// i!=S.end(); ++i) { +// res_bfs.pushAndSetReached(*i); +// } +// //res_bfs.pushAndSetReached(s); + +// typename AugGraph::NodeMap pred(res_graph); +// //filled up with invalid iterators + +// typename AugGraph::NodeMap free(res_graph); + +// //searching for augmenting path +// while ( !res_bfs.finished() ) { +// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); +// if (e.valid() && res_bfs.isBNodeNewlyReached()) { +// Node v=res_graph.tail(e); +// Node w=res_graph.head(e); +// pred.set(w, e); +// if (pred.get(v).valid()) { +// free.set(w, std::min(free.get(v), e.free())); +// } else { +// free.set(w, e.free()); +// } +// if (TMap.get(res_graph.head(e))) { +// _augment=true; +// reached_t_node=res_graph.head(e); +// break; +// } +// } + +// ++res_bfs; +// } //end of searching augmenting path + +// if (_augment) { +// Node n=reached_t_node; +// Number augment_value=free.get(reached_t_node); +// while (pred.get(n).valid()) { +// AugEdge e=pred.get(n); +// e.augment(augment_value); +// n=res_graph.tail(e); +// } +// } + +// return _augment; +// } +// void run() { +// while (augment()) { } +// } +// Number flowValue() { +// Number a=0; +// for(typename std::list::const_iterator i=S.begin(); +// i!=S.end(); ++i) { +// for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { +// a+=flow.get(e); +// } +// for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { +// a-=flow.get(e); +// } +// } +// return a; +// } +// }; + + + +} // namespace hugo + +#endif //EDMONDS_KARP_H diff -r de9849252e78 -r 44700ed9ffaa src/work/iterator_bfs_demo.cc --- a/src/work/iterator_bfs_demo.cc Thu Mar 11 23:31:13 2004 +0000 +++ b/src/work/iterator_bfs_demo.cc Fri Mar 12 09:19:54 2004 +0000 @@ -1,9 +1,11 @@ +// -*- c++ -*- #include #include #include -#include -#include +#include +#include +#include #include using namespace hugo; @@ -18,7 +20,7 @@ public: EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : graph(_graph), node_name_map(_node_name_map) { } - string get(typename Graph::EdgeIt e) const { + string get(typename Graph::Edge e) const { return (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); } @@ -26,24 +28,27 @@ int main (int, char*[]) { - typedef ListGraph::NodeIt NodeIt; - typedef ListGraph::EdgeIt EdgeIt; - //typedef ListGraph::EachNodeIt EachNodeIt; - //typedef ListGraph::EachEdgeIt EachEdgeIt; - //typedef ListGraph::OutEdgeIt OutEdgeIt; - //typedef ListGraph::InEdgeIt InEdgeIt; - //typedef ListGraph::SymEdgeIt SymEdgeIt; + //typedef SmartGraph Graph; + typedef ListGraph Graph; + + typedef Graph::Node Node; + typedef Graph::Edge Edge; + //typedef Graph::NodeIt NodeIt; + //typedef Graph::EdgeIt EdgeIt; + //typedef Graph::OutEdgeIt OutEdgeIt; + //typedef Graph::InEdgeIt InEdgeIt; + //typedef Graph::SymEdgeIt SymEdgeIt; - ListGraph G; + Graph G; - NodeIt s=G.addNode(); - NodeIt v1=G.addNode(); - NodeIt v2=G.addNode(); - NodeIt v3=G.addNode(); - NodeIt v4=G.addNode(); - NodeIt t=G.addNode(); + Node s=G.addNode(); + Node v1=G.addNode(); + Node v2=G.addNode(); + Node v3=G.addNode(); + Node v4=G.addNode(); + Node t=G.addNode(); - ListGraph::NodeMap node_name(G); + Graph::NodeMap node_name(G); node_name.set(s, "s"); node_name.set(v1, "v1"); node_name.set(v2, "v2"); @@ -72,72 +77,11 @@ cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; cout << " \\--> -------------> "<< endl; -/* - { - cout << "iterator bfs demo 4 ..." << endl; - BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap > bfs(G); - bfs.pushAndSetReached(s); - while (!bfs.finished()) { - if (OutEdgeIt(bfs).valid()) { - cout << "OutEdgeIt: " << bfs; - cout << " aNode: " << G.aNode(bfs); - cout << " bNode: " << G.bNode(bfs) << " "; - } else { - cout << "OutEdgeIt: " << "invalid"; - cout << " aNode: " << bfs.aNode(); - cout << " bNode: " << "invalid" << " "; - } - if (bfs.isBNodeNewlyReached()) { - cout << "bNodeIsNewlyReached "; - } else { - cout << "bNodeIsNotNewlyReached "; - } - if (bfs.isANodeExamined()) { - cout << "aNodeIsExamined "; - } else { - cout << "aNodeIsNotExamined "; - } - cout << endl; - ++bfs; - } - } - - { - cout << "iterator dfs demo 4 ..." << endl; - DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap > dfs(G); - dfs.pushAndSetReached(s); - while (!dfs.finished()) { - ++dfs; - if (OutEdgeIt(dfs).valid()) { - cout << "OutEdgeIt: " << dfs; - cout << " aNode: " << G.aNode(dfs); - cout << " bNode: " << G.bNode(dfs) << " "; - } else { - cout << "OutEdgeIt: " << "invalid"; - cout << " aNode: " << dfs.aNode(); - cout << " bNode: " << "invalid" << " "; - } - if (dfs.isBNodeNewlyReached()) { - cout << "bNodeIsNewlyReached "; - } else { - cout << "bNodeIsNotNewlyReached "; - } - if (dfs.isANodeExamined()) { - cout << "aNodeIsExamined "; - } else { - cout << "aNodeIsNotExamined "; - } - cout << endl; - //++dfs; - } - } -*/ - -// typedef TrivGraphWrapper CGW; +// typedef TrivGraphWrapper CGW; // CGW wG(G); // cout << "bfs and dfs demo on the directed graph" << endl; -// for(CGW::EachNodeIt n=wG.first(); n.valid(); ++n) { +// for(CGW::NodeIt n=wG.first(); n.valid(); ++n) { // cout << n << ": "; // cout << "out edges: "; // for(CGW::OutEdgeIt e=wG.first(n); e.valid(); ++e) @@ -149,13 +93,13 @@ // } { - typedef TrivGraphWrapper GW; + typedef TrivGraphWrapper GW; GW wG(G); - EdgeNameMap< GW, ListGraph::NodeMap > edge_name(wG, node_name); + EdgeNameMap< GW, Graph::NodeMap > edge_name(wG, node_name); cout << "bfs and dfs iterator demo on the directed graph" << endl; - for(GW::EachNodeIt n=wG.first(); wG.valid(n); wG.next(n)) { + for(GW::NodeIt n=wG.first(); wG.valid(n); wG.next(n)) { cout << node_name.get(n) << ": "; cout << "out edges: "; for(GW::OutEdgeIt e=wG.first(n); wG.valid(e); wG.next(e)) @@ -225,13 +169,13 @@ { - typedef RevGraphWrapper GW; + typedef RevGraphWrapper GW; GW wG(G); - EdgeNameMap< GW, ListGraph::NodeMap > edge_name(wG, node_name); + EdgeNameMap< GW, Graph::NodeMap > edge_name(wG, node_name); cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; - for(GW::EachNodeIt n=wG.first(); wG.valid(n); wG.next(n)) { + for(GW::NodeIt n=wG.first(); wG.valid(n); wG.next(n)) { cout << node_name.get(n) << ": "; cout << "out edges: "; for(GW::OutEdgeIt e=wG.first(n); wG.valid(e); wG.next(e)) @@ -300,13 +244,13 @@ } { - typedef UndirGraphWrapper GW; + typedef UndirGraphWrapper GW; GW wG(G); - EdgeNameMap< GW, ListGraph::NodeMap > edge_name(wG, node_name); + EdgeNameMap< GW, Graph::NodeMap > edge_name(wG, node_name); cout << "bfs and dfs iterator demo on the undirected graph" << endl; - for(GW::EachNodeIt n=wG.first(); wG.valid(n); wG.next(n)) { + for(GW::NodeIt n=wG.first(); wG.valid(n); wG.next(n)) { cout << node_name.get(n) << ": "; cout << "out edges: "; for(GW::OutEdgeIt e=wG.first(n); wG.valid(e); wG.next(e)) diff -r de9849252e78 -r 44700ed9ffaa src/work/jacint/preflow.h --- a/src/work/jacint/preflow.h Thu Mar 11 23:31:13 2004 +0000 +++ b/src/work/jacint/preflow.h Fri Mar 12 09:19:54 2004 +0000 @@ -526,9 +526,11 @@ }; -}//namespace marci -#endif +} //namespace hugo +#endif //PREFLOW_H + + diff -r de9849252e78 -r 44700ed9ffaa src/work/list_graph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/list_graph.h Fri Mar 12 09:19:54 2004 +0000 @@ -0,0 +1,562 @@ +// -*- c++ -*- +#ifndef LIST_GRAPH_H +#define LIST_GRAPH_H + +#include +#include + +#include + +namespace hugo { + + template + int count(It it) { + int i=0; + for( ; it.valid(); ++it) { ++i; } + return i; + } + + class ListGraph { + class node_item; + class edge_item; + public: + class Node; + class NodeIt; + class Edge; + class EdgeIt; + class OutEdgeIt; + class InEdgeIt; + class SymEdgeIt; + template class NodeMap; + template class EdgeMap; + private: + template friend class NodeMap; + template friend class EdgeMap; + + template + class NodeMap { + const ListGraph& G; + std::vector container; + public: + typedef T ValueType; + typedef Node KeyType; + NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { } + NodeMap(const ListGraph& _G, T a) : + G(_G), container(G.node_id, a) { } + void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; } + T get(Node n) const { return container[/*G.id(n)*/n.node->id]; } + T& operator[](Node n) { return container[/*G.id(n)*/n.node->id]; } + const T& operator[](Node n) const { + return container[/*G.id(n)*/n.node->id]; + } + void update() { container.resize(G.node_id); } + void update(T a) { container.resize(G.node_id, a); } + }; + + template + class EdgeMap { + const ListGraph& G; + std::vector container; + public: + typedef T ValueType; + typedef Edge KeyType; + EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { } + EdgeMap(const ListGraph& _G, T a) : + G(_G), container(G.edge_id, a) { } + void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; } + T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; } + T& operator[](Edge e) { return container[/*G.id(e)*/e.edge->id]; } + const T& operator[](Edge e) const { + return container[/*G.id(e)*/e.edge->id]; + } + void update() { container.resize(G.edge_id); } + void update(T a) { container.resize(G.edge_id, a); } + }; + + int node_id; + int edge_id; + int _node_num; + int _edge_num; + + node_item* _first_node; + node_item* _last_node; + + class node_item { + friend class ListGraph; + template friend class NodeMap; + + friend class Node; + friend class NodeIt; + friend class Edge; + friend class EdgeIt; + friend class OutEdgeIt; + friend class InEdgeIt; + friend class SymEdgeIt; + friend std::ostream& operator<<(std::ostream& os, const Node& i); + friend std::ostream& operator<<(std::ostream& os, const Edge& i); + //ListGraph* G; + int id; + edge_item* _first_out_edge; + edge_item* _last_out_edge; + edge_item* _first_in_edge; + edge_item* _last_in_edge; + node_item* _next_node; + node_item* _prev_node; + public: + node_item() { } + }; + + class edge_item { + friend class ListGraph; + template friend class EdgeMap; + + friend class Node; + friend class NodeIt; + friend class Edge; + friend class EdgeIt; + friend class OutEdgeIt; + friend class InEdgeIt; + friend class SymEdgeIt; + friend std::ostream& operator<<(std::ostream& os, const Edge& i); + //ListGraph* G; + int id; + node_item* _tail; + node_item* _head; + edge_item* _next_out; + edge_item* _prev_out; + edge_item* _next_in; + edge_item* _prev_in; + public: + edge_item() { } + }; + + node_item* _add_node() { + node_item* p=new node_item; + p->id=node_id++; + p->_first_out_edge=0; + p->_last_out_edge=0; + p->_first_in_edge=0; + p->_last_in_edge=0; + p->_prev_node=_last_node; + p->_next_node=0; + if (_last_node) _last_node->_next_node=p; + _last_node=p; + if (!_first_node) _first_node=p; + + ++_node_num; + return p; + } + + edge_item* _add_edge(node_item* _tail, node_item* _head) { + edge_item* e=new edge_item; + e->id=edge_id++; + e->_tail=_tail; + e->_head=_head; + + e->_prev_out=_tail->_last_out_edge; + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e; + _tail->_last_out_edge=e; + if (!_tail->_first_out_edge) _tail->_first_out_edge=e; + e->_next_out=0; + + e->_prev_in=_head->_last_in_edge; + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; + _head->_last_in_edge=e; + if (!_head->_first_in_edge) { _head->_first_in_edge=e; } + e->_next_in=0; + + ++_edge_num; + return e; + } + + //deletes a node which has no out edge and no in edge + void _delete_node(node_item* v) { + if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else + _last_node=v->_prev_node; + if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else + _first_node=v->_next_node; + + delete v; + --_node_num; + } + + void _delete_edge(edge_item* e) { + if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else + (e->_tail)->_last_out_edge=e->_prev_out; + if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else + (e->_tail)->_first_out_edge=e->_next_out; + if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else + (e->_head)->_last_in_edge=e->_prev_in; + if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else + (e->_head)->_first_in_edge=e->_next_in; + + delete e; + --_edge_num; + } + + void _set_tail(edge_item* e, node_item* _tail) { + if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else + (e->_tail)->_last_out_edge=e->_prev_out; + if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else + (e->_tail)->_first_out_edge=e->_next_out; + + e->_tail=_tail; + + e->_prev_out=_tail->_last_out_edge; + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e; + _tail->_last_out_edge=e; + if (!_tail->_first_out_edge) _tail->_first_out_edge=e; + e->_next_out=0; + } + + void _set_head(edge_item* e, node_item* _head) { + if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else + (e->_head)->_last_in_edge=e->_prev_in; + if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else + (e->_head)->_first_in_edge=e->_next_in; + + e->_head=_head; + + e->_prev_in=_head->_last_in_edge; + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e; + _head->_last_in_edge=e; + if (!_head->_first_in_edge) { _head->_first_in_edge=e; } + e->_next_in=0; + } + + public: + + /* default constructor */ + + ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { } + + ~ListGraph() { + while (first().valid()) erase(first()); + } + + int nodeNum() const { return _node_num; } + int edgeNum() const { return _edge_num; } + + /* functions to construct iterators from the graph, or from each other */ + + //NodeIt firstNode() const { return NodeIt(*this); } + //EdgeIt firstEdge() const { return EdgeIt(*this); } + + //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); } + //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); } + //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); } + Node tail(Edge e) const { return e.tailNode(); } + Node head(Edge e) const { return e.headNode(); } + + Node aNode(const OutEdgeIt& e) const { return e.aNode(); } + Node aNode(const InEdgeIt& e) const { return e.aNode(); } + Node aNode(const SymEdgeIt& e) const { return e.aNode(); } + + Node bNode(const OutEdgeIt& e) const { return e.bNode(); } + Node bNode(const InEdgeIt& e) const { return e.bNode(); } + Node bNode(const SymEdgeIt& e) const { return e.bNode(); } + + //Node invalid_node() { return Node(); } + //Edge invalid_edge() { return Edge(); } + //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); } + //InEdgeIt invalid_in_edge() { return InEdgeIt(); } + //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); } + + /* same methods in other style */ + /* for experimental purpose */ + + NodeIt& /*getF*/first(NodeIt& v) const { + v=NodeIt(*this); return v; } + EdgeIt& /*getF*/first(EdgeIt& e) const { + e=EdgeIt(*this); return e; } + OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { + e=OutEdgeIt(*this, v); return e; } + InEdgeIt& /*getF*/first(InEdgeIt& e, Node v) const { + e=InEdgeIt(*this, v); return e; } + SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const { + e=SymEdgeIt(*this, v); return e; } + //void getTail(Node& n, const Edge& e) const { n=tail(e); } + //void getHead(Node& n, const Edge& e) const { n=head(e); } + + //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); } + //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); } + //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); } + //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); } + //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); } + //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); } + //void get_invalid(Node& n) { n=Node(); } + //void get_invalid(Edge& e) { e=Edge(); } + //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); } + //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); } + //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); } + + template< typename It > + It first() const { + It e; + /*getF*/first(e); + return e; + } + + template< typename It > + It first(Node v) const { + It e; + /*getF*/first(e, v); + return e; + } + + bool valid(Node n) const { return n.valid(); } + bool valid(Edge e) const { return e.valid(); } + + template It getNext(It it) const { + It tmp(it); return next(tmp); } + template It& next(It& it) const { return ++it; } + + + /* for getting id's of graph objects */ + /* these are important for the implementation of property vectors */ + + int id(Node v) const { return v.node->id; } + int id(Edge e) const { return e.edge->id; } + + /* adding nodes and edges */ + + Node addNode() { return Node(_add_node()); } + Edge addEdge(Node u, Node v) { + return Edge(_add_edge(u.node, v.node)); + } + + void erase(Node i) { + while (first(i).valid()) erase(first(i)); + while (first(i).valid()) erase(first(i)); + _delete_node(i.node); + } + + void erase(Edge e) { _delete_edge(e.edge); } + + void clear() { + while (first().valid()) erase(first()); + } + + void setTail(Edge e, Node tail) { + _set_tail(e.edge, tail.node); + } + + void setHead(Edge e, Node head) { + _set_head(e.edge, head.node); + } + + /* stream operations, for testing purpose */ + + friend std::ostream& operator<<(std::ostream& os, const Node& i) { + os << i.node->id; return os; + } + friend std::ostream& operator<<(std::ostream& os, const Edge& i) { + os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; + return os; + } + + class Node { + friend class ListGraph; + template friend class NodeMap; + + friend class Edge; + friend class OutEdgeIt; + friend class InEdgeIt; + friend class SymEdgeIt; + //public: //FIXME: It is required by op= of NodeIt + protected: + node_item* node; + protected: + friend int ListGraph::id(Node v) const; + public: + Node() /*: node(0)*/ { } + Node(const Invalid&) : node(0) { } + protected: + Node(node_item* _node) : node(_node) { } + bool valid() const { return (node); } + public: + //void makeInvalid() { node=0; } + friend bool operator==(Node u, Node v) { return v.node==u.node; } + friend bool operator!=(Node u, Node v) { return v.node!=u.node; } + friend std::ostream& operator<<(std::ostream& os, const Node& i); + }; + + class NodeIt : public Node { + friend class ListGraph; + //protected: + public: //for everybody but marci + NodeIt(const ListGraph& G) : Node(G._first_node) { } + public: + NodeIt() : Node() { } + NodeIt(const Invalid& i) : Node(i) { } + protected: + NodeIt(node_item* v) : Node(v) { } + NodeIt& operator++() { node=node->_next_node; return *this; } + //FIXME:: + // NodeIt& operator=(const Node& e) + // { node=e.node; return *this; } + }; + + class Edge { + friend class ListGraph; + template friend class EdgeMap; + + friend class Node; + friend class NodeIt; + protected: + edge_item* edge; + friend int ListGraph::id(Edge e) const; + public: + Edge() /*: edge(0)*/ { } + Edge(const Invalid&) : edge(0) { } + //Edge() { } + protected: + Edge(edge_item* _edge) : edge(_edge) { } + bool valid() const { return (edge); } + public: + //void makeInvalid() { edge=0; } + friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; } + friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; } + protected: + Node tailNode() const { return Node(edge->_tail); } + Node headNode() const { return Node(edge->_head); } + public: + friend std::ostream& operator<<(std::ostream& os, const Edge& i); + }; + + class EdgeIt : public Edge { + friend class ListGraph; + //protected: + public: //for alpar + EdgeIt(const ListGraph& G) { + node_item* v=G._first_node; + if (v) edge=v->_first_out_edge; else edge=0; + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } + } + public: + EdgeIt() : Edge() { } + EdgeIt(const Invalid& i) : Edge(i) { } + protected: + EdgeIt(edge_item* _e) : Edge(_e) { } + EdgeIt& operator++() { + node_item* v=edge->_tail; + edge=edge->_next_out; + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } + return *this; + } + }; + + class OutEdgeIt : public Edge { + friend class ListGraph; + //node_item* v; + //protected: + protected: //for alpar + OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; } + public: + OutEdgeIt() : Edge()/*, v(0)*/ { } + OutEdgeIt(const Invalid& i) : Edge(i) { } + OutEdgeIt(const ListGraph& G, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; } + protected: + OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } + protected: + Node aNode() const { return Node(edge->_tail); } + Node bNode() const { return Node(edge->_head); } + }; + + class InEdgeIt : public Edge { + friend class ListGraph; + //node_item* v; + //protected: + protected: //for alpar + InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; } + public: + InEdgeIt() : Edge()/*, v(0)*/ { } + InEdgeIt(const Invalid& i) : Edge(i) { } + InEdgeIt(const ListGraph& G, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; } + protected: + InEdgeIt& operator++() { edge=edge->_next_in; return *this; } + protected: + Node aNode() const { return Node(edge->_head); } + Node bNode() const { return Node(edge->_tail); } + }; + + class SymEdgeIt : public Edge { + friend class ListGraph; + bool out_or_in; //1 iff out, 0 iff in + //node_item* v; + //protected: + public: //for alpar + SymEdgeIt(const Node& _v) /*: v(_v.node)*/ { + out_or_in=1; + edge=_v.node->_first_out_edge; + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; } + } + public: + SymEdgeIt() : Edge() /*, v(0)*/ { } + SymEdgeIt(const Invalid& i) : Edge(i) { } + SymEdgeIt(const ListGraph& G, Node _v) /*: v(_v.node)*/ { + out_or_in=1; + edge=_v.node->_first_out_edge; + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; } + } + protected: + SymEdgeIt& operator++() { + if (out_or_in) { + node_item* v=edge->_tail; + edge=edge->_next_out; + if (!edge) { out_or_in=0; edge=v->_first_in_edge; } + } else { + edge=edge->_next_in; + } + return *this; + } + protected: + Node aNode() const { + return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); } + Node bNode() const { + return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); } + }; + + }; + +// template< typename T > +// T ListGraph::first() const { +// std::cerr << "Invalid use of template T ListGraph::first();" << std::endl; +// return T(); +// } + +// template<> +// ListGraph::NodeIt ListGraph::first() const { +// return firstNode(); +// } + +// template<> +// ListGraph::EdgeIt ListGraph::first() const { +// return firstEdge(); +// } + +// template< typename T > +// T ListGraph::first(ListGraph::Node v) const { +// std::cerr << "Invalid use of template T ListGraph::first(ListGRaph::Node);" << std::endl; +// return T(); +// } + +// template<> +// ListGraph::OutEdgeIt ListGraph::first(const ListGraph::Node v) const { +// return firstOutEdge(v); +// } + +// template<> +// ListGraph::InEdgeIt ListGraph::first(const ListGraph::Node v) const { +// return firstInEdge(v); +// } + +// template<> +// ListGraph::SymEdgeIt ListGraph::first(const ListGraph::Node v) const { +// return firstSymEdge(v); +// } + + +} //namespace hugo + +#endif //LIST_GRAPH_H diff -r de9849252e78 -r 44700ed9ffaa src/work/marci/dimacs.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/marci/dimacs.h Fri Mar 12 09:19:54 2004 +0000 @@ -0,0 +1,62 @@ +// -*- c++ -*- +#ifndef DIMACS_H +#define DIMACS_H + +#include +#include +#include + +namespace hugo { + + template + void readDimacsMaxFlow(std::istream& is, Graph &G, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { + G.clear(); + int cap; + char d; + std::string problem; + char c; + int i, j; + std::string str; + int n, m; + std::vector nodes; + while (is>>c) { + switch (c) { + case 'c': //comment + getline(is, str); + break; +// case 't': //type +// getline(is, str); +// break; + case 'p': //problem definition + is >> problem >> n >> m; + getline(is, str); + nodes.resize(n+1); + for (int k=1; k<=n; ++k) nodes[k]=G.addNode(); + break; + case 'n': //node definition + if (problem=="sp") { //shortest path problem + is >> i; + getline(is, str); + s=nodes[i]; + } + if (problem=="max") { //max flow problem + is >> i >> d; + getline(is, str); + if (d=='s') s=nodes[i]; + if (d=='t') t=nodes[i]; + } + break; + case 'a': + is >> i >> j >> cap; + getline(is, str); + typename Graph::Edge e=G.addEdge(nodes[i], nodes[j]); + capacity.update(); + capacity.set(e, cap); + break; + } + } + } + +} //namespace hugo + +#endif //DIMACS_H diff -r de9849252e78 -r 44700ed9ffaa src/work/marci/edmonds_karp_demo.cc --- a/src/work/marci/edmonds_karp_demo.cc Thu Mar 11 23:31:13 2004 +0000 +++ b/src/work/marci/edmonds_karp_demo.cc Fri Mar 12 09:19:54 2004 +0000 @@ -1,9 +1,11 @@ +// -*- c++ -*- #include #include -#include -#include -#include +#include +#include +#include +#include #include #include @@ -12,157 +14,160 @@ // Use a DIMACS max flow file as stdin. // read_dimacs_demo < dimacs_max_flow_file -/* - struct Ize { - }; + +// struct Ize { +// }; - struct Mize { - Ize bumm; - }; +// struct Mize { +// Ize bumm; +// }; - template - class Huha { - public: - int u; - B brr; - }; -*/ +// template +// class Huha { +// public: +// int u; +// B brr; +// }; + int main(int, char **) { - typedef ListGraph::NodeIt NodeIt; - typedef ListGraph::EachEdgeIt EachEdgeIt; -/* - Mize mize[10]; - Mize bize[0]; - Mize zize; - typedef Mize Tize[0]; + typedef ListGraph MutableGraph; - std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; - std::cout << sizeof(bize) << std::endl; + typedef SmartGraph Graph; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; - Huha k; - std::cout << sizeof(k) << std::endl; +// Mize mize[10]; +// Mize bize[0]; +// Mize zize; +// typedef Mize Tize[0]; +// std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; +// std::cout << sizeof(bize) << std::endl; - struct Bumm { - //int a; - bool b; - }; - std::cout << sizeof(Bumm) << std::endl; -*/ +// Huha k; +// std::cout << sizeof(k) << std::endl; - ListGraph G; - NodeIt s, t; - ListGraph::EdgeMap cap(G); + +// struct Bumm { +// //int a; +// bool b; +// }; + +// std::cout << sizeof(Bumm) << std::endl; + + + Graph G; + Node s, t; + Graph::EdgeMap cap(G); readDimacsMaxFlow(std::cin, G, s, t, cap); -/* - typedef TrivGraphWrapper TGW; - TGW gw(G); - TGW::EachNodeIt sw; - gw.getFirst(sw); - std::cout << "p1:" << gw.nodeNum() << std::endl; - gw.erase(sw); - std::cout << "p2:" << gw.nodeNum() << std::endl; - typedef const ListGraph cLG; - typedef TrivGraphWrapper CTGW; - CTGW cgw(G); - CTGW::EachNodeIt csw; - cgw.getFirst(csw); - std::cout << "p1:" << cgw.nodeNum() << std::endl; - //cgw.erase(csw); - std::cout << "p2:" << cgw.nodeNum() << std::endl; -*/ +// typedef TrivGraphWrapper TGW; +// TGW gw(G); +// TGW::NodeIt sw; +// gw./*getF*/first(sw); +// std::cout << "p1:" << gw.nodeNum() << std::endl; +// gw.erase(sw); +// std::cout << "p2:" << gw.nodeNum() << std::endl; + +// typedef const Graph cLG; +// typedef TrivGraphWrapper CTGW; +// CTGW cgw(G); +// CTGW::NodeIt csw; +// cgw./*getF*/first(csw); +// std::cout << "p1:" << cgw.nodeNum() << std::endl; +// //cgw.erase(csw); +// std::cout << "p2:" << cgw.nodeNum() << std::endl; + { - std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; - ListGraph::EdgeMap flow(G); //0 flow + std::cout << "SmartGraph..." << std::endl; + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow - Timer ts; - ts.reset(); - //double pre_time=currTime(); - MaxFlow, ListGraph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); - int i=0; - while (max_flow_test.augmentOnBlockingFlow()) { -// for(EachEdgeIt e=G.template first(); e.valid(); ++e) { + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + //max_flow_test.augmentWithBlockingFlow(); + int i=0; + while (max_flow_test.augmentOnBlockingFlow()) { +// for(EdgeIt e=G.template first(); e.valid(); ++e) { // std::cout<<"("<"<(); e.valid(); ++e) { - // std::cout<<"("<"<(); e.valid(); ++e) { +// std::cout<<"("<"< flow(G); //0 flow + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow - Timer ts; - ts.reset(); - //double pre_time=currTime(); - MaxFlow, ListGraph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); - int i=0; - while (max_flow_test.augmentOnBlockingFlow2()) { -// for(EachEdgeIt e=G.template first(); e.valid(); ++e) { + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + //max_flow_test.augmentWithBlockingFlow(); + int i=0; + while (max_flow_test.augmentOnBlockingFlow2()) { +// for(EdgeIt e=G.template first(); e.valid(); ++e) { // std::cout<<"("<"<(); e.valid(); ++e) { - // std::cout<<"("<"<(); e.valid(); ++e) { +// std::cout<<"("<"< flow(G); //0 flow + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow - Timer ts; - ts.reset(); - //double pre_time=currTime(); - MaxFlow, ListGraph::EdgeMap > max_flow_test(G, s, t, flow, cap); - //max_flow_test.augmentWithBlockingFlow(); - int i=0; - while (max_flow_test.augmentOnShortestPath()) { -// for(EachEdgeIt e=G.template first(); e.valid(); ++e) { + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + //max_flow_test.augmentWithBlockingFlow(); + int i=0; + while (max_flow_test.augmentOnShortestPath()) { +// for(EdgeIt e=G.template first(); e.valid(); ++e) { // std::cout<<"("<"<(); e.valid(); ++e) { +// std::cout<<"("<"<(); e.valid(); ++e) { - // std::cout<<"("<"< + namespace hugo { template @@ -11,14 +13,14 @@ public: typedef Graph BaseGraph; + typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EachNodeIt EachNodeIt; - typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt OutEdgeIt; typedef typename Graph::InEdgeIt InEdgeIt; //typedef typename Graph::SymEdgeIt SymEdgeIt; - typedef typename Graph::EachEdgeIt EachEdgeIt; + typedef typename Graph::EdgeIt EdgeIt; //TrivGraphWrapper() : graph(0) { } TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } @@ -26,22 +28,22 @@ void setGraph(Graph& _graph) { graph = &_graph; } Graph& getGraph() const { return (*graph); } - template I& getFirst(I& i) const { return graph->getFirst(i); } - template I& getFirst(I& i, const P& p) const { - return graph->getFirst(i, p); } + template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } + template I& /*getF*/first(I& i, const P& p) const { + return graph->/*getF*/first(i, p); } template I getNext(const I& i) const { return graph->getNext(i); } template I& next(I &i) const { return graph->next(i); } template< typename It > It first() const { - It e; getFirst(e); return e; } + It e; /*getF*/first(e); return e; } - template< typename It > It first(const NodeIt& v) const { - It e; getFirst(e, v); return e; } + template< typename It > It first(const Node& v) const { + It e; /*getF*/first(e, v); return e; } - NodeIt head(const EdgeIt& e) const { return graph->head(e); } - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } + Node head(const Edge& e) const { return graph->head(e); } + Node tail(const Edge& e) const { return graph->tail(e); } template bool valid(const I& i) const { return graph->valid(i); } @@ -52,13 +54,13 @@ int nodeNum() const { return graph->nodeNum(); } int edgeNum() const { return graph->edgeNum(); } - template NodeIt aNode(const I& e) const { + template Node aNode(const I& e) const { return graph->aNode(e); } - template NodeIt bNode(const I& e) const { + template Node bNode(const I& e) const { return graph->bNode(e); } - NodeIt addNode() const { return graph->addNode(); } - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { + Node addNode() const { return graph->addNode(); } + Edge addEdge(const Node& tail, const Node& head) const { return graph->addEdge(tail, head); } template void erase(const I& i) const { graph->erase(i); } @@ -90,14 +92,14 @@ public: typedef Graph BaseGraph; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EachNodeIt EachNodeIt; + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EdgeIt EdgeIt; + typedef typename Graph::Edge Edge; typedef typename Graph::OutEdgeIt InEdgeIt; typedef typename Graph::InEdgeIt OutEdgeIt; //typedef typename Graph::SymEdgeIt SymEdgeIt; - typedef typename Graph::EachEdgeIt EachEdgeIt; + typedef typename Graph::EdgeIt EdgeIt; //RevGraphWrapper() : graph(0) { } RevGraphWrapper(Graph& _graph) : graph(&_graph) { } @@ -105,22 +107,22 @@ void setGraph(Graph& _graph) { graph = &_graph; } Graph& getGraph() const { return (*graph); } - template I& getFirst(I& i) const { return graph->getFirst(i); } - template I& getFirst(I& i, const P& p) const { - return graph->getFirst(i, p); } + template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } + template I& /*getF*/first(I& i, const P& p) const { + return graph->/*getF*/first(i, p); } template I getNext(const I& i) const { return graph->getNext(i); } template I& next(I &i) const { return graph->next(i); } template< typename It > It first() const { - It e; getFirst(e); return e; } + It e; /*getF*/first(e); return e; } - template< typename It > It first(const NodeIt& v) const { - It e; getFirst(e, v); return e; } + template< typename It > It first(const Node& v) const { + It e; /*getF*/first(e, v); return e; } - NodeIt head(const EdgeIt& e) const { return graph->tail(e); } - NodeIt tail(const EdgeIt& e) const { return graph->head(e); } + Node head(const Edge& e) const { return graph->tail(e); } + Node tail(const Edge& e) const { return graph->head(e); } template bool valid(const I& i) const { return graph->valid(i); } @@ -128,13 +130,13 @@ //template void setInvalid(const I &i); //{ return graph->setInvalid(i); } - template NodeIt aNode(const I& e) const { + template Node aNode(const I& e) const { return graph->aNode(e); } - template NodeIt bNode(const I& e) const { + template Node bNode(const I& e) const { return graph->bNode(e); } - NodeIt addNode() const { return graph->addNode(); } - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { + Node addNode() const { return graph->addNode(); } + Edge addEdge(const Node& tail, const Node& head) const { return graph->addEdge(tail, head); } int nodeNum() const { return graph->nodeNum(); } @@ -169,17 +171,17 @@ public: typedef Graph BaseGraph; + typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EachNodeIt EachNodeIt; - //typedef typename Graph::EdgeIt EdgeIt; + //typedef typename Graph::Edge Edge; //typedef typename Graph::OutEdgeIt OutEdgeIt; //typedef typename Graph::InEdgeIt InEdgeIt; //typedef typename Graph::SymEdgeIt SymEdgeIt; - //typedef typename Graph::EachEdgeIt EachEdgeIt; + //typedef typename Graph::EdgeIt EdgeIt; //private: - typedef typename Graph::EdgeIt GraphEdgeIt; + typedef typename Graph::Edge GraphEdge; typedef typename Graph::OutEdgeIt GraphOutEdgeIt; typedef typename Graph::InEdgeIt GraphInEdgeIt; //public: @@ -190,48 +192,63 @@ void setGraph(Graph& _graph) { graph = &_graph; } Graph& getGraph() const { return (*graph); } - class EdgeIt { + class Edge { friend class UndirGraphWrapper; bool out_or_in; //true iff out GraphOutEdgeIt out; GraphInEdgeIt in; public: - EdgeIt() : out_or_in(true), out(), in() { } - operator GraphEdgeIt() const { + Edge() : out_or_in(), out(), in() { } + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } + operator GraphEdge() const { if (out_or_in) return(out); else return(in); } + friend bool operator==(const Edge& u, const Edge& v) { + if (v.out_or_in) + return (u.out_or_in && u.out==v.out); + else + return (!u.out_or_in && u.in==v.in); + } + friend bool operator!=(const Edge& u, const Edge& v) { + if (v.out_or_in) + return (!u.out_or_in || u.out!=v.out); + else + return (u.out_or_in || u.in!=v.in); + } }; - class OutEdgeIt : public EdgeIt { + class OutEdgeIt : public Edge { friend class UndirGraphWrapper; public: - OutEdgeIt() : EdgeIt() { } - OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { - _G.graph->getFirst(out, n); + OutEdgeIt() : Edge() { } + OutEdgeIt(const Invalid& i) : Edge(i) { } + OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { + out_or_in=true; + _G.graph->/*getF*/first(out, n); if (!(_G.graph->valid(out))) { out_or_in=false; - _G.graph->getFirst(in, n); + _G.graph->/*getF*/first(in, n); } } }; - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { + OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { e.out_or_in=true; - graph->getFirst(e.out, n); + graph->/*getF*/first(e.out, n); if (!(graph->valid(e.out))) { e.out_or_in=false; - graph->getFirst(e.in, n); + graph->/*getF*/first(e.in, n); } return e; } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - NodeIt n=graph->tail(e.out); + Node n=graph->tail(e.out); graph->next(e.out); if (!graph->valid(e.out)) { e.out_or_in=false; - graph->getFirst(e.in, n); + graph->/*getF*/first(e.in, n); } } else { graph->next(e.in); @@ -239,29 +256,29 @@ return e; } - NodeIt aNode(const OutEdgeIt& e) const { + Node aNode(const OutEdgeIt& e) const { if (e.out_or_in) return graph->tail(e); else return graph->head(e); } - NodeIt bNode(const OutEdgeIt& e) const { + Node bNode(const OutEdgeIt& e) const { if (e.out_or_in) return graph->head(e); else return graph->tail(e); } typedef OutEdgeIt InEdgeIt; - template I& getFirst(I& i) const { return graph->getFirst(i); } -// template I& getFirst(I& i, const P& p) const { -// return graph->getFirst(i, p); } + template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } +// template I& /*getF*/first(I& i, const P& p) const { +// return graph->/*getF*/first(i, p); } template I getNext(const I& i) const { return graph->getNext(i); } template I& next(I &i) const { return graph->next(i); } template< typename It > It first() const { - It e; getFirst(e); return e; } + It e; /*getF*/first(e); return e; } - template< typename It > It first(const NodeIt& v) const { - It e; getFirst(e, v); return e; } + template< typename It > It first(const Node& v) const { + It e; /*getF*/first(e, v); return e; } - NodeIt head(const EdgeIt& e) const { return graph->head(e); } - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } + Node head(const Edge& e) const { return graph->head(e); } + Node tail(const Edge& e) const { return graph->tail(e); } template bool valid(const I& i) const { return graph->valid(i); } @@ -272,13 +289,13 @@ int nodeNum() const { return graph->nodeNum(); } int edgeNum() const { return graph->edgeNum(); } -// template NodeIt aNode(const I& e) const { +// template Node aNode(const I& e) const { // return graph->aNode(e); } -// template NodeIt bNode(const I& e) const { +// template Node bNode(const I& e) const { // return graph->bNode(e); } - NodeIt addNode() const { return graph->addNode(); } - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { + Node addNode() const { return graph->addNode(); } + Edge addEdge(const Node& tail, const Node& head) const { return graph->addEdge(tail, head); } template void erase(const I& i) const { graph->erase(i); } @@ -312,10 +329,10 @@ // public: // typedef Graph BaseGraph; +// typedef typename Graph::Node Node; +// typedef typename Graph::Edge Edge; + // typedef typename Graph::NodeIt NodeIt; -// typedef typename Graph::EdgeIt EdgeIt; - -// typedef typename Graph::EachNodeIt EachNodeIt; // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon // //iranyitatlant, ami van @@ -323,29 +340,29 @@ // typedef typename Graph::OutEdgeIt SymEdgeIt; // //typedef typename Graph::InEdgeIt SymEdgeIt; // //typedef typename Graph::SymEdgeIt SymEdgeIt; -// typedef typename Graph::EachEdgeIt EachEdgeIt; +// typedef typename Graph::EdgeIt EdgeIt; // int nodeNum() const { return graph->nodeNum(); } // int edgeNum() const { return graph->edgeNum(); } -// template I& getFirst(I& i) const { return graph->getFirst(i); } -// template I& getFirst(I& i, const P& p) const { -// return graph->getFirst(i, p); } +// template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } +// template I& /*getF*/first(I& i, const P& p) const { +// return graph->/*getF*/first(i, p); } // //template I next(const I i); { return graph->goNext(i); } // //template I &goNext(I &i); { return graph->goNext(i); } // template< typename It > It first() const { -// It e; getFirst(e); return e; } +// It e; /*getF*/first(e); return e; } -// template< typename It > It first(NodeIt v) const { -// It e; getFirst(e, v); return e; } +// template< typename It > It first(Node v) const { +// It e; /*getF*/first(e, v); return e; } -// NodeIt head(const EdgeIt& e) const { return graph->head(e); } -// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } +// Node head(const Edge& e) const { return graph->head(e); } +// Node tail(const Edge& e) const { return graph->tail(e); } -// template NodeIt aNode(const I& e) const { +// template Node aNode(const I& e) const { // return graph->aNode(e); } -// template NodeIt bNode(const I& e) const { +// template Node bNode(const I& e) const { // return graph->bNode(e); } // //template bool valid(const I i); @@ -354,8 +371,8 @@ // //template void setInvalid(const I &i); // //{ return graph->setInvalid(i); } -// NodeIt addNode() { return graph->addNode(); } -// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { +// Node addNode() { return graph->addNode(); } +// Edge addEdge(const Node& tail, const Node& head) { // return graph->addEdge(tail, head); } // template void erase(const I& i) { graph->erase(i); } @@ -377,192 +394,207 @@ class ResGraphWrapper { public: typedef Graph BaseGraph; + typedef typename Graph::Node Node; typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::EachNodeIt EachNodeIt; private: typedef typename Graph::OutEdgeIt OldOutEdgeIt; typedef typename Graph::InEdgeIt OldInEdgeIt; - const Graph* G; + const Graph* graph; FlowMap* flow; const CapacityMap* capacity; public: ResGraphWrapper(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : - G(&_G), flow(&_flow), capacity(&_capacity) { } -// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : -// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } + graph(&_G), flow(&_flow), capacity(&_capacity) { } void setGraph(const Graph& _graph) { graph = &_graph; } - const Graph& getGraph() const { return (*G); } + const Graph& getGraph() const { return (*graph); } - class EdgeIt; + class Edge; class OutEdgeIt; - friend class EdgeIt; + friend class Edge; friend class OutEdgeIt; - class EdgeIt { + class Edge { friend class ResGraphWrapper; protected: bool out_or_in; //true, iff out OldOutEdgeIt out; OldInEdgeIt in; public: - EdgeIt() : out_or_in(true) { } + Edge() : out_or_in(true) { } + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } // bool valid() const { // return out_or_in && out.valid() || in.valid(); } + friend bool operator==(const Edge& u, const Edge& v) { + if (v.out_or_in) + return (u.out_or_in && u.out==v.out); + else + return (!u.out_or_in && u.in==v.in); + } + friend bool operator!=(const Edge& u, const Edge& v) { + if (v.out_or_in) + return (!u.out_or_in || u.out!=v.out); + else + return (u.out_or_in || u.in!=v.in); + } }; - class OutEdgeIt : public EdgeIt { + class OutEdgeIt : public Edge { friend class ResGraphWrapper; public: OutEdgeIt() { } //FIXME - OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { } + OutEdgeIt(const Edge& e) : Edge(e) { } + OutEdgeIt(const Invalid& i) : Edge(i) { } private: - OutEdgeIt(const ResGraphWrapper& resG, NodeIt v) : EdgeIt() { - resG.G->getFirst(out, v); - while( out.valid() && !(resG.free(out)>0) ) { ++out; } - if (!out.valid()) { + OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { + resG.graph->/*getF*/first(out, v); + while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } + if (!resG.graph->valid(out)) { out_or_in=0; - resG.G->getFirst(in, v); - while( in.valid() && !(resG.free(in)>0) ) { ++in; } + resG.graph->/*getF*/first(in, v); + while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } } } // public: // OutEdgeIt& operator++() { // if (out_or_in) { -// NodeIt v=/*resG->*/G->aNode(out); +// Node v=/*resG->*/G->aNode(out); // ++out; -// while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } +// while( out.valid() && !(Edge::free()>0) ) { ++out; } // if (!out.valid()) { // out_or_in=0; -// G->getFirst(in, v); -// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } +// G->/*getF*/first(in, v); +// while( in.valid() && !(Edge::free()>0) ) { ++in; } // } // } else { // ++in; -// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } +// while( in.valid() && !(Edge::free()>0) ) { ++in; } // } // return *this; // } }; - class EachEdgeIt : public EdgeIt { + class EdgeIt : public Edge { friend class ResGraphWrapper; - typename Graph::EachNodeIt v; + typename Graph::NodeIt v; public: - EachEdgeIt() { } - //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } - EachEdgeIt(const ResGraphWrapper& resG) : EdgeIt() { - resG.G->getFirst(v); - if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt(); - while (out.valid() && !(resG.free(out)>0) ) { ++out; } - while (v.valid() && !out.valid()) { - ++v; - if (v.valid()) resG.G->getFirst(out, v); - while (out.valid() && !(resG.free(out)>0) ) { ++out; } + EdgeIt() { } + //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } + EdgeIt(const Invalid& i) : Edge(i) { } + EdgeIt(const ResGraphWrapper& resG) : Edge() { + resG.graph->/*getF*/first(v); + if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID); + while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } + while (resG.graph->valid(v) && !resG.graph->valid(out)) { + resG.graph->next(v); + if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); + while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } } - if (!out.valid()) { + if (!resG.graph->valid(out)) { out_or_in=0; - resG.G->getFirst(v); - if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt(); - while (in.valid() && !(resG.free(in)>0) ) { ++in; } - while (v.valid() && !in.valid()) { - ++v; - if (v.valid()) resG.G->getFirst(in, v); - while (in.valid() && !(resG.free(in)>0) ) { ++in; } + resG.graph->/*getF*/first(v); + if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID); + while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } + while (resG.graph->valid(v) && !resG.graph->valid(in)) { + resG.graph->next(v); + if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); + while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } } } } -// EachEdgeIt& operator++() { +// EdgeIt& operator++() { // if (out_or_in) { // ++out; -// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } +// while (out.valid() && !(Edge::free()>0) ) { ++out; } // while (v.valid() && !out.valid()) { // ++v; -// if (v.valid()) G->getFirst(out, v); -// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } +// if (v.valid()) G->/*getF*/first(out, v); +// while (out.valid() && !(Edge::free()>0) ) { ++out; } // } // if (!out.valid()) { // out_or_in=0; -// G->getFirst(v); -// if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } +// G->/*getF*/first(v); +// if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt(); +// while (in.valid() && !(Edge::free()>0) ) { ++in; } // while (v.valid() && !in.valid()) { // ++v; -// if (v.valid()) G->getFirst(in, v); -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } +// if (v.valid()) G->/*getF*/first(in, v); +// while (in.valid() && !(Edge::free()>0) ) { ++in; } // } // } // } else { // ++in; -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } +// while (in.valid() && !(Edge::free()>0) ) { ++in; } // while (v.valid() && !in.valid()) { // ++v; -// if (v.valid()) G->getFirst(in, v); -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } +// if (v.valid()) G->/*getF*/first(in, v); +// while (in.valid() && !(Edge::free()>0) ) { ++in; } // } // } // return *this; // } }; - EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); } - OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { + NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); } + OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { e=OutEdgeIt(*this, v); + return e; } - EachEdgeIt& getFirst(EachEdgeIt& e) const { - e=EachEdgeIt(*this); + EdgeIt& /*getF*/first(EdgeIt& e) const { + e=EdgeIt(*this); + return e; } - EachNodeIt& next(EachNodeIt& n) const { return G->next(n); } + NodeIt& next(NodeIt& n) const { return graph->next(n); } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - NodeIt v=G->aNode(e.out); - ++(e.out); - while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } - if (!G->valid(e.out)) { + Node v=graph->aNode(e.out); + graph->next(e.out); + while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } + if (!graph->valid(e.out)) { e.out_or_in=0; - G->getFirst(e.in, v); - while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } + graph->/*getF*/first(e.in, v); + while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } } else { - ++(e.in); - while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } + graph->next(e.in); + while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } return e; } - EachEdgeIt& next(EachEdgeIt& e) const { + EdgeIt& next(EdgeIt& e) const { if (e.out_or_in) { - ++(e.out); - while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } - while (G->valid(e.v) && !G->valid(e.out)) { - ++(e.v); - if (G->valid(e.v)) G->getFirst(e.out, e.v); - while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); } + graph->next(e.out); + while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } + while (graph->valid(e.v) && !graph->valid(e.out)) { + graph->next(e.v); + if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v); + while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } } - if (!G->valid(e.out)) { + if (!graph->valid(e.out)) { e.out_or_in=0; - G->getFirst(e.v); - if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt(); - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } - while (G->valid(e.v) && !G->valid(e.in)) { - ++(e.v); - if (G->valid(e.v)) G->getFirst(e.in, e.v); - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } + graph->/*getF*/first(e.v); + if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } + while (graph->valid(e.v) && !graph->valid(e.in)) { + graph->next(e.v); + if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } } } else { - ++(e.in); - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } - while (G->valid(e.v) && !G->valid(e.in)) { - ++(e.v); - if (G->valid(e.v)) G->getFirst(e.in, e.v); - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } + graph->next(e.in); + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } + while (graph->valid(e.v) && !graph->valid(e.in)) { + graph->next(e.v); + if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } } return e; @@ -572,41 +604,41 @@ template< typename It > It first() const { It e; - getFirst(e); + /*getF*/first(e); return e; } template< typename It > - It first(NodeIt v) const { + It first(Node v) const { It e; - getFirst(e, v); + /*getF*/first(e, v); return e; } - NodeIt tail(EdgeIt e) const { - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); } - NodeIt head(EdgeIt e) const { - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); } + Node tail(Edge e) const { + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } + Node head(Edge e) const { + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } - NodeIt aNode(OutEdgeIt e) const { - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); } - NodeIt bNode(OutEdgeIt e) const { - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); } + Node aNode(OutEdgeIt e) const { + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } + Node bNode(OutEdgeIt e) const { + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } - int id(NodeIt v) const { return G->id(v); } + int id(Node v) const { return graph->id(v); } - bool valid(NodeIt n) const { return G->valid(n); } - bool valid(EdgeIt e) const { - return e.out_or_in ? G->valid(e.out) : G->valid(e.in); } + bool valid(Node n) const { return graph->valid(n); } + bool valid(Edge e) const { + return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } - void augment(const EdgeIt& e, Number a) const { + void augment(const Edge& e, Number a) const { if (e.out_or_in) flow->set(e.out, flow->get(e.out)+a); else flow->set(e.in, flow->get(e.in)-a); } - Number free(const EdgeIt& e) const { + Number free(const Edge& e) const { if (e.out_or_in) return (capacity->get(e.out)-flow->get(e.out)); else @@ -633,10 +665,10 @@ // class NodeMap { // typename Graph::NodeMap node_map; // public: -// NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.G)) { } -// NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.G), a) { } -// void set(NodeIt nit, T a) { node_map.set(nit, a); } -// T get(NodeIt nit) const { return node_map.get(nit); } +// NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.graph)) { } +// NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.graph), a) { } +// void set(Node nit, T a) { node_map.set(nit, a); } +// T get(Node nit) const { return node_map.get(nit); } // }; template @@ -645,13 +677,13 @@ public: EdgeMap(const ResGraphWrapper& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { } EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { } - void set(EdgeIt e, T a) { + void set(Edge e, T a) { if (e.out_or_in) forward_map.set(e.out, a); else backward_map.set(e.in, a); } - T get(EdgeIt e) { + T get(Edge e) { if (e.out_or_in) return forward_map.get(e.out); else @@ -670,9 +702,9 @@ const CapacityMap& _capacity) : ResGraphWrapper(_G, _flow, _capacity), first_out_edges(*this) /*, dist(*this)*/ { - for(EachNodeIt n=this->template first(); this->valid(n); this->next(n)) { + for(NodeIt n=this->template first(); this->valid(n); this->next(n)) { OutEdgeIt e; - ResGraphWrapper::getFirst(e, n); + ResGraphWrapper::/*getF*/first(e, n); first_out_edges.set(n, e); } } @@ -685,49 +717,49 @@ //typedef Graph BaseGraph; + //typedef typename Graph::Node Node; //typedef typename Graph::NodeIt NodeIt; - //typedef typename Graph::EachNodeIt EachNodeIt; - //typedef typename Graph::EdgeIt EdgeIt; + //typedef typename Graph::Edge Edge; //typedef typename Graph::OutEdgeIt OutEdgeIt; //typedef typename Graph::InEdgeIt InEdgeIt; //typedef typename Graph::SymEdgeIt SymEdgeIt; - //typedef typename Graph::EachEdgeIt EachEdgeIt; + //typedef typename Graph::EdgeIt EdgeIt; + typedef typename ResGraphWrapper::Node Node; typedef typename ResGraphWrapper::NodeIt NodeIt; - typedef typename ResGraphWrapper::EachNodeIt EachNodeIt; - typedef typename ResGraphWrapper::EdgeIt EdgeIt; + typedef typename ResGraphWrapper::Edge Edge; typedef typename ResGraphWrapper::OutEdgeIt OutEdgeIt; //typedef typename ResGraphWrapper::InEdgeIt InEdgeIt; //typedef typename Graph::SymEdgeIt SymEdgeIt; - //typedef typename ResGraphWrapper::EachEdgeIt EachEdgeIt; + //typedef typename ResGraphWrapper::EdgeIt EdgeIt; - EachNodeIt& getFirst(EachNodeIt& n) const { - return ResGraphWrapper::getFirst(n); + NodeIt& /*getF*/first(NodeIt& n) const { + return ResGraphWrapper::/*getF*/first(n); } - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { + OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { e=first_out_edges.get(n); return e; } - //ROSSZ template I& getFirst(I& i) const { return getFirst(i); } - //ROSSZ template I& getFirst(I& i, const P& p) const { - // return getFirst(i, p); } + //ROSSZ template I& /*getF*/first(I& i) const { return /*getF*/first(i); } + //ROSSZ template I& /*getF*/first(I& i, const P& p) const { + // return /*getF*/first(i, p); } //template I getNext(const I& i) const { // return graph->getNext(i); } //template I& next(I &i) const { return graph->next(i); } template< typename It > It first() const { - It e; getFirst(e); return e; } + It e; /*getF*/first(e); return e; } - template< typename It > It first(const NodeIt& v) const { - It e; getFirst(e, v); return e; } + template< typename It > It first(const Node& v) const { + It e; /*getF*/first(e, v); return e; } - //NodeIt head(const EdgeIt& e) const { return graph->head(e); } - //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } + //Node head(const Edge& e) const { return graph->head(e); } + //Node tail(const Edge& e) const { return graph->tail(e); } //template bool valid(const I& i) const // { return graph->valid(i); } @@ -735,19 +767,19 @@ //int nodeNum() const { return graph->nodeNum(); } //int edgeNum() const { return graph->edgeNum(); } - //template NodeIt aNode(const I& e) const { + //template Node aNode(const I& e) const { // return graph->aNode(e); } - //template NodeIt bNode(const I& e) const { + //template Node bNode(const I& e) const { // return graph->bNode(e); } - //NodeIt addNode() const { return graph->addNode(); } - //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { + //Node addNode() const { return graph->addNode(); } + //Edge addEdge(const Node& tail, const Node& head) const { // return graph->addEdge(tail, head); } //void erase(const OutEdgeIt& e) { // first_out_edge(this->tail(e))=e; //} - void erase(const EdgeIt& e) { + void erase(const Edge& e) { OutEdgeIt f(e); next(f); first_out_edges.set(this->tail(e), f); @@ -785,14 +817,14 @@ public: //typedef Graph BaseGraph; + typedef typename ErasingResGraphWrapper::Node Node; typedef typename ErasingResGraphWrapper::NodeIt NodeIt; - typedef typename ErasingResGraphWrapper::EachNodeIt EachNodeIt; - typedef typename ErasingResGraphWrapper::EdgeIt EdgeIt; + typedef typename ErasingResGraphWrapper::Edge Edge; typedef typename ErasingResGraphWrapper::OutEdgeIt OutEdgeIt; //typedef typename ErasingResGraphWrapper::InEdgeIt InEdgeIt; //typedef typename Graph::SymEdgeIt SymEdgeIt; - typedef typename ErasingResGraphWrapper::EachEdgeIt EachEdgeIt; + typedef typename ErasingResGraphWrapper::EdgeIt EdgeIt; //FilterGraphWrapper::NodeMap::OutEdgeIt> first_out_edges; @@ -802,14 +834,14 @@ ErasingResGraphWrapper(_G, _flow, _capacity), dist(*this) { } - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { - ErasingResGraphWrapper::getFirst(e, n); + OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { + ErasingResGraphWrapper::/*getF*/first(e, n); while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) ErasingResGraphWrapper::next(e); return e; } - EachNodeIt& next(EachNodeIt& e) const { + NodeIt& next(NodeIt& e) const { return ErasingResGraphWrapper::next(e); } @@ -820,11 +852,11 @@ return e; } - EachNodeIt& getFirst(EachNodeIt& n) const { - return ErasingResGraphWrapper::getFirst(n); + NodeIt& /*getF*/first(NodeIt& n) const { + return ErasingResGraphWrapper::/*getF*/first(n); } - void erase(const EdgeIt& e) { + void erase(const Edge& e) { OutEdgeIt f(e); ErasingResGraphWrapper::next(f); while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) @@ -838,22 +870,22 @@ //void setGraph(Graph& _graph) { graph = &_graph; } //Graph& getGraph() const { return (*graph); } - //template I& getFirst(I& i) const { return graph->getFirst(i); } - //template I& getFirst(I& i, const P& p) const { - // return graph->getFirst(i, p); } + //template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } + //template I& /*getF*/first(I& i, const P& p) const { + // return graph->/*getF*/first(i, p); } //template I getNext(const I& i) const { // return graph->getNext(i); } //template I& next(I &i) const { return graph->next(i); } template< typename It > It first() const { - It e; getFirst(e); return e; } + It e; /*getF*/first(e); return e; } - template< typename It > It first(const NodeIt& v) const { - It e; getFirst(e, v); return e; } + template< typename It > It first(const Node& v) const { + It e; /*getF*/first(e, v); return e; } - //NodeIt head(const EdgeIt& e) const { return graph->head(e); } - //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } + //Node head(const Edge& e) const { return graph->head(e); } + //Node tail(const Edge& e) const { return graph->tail(e); } //template bool valid(const I& i) const // { return graph->valid(i); } @@ -864,13 +896,13 @@ //int nodeNum() const { return graph->nodeNum(); } //int edgeNum() const { return graph->edgeNum(); } - //template NodeIt aNode(const I& e) const { + //template Node aNode(const I& e) const { // return graph->aNode(e); } - //template NodeIt bNode(const I& e) const { + //template Node bNode(const I& e) const { // return graph->bNode(e); } - //NodeIt addNode() const { return graph->addNode(); } - //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { + //Node addNode() const { return graph->addNode(); } + //Edge addEdge(const Node& tail, const Node& head) const { // return graph->addEdge(tail, head); } //template void erase(const I& i) const { graph->erase(i); } @@ -909,45 +941,45 @@ // public: // typedef Graph BaseGraph; +// typedef typename Graph::Node Node; +// typedef typename Graph::Edge Edge; + // typedef typename Graph::NodeIt NodeIt; -// typedef typename Graph::EdgeIt EdgeIt; - -// typedef typename Graph::EachNodeIt EachNodeIt; // class OutEdgeIt { // public: -// //Graph::NodeIt n; +// //Graph::Node n; // bool out_or_in; // typename Graph::OutEdgeIt o; // typename Graph::InEdgeIt i; // }; // class InEdgeIt { // public: -// //Graph::NodeIt n; +// //Graph::Node n; // bool out_or_in; // typename Graph::OutEdgeIt o; // typename Graph::InEdgeIt i; // }; // typedef typename Graph::SymEdgeIt SymEdgeIt; -// typedef typename Graph::EachEdgeIt EachEdgeIt; +// typedef typename Graph::EdgeIt EdgeIt; // int nodeNum() const { return graph->nodeNum(); } // int edgeNum() const { return graph->edgeNum(); } -// NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); } +// Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); } -// // EachEdge and SymEdge is missing!!!! -// // EdgeIt <-> In/OutEdgeIt conversion is missing!!!! +// // Edge and SymEdge is missing!!!! +// // Edge <-> In/OutEdgeIt conversion is missing!!!! // //FIXME -// OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const +// OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const // { // e.n=n; -// graph->getFirst(e.o,n); +// graph->/*getF*/first(e.o,n); // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) // graph->goNext(e.o); // if(!graph->valid(e.o)) { -// graph->getFirst(e.i,n); +// graph->/*getF*/first(e.i,n); // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) // graph->goNext(e.i); // } @@ -960,7 +992,7 @@ // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) // graph->goNext(e.o); // if(graph->valid(e.o)) return e; -// else graph->getFirst(e.i,e.n); +// else graph->/*getF*/first(e.i,e.n); // } // else { // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) @@ -973,14 +1005,14 @@ // //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);} // //FIXME -// InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const +// InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const // { // e.n=n; -// graph->getFirst(e.i,n); +// graph->/*getF*/first(e.i,n); // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) // graph->goNext(e.i); // if(!graph->valid(e.i)) { -// graph->getFirst(e.o,n); +// graph->/*getF*/first(e.o,n); // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) // graph->goNext(e.o); // } @@ -993,7 +1025,7 @@ // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) // graph->goNext(e.i); // if(graph->valid(e.i)) return e; -// else graph->getFirst(e.o,e.n); +// else graph->/*getF*/first(e.o,e.n); // } // else { // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) @@ -1009,17 +1041,17 @@ // //template I next(const I i); { return graph->goNext(i); } // template< typename It > It first() const { -// It e; getFirst(e); return e; } +// It e; /*getF*/first(e); return e; } -// template< typename It > It first(NodeIt v) const { -// It e; getFirst(e, v); return e; } +// template< typename It > It first(Node v) const { +// It e; /*getF*/first(e, v); return e; } -// NodeIt head(const EdgeIt& e) const { return graph->head(e); } -// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); } +// Node head(const Edge& e) const { return graph->head(e); } +// Node tail(const Edge& e) const { return graph->tail(e); } -// template NodeIt aNode(const I& e) const { +// template Node aNode(const I& e) const { // return graph->aNode(e); } -// template NodeIt bNode(const I& e) const { +// template Node bNode(const I& e) const { // return graph->bNode(e); } // //template bool valid(const I i); @@ -1028,8 +1060,8 @@ // //template void setInvalid(const I &i); // //{ return graph->setInvalid(i); } -// NodeIt addNode() { return graph->addNode(); } -// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { +// Node addNode() { return graph->addNode(); } +// Edge addEdge(const Node& tail, const Node& head) { // return graph->addEdge(tail, head); } // template void erase(const I& i) { graph->erase(i); } diff -r de9849252e78 -r 44700ed9ffaa src/work/marci/lg_vs_sg.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/marci/lg_vs_sg.cc Fri Mar 12 09:19:54 2004 +0000 @@ -0,0 +1,147 @@ +// -*- c++ -*- +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +using namespace hugo; + +// Use a DIMACS max flow file as stdin. +// read_dimacs_demo dimacs_max_flow_file + +int main(int, char** argv) { + + std::string in=argv[1]; + typedef ListGraph MutableGraph; + + { + typedef ListGraph Graph; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; + + Graph G; + Node s, t; + Graph::EdgeMap cap(G); + std::ifstream ins(in.c_str()); + readDimacsMaxFlow(ins, G, s, t, cap); + + { + std::cout << "ListGraph..." << std::endl; + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow + + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + int i=0; + while (max_flow_test.augmentOnBlockingFlow()) { ++i; } + + std::cout << "elapsed time: " << ts << std::endl; + std::cout << "number of augmentation phases: " << i << std::endl; + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; + } + + { + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow + + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + int i=0; + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } + + std::cout << "elapsed time: " << ts << std::endl; + std::cout << "number of augmentation phases: " << i << std::endl; + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; + } + + { + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow + + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + int i=0; + while (max_flow_test.augmentOnShortestPath()) { ++i; } + + std::cout << "elapsed time: " << ts << std::endl; + std::cout << "number of augmentation phases: " << i << std::endl; + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; + } + } + + + { + typedef SmartGraph Graph; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; + + Graph G; + Node s, t; + Graph::EdgeMap cap(G); + std::ifstream ins(in.c_str()); + readDimacsMaxFlow(ins, G, s, t, cap); + + { + std::cout << "SmartGraph..." << std::endl; + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow + + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + int i=0; + while (max_flow_test.augmentOnBlockingFlow()) { ++i; } + + std::cout << "elapsed time: " << ts << std::endl; + std::cout << "number of augmentation phases: " << i << std::endl; + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; + } + + { + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow + + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + int i=0; + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } + + std::cout << "elapsed time: " << ts << std::endl; + std::cout << "number of augmentation phases: " << i << std::endl; + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; + } + + { + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl; + Graph::EdgeMap flow(G); //0 flow + + Timer ts; + ts.reset(); + + MaxFlow, Graph::EdgeMap > max_flow_test(G, s, t, flow, cap); + int i=0; + while (max_flow_test.augmentOnShortestPath()) { ++i; } + + std::cout << "elapsed time: " << ts << std::endl; + std::cout << "number of augmentation phases: " << i << std::endl; + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; + } + } + + return 0; +} diff -r de9849252e78 -r 44700ed9ffaa src/work/marci/makefile --- a/src/work/marci/makefile Thu Mar 11 23:31:13 2004 +0000 +++ b/src/work/marci/makefile Fri Mar 12 09:19:54 2004 +0000 @@ -1,10 +1,10 @@ CXX3 = g++-3.0 CXX2 = g++-2.95 CXX3.3 = g++ -CXXFLAGS = -W -Wall -ansi -pedantic +CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar LEDAROOT ?= /ledasrc/LEDA-4.1 -BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos +BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos lg_vs_sg all: $(BINARIES) @@ -16,8 +16,11 @@ sinclude .depend edmonds_karp_demo: - $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc - $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc + $(CXX3) $(CXXFLAGS) -g -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc + $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc + +lg_vs_sg: + $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o lg_vs_sg lg_vs_sg.cc edmonds_karp_demo_alpar: $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../alpar -o edmonds_karp_demo_alpar edmonds_karp_demo_alpar.cc