diff -r d9691d0102bd -r 6e6db1c49bc1 src/work/marci/graph_wrapper.h --- a/src/work/marci/graph_wrapper.h Thu Apr 08 13:11:58 2004 +0000 +++ b/src/work/marci/graph_wrapper.h Tue Apr 13 20:35:47 2004 +0000 @@ -6,156 +6,6 @@ namespace hugo { -// template -// class TrivGraphWrapper { -// protected: -// Graph* graph; - -// public: -// // typedef Graph BaseGraph; -// typedef Graph ParentGraph; - -// // TrivGraphWrapper() : graph(0) { } -// TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } -// // void setGraph(Graph& _graph) { graph = &_graph; } -// // Graph& getGraph() const { return *graph; } - -// typedef typename Graph::Node Node; -// class NodeIt : public Graph::NodeIt { -// public: -// NodeIt() { } -// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } -// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } -// NodeIt(const TrivGraphWrapper& _G) : -// Graph::NodeIt(*(_G.graph)) { } -// }; -// typedef typename Graph::Edge Edge; -// class OutEdgeIt : public Graph::OutEdgeIt { -// public: -// OutEdgeIt() { } -// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } -// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } -// OutEdgeIt(const TrivGraphWrapper& _G, const Node& n) : -// Graph::OutEdgeIt(*(_G.graph), n) { } -// }; -// class InEdgeIt : public Graph::InEdgeIt { -// public: -// InEdgeIt() { } -// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } -// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } -// InEdgeIt(const TrivGraphWrapper& _G, const Node& n) : -// Graph::InEdgeIt(*(_G.graph), n) { } -// }; -// //typedef typename Graph::SymEdgeIt SymEdgeIt; -// class EdgeIt : public Graph::EdgeIt { -// public: -// EdgeIt() { } -// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } -// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } -// EdgeIt(const TrivGraphWrapper& _G) : -// Graph::EdgeIt(*(_G.graph)) { } -// }; - -// NodeIt& first(NodeIt& i) const { -// i=NodeIt(*this); -// return i; -// } -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { -// i=OutEdgeIt(*this, p); -// return i; -// } -// InEdgeIt& first(InEdgeIt& i, const Node& p) const { -// i=InEdgeIt(*this, p); -// return i; -// } -// EdgeIt& first(EdgeIt& i) const { -// i=EdgeIt(*this); -// return i; -// } -// // template I& first(I& i) const { -// // i=I(*this); -// // return i; -// // } -// // template I& first(I& i, const P& p) const { -// // i=I(*this, p); -// // return i; -// // } - -// // template I getNext(const I& i) const { -// // return graph->getNext(i); } - -// NodeIt& next(NodeIt& i) const { graph->next(i); return i; } -// OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } -// InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } -// EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } -// // template I& next(I &i) const { graph->next(i); return i; } -// template< typename It > It first() const { -// It e; this->first(e); return e; } - -// template< typename It > It first(const Node& v) const { -// It e; this->first(e, v); return e; } - -// Node head(const Edge& e) const { return graph->head(e); } -// Node tail(const Edge& e) const { return graph->tail(e); } - -// template bool valid(const I& i) const { -// return graph->valid(i); } - -// //template void setInvalid(const I &i); -// //{ return graph->setInvalid(i); } - -// int nodeNum() const { return graph->nodeNum(); } -// int edgeNum() const { return graph->edgeNum(); } - -// template Node aNode(const I& e) const { -// return graph->aNode(e); } -// template Node bNode(const I& e) const { -// return graph->bNode(e); } - -// Node addNode() const { return graph->addNode(); } -// Edge addEdge(const Node& tail, const Node& head) const { -// return graph->addEdge(tail, head); } - -// template void erase(const I& i) const { graph->erase(i); } - -// void clear() const { graph->clear(); } - -// template class NodeMap : public Graph::NodeMap { -// public: -// NodeMap(const TrivGraphWrapper& _G) : -// Graph::NodeMap(*(_G.graph)) { } -// NodeMap(const TrivGraphWrapper& _G, T a) : -// Graph::NodeMap(*(_G.graph), a) { } -// }; - -// template class EdgeMap : public Graph::EdgeMap { -// public: -// EdgeMap(const TrivGraphWrapper& _G) : -// Graph::EdgeMap(*(_G.graph)) { } -// EdgeMap(const TrivGraphWrapper& _G, T a) : -// Graph::EdgeMap(*(_G.graph), a) { } -// }; - -// // template class NodeMapWrapper { -// // protected: -// // Map* map; -// // public: -// // NodeMapWrapper(Map& _map) : map(&_map) { } -// // void set(Node n, T a) { map->set(n, a); } -// // T get(Node n) const { return map->get(n); } -// // }; - -// // template class EdgeMapWrapper { -// // protected: -// // Map* map; -// // public: -// // EdgeMapWrapper(Map& _map) : map(&_map) { } -// // void set(Edge n, T a) { map->set(n, a); } -// // T get(Edge n) const { return map->get(n); } -// // }; -// }; - - template class GraphWrapper { protected: @@ -170,77 +20,100 @@ // void setGraph(Graph& _graph) { graph=&_graph; } // Graph& getGraph() const { return *graph; } - typedef typename Graph::Node Node; - class NodeIt : public Graph::NodeIt { - typedef typename Graph::NodeIt GraphNodeIt; +// typedef typename Graph::Node Node; + class Node : public Graph::Node { + friend class GraphWrapper; public: + Node() { } + Node(const typename Graph::Node& _n) : Graph::Node(_n) { } + Node(const Invalid& i) : Graph::Node(i) { } + }; + class NodeIt { + friend class GraphWrapper; + typename Graph::NodeIt n; + public: NodeIt() { } - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } - NodeIt(const Invalid& i) : Graph::NodeIt(i) { } - NodeIt(const GraphWrapper& _G) : - Graph::NodeIt(*(_G.graph)) { } -// operator Node() const { -// std::cout << "ize" << std::endl; -// return Node(this->GraphNodeIt); -// } + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } + NodeIt(const Invalid& i) : n(i) { } + NodeIt(const GraphWrapper& _G) : n(*(_G.graph)) { } + operator Node() const { return Node(typename Graph::Node(n)); } }; - typedef typename Graph::Edge Edge; - class OutEdgeIt : public Graph::OutEdgeIt { - typedef typename Graph::OutEdgeIt GraphOutEdgeIt; +// class Node : public Graph::Node { +// public: +// Node() { } +// Node(const typename Graph::Node& n) : Graph::Node(n) { } +// Node(const Invalid& i) : Graph::Node(i) { } +// }; +// class NodeIt : public Graph::NodeIt { +// typedef typename Graph::NodeIt GraphNodeIt; +// public: +// NodeIt() { } +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } +// NodeIt(const GraphWrapper& _G) : +// Graph::NodeIt(*(_G.graph)) { } +// operator Node() const { +// return Node(typename Graph::Node( +// static_cast(*this) +// )); +// } +// }; +// typedef typename Graph::Edge Edge; + class Edge : public Graph::Edge { + friend class GraphWrapper; + public: + Edge() { } + Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } + Edge(const Invalid& i) : Graph::Edge(i) { } + }; + class OutEdgeIt { + friend class GraphWrapper; +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; + typename Graph::OutEdgeIt e; public: OutEdgeIt() { } - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } - OutEdgeIt(const GraphWrapper& _G, const Node& n) : - Graph::OutEdgeIt(*(_G.graph), n) { } -// operator Edge() const { -// std::cout << "ize" << std::endl; -// return Edge(this->GraphOutEdgeIt); -// } + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } + OutEdgeIt(const Invalid& i) : e(i) { } + OutEdgeIt(const GraphWrapper& _G, const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; - class InEdgeIt : public Graph::InEdgeIt { - typedef typename Graph::InEdgeIt GraphInEdgeIt; + class InEdgeIt { + friend class GraphWrapper; +// typedef typename Graph::InEdgeIt GraphInEdgeIt; + typename Graph::InEdgeIt e; public: InEdgeIt() { } - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } - InEdgeIt(const GraphWrapper& _G, const Node& n) : - Graph::InEdgeIt(*(_G.graph), n) { } -// operator Edge() const { -// std::cout << "ize" << std::endl; -// return Edge(this->InOutEdgeIt); -// } + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } + InEdgeIt(const Invalid& i) : e(i) { } + InEdgeIt(const GraphWrapper& _G, const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; //typedef typename Graph::SymEdgeIt SymEdgeIt; - class EdgeIt : public Graph::EdgeIt { - typedef typename Graph::EdgeIt GraphEdgeIt; + class EdgeIt { + friend class GraphWrapper; +// typedef typename Graph::EdgeIt GraphEdgeIt; + typename Graph::EdgeIt e; public: EdgeIt() { } - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } - EdgeIt(const GraphWrapper& _G) : - Graph::EdgeIt(*(_G.graph)) { } -// operator Edge() const { -// std::cout << "ize" << std::endl; -// return Edge(this->GraphEdgeIt); -// } + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } + EdgeIt(const Invalid& i) : e(i) { } + EdgeIt(const GraphWrapper& _G) : e(*(_G.graph)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); - return i; + i=NodeIt(*this); return i; } OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); - return i; + i=OutEdgeIt(*this, p); return i; } InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); - return i; + i=InEdgeIt(*this, p); return i; } EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); - return i; + i=EdgeIt(*this); return i; } // template I& first(I& i) const { // i=I(*this); @@ -254,10 +127,10 @@ // template I getNext(const I& i) const { // return gw.getNext(i); } - NodeIt& next(NodeIt& i) const { graph->next(i); return i; } - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; } - InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; } - EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; } + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } // template I& next(I &i) const { graph->next(i); return i; } template< typename It > It first() const { It e; this->first(e); return e; } @@ -265,12 +138,18 @@ template< typename It > It first(const Node& v) const { It e; this->first(e, v); return e; } - Node head(const Edge& e) const { return graph->head(e); } - Node tail(const Edge& e) const { return graph->tail(e); } + Node head(const Edge& e) const { + return Node(graph->head(static_cast(e))); } + Node tail(const Edge& e) const { + return Node(graph->tail(static_cast(e))); } // Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); } - template bool valid(const I& i) const { - return graph->valid(i); } + bool valid(const Node& n) const { + return graph->valid(static_cast(n)); } + bool valid(const Edge& e) const { + return graph->valid(static_cast(e)); } +// template bool valid(const I& i) const { +// return graph->valid(i); } //template void setInvalid(const I &i); //{ return graph->setInvalid(i); } @@ -278,16 +157,22 @@ int nodeNum() const { return graph->nodeNum(); } int edgeNum() const { return graph->edgeNum(); } - template Node aNode(const I& e) const { - return graph->aNode(e); } - template Node bNode(const I& e) const { - return graph->bNode(e); } + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } +// template Node aNode(const I& e) const { +// return Node(graph->aNode(e.e)); } +// template Node bNode(const I& e) const { +// return Node(graph->bNode(e.e)); } - Node addNode() const { return graph->addNode(); } + Node addNode() const { return Node(graph->addNode()); } Edge addEdge(const Node& tail, const Node& head) const { - return graph->addEdge(tail, head); } - - template void erase(const I& i) const { graph->erase(i); } + return Edge(graph->addEdge(tail, head)); } + + void erase(const Node& i) const { graph->erase(i); } + void erase(const Edge& i) const { graph->erase(i); } +// template void erase(const I& i) const { graph->erase(i); } void clear() const { graph->clear(); } @@ -297,6 +182,9 @@ Graph::NodeMap(*(_G.graph)) { } NodeMap(const GraphWrapper& _G, T a) : Graph::NodeMap(*(_G.graph), a) { } +// T operator[](const Node& n) const { +// return Graph::NodeMap::operator[](n); +// } }; template class EdgeMap : public Graph::EdgeMap { @@ -429,80 +317,144 @@ GraphWrapper(_graph), node_filter_map(&_node_filter_map), edge_filter_map(&_edge_filter_map) { } - - typedef typename Graph::Node Node; - class NodeIt : public Graph::NodeIt { -// typedef typename Graph::NodeIt GraphNodeIt; - public: + typedef typename GraphWrapper::Node Node; + class NodeIt { + friend class GraphWrapper; + friend class SubGraphWrapper; + typename Graph::NodeIt n; + public: NodeIt() { } - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } - NodeIt(const Invalid& i) : Graph::NodeIt(i) { } + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } + NodeIt(const Invalid& i) : n(i) { } NodeIt(const SubGraphWrapper& _G) : - Graph::NodeIt(*(_G.graph)) { - while (_G.graph->valid((*this)/*.GraphNodeIt*/) && - !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) - _G.graph->next((*this)/*.GraphNodeIt*/); + n(*(_G.graph)) { + while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) + _G.graph->next(n); } + operator Node() const { return Node(typename Graph::Node(n)); } }; - typedef typename Graph::Edge Edge; - class OutEdgeIt : public Graph::OutEdgeIt { +// class NodeIt : public Graph::NodeIt { +// // typedef typename Graph::NodeIt GraphNodeIt; +// public: +// NodeIt() { } +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } +// NodeIt(const SubGraphWrapper& _G) : +// Graph::NodeIt(*(_G.graph)) { +// while (_G.graph->valid((*this)/*.GraphNodeIt*/) && +// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) +// _G.graph->next((*this)/*.GraphNodeIt*/); +// } +// }; + typedef typename GraphWrapper::Edge Edge; + class OutEdgeIt { + friend class GraphWrapper; + friend class SubGraphWrapper; // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; + typename Graph::OutEdgeIt e; public: OutEdgeIt() { } - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } - OutEdgeIt(const SubGraphWrapper& - _G, const Node& n) : - Graph::OutEdgeIt(*(_G.graph), n) { - while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && - !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) - _G.graph->next((*this)/*.GraphOutEdgeIt*/); + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } + OutEdgeIt(const Invalid& i) : e(i) { } + OutEdgeIt(const SubGraphWrapper& _G, + const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) + _G.graph->next(e); } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; - class InEdgeIt : public Graph::InEdgeIt { + class InEdgeIt { + friend class GraphWrapper; + friend class SubGraphWrapper; // typedef typename Graph::InEdgeIt GraphInEdgeIt; + typename Graph::InEdgeIt e; public: InEdgeIt() { } - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } + InEdgeIt(const Invalid& i) : e(i) { } InEdgeIt(const SubGraphWrapper& _G, - const Node& n) : - Graph::InEdgeIt(*(_G.graph), n) { - while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && - !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) - _G.graph->next((*this)/*.GraphInEdgeIt*/); + const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) + _G.graph->next(e); } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; -// //typedef typename Graph::SymEdgeIt SymEdgeIt; - class EdgeIt : public Graph::EdgeIt { + //typedef typename Graph::SymEdgeIt SymEdgeIt; + class EdgeIt { + friend class GraphWrapper; + friend class SubGraphWrapper; // typedef typename Graph::EdgeIt GraphEdgeIt; + typename Graph::EdgeIt e; public: EdgeIt() { } - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } + EdgeIt(const Invalid& i) : e(i) { } EdgeIt(const SubGraphWrapper& _G) : - Graph::EdgeIt(*(_G.graph)) { - while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && - !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) - _G.graph->next((*this)/*.GraphEdgeIt*/); + e(*(_G.graph)) { + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) + _G.graph->next(e); } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; +// operator Edge() const { return Edge(typename Graph::Edge(e)); } +// }; +// class OutEdgeIt : public Graph::OutEdgeIt { +// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; +// public: +// OutEdgeIt() { } +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } +// OutEdgeIt(const SubGraphWrapper& +// _G, const Node& n) : +// Graph::OutEdgeIt(*(_G.graph), n) { +// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && +// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) +// _G.graph->next((*this)/*.GraphOutEdgeIt*/); +// } +// }; +// class InEdgeIt : public Graph::InEdgeIt { +// // typedef typename Graph::InEdgeIt GraphInEdgeIt; +// public: +// InEdgeIt() { } +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } +// InEdgeIt(const SubGraphWrapper& _G, +// const Node& n) : +// Graph::InEdgeIt(*(_G.graph), n) { +// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && +// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) +// _G.graph->next((*this)/*.GraphInEdgeIt*/); +// } +// }; +// // //typedef typename Graph::SymEdgeIt SymEdgeIt; +// class EdgeIt : public Graph::EdgeIt { +// // typedef typename Graph::EdgeIt GraphEdgeIt; +// public: +// EdgeIt() { } +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } +// EdgeIt(const SubGraphWrapper& _G) : +// Graph::EdgeIt(*(_G.graph)) { +// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && +// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) +// _G.graph->next((*this)/*.GraphEdgeIt*/); +// } +// }; - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); - return i; + + NodeIt& first(NodeIt& i) const { + i=NodeIt(*this); return i; } - OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { - i=OutEdgeIt(*this, n); - return i; + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { + i=OutEdgeIt(*this, p); return i; } - InEdgeIt& first(InEdgeIt& i, const Node& n) const { - i=InEdgeIt(*this, n); - return i; + InEdgeIt& first(InEdgeIt& i, const Node& p) const { + i=InEdgeIt(*this, p); return i; } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); - return i; + EdgeIt& first(EdgeIt& i) const { + i=EdgeIt(*this); return i; } // template I& first(I& i) const { @@ -519,26 +471,32 @@ // } NodeIt& next(NodeIt& i) const { - graph->next(i); - while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } + graph->next(i.n); + while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); } return i; } OutEdgeIt& next(OutEdgeIt& i) const { - graph->next(i); - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } + graph->next(i.e); + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } return i; } InEdgeIt& next(InEdgeIt& i) const { - graph->next(i); - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } + graph->next(i.e); + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } return i; } EdgeIt& next(EdgeIt& i) const { - graph->next(i); - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } + graph->next(i.e); + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } return i; } + + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } + //template I getNext(const I& i) const { // return gw.getNext(i); //} @@ -556,6 +514,147 @@ It e; this->first(e, v); return e; } }; +// //Subgraph on the same node-set and partial edge-set +// template +// class SubGraphWrapper : public GraphWrapper { +// protected: +// NodeFilterMap* node_filter_map; +// EdgeFilterMap* edge_filter_map; +// public: +// // SubGraphWrapper() : GraphWrapper(), filter_map(0) { } +// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, +// EdgeFilterMap& _edge_filter_map) : +// GraphWrapper(_graph), node_filter_map(&_node_filter_map), +// edge_filter_map(&_edge_filter_map) { } + + +// typedef typename Graph::Node Node; +// class NodeIt : public Graph::NodeIt { +// // typedef typename Graph::NodeIt GraphNodeIt; +// public: +// NodeIt() { } +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } +// NodeIt(const SubGraphWrapper& _G) : +// Graph::NodeIt(*(_G.graph)) { +// while (_G.graph->valid((*this)/*.GraphNodeIt*/) && +// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) +// _G.graph->next((*this)/*.GraphNodeIt*/); +// } +// }; +// typedef typename Graph::Edge Edge; +// class OutEdgeIt : public Graph::OutEdgeIt { +// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; +// public: +// OutEdgeIt() { } +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } +// OutEdgeIt(const SubGraphWrapper& +// _G, const Node& n) : +// Graph::OutEdgeIt(*(_G.graph), n) { +// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && +// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) +// _G.graph->next((*this)/*.GraphOutEdgeIt*/); +// } +// }; +// class InEdgeIt : public Graph::InEdgeIt { +// // typedef typename Graph::InEdgeIt GraphInEdgeIt; +// public: +// InEdgeIt() { } +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } +// InEdgeIt(const SubGraphWrapper& _G, +// const Node& n) : +// Graph::InEdgeIt(*(_G.graph), n) { +// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && +// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) +// _G.graph->next((*this)/*.GraphInEdgeIt*/); +// } +// }; +// // //typedef typename Graph::SymEdgeIt SymEdgeIt; +// class EdgeIt : public Graph::EdgeIt { +// // typedef typename Graph::EdgeIt GraphEdgeIt; +// public: +// EdgeIt() { } +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } +// EdgeIt(const SubGraphWrapper& _G) : +// Graph::EdgeIt(*(_G.graph)) { +// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && +// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) +// _G.graph->next((*this)/*.GraphEdgeIt*/); +// } +// }; + +// NodeIt& first(NodeIt& i) const { +// i=NodeIt(*this); +// return i; +// } +// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { +// i=OutEdgeIt(*this, n); +// return i; +// } +// InEdgeIt& first(InEdgeIt& i, const Node& n) const { +// i=InEdgeIt(*this, n); +// return i; +// } +// EdgeIt& first(EdgeIt& i) const { +// i=EdgeIt(*this); +// return i; +// } + +// // template I& first(I& i) const { +// // graph->first(i); +// // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } +// // return i; +// // } +// // template I& first(I& i, const P& p) const { +// // graph->first(i, p); +// // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } +// // return i; +// // } + +// NodeIt& next(NodeIt& i) const { +// graph->next(i); +// while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } +// return i; +// } +// OutEdgeIt& next(OutEdgeIt& i) const { +// graph->next(i); +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } +// return i; +// } +// InEdgeIt& next(InEdgeIt& i) const { +// graph->next(i); +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } +// return i; +// } +// EdgeIt& next(EdgeIt& i) const { +// graph->next(i); +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } +// return i; +// } + +// //template I getNext(const I& i) const { +// // return gw.getNext(i); +// //} +// // template I& next(I &i) const { +// // graph->next(i); +// // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } +// // return i; +// // } + +// template< typename It > It first() const { +// It e; this->first(e); return e; } + +// template< typename It > It first(const Node& v) const { +// It e; this->first(e, v); return e; } +// }; + // template // class UndirGraphWrapper { // protected: @@ -718,109 +817,129 @@ template class UndirGraphWrapper : public GraphWrapper { - protected: - typedef typename Graph::Edge GraphEdge; - typedef typename Graph::OutEdgeIt GraphOutEdgeIt; - typedef typename Graph::InEdgeIt GraphInEdgeIt; +// protected: +// typedef typename Graph::Edge GraphEdge; +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; +// typedef typename Graph::InEdgeIt GraphInEdgeIt; public: typedef typename GraphWrapper::Node Node; typedef typename GraphWrapper::NodeIt NodeIt; + typedef typename GraphWrapper::Edge Edge; + typedef typename GraphWrapper::EdgeIt EdgeIt; // UndirGraphWrapper() : GraphWrapper() { } UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } - class Edge { + +// class Edge { +// friend class UndirGraphWrapper; +// protected: +// bool out_or_in; //true iff out +// GraphOutEdgeIt out; +// GraphInEdgeIt in; +// public: +// Edge() : out_or_in(), out(), in() { } +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } +// operator GraphEdge() const { +// if (out_or_in) return(out); else return(in); +// } +// //FIXME +// //2 edges are equal if they "refer" to the same physical edge +// //is it good? +// friend bool operator==(const Edge& u, const Edge& v) { +// if (v.out_or_in) +// if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); +// //return (u.out_or_in && u.out==v.out); +// else +// if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); +// //return (!u.out_or_in && u.in==v.in); +// } +// friend bool operator!=(const Edge& u, const Edge& v) { +// if (v.out_or_in) +// if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); +// //return (!u.out_or_in || u.out!=v.out); +// else +// if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); +// //return (u.out_or_in || u.in!=v.in); +// } +// }; + + class OutEdgeIt { friend class UndirGraphWrapper; - protected: bool out_or_in; //true iff out - GraphOutEdgeIt out; - GraphInEdgeIt in; + typename Graph::OutEdgeIt out; + typename Graph::InEdgeIt in; public: - Edge() : out_or_in(), out(), in() { } - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } - operator GraphEdge() const { - if (out_or_in) return(out); else return(in); - } -//FIXME -//2 edges are equal if they "refer" to the same physical edge -//is it good? - friend bool operator==(const Edge& u, const Edge& v) { - if (v.out_or_in) - if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); - //return (u.out_or_in && u.out==v.out); - else - if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); - //return (!u.out_or_in && u.in==v.in); + OutEdgeIt() { } + OutEdgeIt(const Invalid& i) : Edge(i) { } + OutEdgeIt(const UndirGraphWrapper& _G, const Node& _n) { + out_or_in=true; _G.graph->first(out, _n); + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } } - friend bool operator!=(const Edge& u, const Edge& v) { - if (v.out_or_in) - if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); - //return (!u.out_or_in || u.out!=v.out); - else - if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); - //return (u.out_or_in || u.in!=v.in); - } - }; - - class OutEdgeIt : public Edge { - friend class UndirGraphWrapper; - public: - OutEdgeIt() : Edge() { } - OutEdgeIt(const Invalid& i) : Edge(i) { } - OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) - : Edge() { - out_or_in=true; _G.graph->first(out, n); - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } + operator Edge() const { + if (out_or_in) return Edge(out); else return Edge(in); } }; +// class OutEdgeIt : public Edge { +// friend class UndirGraphWrapper; +// public: +// OutEdgeIt() : Edge() { } +// OutEdgeIt(const Invalid& i) : Edge(i) { } +// OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) +// : Edge() { +// out_or_in=true; _G.graph->first(out, n); +// if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } +// } +// }; +//FIXME InEdgeIt typedef OutEdgeIt InEdgeIt; - class EdgeIt : public Edge { - friend class UndirGraphWrapper; - protected: - NodeIt v; - public: - EdgeIt() : Edge() { } - EdgeIt(const Invalid& i) : Edge(i) { } - EdgeIt(const UndirGraphWrapper& _G) - : Edge() { - out_or_in=true; - //Node v; - _G.first(v); - if (_G.valid(v)) _G.graph->first(out); else out=INVALID; - while (_G.valid(v) && !_G.graph->valid(out)) { - _G.graph->next(v); - if (_G.valid(v)) _G.graph->first(out); - } - } - }; +// class EdgeIt : public Edge { +// friend class UndirGraphWrapper; +// protected: +// NodeIt v; +// public: +// EdgeIt() : Edge() { } +// EdgeIt(const Invalid& i) : Edge(i) { } +// EdgeIt(const UndirGraphWrapper& _G) +// : Edge() { +// out_or_in=true; +// //Node v; +// _G.first(v); +// if (_G.valid(v)) _G.graph->first(out); else out=INVALID; +// while (_G.valid(v) && !_G.graph->valid(out)) { +// _G.graph->next(v); +// if (_G.valid(v)) _G.graph->first(out); +// } +// } +// }; - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { - e.out_or_in=true; graph->first(e.out, n); - if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } - return e; + NodeIt& first(NodeIt& i) const { + i=NodeIt(*this); return i; } - - EdgeIt& first(EdgeIt& e) const { - e.out_or_in=true; - //NodeIt v; - first(e.v); - if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; - while (valid(e.v) && !graph->valid(e.out)) { - graph->next(e.v); - if (valid(e.v)) graph->first(e.out, e.v); - } - return e; + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { + i=OutEdgeIt(*this, p); return i; + } +//FIXME +// InEdgeIt& first(InEdgeIt& i, const Node& p) const { +// i=InEdgeIt(*this, p); return i; +// } + EdgeIt& first(EdgeIt& i) const { + i=EdgeIt(*this); return i; } template I& first(I& i) const { graph->first(i); return i; } template I& first(I& i, const P& p) const { graph->first(i, p); return i; } + NodeIt& next(NodeIt& n) const { + GraphWrapper::next(n); + return n; + } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { - Node n=graph->tail(e.out); + typename Graph::Node n=graph->tail(e.out); graph->next(e.out); if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } } else { @@ -828,18 +947,14 @@ } return e; } - + //FIXME InEdgeIt EdgeIt& next(EdgeIt& e) const { - //NodeIt v=tail(e); - graph->next(e.out); - while (valid(e.v) && !graph->valid(e.out)) { - next(e.v); - if (valid(e.v)) graph->first(e.out, e.v); - } + GraphWrapper::next(n); +// graph->next(e.e); return e; } - template I& next(I &i) const { graph->next(i); return i; } +// template I& next(I &i) const { graph->next(i); return i; } // template I getNext(const I& i) const { return gw.getNext(i); } template< typename It > It first() const { @@ -968,12 +1083,14 @@ // }; + + template class ResGraphWrapper : public GraphWrapper { protected: - typedef typename Graph::OutEdgeIt GraphOutEdgeIt; - typedef typename Graph::InEdgeIt GraphInEdgeIt; - typedef typename Graph::Edge GraphEdge; +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; +// typedef typename Graph::InEdgeIt GraphInEdgeIt; +// typedef typename Graph::Edge GraphEdge; FlowMap* flow; const CapacityMap* capacity; public: @@ -989,49 +1106,104 @@ typedef typename GraphWrapper::Node Node; typedef typename GraphWrapper::NodeIt NodeIt; - class Edge { + class Edge : public Graph::Edge { friend class ResGraphWrapper; protected: - bool out_or_in; //true, iff out - GraphOutEdgeIt out; - GraphInEdgeIt in; + bool forward; //true, iff forward +// typename Graph::Edge e; public: - Edge() : out_or_in(true) { } - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } -// bool valid() const { -// return out_or_in && out.valid() || in.valid(); } + Edge() { } + Edge(const typename Graph::Edge& _e, bool _forward) : + Graph::Edge(_e), forward(_forward) { } + Edge(const Invalid& i) : Graph::Edge(i), forward(false) { } +//the unique invalid iterator friend bool operator==(const Edge& u, const Edge& v) { - if (v.out_or_in) - return (u.out_or_in && u.out==v.out); - else - return (!u.out_or_in && u.in==v.in); + return (v.forward==u.forward && + static_cast(u)== + static_cast(v)); } friend bool operator!=(const Edge& u, const Edge& v) { - if (v.out_or_in) - return (!u.out_or_in || u.out!=v.out); - else - return (u.out_or_in || u.in!=v.in); + return (v.forward!=u.forward || + static_cast(u)!= + static_cast(v)); } - operator GraphEdge() const { - if (out_or_in) return(out); else return(in); - } }; - class OutEdgeIt : public Edge { +// class Edge { +// friend class ResGraphWrapper; +// protected: +// bool out_or_in; //true, iff out +// GraphOutEdgeIt out; +// GraphInEdgeIt in; +// public: +// Edge() : out_or_in(true) { } +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } +// // bool valid() const { +// // return out_or_in && out.valid() || in.valid(); } +// friend bool operator==(const Edge& u, const Edge& v) { +// if (v.out_or_in) +// return (u.out_or_in && u.out==v.out); +// else +// return (!u.out_or_in && u.in==v.in); +// } +// friend bool operator!=(const Edge& u, const Edge& v) { +// if (v.out_or_in) +// return (!u.out_or_in || u.out!=v.out); +// else +// return (u.out_or_in || u.in!=v.in); +// } +// operator GraphEdge() const { +// if (out_or_in) return(out); else return(in); +// } +// }; + class OutEdgeIt { friend class ResGraphWrapper; + protected: + typename Graph::OutEdgeIt out; + typename Graph::InEdgeIt in; + bool forward; public: OutEdgeIt() { } //FIXME - OutEdgeIt(const Edge& e) : Edge(e) { } - OutEdgeIt(const Invalid& i) : Edge(i) { } - OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { +// OutEdgeIt(const Edge& e) : Edge(e) { } + OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } +//the unique invalid iterator + OutEdgeIt(const ResGraphWrapper& resG, Node v) { + forward=true; resG.graph->first(out, v); - while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } if (!resG.graph->valid(out)) { - out_or_in=0; + forward=false; resG.graph->first(in, v); - while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } } } + operator Edge() const { +// Edge e; +// e.forward=this->forward; +// if (this->forward) e=out; else e=in; +// return e; + if (this->forward) + return Edge(out, this->forward); + else + return Edge(in, this->forward); + } + }; +// class OutEdgeIt : public Edge { +// friend class ResGraphWrapper; +// public: +// OutEdgeIt() { } +// //FIXME +// OutEdgeIt(const Edge& e) : Edge(e) { } +// OutEdgeIt(const Invalid& i) : Edge(i) { } +// OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { +// resG.graph->first(out, v); +// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } +// if (!resG.graph->valid(out)) { +// out_or_in=0; +// resG.graph->first(in, v); +// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } +// } +// } // public: // OutEdgeIt& operator++() { // if (out_or_in) { @@ -1049,39 +1221,95 @@ // } // return *this; // } - }; +// }; //FIXME This is just for having InEdgeIt // class InEdgeIt : public Edge { }; - class EdgeIt : public Edge { + class InEdgeIt { friend class ResGraphWrapper; - NodeIt v; + protected: + typename Graph::OutEdgeIt out; + typename Graph::InEdgeIt in; + bool forward; + public: + InEdgeIt() { } + //FIXME +// OutEdgeIt(const Edge& e) : Edge(e) { } + InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } +//the unique invalid iterator + InEdgeIt(const ResGraphWrapper& resG, Node v) { + forward=true; + resG.graph->first(in, v); + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } + if (!resG.graph->valid(in)) { + forward=false; + resG.graph->first(out, v); + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } + } + } + operator Edge() const { +// Edge e; +// e.forward=this->forward; +// if (this->forward) e=out; else e=in; +// return e; + if (this->forward) + return Edge(in, this->forward); + else + return Edge(out, this->forward); + } + }; + + class EdgeIt { + friend class ResGraphWrapper; + protected: + typename Graph::EdgeIt e; + bool forward; public: EdgeIt() { } - //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } - EdgeIt(const Invalid& i) : Edge(i) { } - EdgeIt(const ResGraphWrapper& resG) : Edge() { - resG.graph->first(v); - if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } - while (resG.graph->valid(v) && !resG.graph->valid(out)) { - resG.graph->next(v); - if (resG.graph->valid(v)) resG.graph->first(out, v); - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } - } - if (!resG.graph->valid(out)) { - out_or_in=0; - resG.graph->first(v); - if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } - while (resG.graph->valid(v) && !resG.graph->valid(in)) { - resG.graph->next(v); - if (resG.graph->valid(v)) resG.graph->first(in, v); - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } - } + EdgeIt(const Invalid& i) : e(i), forward(false) { } + EdgeIt(const ResGraphWrapper& resG) { + forward=true; + resG.graph->first(e); + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); + if (!resG.graph->valid(e)) { + forward=false; + resG.graph->first(e); + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); } } + operator Edge() const { + return Edge(e, this->forward); + } + }; +// class EdgeIt : public Edge { +// friend class ResGraphWrapper; +// NodeIt v; +// public: +// EdgeIt() { } +// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } +// EdgeIt(const Invalid& i) : Edge(i) { } +// EdgeIt(const ResGraphWrapper& resG) : Edge() { +// resG.graph->first(v); +// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } +// while (resG.graph->valid(v) && !resG.graph->valid(out)) { +// resG.graph->next(v); +// if (resG.graph->valid(v)) resG.graph->first(out, v); +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } +// } +// if (!resG.graph->valid(out)) { +// out_or_in=0; +// resG.graph->first(v); +// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } +// while (resG.graph->valid(v) && !resG.graph->valid(in)) { +// resG.graph->next(v); +// if (resG.graph->valid(v)) resG.graph->first(in, v); +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } +// } +// } +// } // EdgeIt& operator++() { // if (out_or_in) { // ++out; @@ -1113,78 +1341,102 @@ // } // return *this; // } - }; +// }; NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); - return i; + i=NodeIt(*this); return i; } OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); - return i; + i=OutEdgeIt(*this, p); return i; } - //FIXME Not yet implemented - //InEdgeIt& first(InEdgeIt& i, const Node& p) const { - //i=InEdgeIt(*this, p); - // return i; - //} - EdgeIt& first(EdgeIt& e) const { - e=EdgeIt(*this); - return e; +// FIXME not tested + InEdgeIt& first(InEdgeIt& i, const Node& p) const { + i=InEdgeIt(*this, p); return i; + } + EdgeIt& first(EdgeIt& i) const { + i=EdgeIt(*this); return i; } - NodeIt& next(NodeIt& n) const { graph->next(n); return n; } + NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } OutEdgeIt& next(OutEdgeIt& e) const { - if (e.out_or_in) { + if (e.forward) { Node v=graph->aNode(e.out); graph->next(e.out); - while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } if (!graph->valid(e.out)) { - e.out_or_in=0; + e.forward=false; graph->first(e.in, v); - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } } } else { graph->next(e.in); - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } } return e; } - //FIXME Not yet implemented - //InEdgeIt& next(InEdgeIt& e) const { - // return e; - //} - EdgeIt& next(EdgeIt& e) const { - if (e.out_or_in) { +// FIXME Not tested + InEdgeIt& next(InEdgeIt& e) const { + if (e.forward) { + Node v=graph->aNode(e.in); + graph->next(e.in); + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } + if (!graph->valid(e.in)) { + e.forward=false; + graph->first(e.out, v); + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } + } + } else { graph->next(e.out); - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } - while (graph->valid(e.v) && !graph->valid(e.out)) { - graph->next(e.v); - if (graph->valid(e.v)) graph->first(e.out, e.v); - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } - } - if (!graph->valid(e.out)) { - e.out_or_in=0; - graph->first(e.v); - if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } - while (graph->valid(e.v) && !graph->valid(e.in)) { - graph->next(e.v); - if (graph->valid(e.v)) graph->first(e.in, e.v); - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } - } - } - } else { - graph->next(e.in); - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } - while (graph->valid(e.v) && !graph->valid(e.in)) { - graph->next(e.v); - if (graph->valid(e.v)) graph->first(e.in, e.v); - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } - } + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } + } + return e; + } + EdgeIt& next(EdgeIt& e) const { + if (e.forward) { + graph->next(e.e); + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } + if (!graph->valid(e.e)) { + e.forward=false; + graph->first(e.e); + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } } - return e; + } else { + graph->next(e.e); + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } } + return e; + } +// EdgeIt& next(EdgeIt& e) const { +// if (e.out_or_in) { +// graph->next(e.out); +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } +// while (graph->valid(e.v) && !graph->valid(e.out)) { +// graph->next(e.v); +// if (graph->valid(e.v)) graph->first(e.out, e.v); +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } +// } +// if (!graph->valid(e.out)) { +// e.out_or_in=0; +// graph->first(e.v); +// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// while (graph->valid(e.v) && !graph->valid(e.in)) { +// graph->next(e.v); +// if (graph->valid(e.v)) graph->first(e.in, e.v); +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// } +// } +// } else { +// graph->next(e.in); +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// while (graph->valid(e.v) && !graph->valid(e.in)) { +// graph->next(e.v); +// if (graph->valid(e.v)) graph->first(e.in, e.v); +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// } +// } +// return e; +// } template< typename It > @@ -1202,53 +1454,55 @@ } Node tail(Edge e) const { - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } + return ((e.forward) ? graph->tail(e) : graph->head(e)); } Node head(Edge e) const { - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } + return ((e.forward) ? graph->head(e) : graph->tail(e)); } Node aNode(OutEdgeIt e) const { - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } + return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); } Node bNode(OutEdgeIt e) const { - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } + return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); } int nodeNum() const { return graph->nodeNum(); } //FIXME //int edgeNum() const { return graph->edgeNum(); } - int id(Node v) const { return graph->id(v); } +// int id(Node v) const { return graph->id(v); } - bool valid(Node n) const { return graph->valid(n); } + bool valid(Node n) const { return GraphWrapper::valid(n); } bool valid(Edge e) const { - return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } + return graph->valid(e); + //return e.forward ? graph->valid(e.out) : graph->valid(e.in); + } void augment(const Edge& e, Number a) const { - if (e.out_or_in) + if (e.forward) // flow->set(e.out, flow->get(e.out)+a); - flow->set(e.out, (*flow)[e.out]+a); + flow->set(e, (*flow)[e]+a); else // flow->set(e.in, flow->get(e.in)-a); - flow->set(e.in, (*flow)[e.in]-a); + flow->set(e, (*flow)[e]-a); } Number resCap(const Edge& e) const { - if (e.out_or_in) + if (e.forward) // return (capacity->get(e.out)-flow->get(e.out)); - return ((*capacity)[e.out]-(*flow)[e.out]); + return ((*capacity)[e]-(*flow)[e]); else // return (flow->get(e.in)); - return ((*flow)[e.in]); + return ((*flow)[e]); } - Number resCap(GraphOutEdgeIt out) const { -// return (capacity->get(out)-flow->get(out)); - return ((*capacity)[out]-(*flow)[out]); - } +// Number resCap(typename Graph::OutEdgeIt out) const { +// // return (capacity->get(out)-flow->get(out)); +// return ((*capacity)[out]-(*flow)[out]); +// } - Number resCap(GraphInEdgeIt in) const { -// return (flow->get(in)); - return ((*flow)[in]); - } +// Number resCap(typename Graph::InEdgeIt in) const { +// // return (flow->get(in)); +// return ((*flow)[in]); +// } // template class NodeMap : public Graph::NodeMap { // public: @@ -1275,13 +1529,13 @@ EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } void set(Edge e, T a) { - if (e.out_or_in) + if (e.forward) forward_map.set(e.out, a); else backward_map.set(e.in, a); } T operator[](Edge e) const { - if (e.out_or_in) + if (e.forward) return forward_map[e.out]; else return backward_map[e.in]; @@ -1295,6 +1549,336 @@ }; }; + + +// template +// class ResGraphWrapper : public GraphWrapper { +// protected: +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; +// typedef typename Graph::InEdgeIt GraphInEdgeIt; +// typedef typename Graph::Edge GraphEdge; +// FlowMap* flow; +// const CapacityMap* capacity; +// public: + +// ResGraphWrapper(Graph& _graph, FlowMap& _flow, +// const CapacityMap& _capacity) : +// GraphWrapper(_graph), flow(&_flow), capacity(&_capacity) { } + +// class Edge; +// class OutEdgeIt; +// friend class Edge; +// friend class OutEdgeIt; + +// typedef typename GraphWrapper::Node Node; +// typedef typename GraphWrapper::NodeIt NodeIt; +// class Edge { +// friend class ResGraphWrapper; +// protected: +// bool out_or_in; //true, iff out +// GraphOutEdgeIt out; +// GraphInEdgeIt in; +// public: +// Edge() : out_or_in(true) { } +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } +// // bool valid() const { +// // return out_or_in && out.valid() || in.valid(); } +// friend bool operator==(const Edge& u, const Edge& v) { +// if (v.out_or_in) +// return (u.out_or_in && u.out==v.out); +// else +// return (!u.out_or_in && u.in==v.in); +// } +// friend bool operator!=(const Edge& u, const Edge& v) { +// if (v.out_or_in) +// return (!u.out_or_in || u.out!=v.out); +// else +// return (u.out_or_in || u.in!=v.in); +// } +// operator GraphEdge() const { +// if (out_or_in) return(out); else return(in); +// } +// }; +// class OutEdgeIt : public Edge { +// friend class ResGraphWrapper; +// public: +// OutEdgeIt() { } +// //FIXME +// OutEdgeIt(const Edge& e) : Edge(e) { } +// OutEdgeIt(const Invalid& i) : Edge(i) { } +// OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { +// resG.graph->first(out, v); +// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } +// if (!resG.graph->valid(out)) { +// out_or_in=0; +// resG.graph->first(in, v); +// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } +// } +// } +// // public: +// // OutEdgeIt& operator++() { +// // if (out_or_in) { +// // Node v=/*resG->*/G->aNode(out); +// // ++out; +// // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } +// // if (!out.valid()) { +// // out_or_in=0; +// // G->first(in, v); +// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } +// // } +// // } else { +// // ++in; +// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } +// // } +// // return *this; +// // } +// }; + +// //FIXME This is just for having InEdgeIt +// // class InEdgeIt : public Edge { }; + +// class EdgeIt : public Edge { +// friend class ResGraphWrapper; +// NodeIt v; +// public: +// EdgeIt() { } +// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } +// EdgeIt(const Invalid& i) : Edge(i) { } +// EdgeIt(const ResGraphWrapper& resG) : Edge() { +// resG.graph->first(v); +// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } +// while (resG.graph->valid(v) && !resG.graph->valid(out)) { +// resG.graph->next(v); +// if (resG.graph->valid(v)) resG.graph->first(out, v); +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } +// } +// if (!resG.graph->valid(out)) { +// out_or_in=0; +// resG.graph->first(v); +// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } +// while (resG.graph->valid(v) && !resG.graph->valid(in)) { +// resG.graph->next(v); +// if (resG.graph->valid(v)) resG.graph->first(in, v); +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } +// } +// } +// } +// // EdgeIt& operator++() { +// // if (out_or_in) { +// // ++out; +// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } +// // while (v.valid() && !out.valid()) { +// // ++v; +// // if (v.valid()) G->first(out, v); +// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } +// // } +// // if (!out.valid()) { +// // out_or_in=0; +// // G->first(v); +// // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } +// // while (v.valid() && !in.valid()) { +// // ++v; +// // if (v.valid()) G->first(in, v); +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } +// // } +// // } +// // } else { +// // ++in; +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } +// // while (v.valid() && !in.valid()) { +// // ++v; +// // if (v.valid()) G->first(in, v); +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } +// // } +// // } +// // return *this; +// // } +// }; + +// NodeIt& first(NodeIt& i) const { +// i=NodeIt(*this); +// return i; +// } +// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { +// i=OutEdgeIt(*this, p); +// return i; +// } +// //FIXME Not yet implemented +// //InEdgeIt& first(InEdgeIt& i, const Node& p) const { +// //i=InEdgeIt(*this, p); +// // return i; +// //} +// EdgeIt& first(EdgeIt& e) const { +// e=EdgeIt(*this); +// return e; +// } + +// NodeIt& next(NodeIt& n) const { graph->next(n); return n; } +// OutEdgeIt& next(OutEdgeIt& e) const { +// if (e.out_or_in) { +// Node v=graph->aNode(e.out); +// graph->next(e.out); +// while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } +// if (!graph->valid(e.out)) { +// e.out_or_in=0; +// graph->first(e.in, v); +// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// } +// } else { +// graph->next(e.in); +// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// } +// return e; +// } +// //FIXME Not yet implemented +// //InEdgeIt& next(InEdgeIt& e) const { +// // return e; +// //} +// EdgeIt& next(EdgeIt& e) const { +// if (e.out_or_in) { +// graph->next(e.out); +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } +// while (graph->valid(e.v) && !graph->valid(e.out)) { +// graph->next(e.v); +// if (graph->valid(e.v)) graph->first(e.out, e.v); +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } +// } +// if (!graph->valid(e.out)) { +// e.out_or_in=0; +// graph->first(e.v); +// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// while (graph->valid(e.v) && !graph->valid(e.in)) { +// graph->next(e.v); +// if (graph->valid(e.v)) graph->first(e.in, e.v); +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// } +// } +// } else { +// graph->next(e.in); +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// while (graph->valid(e.v) && !graph->valid(e.in)) { +// graph->next(e.v); +// if (graph->valid(e.v)) graph->first(e.in, e.v); +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } +// } +// } +// return e; +// } + + +// template< typename It > +// It first() const { +// It e; +// first(e); +// return e; +// } + +// template< typename It > +// It first(Node v) const { +// It e; +// first(e, v); +// return e; +// } + +// Node tail(Edge e) const { +// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } +// Node head(Edge e) const { +// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } + +// Node aNode(OutEdgeIt e) const { +// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } +// Node bNode(OutEdgeIt e) const { +// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } + +// int nodeNum() const { return graph->nodeNum(); } +// //FIXME +// //int edgeNum() const { return graph->edgeNum(); } + + +// int id(Node v) const { return graph->id(v); } + +// bool valid(Node n) const { return graph->valid(n); } +// bool valid(Edge e) const { +// return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } + +// void augment(const Edge& e, Number a) const { +// if (e.out_or_in) +// // flow->set(e.out, flow->get(e.out)+a); +// flow->set(e.out, (*flow)[e.out]+a); +// else +// // flow->set(e.in, flow->get(e.in)-a); +// flow->set(e.in, (*flow)[e.in]-a); +// } + +// Number resCap(const Edge& e) const { +// if (e.out_or_in) +// // return (capacity->get(e.out)-flow->get(e.out)); +// return ((*capacity)[e.out]-(*flow)[e.out]); +// else +// // return (flow->get(e.in)); +// return ((*flow)[e.in]); +// } + +// Number resCap(GraphOutEdgeIt out) const { +// // return (capacity->get(out)-flow->get(out)); +// return ((*capacity)[out]-(*flow)[out]); +// } + +// Number resCap(GraphInEdgeIt in) const { +// // return (flow->get(in)); +// return ((*flow)[in]); +// } + +// // template class NodeMap : public Graph::NodeMap { +// // public: +// // NodeMap(const ResGraphWrapper& _G) +// // : Graph::NodeMap(_G.gw) { } +// // NodeMap(const ResGraphWrapper& _G, +// // T a) : Graph::NodeMap(_G.gw, a) { } +// // }; + +// // template +// // class NodeMap { +// // typename Graph::NodeMap node_map; +// // public: +// // NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.graph)) { } +// // NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.graph), a) { } +// // void set(Node nit, T a) { node_map.set(nit, a); } +// // T get(Node nit) const { return node_map.get(nit); } +// // }; + +// template +// class EdgeMap { +// typename Graph::EdgeMap forward_map, backward_map; +// public: +// EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } +// EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } +// void set(Edge e, T a) { +// if (e.out_or_in) +// forward_map.set(e.out, a); +// else +// backward_map.set(e.in, a); +// } +// T operator[](Edge e) const { +// if (e.out_or_in) +// return forward_map[e.out]; +// else +// return backward_map[e.in]; +// } +// // T get(Edge e) const { +// // if (e.out_or_in) +// // return forward_map.get(e.out); +// // else +// // return backward_map.get(e.in); +// // } +// }; +// }; + + //ErasingFirstGraphWrapper for blocking flows template class ErasingFirstGraphWrapper : public GraphWrapper { @@ -1305,60 +1889,74 @@ FirstOutEdgesMap& _first_out_edges) : GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } - typedef typename Graph::Node Node; - class NodeIt : public Graph::NodeIt { - public: + typedef typename GraphWrapper::Node Node; + class NodeIt { + friend class GraphWrapper; + friend class ErasingFirstGraphWrapper; + typename Graph::NodeIt n; + public: NodeIt() { } - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } - NodeIt(const Invalid& i) : Graph::NodeIt(i) { } + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } + NodeIt(const Invalid& i) : n(i) { } NodeIt(const ErasingFirstGraphWrapper& _G) : - Graph::NodeIt(*(_G.graph)) { } + n(*(_G.graph)) { } + operator Node() const { return Node(typename Graph::Node(n)); } }; - typedef typename Graph::Edge Edge; - class OutEdgeIt : public Graph::OutEdgeIt { + typedef typename GraphWrapper::Edge Edge; + class OutEdgeIt { + friend class GraphWrapper; + friend class ErasingFirstGraphWrapper; +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; + typename Graph::OutEdgeIt e; public: OutEdgeIt() { } - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } + OutEdgeIt(const Invalid& i) : e(i) { } OutEdgeIt(const ErasingFirstGraphWrapper& _G, - const Node& n) : - Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } + const Node& _n) : + e((*_G.first_out_edges)[_n]) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; - class InEdgeIt : public Graph::InEdgeIt { + class InEdgeIt { + friend class GraphWrapper; + friend class ErasingFirstGraphWrapper; +// typedef typename Graph::InEdgeIt GraphInEdgeIt; + typename Graph::InEdgeIt e; public: InEdgeIt() { } - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } + InEdgeIt(const Invalid& i) : e(i) { } InEdgeIt(const ErasingFirstGraphWrapper& _G, - const Node& n) : - Graph::InEdgeIt(*(_G.graph), n) { } + const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; //typedef typename Graph::SymEdgeIt SymEdgeIt; - class EdgeIt : public Graph::EdgeIt { + class EdgeIt { + friend class GraphWrapper; + friend class ErasingFirstGraphWrapper; +// typedef typename Graph::EdgeIt GraphEdgeIt; + typename Graph::EdgeIt e; public: EdgeIt() { } - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } + EdgeIt(const Invalid& i) : e(i) { } EdgeIt(const ErasingFirstGraphWrapper& _G) : - Graph::EdgeIt(*(_G.graph)) { } + e(*(_G.graph)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } }; - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); - return i; + NodeIt& first(NodeIt& i) const { + i=NodeIt(*this); return i; } - OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { - i=OutEdgeIt(*this, n); -// i=(*first_out_edges)[n]; - return i; + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { + i=OutEdgeIt(*this, p); return i; } - InEdgeIt& first(InEdgeIt& i, const Node& n) const { - i=InEdgeIt(*this, n); - return i; + InEdgeIt& first(InEdgeIt& i, const Node& p) const { + i=InEdgeIt(*this, p); return i; } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); - return i; + EdgeIt& first(EdgeIt& i) const { + i=EdgeIt(*this); return i; } // template I& first(I& i) const { @@ -1380,22 +1978,15 @@ //} - NodeIt& next(NodeIt& i) const { - graph->next(i); - return i; - } - OutEdgeIt& next(OutEdgeIt& i) const { - graph->next(i); - return i; - } - InEdgeIt& next(InEdgeIt& i) const { - graph->next(i); - return i; - } - EdgeIt& next(EdgeIt& i) const { - graph->next(i); - return i; - } + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } + + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } // template I& next(I &i) const { // graph->next(i); @@ -1411,10 +2002,131 @@ void erase(const OutEdgeIt& e) const { OutEdgeIt f=e; this->next(f); - first_out_edges->set(this->tail(e), f); + first_out_edges->set(this->tail(e), f.e); } }; +// //ErasingFirstGraphWrapper for blocking flows +// template +// class ErasingFirstGraphWrapper : public GraphWrapper { +// protected: +// FirstOutEdgesMap* first_out_edges; +// public: +// ErasingFirstGraphWrapper(Graph& _graph, +// FirstOutEdgesMap& _first_out_edges) : +// GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } + +// typedef typename Graph::Node Node; +// class NodeIt : public Graph::NodeIt { +// public: +// NodeIt() { } +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } +// NodeIt(const ErasingFirstGraphWrapper& _G) : +// Graph::NodeIt(*(_G.graph)) { } +// }; +// typedef typename Graph::Edge Edge; +// class OutEdgeIt : public Graph::OutEdgeIt { +// public: +// OutEdgeIt() { } +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } +// OutEdgeIt(const ErasingFirstGraphWrapper& _G, +// const Node& n) : +// Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } +// }; +// class InEdgeIt : public Graph::InEdgeIt { +// public: +// InEdgeIt() { } +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } +// InEdgeIt(const ErasingFirstGraphWrapper& _G, +// const Node& n) : +// Graph::InEdgeIt(*(_G.graph), n) { } +// }; +// //typedef typename Graph::SymEdgeIt SymEdgeIt; +// class EdgeIt : public Graph::EdgeIt { +// public: +// EdgeIt() { } +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } +// EdgeIt(const ErasingFirstGraphWrapper& _G) : +// Graph::EdgeIt(*(_G.graph)) { } +// }; + +// NodeIt& first(NodeIt& i) const { +// i=NodeIt(*this); +// return i; +// } +// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { +// i=OutEdgeIt(*this, n); +// // i=(*first_out_edges)[n]; +// return i; +// } +// InEdgeIt& first(InEdgeIt& i, const Node& n) const { +// i=InEdgeIt(*this, n); +// return i; +// } +// EdgeIt& first(EdgeIt& i) const { +// i=EdgeIt(*this); +// return i; +// } + +// // template I& first(I& i) const { +// // graph->first(i); +// // return i; +// // } +// // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { +// // // e=first_out_edges->get(n); +// // e=(*first_out_edges)[n]; +// // return e; +// // } +// // template I& first(I& i, const P& p) const { +// // graph->first(i, p); +// // return i; +// // } + +// //template I getNext(const I& i) const { +// // return gw.getNext(i); +// //} + + +// NodeIt& next(NodeIt& i) const { +// graph->next(i); +// return i; +// } +// OutEdgeIt& next(OutEdgeIt& i) const { +// graph->next(i); +// return i; +// } +// InEdgeIt& next(InEdgeIt& i) const { +// graph->next(i); +// return i; +// } +// EdgeIt& next(EdgeIt& i) const { +// graph->next(i); +// return i; +// } + +// // template I& next(I &i) const { +// // graph->next(i); +// // return i; +// // } + +// template< typename It > It first() const { +// It e; this->first(e); return e; } + +// template< typename It > It first(const Node& v) const { +// It e; this->first(e, v); return e; } + +// void erase(const OutEdgeIt& e) const { +// OutEdgeIt f=e; +// this->next(f); +// first_out_edges->set(this->tail(e), f); +// } +// }; + + // // FIXME: comparison should be made better!!! // template // class ResGraphWrapper