# HG changeset patch # User marci # Date 1081177359 0 # Node ID 7eb324ed5da386dc516d3636eb8b85699e9c3b5a # Parent 60b578e3d5076941f56b64b2de02d5c92626db5d kicsi moveolgatas diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/bfs_iterator.h --- a/src/work/bfs_iterator.h Mon Apr 05 14:56:41 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,841 +0,0 @@ -// -*- c++ -*- -#ifndef HUGO_BFS_ITERATOR_H -#define HUGO_BFS_ITERATOR_H - -#include -#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); - OutEdgeIt e; - G.first(e, s); - dfs_stack.push(e); - } - 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)) { - OutEdgeIt e; - G.first(e, w); - dfs_stack.push(e); - 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 //HUGO_BFS_ITERATOR_H diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/edmonds_karp.h --- a/src/work/edmonds_karp.h Mon Apr 05 14:56:41 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1238 +0,0 @@ -// -*- c++ -*- -#ifndef HUGO_EDMONDS_KARP_H -#define HUGO_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 { - protected: - typedef GraphWrapper GW; - typedef typename GW::Node Node; - typedef typename GW::Edge Edge; - typedef typename GW::EdgeIt EdgeIt; - typedef typename GW::OutEdgeIt OutEdgeIt; - typedef typename GW::InEdgeIt InEdgeIt; - //const Graph* G; - GW gw; - Node s; - Node t; - FlowMap* flow; - const CapacityMap* capacity; - typedef ResGraphWrapper ResGW; - typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; - typedef typename ResGW::Edge ResGWEdge; - public: - - MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : - gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } - - bool augmentOnShortestPath() { - ResGW res_graph(gw, *flow, *capacity); - bool _augment=false; - - typedef typename ResGW::NodeMap ReachedMap; - BfsIterator5< ResGW, ReachedMap > bfs(res_graph); - bfs.pushAndSetReached(s); - - typename ResGW::NodeMap pred(res_graph); - pred.set(s, INVALID); - - typename ResGW::NodeMap free(res_graph); - - //searching for augmenting path - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; - if (res_graph.valid(e) && 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.resCap(e))); - } else { - free.set(w, res_graph.resCap(e)); - } - if (res_graph.head(e)==t) { _augment=true; break; } - } - - ++bfs; - } //end of searching augmenting path - - if (_augment) { - Node n=t; - Number augment_value=free.get(t); - while (res_graph.valid(pred.get(n))) { - ResGWEdge e=pred.get(n); - res_graph.augment(e, augment_value); - n=res_graph.tail(e); - } - } - - return _augment; - } - - template - class DistanceMap { - protected: - MapGraphWrapper gw; - typename MapGraphWrapper::NodeMap dist; - public: - DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } - void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } - int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } - bool get(const typename MapGraphWrapper::Edge& e) const { - return (dist.get(gw.tail(e)) bool augmentOnBlockingFlow() { - typedef MutableGraph MG; - bool _augment=false; - - ResGW res_graph(gw, *flow, *capacity); - - typedef typename ResGW::NodeMap ReachedMap; - BfsIterator5< ResGW, ReachedMap > bfs(res_graph); - - bfs.pushAndSetReached(s); - //typename ResGW::NodeMap dist(res_graph); //filled up with 0's - DistanceMap dist(res_graph); - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=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 - - MG F; - typedef SubGraphWrapper > FilterResGW; - FilterResGW filter_res_graph(res_graph, dist); - typename ResGW::NodeMap res_graph_to_F(res_graph); - { - typename ResGW::NodeIt n; - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { - res_graph_to_F.set(n, F.addNode()); - } - } - - typename MG::Node sF=res_graph_to_F.get(s); - typename MG::Node tF=res_graph_to_F.get(t); - typename MG::EdgeMap original_edge(F); - typename MG::EdgeMap residual_capacity(F); - - //Making F to the graph containing the edges of the residual graph - //which are in some shortest paths - { - typename FilterResGW::EdgeIt e; - for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { - typename MG::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.resCap(e)); - //} - } - } - - bool __augment=true; - - while (__augment) { - __augment=false; - //computing blocking flow with dfs - typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; - DfsIterator5< TrivGraphWrapper, BlockingReachedMap > dfs(F); - typename MG::NodeMap pred(F); - pred.set(sF, INVALID); - //invalid iterators for sources - - typename MG::NodeMap free(F); - - dfs.pushAndSetReached(sF); - while (!dfs.finished()) { - ++dfs; - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { - if (dfs.isBNodeNewlyReached()) { - typename MG::Node v=F.aNode(dfs); - typename MG::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) { - __augment=true; - _augment=true; - break; - } - - } else { - F.erase(/*typename MG::OutEdgeIt*/(dfs)); - } - } - } - - if (__augment) { - typename MG::Node n=tF; - Number augment_value=free.get(tF); - while (F.valid(pred.get(n))) { - typename MG::Edge e=pred.get(n); - res_graph.augment(original_edge.get(e), augment_value); - n=F.tail(e); - if (residual_capacity.get(e)==augment_value) - F.erase(e); - else - residual_capacity.set(e, residual_capacity.get(e)-augment_value); - } - } - - } - - return _augment; - } - - template bool augmentOnBlockingFlow1() { - typedef MutableGraph MG; - bool _augment=false; - - ResGW res_graph(gw, *flow, *capacity); - - //bfs for distances on the residual graph - typedef typename ResGW::NodeMap ReachedMap; - BfsIterator5< ResGW, ReachedMap > bfs(res_graph); - bfs.pushAndSetReached(s); - typename ResGW::NodeMap dist(res_graph); //filled up with 0's - - //F will contain the physical copy of the residual graph - //with the set of edges which are on shortest paths - MG F; - typename ResGW::NodeMap res_graph_to_F(res_graph); - { - typename ResGW::NodeIt n; - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { - res_graph_to_F.set(n, F.addNode()); - } - } - - typename MG::Node sF=res_graph_to_F.get(s); - typename MG::Node tF=res_graph_to_F.get(t); - typename MG::EdgeMap original_edge(F); - typename MG::EdgeMap residual_capacity(F); - - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=bfs; - if (res_graph.valid(e)) { - if (bfs.isBNodeNewlyReached()) { - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); - typename MG::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.resCap(e)); - } else { - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { - typename MG::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.resCap(e)); - } - } - } - ++bfs; - } //computing distances from s in the residual graph - - bool __augment=true; - - while (__augment) { - __augment=false; - //computing blocking flow with dfs - typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; - DfsIterator5< TrivGraphWrapper, BlockingReachedMap > dfs(F); - typename MG::NodeMap pred(F); - pred.set(sF, INVALID); - //invalid iterators for sources - - typename MG::NodeMap free(F); - - dfs.pushAndSetReached(sF); - while (!dfs.finished()) { - ++dfs; - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { - if (dfs.isBNodeNewlyReached()) { - typename MG::Node v=F.aNode(dfs); - typename MG::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) { - __augment=true; - _augment=true; - break; - } - - } else { - F.erase(/*typename MG::OutEdgeIt*/(dfs)); - } - } - } - - if (__augment) { - typename MG::Node n=tF; - Number augment_value=free.get(tF); - while (F.valid(pred.get(n))) { - typename MG::Edge e=pred.get(n); - res_graph.augment(original_edge.get(e), augment_value); - n=F.tail(e); - if (residual_capacity.get(e)==augment_value) - F.erase(e); - else - residual_capacity.set(e, residual_capacity.get(e)-augment_value); - } - } - - } - - return _augment; - } - - bool augmentOnBlockingFlow2() { - bool _augment=false; - - ResGW res_graph(gw, *flow, *capacity); - - typedef typename ResGW::NodeMap ReachedMap; - BfsIterator5< ResGW, ReachedMap > bfs(res_graph); - - bfs.pushAndSetReached(s); - DistanceMap dist(res_graph); - while ( !bfs.finished() ) { - ResGWOutEdgeIt e=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 - - //Subgraph containing the edges on some shortest paths - typedef SubGraphWrapper > FilterResGW; - FilterResGW filter_res_graph(res_graph, dist); - - //Subgraph, which is able to delete edges which are already - //met by the dfs - typename FilterResGW::NodeMap - first_out_edges(filter_res_graph); - typename FilterResGW::NodeIt v; - for(filter_res_graph.first(v); filter_res_graph.valid(v); - filter_res_graph.next(v)) - { - typename FilterResGW::OutEdgeIt e; - filter_res_graph.first(e, v); - first_out_edges.set(v, e); - } - typedef ErasingFirstGraphWrapper > ErasingResGW; - ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); - - bool __augment=true; - - while (__augment) { - - __augment=false; - //computing blocking flow with dfs - typedef typename ErasingResGW::NodeMap BlockingReachedMap; - DfsIterator5< ErasingResGW, BlockingReachedMap > - dfs(erasing_res_graph); - typename ErasingResGW::NodeMap - pred(erasing_res_graph); - pred.set(s, INVALID); - //invalid iterators for sources - - typename ErasingResGW::NodeMap free(erasing_res_graph); - - dfs.pushAndSetReached(s); - while (!dfs.finished()) { - ++dfs; - if (erasing_res_graph.valid( - /*typename ErasingResGW::OutEdgeIt*/(dfs))) - { - if (dfs.isBNodeNewlyReached()) { - - typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); - typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); - - pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); - if (erasing_res_graph.valid(pred.get(v))) { - free.set(w, std::min(free.get(v), res_graph.resCap(dfs))); - } else { - free.set(w, res_graph.resCap(dfs)); - } - - if (w==t) { - __augment=true; - _augment=true; - break; - } - } else { - erasing_res_graph.erase(dfs); - } - } - } - - if (__augment) { - typename ErasingResGW::Node n=t; - Number augment_value=free.get(n); - while (erasing_res_graph.valid(pred.get(n))) { - typename ErasingResGW::OutEdgeIt e=pred.get(n); - res_graph.augment(e, augment_value); - n=erasing_res_graph.tail(e); - if (res_graph.resCap(e)==0) - erasing_res_graph.erase(e); - } - } - - } //while (__augment) - - return _augment; - } - -// bool augmentOnBlockingFlow2() { -// bool _augment=false; - -// //typedef ErasingResGraphWrapper EAugGraph; -// typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; -// typedef typename EAugGraph::Edge EAugEdge; - -// EAugGraph res_graph(*G, *flow, *capacity); - -// //typedef typename EAugGraph::NodeMap ReachedMap; -// BfsIterator5< -// ErasingResGraphWrapper, -// /*typename ErasingResGraphWrapper::OutEdgeIt,*/ -// ErasingResGraphWrapper::NodeMap > bfs(res_graph); - -// bfs.pushAndSetReached(s); - -// typename ErasingResGraphWrapper:: -// NodeMap& dist=res_graph.dist; - -// while ( !bfs.finished() ) { -// typename ErasingResGraphWrapper::OutEdgeIt e=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 - -// bool __augment=true; - -// while (__augment) { - -// __augment=false; -// //computing blocking flow with dfs -// typedef typename EAugGraph::NodeMap BlockingReachedMap; -// DfsIterator5< 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()) { - -// typename EAugGraph::Node v=res_graph.aNode(dfs); -// typename EAugGraph::Node w=res_graph.bNode(dfs); - -// pred.set(w, EAugOutEdgeIt(dfs)); -// if (res_graph.valid(pred.get(v))) { -// free.set(w, std::min(free.get(v), res_graph.free(dfs))); -// } else { -// free.set(w, res_graph.free(dfs)); -// } - -// if (w==t) { -// __augment=true; -// _augment=true; -// break; -// } -// } else { -// res_graph.erase(dfs); -// } -// } - -// } - -// if (__augment) { -// typename EAugGraph::Node n=t; -// Number augment_value=free.get(t); -// while (res_graph.valid(pred.get(n))) { -// EAugEdge e=pred.get(n); -// res_graph.augment(e, 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<get(e); - } - return a; - } - - }; - - -// template -// class MaxMatching { -// public: -// typedef typename Graph::Node Node; -// typedef typename Graph::NodeIt NodeIt; -// typedef typename Graph::Edge Edge; -// typedef typename Graph::EdgeIt EdgeIt; -// typedef typename Graph::OutEdgeIt OutEdgeIt; -// typedef typename Graph::InEdgeIt InEdgeIt; - -// typedef typename Graph::NodeMap SMap; -// typedef typename Graph::NodeMap TMap; -// private: -// const Graph* G; -// SMap* S; -// TMap* T; -// //Node s; -// //Node t; -// FlowMap* flow; -// const CapacityMap* capacity; -// typedef ResGraphWrapper AugGraph; -// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; -// typedef typename AugGraph::Edge AugEdge; -// typename Graph::NodeMap used; //0 - -// public: -// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : -// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } -// bool augmentOnShortestPath() { -// AugGraph res_graph(*G, *flow, *capacity); -// bool _augment=false; - -// typedef typename AugGraph::NodeMap ReachedMap; -// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); -// typename AugGraph::NodeMap pred(res_graph); -// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { -// if ((S->get(s)) && (used.get(s)<1) ) { -// //Number u=0; -// //for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) -// //u+=flow->get(e); -// //if (u<1) { -// bfs.pushAndSetReached(s); -// pred.set(s, AugEdge(INVALID)); -// //} -// } -// } - -// typename AugGraph::NodeMap free(res_graph); - -// Node n; -// //searching for augmenting path -// while ( !bfs.finished() ) { -// AugOutEdgeIt e=bfs; -// if (res_graph.valid(e) && 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)); -// } -// n=res_graph.head(e); -// if (T->get(n) && (used.get(n)<1) ) { -// //Number u=0; -// //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) -// //u+=flow->get(f); -// //if (u<1) { -// _augment=true; -// break; -// //} -// } -// } - -// ++bfs; -// } //end of searching augmenting path - -// if (_augment) { -// //Node n=t; -// used.set(n, 1); //mind2 vegen jav -// Number augment_value=free.get(n); -// while (res_graph.valid(pred.get(n))) { -// AugEdge e=pred.get(n); -// res_graph.augment(e, augment_value); -// n=res_graph.tail(e); -// } -// used.set(n, 1); //mind2 vegen jav -// } - -// return _augment; -// } - -// // template bool augmentOnBlockingFlow() { -// // bool _augment=false; - -// // AugGraph res_graph(*G, *flow, *capacity); - -// // typedef typename AugGraph::NodeMap ReachedMap; -// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); - - - - - -// // //typename AugGraph::NodeMap pred(res_graph); -// // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { -// // if (S->get(s)) { -// // Number u=0; -// // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) -// // u+=flow->get(e); -// // if (u<1) { -// // bfs.pushAndSetReached(s); -// // //pred.set(s, AugEdge(INVALID)); -// // } -// // } -// // } - - - - -// // //bfs.pushAndSetReached(s); -// // typename AugGraph::NodeMap dist(res_graph); //filled up with 0's -// // while ( !bfs.finished() ) { -// // AugOutEdgeIt e=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 - -// // 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)); -// // } -// // } - -// // 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()) { -// // 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) { -// // __augment=true; -// // _augment=true; -// // break; -// // } - -// // } else { -// // F.erase(typename MutableGraph::OutEdgeIt(dfs)); -// // } -// // } -// // } - -// // if (__augment) { -// // typename MutableGraph::Node n=tF; -// // Number augment_value=free.get(tF); -// // while (F.valid(pred.get(n))) { -// // typename MutableGraph::Edge e=pred.get(n); -// // res_graph.augment(original_edge.get(e), augment_value); -// // n=F.tail(e); -// // if (residual_capacity.get(e)==augment_value) -// // F.erase(e); -// // else -// // residual_capacity.set(e, residual_capacity.get(e)-augment_value); -// // } -// // } - -// // } - -// // return _augment; -// // } -// bool augmentOnBlockingFlow2() { -// bool _augment=false; - -// //typedef ErasingResGraphWrapper EAugGraph; -// typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; -// typedef typename EAugGraph::Edge EAugEdge; - -// EAugGraph res_graph(*G, *flow, *capacity); - -// //typedef typename EAugGraph::NodeMap ReachedMap; -// BfsIterator5< -// ErasingResGraphWrapper, -// /*typename ErasingResGraphWrapper::OutEdgeIt,*/ -// ErasingResGraphWrapper::NodeMap > bfs(res_graph); - - -// //typename AugGraph::NodeMap pred(res_graph); -// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { -// if (S->get(s)) { -// Number u=0; -// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) -// u+=flow->get(e); -// if (u<1) { -// bfs.pushAndSetReached(s); -// //pred.set(s, AugEdge(INVALID)); -// } -// } -// } - - -// //bfs.pushAndSetReached(s); - -// typename ErasingResGraphWrapper:: -// NodeMap& dist=res_graph.dist; - -// while ( !bfs.finished() ) { -// typename ErasingResGraphWrapper::OutEdgeIt e=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 - -// bool __augment=true; - -// while (__augment) { - -// __augment=false; -// //computing blocking flow with dfs -// typedef typename EAugGraph::NodeMap BlockingReachedMap; -// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > -// dfs(res_graph); -// typename EAugGraph::NodeMap pred(res_graph, INVALID); -// //pred.set(s, EAugEdge(INVALID)); -// //invalid iterators for sources - -// typename EAugGraph::NodeMap free(res_graph); - - -// //typename AugGraph::NodeMap pred(res_graph); -// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { -// if (S->get(s)) { -// Number u=0; -// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) -// u+=flow->get(e); -// if (u<1) { -// dfs.pushAndSetReached(s); -// //pred.set(s, AugEdge(INVALID)); -// } -// } -// } - - - -// //dfs.pushAndSetReached(s); -// typename EAugGraph::Node n; -// while (!dfs.finished()) { -// ++dfs; -// if (res_graph.valid(EAugOutEdgeIt(dfs))) { -// if (dfs.isBNodeNewlyReached()) { - -// typename EAugGraph::Node v=res_graph.aNode(dfs); -// typename EAugGraph::Node w=res_graph.bNode(dfs); - -// pred.set(w, EAugOutEdgeIt(dfs)); -// if (res_graph.valid(pred.get(v))) { -// free.set(w, std::min(free.get(v), res_graph.free(dfs))); -// } else { -// free.set(w, res_graph.free(dfs)); -// } - -// n=w; -// if (T->get(w)) { -// Number u=0; -// for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) -// u+=flow->get(f); -// if (u<1) { -// __augment=true; -// _augment=true; -// break; -// } -// } -// } else { -// res_graph.erase(dfs); -// } -// } - -// } - -// if (__augment) { -// // typename EAugGraph::Node n=t; -// Number augment_value=free.get(n); -// while (res_graph.valid(pred.get(n))) { -// EAugEdge e=pred.get(n); -// res_graph.augment(e, 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); 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 > bfs(res_graph); -// // for(typename std::list::const_iterator i=S.begin(); -// // i!=S.end(); ++i) { -// // bfs.pushAndSetReached(*i); -// // } -// // //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 ( !bfs.finished() ) { -// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); -// // if (e.valid() && 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; -// // } -// // } - -// // ++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 //HUGO_EDMONDS_KARP_H diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/iterator_bfs_demo.cc --- a/src/work/iterator_bfs_demo.cc Mon Apr 05 14:56:41 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,322 +0,0 @@ -// -*- c++ -*- -#include -#include -#include - -#include -#include -#include -#include - -using namespace hugo; -using std::cout; -using std::endl; -using std::string; - -template -class EdgeNameMap { - Graph& graph; - NodeNameMap& node_name_map; -public: - EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : - graph(_graph), node_name_map(_node_name_map) { } - string get(typename Graph::Edge e) const { - return - (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); - } -}; - -int main (int, char*[]) -{ - //typedef SmartGraph Graph; - typedef ListGraph Graph; - - typedef Graph::Node Node; - typedef Graph::Edge Edge; - - Graph G; - - Node s=G.addNode(); - Node v1=G.addNode(); - Node v2=G.addNode(); - Node v3=G.addNode(); - Node v4=G.addNode(); - Node t=G.addNode(); - - Graph::NodeMap node_name(G); - node_name.set(s, "s"); - node_name.set(v1, "v1"); - node_name.set(v2, "v2"); - node_name.set(v3, "v3"); - node_name.set(v4, "v4"); - node_name.set(t, "t"); - - G.addEdge(s, v1); - G.addEdge(s, v2); - G.addEdge(v1, v2); - G.addEdge(v2, v1); - G.addEdge(v1, v3); - G.addEdge(v3, v2); - G.addEdge(v2, v4); - G.addEdge(v4, v3); - G.addEdge(v3, t); - G.addEdge(v4, t); - - cout << " /--> -------------> "<< endl; - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; - cout << " / | | / /-> \\ "<< endl; - cout << " / | | / | ^ \\ "<< endl; - cout << "s | | / | | \\-> t "<< endl; - cout << " \\ | | / | | /-> "<< endl; - cout << " \\ | --/ / | | / "<< endl; - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; - cout << " \\--> -------------> "<< endl; - -// typedef TrivGraphWrapper CGW; -// CGW gw(G); - -// cout << "bfs and dfs demo on the directed graph" << endl; -// for(CGW::NodeIt n=gw.first(); n.valid(); ++n) { -// cout << n << ": "; -// cout << "out edges: "; -// for(CGW::OutEdgeIt e=gw.first(n); e.valid(); ++e) -// cout << e << " "; -// cout << "in edges: "; -// for(CGW::InEdgeIt e=gw.first(n); e.valid(); ++e) -// cout << e << " "; -// cout << endl; -// } - - { - typedef TrivGraphWrapper GW; - GW gw(G); - - EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); - - cout << "bfs and dfs iterator demo on the directed graph" << endl; - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { - cout << node_name.get(n) << ": "; - cout << "out edges: "; - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name.get(e) << " "; - cout << "in edges: "; - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name.get(e) << " "; - cout << endl; - } - - cout << "bfs from s ..." << endl; - BfsIterator5< GW, GW::NodeMap > bfs(gw); - bfs.pushAndSetReached(s); - while (!bfs.finished()) { - //cout << "edge: "; - if (gw.valid(bfs)) { - cout << edge_name.get(bfs) << /*endl*/", " << - node_name.get(gw.aNode(bfs)) << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name.get(gw.bNode(bfs)) << - (bfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name.get(bfs.aNode()) << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - ++bfs; - } - - cout << " /--> -------------> "<< endl; - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; - cout << " / | | / /-> \\ "<< endl; - cout << " / | | / | ^ \\ "<< endl; - cout << "s | | / | | \\-> t "<< endl; - cout << " \\ | | / | | /-> "<< endl; - cout << " \\ | --/ / | | / "<< endl; - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; - cout << " \\--> -------------> "<< endl; - - cout << "dfs from s ..." << endl; - DfsIterator5< GW, GW::NodeMap > dfs(gw); - dfs.pushAndSetReached(s); - while (!dfs.finished()) { - ++dfs; - //cout << "edge: "; - if (gw.valid(dfs)) { - cout << edge_name.get(dfs) << /*endl*/", " << - node_name.get(gw.aNode(dfs)) << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name.get(gw.bNode(dfs)) << - (dfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name.get(dfs.aNode()) << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - } - } - - - { - typedef RevGraphWrapper > GW; - GW gw(G); - - EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); - - cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { - cout << node_name.get(n) << ": "; - cout << "out edges: "; - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name.get(e) << " "; - cout << "in edges: "; - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name.get(e) << " "; - cout << endl; - } - - cout << "bfs from t ..." << endl; - BfsIterator5< GW, GW::NodeMap > bfs(gw); - bfs.pushAndSetReached(t); - while (!bfs.finished()) { - //cout << "edge: "; - if (gw.valid(bfs)) { - cout << edge_name.get(bfs) << /*endl*/", " << - node_name.get(gw.aNode(bfs)) << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name.get(gw.bNode(bfs)) << - (bfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name.get(bfs.aNode()) << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - ++bfs; - } - - cout << " /--> -------------> "<< endl; - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; - cout << " / | | / /-> \\ "<< endl; - cout << " / | | / | ^ \\ "<< endl; - cout << "s | | / | | \\-> t "<< endl; - cout << " \\ | | / | | /-> "<< endl; - cout << " \\ | --/ / | | / "<< endl; - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; - cout << " \\--> -------------> "<< endl; - - cout << "dfs from t ..." << endl; - DfsIterator5< GW, GW::NodeMap > dfs(gw); - dfs.pushAndSetReached(t); - while (!dfs.finished()) { - ++dfs; - //cout << "edge: "; - if (gw.valid(dfs)) { - cout << edge_name.get(dfs) << /*endl*/", " << - node_name.get(gw.aNode(dfs)) << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name.get(gw.bNode(dfs)) << - (dfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name.get(dfs.aNode()) << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - } - } - - { - //typedef UndirGraphWrapper GW; - typedef UndirGraphWrapper > GW; - GW gw(G); - - EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); - - cout << "bfs and dfs iterator demo on the undirected graph" << endl; - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { - cout << node_name.get(n) << ": "; - cout << "out edges: "; - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name.get(e) << " "; - cout << "in edges: "; - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name.get(e) << " "; - cout << endl; - } -// for(GW::EdgeIt e=gw.first(); gw.valid(e); gw.next(e)) { -// cout << edge_name.get(e) << " "; -// } -// cout << endl; - - cout << "bfs from t ..." << endl; - BfsIterator5< GW, GW::NodeMap > bfs(gw); - bfs.pushAndSetReached(t); - while (!bfs.finished()) { - //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(bfs))) { - cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << - node_name.get(gw.aNode(bfs)) << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name.get(gw.bNode(bfs)) << - (bfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name.get(bfs.aNode()) << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - ++bfs; - } - - cout << " /--> -------------> "<< endl; - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; - cout << " / | | / /-> \\ "<< endl; - cout << " / | | / | ^ \\ "<< endl; - cout << "s | | / | | \\-> t "<< endl; - cout << " \\ | | / | | /-> "<< endl; - cout << " \\ | --/ / | | / "<< endl; - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; - cout << " \\--> -------------> "<< endl; - - cout << "dfs from t ..." << endl; - DfsIterator5< GW, GW::NodeMap > dfs(gw); - dfs.pushAndSetReached(t); - while (!dfs.finished()) { - ++dfs; - //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(dfs))) { - cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << - node_name.get(gw.aNode(dfs)) << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name.get(gw.bNode(dfs)) << - (dfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name.get(dfs.aNode()) << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - } - } - - return 0; -} diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/makefile --- a/src/work/makefile Mon Apr 05 14:56:41 2004 +0000 +++ b/src/work/makefile Mon Apr 05 15:02:39 2004 +0000 @@ -23,7 +23,7 @@ .depend dep depend: - -$(CXX) $(CXXFLAGS) -M *.cc > .depend + -$(CXX) $(CXXFLAGS) -M $(BINARIES:=.cc) > .depend makefile: .depend sinclude .depend diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/marci/bfs_iterator.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/marci/bfs_iterator.h Mon Apr 05 15:02:39 2004 +0000 @@ -0,0 +1,841 @@ +// -*- c++ -*- +#ifndef HUGO_BFS_ITERATOR_H +#define HUGO_BFS_ITERATOR_H + +#include +#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); + OutEdgeIt e; + G.first(e, s); + dfs_stack.push(e); + } + 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)) { + OutEdgeIt e; + G.first(e, w); + dfs_stack.push(e); + 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 //HUGO_BFS_ITERATOR_H diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/marci/edmonds_karp.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/marci/edmonds_karp.h Mon Apr 05 15:02:39 2004 +0000 @@ -0,0 +1,1238 @@ +// -*- c++ -*- +#ifndef HUGO_EDMONDS_KARP_H +#define HUGO_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 { + protected: + typedef GraphWrapper GW; + typedef typename GW::Node Node; + typedef typename GW::Edge Edge; + typedef typename GW::EdgeIt EdgeIt; + typedef typename GW::OutEdgeIt OutEdgeIt; + typedef typename GW::InEdgeIt InEdgeIt; + //const Graph* G; + GW gw; + Node s; + Node t; + FlowMap* flow; + const CapacityMap* capacity; + typedef ResGraphWrapper ResGW; + typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; + typedef typename ResGW::Edge ResGWEdge; + public: + + MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : + gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } + + bool augmentOnShortestPath() { + ResGW res_graph(gw, *flow, *capacity); + bool _augment=false; + + typedef typename ResGW::NodeMap ReachedMap; + BfsIterator5< ResGW, ReachedMap > bfs(res_graph); + bfs.pushAndSetReached(s); + + typename ResGW::NodeMap pred(res_graph); + pred.set(s, INVALID); + + typename ResGW::NodeMap free(res_graph); + + //searching for augmenting path + while ( !bfs.finished() ) { + ResGWOutEdgeIt e=bfs; + if (res_graph.valid(e) && 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.resCap(e))); + } else { + free.set(w, res_graph.resCap(e)); + } + if (res_graph.head(e)==t) { _augment=true; break; } + } + + ++bfs; + } //end of searching augmenting path + + if (_augment) { + Node n=t; + Number augment_value=free.get(t); + while (res_graph.valid(pred.get(n))) { + ResGWEdge e=pred.get(n); + res_graph.augment(e, augment_value); + n=res_graph.tail(e); + } + } + + return _augment; + } + + template + class DistanceMap { + protected: + MapGraphWrapper gw; + typename MapGraphWrapper::NodeMap dist; + public: + DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } + void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } + int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } + bool get(const typename MapGraphWrapper::Edge& e) const { + return (dist.get(gw.tail(e)) bool augmentOnBlockingFlow() { + typedef MutableGraph MG; + bool _augment=false; + + ResGW res_graph(gw, *flow, *capacity); + + typedef typename ResGW::NodeMap ReachedMap; + BfsIterator5< ResGW, ReachedMap > bfs(res_graph); + + bfs.pushAndSetReached(s); + //typename ResGW::NodeMap dist(res_graph); //filled up with 0's + DistanceMap dist(res_graph); + while ( !bfs.finished() ) { + ResGWOutEdgeIt e=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 + + MG F; + typedef SubGraphWrapper > FilterResGW; + FilterResGW filter_res_graph(res_graph, dist); + typename ResGW::NodeMap res_graph_to_F(res_graph); + { + typename ResGW::NodeIt n; + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { + res_graph_to_F.set(n, F.addNode()); + } + } + + typename MG::Node sF=res_graph_to_F.get(s); + typename MG::Node tF=res_graph_to_F.get(t); + typename MG::EdgeMap original_edge(F); + typename MG::EdgeMap residual_capacity(F); + + //Making F to the graph containing the edges of the residual graph + //which are in some shortest paths + { + typename FilterResGW::EdgeIt e; + for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { + //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { + typename MG::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.resCap(e)); + //} + } + } + + bool __augment=true; + + while (__augment) { + __augment=false; + //computing blocking flow with dfs + typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; + DfsIterator5< TrivGraphWrapper, BlockingReachedMap > dfs(F); + typename MG::NodeMap pred(F); + pred.set(sF, INVALID); + //invalid iterators for sources + + typename MG::NodeMap free(F); + + dfs.pushAndSetReached(sF); + while (!dfs.finished()) { + ++dfs; + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { + if (dfs.isBNodeNewlyReached()) { + typename MG::Node v=F.aNode(dfs); + typename MG::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) { + __augment=true; + _augment=true; + break; + } + + } else { + F.erase(/*typename MG::OutEdgeIt*/(dfs)); + } + } + } + + if (__augment) { + typename MG::Node n=tF; + Number augment_value=free.get(tF); + while (F.valid(pred.get(n))) { + typename MG::Edge e=pred.get(n); + res_graph.augment(original_edge.get(e), augment_value); + n=F.tail(e); + if (residual_capacity.get(e)==augment_value) + F.erase(e); + else + residual_capacity.set(e, residual_capacity.get(e)-augment_value); + } + } + + } + + return _augment; + } + + template bool augmentOnBlockingFlow1() { + typedef MutableGraph MG; + bool _augment=false; + + ResGW res_graph(gw, *flow, *capacity); + + //bfs for distances on the residual graph + typedef typename ResGW::NodeMap ReachedMap; + BfsIterator5< ResGW, ReachedMap > bfs(res_graph); + bfs.pushAndSetReached(s); + typename ResGW::NodeMap dist(res_graph); //filled up with 0's + + //F will contain the physical copy of the residual graph + //with the set of edges which are on shortest paths + MG F; + typename ResGW::NodeMap res_graph_to_F(res_graph); + { + typename ResGW::NodeIt n; + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { + res_graph_to_F.set(n, F.addNode()); + } + } + + typename MG::Node sF=res_graph_to_F.get(s); + typename MG::Node tF=res_graph_to_F.get(t); + typename MG::EdgeMap original_edge(F); + typename MG::EdgeMap residual_capacity(F); + + while ( !bfs.finished() ) { + ResGWOutEdgeIt e=bfs; + if (res_graph.valid(e)) { + if (bfs.isBNodeNewlyReached()) { + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); + typename MG::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.resCap(e)); + } else { + if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { + typename MG::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.resCap(e)); + } + } + } + ++bfs; + } //computing distances from s in the residual graph + + bool __augment=true; + + while (__augment) { + __augment=false; + //computing blocking flow with dfs + typedef typename TrivGraphWrapper::NodeMap BlockingReachedMap; + DfsIterator5< TrivGraphWrapper, BlockingReachedMap > dfs(F); + typename MG::NodeMap pred(F); + pred.set(sF, INVALID); + //invalid iterators for sources + + typename MG::NodeMap free(F); + + dfs.pushAndSetReached(sF); + while (!dfs.finished()) { + ++dfs; + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { + if (dfs.isBNodeNewlyReached()) { + typename MG::Node v=F.aNode(dfs); + typename MG::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) { + __augment=true; + _augment=true; + break; + } + + } else { + F.erase(/*typename MG::OutEdgeIt*/(dfs)); + } + } + } + + if (__augment) { + typename MG::Node n=tF; + Number augment_value=free.get(tF); + while (F.valid(pred.get(n))) { + typename MG::Edge e=pred.get(n); + res_graph.augment(original_edge.get(e), augment_value); + n=F.tail(e); + if (residual_capacity.get(e)==augment_value) + F.erase(e); + else + residual_capacity.set(e, residual_capacity.get(e)-augment_value); + } + } + + } + + return _augment; + } + + bool augmentOnBlockingFlow2() { + bool _augment=false; + + ResGW res_graph(gw, *flow, *capacity); + + typedef typename ResGW::NodeMap ReachedMap; + BfsIterator5< ResGW, ReachedMap > bfs(res_graph); + + bfs.pushAndSetReached(s); + DistanceMap dist(res_graph); + while ( !bfs.finished() ) { + ResGWOutEdgeIt e=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 + + //Subgraph containing the edges on some shortest paths + typedef SubGraphWrapper > FilterResGW; + FilterResGW filter_res_graph(res_graph, dist); + + //Subgraph, which is able to delete edges which are already + //met by the dfs + typename FilterResGW::NodeMap + first_out_edges(filter_res_graph); + typename FilterResGW::NodeIt v; + for(filter_res_graph.first(v); filter_res_graph.valid(v); + filter_res_graph.next(v)) + { + typename FilterResGW::OutEdgeIt e; + filter_res_graph.first(e, v); + first_out_edges.set(v, e); + } + typedef ErasingFirstGraphWrapper > ErasingResGW; + ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); + + bool __augment=true; + + while (__augment) { + + __augment=false; + //computing blocking flow with dfs + typedef typename ErasingResGW::NodeMap BlockingReachedMap; + DfsIterator5< ErasingResGW, BlockingReachedMap > + dfs(erasing_res_graph); + typename ErasingResGW::NodeMap + pred(erasing_res_graph); + pred.set(s, INVALID); + //invalid iterators for sources + + typename ErasingResGW::NodeMap free(erasing_res_graph); + + dfs.pushAndSetReached(s); + while (!dfs.finished()) { + ++dfs; + if (erasing_res_graph.valid( + /*typename ErasingResGW::OutEdgeIt*/(dfs))) + { + if (dfs.isBNodeNewlyReached()) { + + typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); + typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); + + pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); + if (erasing_res_graph.valid(pred.get(v))) { + free.set(w, std::min(free.get(v), res_graph.resCap(dfs))); + } else { + free.set(w, res_graph.resCap(dfs)); + } + + if (w==t) { + __augment=true; + _augment=true; + break; + } + } else { + erasing_res_graph.erase(dfs); + } + } + } + + if (__augment) { + typename ErasingResGW::Node n=t; + Number augment_value=free.get(n); + while (erasing_res_graph.valid(pred.get(n))) { + typename ErasingResGW::OutEdgeIt e=pred.get(n); + res_graph.augment(e, augment_value); + n=erasing_res_graph.tail(e); + if (res_graph.resCap(e)==0) + erasing_res_graph.erase(e); + } + } + + } //while (__augment) + + return _augment; + } + +// bool augmentOnBlockingFlow2() { +// bool _augment=false; + +// //typedef ErasingResGraphWrapper EAugGraph; +// typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; +// typedef typename EAugGraph::Edge EAugEdge; + +// EAugGraph res_graph(*G, *flow, *capacity); + +// //typedef typename EAugGraph::NodeMap ReachedMap; +// BfsIterator5< +// ErasingResGraphWrapper, +// /*typename ErasingResGraphWrapper::OutEdgeIt,*/ +// ErasingResGraphWrapper::NodeMap > bfs(res_graph); + +// bfs.pushAndSetReached(s); + +// typename ErasingResGraphWrapper:: +// NodeMap& dist=res_graph.dist; + +// while ( !bfs.finished() ) { +// typename ErasingResGraphWrapper::OutEdgeIt e=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 + +// bool __augment=true; + +// while (__augment) { + +// __augment=false; +// //computing blocking flow with dfs +// typedef typename EAugGraph::NodeMap BlockingReachedMap; +// DfsIterator5< 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()) { + +// typename EAugGraph::Node v=res_graph.aNode(dfs); +// typename EAugGraph::Node w=res_graph.bNode(dfs); + +// pred.set(w, EAugOutEdgeIt(dfs)); +// if (res_graph.valid(pred.get(v))) { +// free.set(w, std::min(free.get(v), res_graph.free(dfs))); +// } else { +// free.set(w, res_graph.free(dfs)); +// } + +// if (w==t) { +// __augment=true; +// _augment=true; +// break; +// } +// } else { +// res_graph.erase(dfs); +// } +// } + +// } + +// if (__augment) { +// typename EAugGraph::Node n=t; +// Number augment_value=free.get(t); +// while (res_graph.valid(pred.get(n))) { +// EAugEdge e=pred.get(n); +// res_graph.augment(e, 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<get(e); + } + return a; + } + + }; + + +// template +// class MaxMatching { +// public: +// typedef typename Graph::Node Node; +// typedef typename Graph::NodeIt NodeIt; +// typedef typename Graph::Edge Edge; +// typedef typename Graph::EdgeIt EdgeIt; +// typedef typename Graph::OutEdgeIt OutEdgeIt; +// typedef typename Graph::InEdgeIt InEdgeIt; + +// typedef typename Graph::NodeMap SMap; +// typedef typename Graph::NodeMap TMap; +// private: +// const Graph* G; +// SMap* S; +// TMap* T; +// //Node s; +// //Node t; +// FlowMap* flow; +// const CapacityMap* capacity; +// typedef ResGraphWrapper AugGraph; +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; +// typedef typename AugGraph::Edge AugEdge; +// typename Graph::NodeMap used; //0 + +// public: +// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : +// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } +// bool augmentOnShortestPath() { +// AugGraph res_graph(*G, *flow, *capacity); +// bool _augment=false; + +// typedef typename AugGraph::NodeMap ReachedMap; +// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); +// typename AugGraph::NodeMap pred(res_graph); +// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// if ((S->get(s)) && (used.get(s)<1) ) { +// //Number u=0; +// //for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// //u+=flow->get(e); +// //if (u<1) { +// bfs.pushAndSetReached(s); +// pred.set(s, AugEdge(INVALID)); +// //} +// } +// } + +// typename AugGraph::NodeMap free(res_graph); + +// Node n; +// //searching for augmenting path +// while ( !bfs.finished() ) { +// AugOutEdgeIt e=bfs; +// if (res_graph.valid(e) && 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)); +// } +// n=res_graph.head(e); +// if (T->get(n) && (used.get(n)<1) ) { +// //Number u=0; +// //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) +// //u+=flow->get(f); +// //if (u<1) { +// _augment=true; +// break; +// //} +// } +// } + +// ++bfs; +// } //end of searching augmenting path + +// if (_augment) { +// //Node n=t; +// used.set(n, 1); //mind2 vegen jav +// Number augment_value=free.get(n); +// while (res_graph.valid(pred.get(n))) { +// AugEdge e=pred.get(n); +// res_graph.augment(e, augment_value); +// n=res_graph.tail(e); +// } +// used.set(n, 1); //mind2 vegen jav +// } + +// return _augment; +// } + +// // template bool augmentOnBlockingFlow() { +// // bool _augment=false; + +// // AugGraph res_graph(*G, *flow, *capacity); + +// // typedef typename AugGraph::NodeMap ReachedMap; +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); + + + + + +// // //typename AugGraph::NodeMap pred(res_graph); +// // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// // if (S->get(s)) { +// // Number u=0; +// // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// // u+=flow->get(e); +// // if (u<1) { +// // bfs.pushAndSetReached(s); +// // //pred.set(s, AugEdge(INVALID)); +// // } +// // } +// // } + + + + +// // //bfs.pushAndSetReached(s); +// // typename AugGraph::NodeMap dist(res_graph); //filled up with 0's +// // while ( !bfs.finished() ) { +// // AugOutEdgeIt e=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 + +// // 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)); +// // } +// // } + +// // 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()) { +// // 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) { +// // __augment=true; +// // _augment=true; +// // break; +// // } + +// // } else { +// // F.erase(typename MutableGraph::OutEdgeIt(dfs)); +// // } +// // } +// // } + +// // if (__augment) { +// // typename MutableGraph::Node n=tF; +// // Number augment_value=free.get(tF); +// // while (F.valid(pred.get(n))) { +// // typename MutableGraph::Edge e=pred.get(n); +// // res_graph.augment(original_edge.get(e), augment_value); +// // n=F.tail(e); +// // if (residual_capacity.get(e)==augment_value) +// // F.erase(e); +// // else +// // residual_capacity.set(e, residual_capacity.get(e)-augment_value); +// // } +// // } + +// // } + +// // return _augment; +// // } +// bool augmentOnBlockingFlow2() { +// bool _augment=false; + +// //typedef ErasingResGraphWrapper EAugGraph; +// typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; +// typedef typename EAugGraph::Edge EAugEdge; + +// EAugGraph res_graph(*G, *flow, *capacity); + +// //typedef typename EAugGraph::NodeMap ReachedMap; +// BfsIterator5< +// ErasingResGraphWrapper, +// /*typename ErasingResGraphWrapper::OutEdgeIt,*/ +// ErasingResGraphWrapper::NodeMap > bfs(res_graph); + + +// //typename AugGraph::NodeMap pred(res_graph); +// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// if (S->get(s)) { +// Number u=0; +// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// u+=flow->get(e); +// if (u<1) { +// bfs.pushAndSetReached(s); +// //pred.set(s, AugEdge(INVALID)); +// } +// } +// } + + +// //bfs.pushAndSetReached(s); + +// typename ErasingResGraphWrapper:: +// NodeMap& dist=res_graph.dist; + +// while ( !bfs.finished() ) { +// typename ErasingResGraphWrapper::OutEdgeIt e=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 + +// bool __augment=true; + +// while (__augment) { + +// __augment=false; +// //computing blocking flow with dfs +// typedef typename EAugGraph::NodeMap BlockingReachedMap; +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > +// dfs(res_graph); +// typename EAugGraph::NodeMap pred(res_graph, INVALID); +// //pred.set(s, EAugEdge(INVALID)); +// //invalid iterators for sources + +// typename EAugGraph::NodeMap free(res_graph); + + +// //typename AugGraph::NodeMap pred(res_graph); +// for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { +// if (S->get(s)) { +// Number u=0; +// for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) +// u+=flow->get(e); +// if (u<1) { +// dfs.pushAndSetReached(s); +// //pred.set(s, AugEdge(INVALID)); +// } +// } +// } + + + +// //dfs.pushAndSetReached(s); +// typename EAugGraph::Node n; +// while (!dfs.finished()) { +// ++dfs; +// if (res_graph.valid(EAugOutEdgeIt(dfs))) { +// if (dfs.isBNodeNewlyReached()) { + +// typename EAugGraph::Node v=res_graph.aNode(dfs); +// typename EAugGraph::Node w=res_graph.bNode(dfs); + +// pred.set(w, EAugOutEdgeIt(dfs)); +// if (res_graph.valid(pred.get(v))) { +// free.set(w, std::min(free.get(v), res_graph.free(dfs))); +// } else { +// free.set(w, res_graph.free(dfs)); +// } + +// n=w; +// if (T->get(w)) { +// Number u=0; +// for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) +// u+=flow->get(f); +// if (u<1) { +// __augment=true; +// _augment=true; +// break; +// } +// } +// } else { +// res_graph.erase(dfs); +// } +// } + +// } + +// if (__augment) { +// // typename EAugGraph::Node n=t; +// Number augment_value=free.get(n); +// while (res_graph.valid(pred.get(n))) { +// EAugEdge e=pred.get(n); +// res_graph.augment(e, 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); 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 > bfs(res_graph); +// // for(typename std::list::const_iterator i=S.begin(); +// // i!=S.end(); ++i) { +// // bfs.pushAndSetReached(*i); +// // } +// // //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 ( !bfs.finished() ) { +// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); +// // if (e.valid() && 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; +// // } +// // } + +// // ++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 //HUGO_EDMONDS_KARP_H diff -r 60b578e3d507 -r 7eb324ed5da3 src/work/marci/iterator_bfs_demo.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/marci/iterator_bfs_demo.cc Mon Apr 05 15:02:39 2004 +0000 @@ -0,0 +1,322 @@ +// -*- c++ -*- +#include +#include +#include + +#include +#include +#include +#include + +using namespace hugo; +using std::cout; +using std::endl; +using std::string; + +template +class EdgeNameMap { + Graph& graph; + NodeNameMap& node_name_map; +public: + EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : + graph(_graph), node_name_map(_node_name_map) { } + string get(typename Graph::Edge e) const { + return + (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); + } +}; + +int main (int, char*[]) +{ + //typedef SmartGraph Graph; + typedef ListGraph Graph; + + typedef Graph::Node Node; + typedef Graph::Edge Edge; + + Graph G; + + Node s=G.addNode(); + Node v1=G.addNode(); + Node v2=G.addNode(); + Node v3=G.addNode(); + Node v4=G.addNode(); + Node t=G.addNode(); + + Graph::NodeMap node_name(G); + node_name.set(s, "s"); + node_name.set(v1, "v1"); + node_name.set(v2, "v2"); + node_name.set(v3, "v3"); + node_name.set(v4, "v4"); + node_name.set(t, "t"); + + G.addEdge(s, v1); + G.addEdge(s, v2); + G.addEdge(v1, v2); + G.addEdge(v2, v1); + G.addEdge(v1, v3); + G.addEdge(v3, v2); + G.addEdge(v2, v4); + G.addEdge(v4, v3); + G.addEdge(v3, t); + G.addEdge(v4, t); + + cout << " /--> -------------> "<< endl; + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; + cout << " / | | / /-> \\ "<< endl; + cout << " / | | / | ^ \\ "<< endl; + cout << "s | | / | | \\-> t "<< endl; + cout << " \\ | | / | | /-> "<< endl; + cout << " \\ | --/ / | | / "<< endl; + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; + cout << " \\--> -------------> "<< endl; + +// typedef TrivGraphWrapper CGW; +// CGW gw(G); + +// cout << "bfs and dfs demo on the directed graph" << endl; +// for(CGW::NodeIt n=gw.first(); n.valid(); ++n) { +// cout << n << ": "; +// cout << "out edges: "; +// for(CGW::OutEdgeIt e=gw.first(n); e.valid(); ++e) +// cout << e << " "; +// cout << "in edges: "; +// for(CGW::InEdgeIt e=gw.first(n); e.valid(); ++e) +// cout << e << " "; +// cout << endl; +// } + + { + typedef TrivGraphWrapper GW; + GW gw(G); + + EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); + + cout << "bfs and dfs iterator demo on the directed graph" << endl; + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { + cout << node_name.get(n) << ": "; + cout << "out edges: "; + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + cout << edge_name.get(e) << " "; + cout << "in edges: "; + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + cout << edge_name.get(e) << " "; + cout << endl; + } + + cout << "bfs from s ..." << endl; + BfsIterator5< GW, GW::NodeMap > bfs(gw); + bfs.pushAndSetReached(s); + while (!bfs.finished()) { + //cout << "edge: "; + if (gw.valid(bfs)) { + cout << edge_name.get(bfs) << /*endl*/", " << + node_name.get(gw.aNode(bfs)) << + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + node_name.get(gw.bNode(bfs)) << + (bfs.isBNodeNewlyReached() ? ": is newly reached." : + ": is not newly reached."); + } else { + cout << "invalid" << /*endl*/", " << + node_name.get(bfs.aNode()) << + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + + "invalid."; + } + cout << endl; + ++bfs; + } + + cout << " /--> -------------> "<< endl; + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; + cout << " / | | / /-> \\ "<< endl; + cout << " / | | / | ^ \\ "<< endl; + cout << "s | | / | | \\-> t "<< endl; + cout << " \\ | | / | | /-> "<< endl; + cout << " \\ | --/ / | | / "<< endl; + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; + cout << " \\--> -------------> "<< endl; + + cout << "dfs from s ..." << endl; + DfsIterator5< GW, GW::NodeMap > dfs(gw); + dfs.pushAndSetReached(s); + while (!dfs.finished()) { + ++dfs; + //cout << "edge: "; + if (gw.valid(dfs)) { + cout << edge_name.get(dfs) << /*endl*/", " << + node_name.get(gw.aNode(dfs)) << + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + node_name.get(gw.bNode(dfs)) << + (dfs.isBNodeNewlyReached() ? ": is newly reached." : + ": is not newly reached."); + } else { + cout << "invalid" << /*endl*/", " << + node_name.get(dfs.aNode()) << + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + + "invalid."; + } + cout << endl; + } + } + + + { + typedef RevGraphWrapper > GW; + GW gw(G); + + EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); + + cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { + cout << node_name.get(n) << ": "; + cout << "out edges: "; + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + cout << edge_name.get(e) << " "; + cout << "in edges: "; + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + cout << edge_name.get(e) << " "; + cout << endl; + } + + cout << "bfs from t ..." << endl; + BfsIterator5< GW, GW::NodeMap > bfs(gw); + bfs.pushAndSetReached(t); + while (!bfs.finished()) { + //cout << "edge: "; + if (gw.valid(bfs)) { + cout << edge_name.get(bfs) << /*endl*/", " << + node_name.get(gw.aNode(bfs)) << + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + node_name.get(gw.bNode(bfs)) << + (bfs.isBNodeNewlyReached() ? ": is newly reached." : + ": is not newly reached."); + } else { + cout << "invalid" << /*endl*/", " << + node_name.get(bfs.aNode()) << + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + + "invalid."; + } + cout << endl; + ++bfs; + } + + cout << " /--> -------------> "<< endl; + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; + cout << " / | | / /-> \\ "<< endl; + cout << " / | | / | ^ \\ "<< endl; + cout << "s | | / | | \\-> t "<< endl; + cout << " \\ | | / | | /-> "<< endl; + cout << " \\ | --/ / | | / "<< endl; + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; + cout << " \\--> -------------> "<< endl; + + cout << "dfs from t ..." << endl; + DfsIterator5< GW, GW::NodeMap > dfs(gw); + dfs.pushAndSetReached(t); + while (!dfs.finished()) { + ++dfs; + //cout << "edge: "; + if (gw.valid(dfs)) { + cout << edge_name.get(dfs) << /*endl*/", " << + node_name.get(gw.aNode(dfs)) << + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + node_name.get(gw.bNode(dfs)) << + (dfs.isBNodeNewlyReached() ? ": is newly reached." : + ": is not newly reached."); + } else { + cout << "invalid" << /*endl*/", " << + node_name.get(dfs.aNode()) << + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + + "invalid."; + } + cout << endl; + } + } + + { + //typedef UndirGraphWrapper GW; + typedef UndirGraphWrapper > GW; + GW gw(G); + + EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); + + cout << "bfs and dfs iterator demo on the undirected graph" << endl; + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { + cout << node_name.get(n) << ": "; + cout << "out edges: "; + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + cout << edge_name.get(e) << " "; + cout << "in edges: "; + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + cout << edge_name.get(e) << " "; + cout << endl; + } +// for(GW::EdgeIt e=gw.first(); gw.valid(e); gw.next(e)) { +// cout << edge_name.get(e) << " "; +// } +// cout << endl; + + cout << "bfs from t ..." << endl; + BfsIterator5< GW, GW::NodeMap > bfs(gw); + bfs.pushAndSetReached(t); + while (!bfs.finished()) { + //cout << "edge: "; + if (gw.valid(GW::OutEdgeIt(bfs))) { + cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << + node_name.get(gw.aNode(bfs)) << + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + node_name.get(gw.bNode(bfs)) << + (bfs.isBNodeNewlyReached() ? ": is newly reached." : + ": is not newly reached."); + } else { + cout << "invalid" << /*endl*/", " << + node_name.get(bfs.aNode()) << + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + + "invalid."; + } + cout << endl; + ++bfs; + } + + cout << " /--> -------------> "<< endl; + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; + cout << " / | | / /-> \\ "<< endl; + cout << " / | | / | ^ \\ "<< endl; + cout << "s | | / | | \\-> t "<< endl; + cout << " \\ | | / | | /-> "<< endl; + cout << " \\ | --/ / | | / "<< endl; + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; + cout << " \\--> -------------> "<< endl; + + cout << "dfs from t ..." << endl; + DfsIterator5< GW, GW::NodeMap > dfs(gw); + dfs.pushAndSetReached(t); + while (!dfs.finished()) { + ++dfs; + //cout << "edge: "; + if (gw.valid(GW::OutEdgeIt(dfs))) { + cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << + node_name.get(gw.aNode(dfs)) << + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + node_name.get(gw.bNode(dfs)) << + (dfs.isBNodeNewlyReached() ? ": is newly reached." : + ": is not newly reached."); + } else { + cout << "invalid" << /*endl*/", " << + node_name.get(dfs.aNode()) << + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + + "invalid."; + } + cout << endl; + } + } + + return 0; +}