marci@174: // -*- c++ -*- marci@259: #ifndef HUGO_GRAPH_WRAPPER_H marci@259: #define HUGO_GRAPH_WRAPPER_H marci@76: marci@174: #include marci@174: alpar@105: namespace hugo { marci@76: marci@303: template marci@303: class GraphWrapper { marci@212: protected: marci@303: Graph* graph; marci@212: marci@212: public: marci@311: typedef Graph BaseGraph; marci@303: typedef Graph ParentGraph; marci@212: marci@303: // GraphWrapper() : graph(0) { } marci@303: GraphWrapper(Graph& _graph) : graph(&_graph) { } marci@303: // void setGraph(Graph& _graph) { graph=&_graph; } marci@303: // Graph& getGraph() const { return *graph; } marci@303: marci@317: // typedef typename Graph::Node Node; marci@317: class Node : public Graph::Node { marci@317: friend class GraphWrapper; marci@265: public: marci@317: Node() { } marci@317: Node(const typename Graph::Node& _n) : Graph::Node(_n) { } marci@317: Node(const Invalid& i) : Graph::Node(i) { } marci@317: }; marci@317: class NodeIt { marci@317: friend class GraphWrapper; marci@317: typename Graph::NodeIt n; marci@317: public: marci@265: NodeIt() { } marci@317: NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } marci@317: NodeIt(const Invalid& i) : n(i) { } marci@317: NodeIt(const GraphWrapper& _G) : n(*(_G.graph)) { } marci@317: operator Node() const { return Node(typename Graph::Node(n)); } marci@265: }; marci@317: // typedef typename Graph::Edge Edge; marci@317: class Edge : public Graph::Edge { marci@317: friend class GraphWrapper; marci@317: public: marci@317: Edge() { } marci@317: Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } marci@317: Edge(const Invalid& i) : Graph::Edge(i) { } marci@317: }; marci@317: class OutEdgeIt { marci@317: friend class GraphWrapper; marci@317: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: typename Graph::OutEdgeIt e; marci@265: public: marci@265: OutEdgeIt() { } marci@317: OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@317: OutEdgeIt(const Invalid& i) : e(i) { } marci@317: OutEdgeIt(const GraphWrapper& _G, const Node& _n) : marci@317: e(*(_G.graph), typename Graph::Node(_n)) { } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@265: }; marci@317: class InEdgeIt { marci@317: friend class GraphWrapper; marci@317: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: typename Graph::InEdgeIt e; marci@265: public: marci@265: InEdgeIt() { } marci@317: InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@317: InEdgeIt(const Invalid& i) : e(i) { } marci@317: InEdgeIt(const GraphWrapper& _G, const Node& _n) : marci@317: e(*(_G.graph), typename Graph::Node(_n)) { } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@265: }; marci@303: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@317: class EdgeIt { marci@317: friend class GraphWrapper; marci@317: // typedef typename Graph::EdgeIt GraphEdgeIt; marci@317: typename Graph::EdgeIt e; marci@265: public: marci@265: EdgeIt() { } marci@317: EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@317: EdgeIt(const Invalid& i) : e(i) { } marci@317: EdgeIt(const GraphWrapper& _G) : e(*(_G.graph)) { } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@265: }; marci@303: marci@303: NodeIt& first(NodeIt& i) const { marci@317: i=NodeIt(*this); return i; marci@265: } marci@303: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@317: i=OutEdgeIt(*this, p); return i; marci@303: } marci@303: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@317: i=InEdgeIt(*this, p); return i; marci@303: } marci@311: EdgeIt& first(EdgeIt& i) const { marci@317: i=EdgeIt(*this); return i; marci@311: } marci@312: // template I& first(I& i) const { marci@312: // i=I(*this); marci@312: // return i; marci@312: // } marci@303: // template I& first(I& i, const P& p) const { marci@303: // i=I(*this, p); marci@303: // return i; marci@303: // } marci@212: marci@317: NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } marci@317: OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } marci@317: InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } marci@317: EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } marci@312: // template I& next(I &i) const { graph->next(i); return i; } marci@212: template< typename It > It first() const { marci@212: It e; this->first(e); return e; } marci@212: marci@212: template< typename It > It first(const Node& v) const { marci@212: It e; this->first(e, v); return e; } marci@212: marci@317: Node head(const Edge& e) const { marci@317: return Node(graph->head(static_cast(e))); } marci@317: Node tail(const Edge& e) const { marci@317: return Node(graph->tail(static_cast(e))); } marci@212: marci@317: bool valid(const Node& n) const { marci@317: return graph->valid(static_cast(n)); } marci@317: bool valid(const Edge& e) const { marci@317: return graph->valid(static_cast(e)); } marci@317: // template bool valid(const I& i) const { marci@317: // return graph->valid(i); } marci@212: marci@212: //template void setInvalid(const I &i); marci@212: //{ return graph->setInvalid(i); } marci@212: marci@303: int nodeNum() const { return graph->nodeNum(); } marci@303: int edgeNum() const { return graph->edgeNum(); } marci@212: marci@317: Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@317: Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@317: Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@317: Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@317: // template Node aNode(const I& e) const { marci@317: // return Node(graph->aNode(e.e)); } marci@317: // template Node bNode(const I& e) const { marci@317: // return Node(graph->bNode(e.e)); } marci@212: marci@317: Node addNode() const { return Node(graph->addNode()); } marci@212: Edge addEdge(const Node& tail, const Node& head) const { marci@317: return Edge(graph->addEdge(tail, head)); } marci@317: marci@317: void erase(const Node& i) const { graph->erase(i); } marci@317: void erase(const Edge& i) const { graph->erase(i); } marci@317: // template void erase(const I& i) const { graph->erase(i); } marci@212: marci@303: void clear() const { graph->clear(); } marci@212: marci@303: template class NodeMap : public Graph::NodeMap { marci@212: public: marci@303: NodeMap(const GraphWrapper& _G) : marci@303: Graph::NodeMap(*(_G.graph)) { } marci@303: NodeMap(const GraphWrapper& _G, T a) : marci@303: Graph::NodeMap(*(_G.graph), a) { } marci@212: }; marci@212: marci@303: template class EdgeMap : public Graph::EdgeMap { marci@212: public: marci@303: EdgeMap(const GraphWrapper& _G) : marci@303: Graph::EdgeMap(*(_G.graph)) { } marci@303: EdgeMap(const GraphWrapper& _G, T a) : marci@303: Graph::EdgeMap(*(_G.graph), a) { } marci@212: }; marci@212: }; marci@212: marci@303: marci@230: // template marci@230: // class RevGraphWrapper marci@230: // { marci@230: // protected: marci@230: // Graph* graph; marci@230: marci@230: // public: marci@303: // typedef Graph ParentGraph; marci@230: marci@230: // typedef typename Graph::Node Node; marci@230: // typedef typename Graph::NodeIt NodeIt; marci@230: marci@230: // typedef typename Graph::Edge Edge; marci@230: // typedef typename Graph::OutEdgeIt InEdgeIt; marci@230: // typedef typename Graph::InEdgeIt OutEdgeIt; marci@230: // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@230: // typedef typename Graph::EdgeIt EdgeIt; marci@230: marci@230: // //RevGraphWrapper() : graph(0) { } marci@230: // RevGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@230: marci@230: // void setGraph(Graph& _graph) { graph = &_graph; } marci@230: // Graph& getGraph() const { return (*graph); } marci@230: marci@230: // template I& first(I& i) const { return graph->first(i); } marci@230: // template I& first(I& i, const P& p) const { marci@230: // return graph->first(i, p); } marci@230: marci@230: // template I& next(I &i) const { return graph->next(i); } marci@230: marci@230: // template< typename It > It first() const { marci@230: // It e; first(e); return e; } marci@230: marci@230: // template< typename It > It first(const Node& v) const { marci@230: // It e; first(e, v); return e; } marci@230: marci@230: // Node head(const Edge& e) const { return graph->tail(e); } marci@230: // Node tail(const Edge& e) const { return graph->head(e); } marci@230: marci@230: // template bool valid(const I& i) const marci@230: // { return graph->valid(i); } marci@230: marci@230: // //template void setInvalid(const I &i); marci@230: // //{ return graph->setInvalid(i); } marci@230: marci@230: // template Node aNode(const I& e) const { marci@230: // return graph->aNode(e); } marci@230: // template Node bNode(const I& e) const { marci@230: // return graph->bNode(e); } marci@230: marci@230: // Node addNode() const { return graph->addNode(); } marci@230: // Edge addEdge(const Node& tail, const Node& head) const { marci@230: // return graph->addEdge(tail, head); } marci@230: marci@230: // int nodeNum() const { return graph->nodeNum(); } marci@230: // int edgeNum() const { return graph->edgeNum(); } marci@230: marci@230: // template void erase(const I& i) const { graph->erase(i); } marci@230: marci@230: // void clear() const { graph->clear(); } marci@230: marci@230: // template class NodeMap : public Graph::NodeMap { marci@230: // public: marci@230: // NodeMap(const RevGraphWrapper& _G) : marci@230: // Graph::NodeMap(_G.getGraph()) { } marci@230: // NodeMap(const RevGraphWrapper& _G, T a) : marci@230: // Graph::NodeMap(_G.getGraph(), a) { } marci@230: // }; marci@230: marci@230: // template class EdgeMap : public Graph::EdgeMap { marci@230: // public: marci@230: // EdgeMap(const RevGraphWrapper& _G) : marci@230: // Graph::EdgeMap(_G.getGraph()) { } marci@230: // EdgeMap(const RevGraphWrapper& _G, T a) : marci@230: // Graph::EdgeMap(_G.getGraph(), a) { } marci@230: // }; marci@230: // }; marci@230: marci@235: marci@303: template marci@303: class RevGraphWrapper : public GraphWrapper { marci@230: public: marci@303: typedef typename GraphWrapper::Node Node; marci@303: typedef typename GraphWrapper::Edge Edge; marci@279: //FIXME marci@303: //If Graph::OutEdgeIt is not defined marci@279: //and we do not want to use RevGraphWrapper::InEdgeIt, marci@279: //this won't work, because of typedef marci@279: //OR marci@279: //graphs have to define their non-existing iterators to void marci@279: //Unfortunately all the typedefs are instantiated in templates, marci@279: //unlike other stuff marci@303: typedef typename GraphWrapper::OutEdgeIt InEdgeIt; marci@303: typedef typename GraphWrapper::InEdgeIt OutEdgeIt; marci@237: marci@303: // RevGraphWrapper() : GraphWrapper() { } marci@303: RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@238: marci@237: Node head(const Edge& e) const marci@303: { return GraphWrapper::tail(e); } marci@237: Node tail(const Edge& e) const marci@303: { return GraphWrapper::head(e); } marci@76: }; marci@76: marci@263: //Subgraph on the same node-set and partial edge-set marci@311: template marci@303: class SubGraphWrapper : public GraphWrapper { marci@263: protected: marci@311: NodeFilterMap* node_filter_map; marci@311: EdgeFilterMap* edge_filter_map; marci@263: public: marci@311: // SubGraphWrapper() : GraphWrapper(), filter_map(0) { } marci@311: SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, marci@311: EdgeFilterMap& _edge_filter_map) : marci@311: GraphWrapper(_graph), node_filter_map(&_node_filter_map), marci@311: edge_filter_map(&_edge_filter_map) { } marci@263: marci@317: typedef typename GraphWrapper::Node Node; marci@317: class NodeIt { marci@317: friend class GraphWrapper; marci@317: friend class SubGraphWrapper; marci@317: typename Graph::NodeIt n; marci@317: public: marci@311: NodeIt() { } marci@317: NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } marci@317: NodeIt(const Invalid& i) : n(i) { } marci@311: NodeIt(const SubGraphWrapper& _G) : marci@317: n(*(_G.graph)) { marci@317: while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) marci@317: _G.graph->next(n); marci@311: } marci@317: operator Node() const { return Node(typename Graph::Node(n)); } marci@311: }; marci@317: // class NodeIt : public Graph::NodeIt { marci@317: // // typedef typename Graph::NodeIt GraphNodeIt; marci@317: // public: marci@317: // NodeIt() { } marci@317: // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } marci@317: // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } marci@317: // NodeIt(const SubGraphWrapper& _G) : marci@317: // Graph::NodeIt(*(_G.graph)) { marci@317: // while (_G.graph->valid((*this)/*.GraphNodeIt*/) && marci@317: // !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphNodeIt*/); marci@317: // } marci@317: // }; marci@317: typedef typename GraphWrapper::Edge Edge; marci@317: class OutEdgeIt { marci@317: friend class GraphWrapper; marci@317: friend class SubGraphWrapper; marci@311: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: typename Graph::OutEdgeIt e; marci@311: public: marci@311: OutEdgeIt() { } marci@317: OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@317: OutEdgeIt(const Invalid& i) : e(i) { } marci@317: OutEdgeIt(const SubGraphWrapper& _G, marci@317: const Node& _n) : marci@317: e(*(_G.graph), typename Graph::Node(_n)) { marci@317: while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) marci@317: _G.graph->next(e); marci@311: } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@311: }; marci@317: class InEdgeIt { marci@317: friend class GraphWrapper; marci@317: friend class SubGraphWrapper; marci@311: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: typename Graph::InEdgeIt e; marci@311: public: marci@311: InEdgeIt() { } marci@317: InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@317: InEdgeIt(const Invalid& i) : e(i) { } marci@311: InEdgeIt(const SubGraphWrapper& _G, marci@317: const Node& _n) : marci@317: e(*(_G.graph), typename Graph::Node(_n)) { marci@317: while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) marci@317: _G.graph->next(e); marci@311: } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@311: }; marci@317: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@317: class EdgeIt { marci@317: friend class GraphWrapper; marci@317: friend class SubGraphWrapper; marci@311: // typedef typename Graph::EdgeIt GraphEdgeIt; marci@317: typename Graph::EdgeIt e; marci@311: public: marci@311: EdgeIt() { } marci@317: EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@317: EdgeIt(const Invalid& i) : e(i) { } marci@311: EdgeIt(const SubGraphWrapper& _G) : marci@317: e(*(_G.graph)) { marci@317: while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) marci@317: _G.graph->next(e); marci@311: } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@311: }; marci@317: // operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@317: // }; marci@317: // class OutEdgeIt : public Graph::OutEdgeIt { marci@317: // // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: // public: marci@317: // OutEdgeIt() { } marci@317: // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } marci@317: // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } marci@317: // OutEdgeIt(const SubGraphWrapper& marci@317: // _G, const Node& n) : marci@317: // Graph::OutEdgeIt(*(_G.graph), n) { marci@317: // while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && marci@317: // !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphOutEdgeIt*/); marci@317: // } marci@317: // }; marci@317: // class InEdgeIt : public Graph::InEdgeIt { marci@317: // // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: // public: marci@317: // InEdgeIt() { } marci@317: // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } marci@317: // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } marci@317: // InEdgeIt(const SubGraphWrapper& _G, marci@317: // const Node& n) : marci@317: // Graph::InEdgeIt(*(_G.graph), n) { marci@317: // while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && marci@317: // !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphInEdgeIt*/); marci@317: // } marci@317: // }; marci@317: // // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@317: // class EdgeIt : public Graph::EdgeIt { marci@317: // // typedef typename Graph::EdgeIt GraphEdgeIt; marci@317: // public: marci@317: // EdgeIt() { } marci@317: // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } marci@317: // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } marci@317: // EdgeIt(const SubGraphWrapper& _G) : marci@317: // Graph::EdgeIt(*(_G.graph)) { marci@317: // while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && marci@317: // !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphEdgeIt*/); marci@317: // } marci@317: // }; marci@311: marci@317: marci@317: NodeIt& first(NodeIt& i) const { marci@317: i=NodeIt(*this); return i; marci@263: } marci@317: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@317: i=OutEdgeIt(*this, p); return i; marci@311: } marci@317: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@317: i=InEdgeIt(*this, p); return i; marci@311: } marci@317: EdgeIt& first(EdgeIt& i) const { marci@317: i=EdgeIt(*this); return i; marci@263: } marci@263: marci@311: // template I& first(I& i) const { marci@311: // graph->first(i); marci@311: // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@311: // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@311: // return i; marci@311: // } marci@311: // template I& first(I& i, const P& p) const { marci@311: // graph->first(i, p); marci@311: // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@311: // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@311: // return i; marci@311: // } marci@311: marci@311: NodeIt& next(NodeIt& i) const { marci@317: graph->next(i.n); marci@317: while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); } marci@311: return i; marci@311: } marci@311: OutEdgeIt& next(OutEdgeIt& i) const { marci@317: graph->next(i.e); marci@317: while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } marci@311: return i; marci@311: } marci@311: InEdgeIt& next(InEdgeIt& i) const { marci@317: graph->next(i.e); marci@317: while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } marci@311: return i; marci@311: } marci@311: EdgeIt& next(EdgeIt& i) const { marci@317: graph->next(i.e); marci@317: while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } marci@311: return i; marci@311: } marci@311: marci@311: // template I& next(I &i) const { marci@311: // graph->next(i); marci@311: // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } marci@311: // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@311: // return i; marci@323: // } marci@323: marci@323: Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@323: Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@323: Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@323: Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@323: marci@323: void hide(const Node& n) const { node_filter_map->set(n, false); } marci@323: void hide(const Edge& e) const { edge_filter_map->set(e, false); } marci@323: marci@323: void unHide(const Node& n) const { node_filter_map->set(n, true); } marci@323: void unHide(const Edge& e) const { edge_filter_map->set(e, true); } marci@323: marci@323: bool hidden(const Node& n) const { return (*node_filter_map)[n]; } marci@323: bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } marci@323: marci@263: template< typename It > It first() const { marci@263: It e; this->first(e); return e; } marci@263: marci@263: template< typename It > It first(const Node& v) const { marci@263: It e; this->first(e, v); return e; } marci@263: }; marci@155: marci@317: // //Subgraph on the same node-set and partial edge-set marci@317: // template marci@317: // class SubGraphWrapper : public GraphWrapper { marci@317: // protected: marci@317: // NodeFilterMap* node_filter_map; marci@317: // EdgeFilterMap* edge_filter_map; marci@317: // public: marci@317: // // SubGraphWrapper() : GraphWrapper(), filter_map(0) { } marci@317: // SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, marci@317: // EdgeFilterMap& _edge_filter_map) : marci@317: // GraphWrapper(_graph), node_filter_map(&_node_filter_map), marci@317: // edge_filter_map(&_edge_filter_map) { } marci@317: marci@317: marci@317: // typedef typename Graph::Node Node; marci@317: // class NodeIt : public Graph::NodeIt { marci@317: // // typedef typename Graph::NodeIt GraphNodeIt; marci@317: // public: marci@317: // NodeIt() { } marci@317: // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } marci@317: // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } marci@317: // NodeIt(const SubGraphWrapper& _G) : marci@317: // Graph::NodeIt(*(_G.graph)) { marci@317: // while (_G.graph->valid((*this)/*.GraphNodeIt*/) && marci@317: // !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphNodeIt*/); marci@317: // } marci@317: // }; marci@317: // typedef typename Graph::Edge Edge; marci@317: // class OutEdgeIt : public Graph::OutEdgeIt { marci@317: // // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: // public: marci@317: // OutEdgeIt() { } marci@317: // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } marci@317: // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } marci@317: // OutEdgeIt(const SubGraphWrapper& marci@317: // _G, const Node& n) : marci@317: // Graph::OutEdgeIt(*(_G.graph), n) { marci@317: // while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && marci@317: // !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphOutEdgeIt*/); marci@317: // } marci@317: // }; marci@317: // class InEdgeIt : public Graph::InEdgeIt { marci@317: // // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: // public: marci@317: // InEdgeIt() { } marci@317: // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } marci@317: // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } marci@317: // InEdgeIt(const SubGraphWrapper& _G, marci@317: // const Node& n) : marci@317: // Graph::InEdgeIt(*(_G.graph), n) { marci@317: // while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && marci@317: // !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphInEdgeIt*/); marci@317: // } marci@317: // }; marci@317: // // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@317: // class EdgeIt : public Graph::EdgeIt { marci@317: // // typedef typename Graph::EdgeIt GraphEdgeIt; marci@317: // public: marci@317: // EdgeIt() { } marci@317: // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } marci@317: // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } marci@317: // EdgeIt(const SubGraphWrapper& _G) : marci@317: // Graph::EdgeIt(*(_G.graph)) { marci@317: // while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && marci@317: // !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) marci@317: // _G.graph->next((*this)/*.GraphEdgeIt*/); marci@317: // } marci@317: // }; marci@317: marci@317: // NodeIt& first(NodeIt& i) const { marci@317: // i=NodeIt(*this); marci@317: // return i; marci@317: // } marci@317: // OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { marci@317: // i=OutEdgeIt(*this, n); marci@317: // return i; marci@317: // } marci@317: // InEdgeIt& first(InEdgeIt& i, const Node& n) const { marci@317: // i=InEdgeIt(*this, n); marci@317: // return i; marci@317: // } marci@317: // EdgeIt& first(EdgeIt& i) const { marci@317: // i=EdgeIt(*this); marci@317: // return i; marci@317: // } marci@317: marci@317: // // template I& first(I& i) const { marci@317: // // graph->first(i); marci@317: // // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@317: // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@317: // // return i; marci@317: // // } marci@317: // // template I& first(I& i, const P& p) const { marci@317: // // graph->first(i, p); marci@317: // // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@317: // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@317: // // return i; marci@317: // // } marci@317: marci@317: // NodeIt& next(NodeIt& i) const { marci@317: // graph->next(i); marci@317: // while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } marci@317: // return i; marci@317: // } marci@317: // OutEdgeIt& next(OutEdgeIt& i) const { marci@317: // graph->next(i); marci@317: // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@317: // return i; marci@317: // } marci@317: // InEdgeIt& next(InEdgeIt& i) const { marci@317: // graph->next(i); marci@317: // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@317: // return i; marci@317: // } marci@317: // EdgeIt& next(EdgeIt& i) const { marci@317: // graph->next(i); marci@317: // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@317: // return i; marci@317: // } marci@317: marci@317: // // template I& next(I &i) const { marci@317: // // graph->next(i); marci@317: // // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } marci@317: // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } marci@317: // // return i; marci@317: // // } marci@317: marci@317: // template< typename It > It first() const { marci@317: // It e; this->first(e); return e; } marci@317: marci@317: // template< typename It > It first(const Node& v) const { marci@317: // It e; this->first(e, v); return e; } marci@317: // }; marci@317: marci@303: template marci@303: class UndirGraphWrapper : public GraphWrapper { marci@317: // protected: marci@317: // typedef typename Graph::Edge GraphEdge; marci@317: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@303: public: marci@303: typedef typename GraphWrapper::Node Node; marci@303: typedef typename GraphWrapper::NodeIt NodeIt; marci@317: typedef typename GraphWrapper::Edge Edge; marci@317: typedef typename GraphWrapper::EdgeIt EdgeIt; marci@236: marci@303: // UndirGraphWrapper() : GraphWrapper() { } marci@303: UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@158: marci@317: marci@317: // class Edge { marci@317: // friend class UndirGraphWrapper; marci@317: // protected: marci@317: // bool out_or_in; //true iff out marci@317: // GraphOutEdgeIt out; marci@317: // GraphInEdgeIt in; marci@317: // public: marci@317: // Edge() : out_or_in(), out(), in() { } marci@317: // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } marci@317: // operator GraphEdge() const { marci@317: // if (out_or_in) return(out); else return(in); marci@317: // } marci@317: // //FIXME marci@317: // //2 edges are equal if they "refer" to the same physical edge marci@317: // //is it good? marci@317: // friend bool operator==(const Edge& u, const Edge& v) { marci@317: // if (v.out_or_in) marci@317: // if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); marci@317: // //return (u.out_or_in && u.out==v.out); marci@317: // else marci@317: // if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); marci@317: // //return (!u.out_or_in && u.in==v.in); marci@317: // } marci@317: // friend bool operator!=(const Edge& u, const Edge& v) { marci@317: // if (v.out_or_in) marci@317: // if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); marci@317: // //return (!u.out_or_in || u.out!=v.out); marci@317: // else marci@317: // if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); marci@317: // //return (u.out_or_in || u.in!=v.in); marci@317: // } marci@317: // }; marci@317: marci@317: class OutEdgeIt { marci@303: friend class UndirGraphWrapper; marci@158: bool out_or_in; //true iff out marci@317: typename Graph::OutEdgeIt out; marci@317: typename Graph::InEdgeIt in; marci@158: public: marci@317: OutEdgeIt() { } marci@317: OutEdgeIt(const Invalid& i) : Edge(i) { } marci@317: OutEdgeIt(const UndirGraphWrapper& _G, const Node& _n) { marci@317: out_or_in=true; _G.graph->first(out, _n); marci@317: if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } marci@174: } marci@317: operator Edge() const { marci@317: if (out_or_in) return Edge(out); else return Edge(in); marci@158: } marci@158: }; marci@317: // class OutEdgeIt : public Edge { marci@317: // friend class UndirGraphWrapper; marci@317: // public: marci@317: // OutEdgeIt() : Edge() { } marci@317: // OutEdgeIt(const Invalid& i) : Edge(i) { } marci@317: // OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) marci@317: // : Edge() { marci@317: // out_or_in=true; _G.graph->first(out, n); marci@317: // if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } marci@317: // } marci@317: // }; marci@158: marci@317: //FIXME InEdgeIt marci@238: typedef OutEdgeIt InEdgeIt; marci@238: marci@317: // class EdgeIt : public Edge { marci@317: // friend class UndirGraphWrapper; marci@317: // protected: marci@317: // NodeIt v; marci@317: // public: marci@317: // EdgeIt() : Edge() { } marci@317: // EdgeIt(const Invalid& i) : Edge(i) { } marci@317: // EdgeIt(const UndirGraphWrapper& _G) marci@317: // : Edge() { marci@317: // out_or_in=true; marci@317: // //Node v; marci@317: // _G.first(v); marci@317: // if (_G.valid(v)) _G.graph->first(out); else out=INVALID; marci@317: // while (_G.valid(v) && !_G.graph->valid(out)) { marci@317: // _G.graph->next(v); marci@317: // if (_G.valid(v)) _G.graph->first(out); marci@317: // } marci@317: // } marci@317: // }; marci@238: marci@317: NodeIt& first(NodeIt& i) const { marci@317: i=NodeIt(*this); return i; marci@158: } marci@317: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@317: i=OutEdgeIt(*this, p); return i; marci@317: } marci@317: //FIXME marci@317: // InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@317: // i=InEdgeIt(*this, p); return i; marci@317: // } marci@317: EdgeIt& first(EdgeIt& i) const { marci@317: i=EdgeIt(*this); return i; marci@238: } marci@238: marci@303: template I& first(I& i) const { graph->first(i); return i; } marci@238: template I& first(I& i, const P& p) const { marci@303: graph->first(i, p); return i; } marci@238: marci@317: NodeIt& next(NodeIt& n) const { marci@317: GraphWrapper::next(n); marci@317: return n; marci@317: } marci@158: OutEdgeIt& next(OutEdgeIt& e) const { marci@158: if (e.out_or_in) { marci@317: typename Graph::Node n=graph->tail(e.out); marci@303: graph->next(e.out); marci@303: if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } marci@158: } else { marci@303: graph->next(e.in); marci@158: } marci@158: return e; marci@158: } marci@317: //FIXME InEdgeIt marci@238: EdgeIt& next(EdgeIt& e) const { marci@317: GraphWrapper::next(n); marci@317: // graph->next(e.e); marci@238: return e; marci@238: } marci@158: marci@317: // template I& next(I &i) const { graph->next(i); return i; } marci@158: template< typename It > It first() const { marci@303: It e; this->first(e); return e; } marci@158: marci@174: template< typename It > It first(const Node& v) const { marci@303: It e; this->first(e, v); return e; } marci@158: marci@238: // Node head(const Edge& e) const { return gw.head(e); } marci@238: // Node tail(const Edge& e) const { return gw.tail(e); } marci@158: marci@238: // template bool valid(const I& i) const marci@238: // { return gw.valid(i); } marci@158: marci@238: // int nodeNum() const { return gw.nodeNum(); } marci@238: // int edgeNum() const { return gw.edgeNum(); } marci@158: marci@174: // template Node aNode(const I& e) const { marci@158: // return graph->aNode(e); } marci@174: // template Node bNode(const I& e) const { marci@158: // return graph->bNode(e); } marci@238: marci@238: Node aNode(const OutEdgeIt& e) const { marci@303: if (e.out_or_in) return graph->tail(e); else return graph->head(e); } marci@238: Node bNode(const OutEdgeIt& e) const { marci@303: if (e.out_or_in) return graph->head(e); else return graph->tail(e); } marci@158: marci@238: // Node addNode() const { return gw.addNode(); } marci@238: marci@231: // FIXME: ez igy nem jo, mert nem marci@231: // Edge addEdge(const Node& tail, const Node& head) const { marci@231: // return graph->addEdge(tail, head); } marci@158: marci@238: // template void erase(const I& i) const { gw.erase(i); } marci@158: marci@238: // void clear() const { gw.clear(); } marci@158: marci@303: // template class NodeMap : public Graph::NodeMap { marci@238: // public: marci@303: // NodeMap(const UndirGraphWrapper& _G) : marci@303: // Graph::NodeMap(_G.gw) { } marci@303: // NodeMap(const UndirGraphWrapper& _G, T a) : marci@303: // Graph::NodeMap(_G.gw, a) { } marci@238: // }; marci@168: marci@238: // template class EdgeMap : marci@303: // public GraphWrapperSkeleton::EdgeMap { marci@238: // public: marci@303: // EdgeMap(const UndirGraphWrapper& _G) : marci@303: // GraphWrapperSkeleton::EdgeMap(_G.gw) { } marci@303: // EdgeMap(const UndirGraphWrapper& _G, T a) : marci@303: // Graph::EdgeMap(_G.gw, a) { } marci@238: // }; marci@238: }; marci@158: marci@158: marci@158: marci@236: marci@236: marci@155: // template marci@155: // class SymGraphWrapper marci@155: // { marci@155: // Graph* graph; marci@76: marci@155: // public: marci@303: // typedef Graph ParentGraph; marci@155: marci@174: // typedef typename Graph::Node Node; marci@174: // typedef typename Graph::Edge Edge; marci@174: marci@155: // typedef typename Graph::NodeIt NodeIt; marci@155: marci@155: // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon marci@155: // //iranyitatlant, ami van marci@155: // //mert csak 1 dolgot lehet be typedef-elni marci@155: // typedef typename Graph::OutEdgeIt SymEdgeIt; marci@155: // //typedef typename Graph::InEdgeIt SymEdgeIt; marci@155: // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@174: // typedef typename Graph::EdgeIt EdgeIt; marci@155: marci@155: // int nodeNum() const { return graph->nodeNum(); } marci@155: // int edgeNum() const { return graph->edgeNum(); } marci@155: marci@212: // template I& first(I& i) const { return graph->first(i); } marci@212: // template I& first(I& i, const P& p) const { marci@212: // return graph->first(i, p); } marci@155: // //template I next(const I i); { return graph->goNext(i); } marci@155: // //template I &goNext(I &i); { return graph->goNext(i); } marci@155: marci@155: // template< typename It > It first() const { marci@212: // It e; first(e); return e; } marci@155: marci@174: // template< typename It > It first(Node v) const { marci@212: // It e; first(e, v); return e; } marci@155: marci@174: // Node head(const Edge& e) const { return graph->head(e); } marci@174: // Node tail(const Edge& e) const { return graph->tail(e); } marci@155: marci@174: // template Node aNode(const I& e) const { marci@155: // return graph->aNode(e); } marci@174: // template Node bNode(const I& e) const { marci@155: // return graph->bNode(e); } marci@155: marci@155: // //template bool valid(const I i); marci@155: // //{ return graph->valid(i); } marci@155: marci@155: // //template void setInvalid(const I &i); marci@155: // //{ return graph->setInvalid(i); } marci@155: marci@174: // Node addNode() { return graph->addNode(); } marci@174: // Edge addEdge(const Node& tail, const Node& head) { marci@155: // return graph->addEdge(tail, head); } marci@155: marci@155: // template void erase(const I& i) { graph->erase(i); } marci@155: marci@155: // void clear() { graph->clear(); } marci@155: marci@155: // template class NodeMap : public Graph::NodeMap { }; marci@155: // template class EdgeMap : public Graph::EdgeMap { }; marci@155: marci@155: // void setGraph(Graph& _graph) { graph = &_graph; } marci@155: // Graph& getGraph() { return (*graph); } marci@155: marci@155: // //SymGraphWrapper() : graph(0) { } marci@155: // SymGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@155: // }; marci@155: marci@155: marci@317: marci@317: marci@303: template marci@311: class ResGraphWrapper : public GraphWrapper { marci@199: protected: marci@317: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: // typedef typename Graph::Edge GraphEdge; marci@155: FlowMap* flow; marci@155: const CapacityMap* capacity; marci@155: public: marci@168: marci@303: ResGraphWrapper(Graph& _graph, FlowMap& _flow, marci@266: const CapacityMap& _capacity) : marci@303: GraphWrapper(_graph), flow(&_flow), capacity(&_capacity) { } marci@168: marci@174: class Edge; marci@155: class OutEdgeIt; marci@174: friend class Edge; marci@155: friend class OutEdgeIt; marci@76: marci@311: typedef typename GraphWrapper::Node Node; marci@311: typedef typename GraphWrapper::NodeIt NodeIt; marci@317: class Edge : public Graph::Edge { marci@303: friend class ResGraphWrapper; marci@155: protected: marci@317: bool forward; //true, iff forward marci@317: // typename Graph::Edge e; marci@155: public: marci@317: Edge() { } marci@317: Edge(const typename Graph::Edge& _e, bool _forward) : marci@317: Graph::Edge(_e), forward(_forward) { } marci@317: Edge(const Invalid& i) : Graph::Edge(i), forward(false) { } marci@317: //the unique invalid iterator marci@174: friend bool operator==(const Edge& u, const Edge& v) { marci@317: return (v.forward==u.forward && marci@317: static_cast(u)== marci@317: static_cast(v)); marci@174: } marci@174: friend bool operator!=(const Edge& u, const Edge& v) { marci@317: return (v.forward!=u.forward || marci@317: static_cast(u)!= marci@317: static_cast(v)); marci@174: } marci@155: }; marci@317: // class Edge { marci@317: // friend class ResGraphWrapper; marci@317: // protected: marci@317: // bool out_or_in; //true, iff out marci@317: // GraphOutEdgeIt out; marci@317: // GraphInEdgeIt in; marci@317: // public: marci@317: // Edge() : out_or_in(true) { } marci@317: // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } marci@317: // // bool valid() const { marci@317: // // return out_or_in && out.valid() || in.valid(); } marci@317: // friend bool operator==(const Edge& u, const Edge& v) { marci@317: // if (v.out_or_in) marci@317: // return (u.out_or_in && u.out==v.out); marci@317: // else marci@317: // return (!u.out_or_in && u.in==v.in); marci@317: // } marci@317: // friend bool operator!=(const Edge& u, const Edge& v) { marci@317: // if (v.out_or_in) marci@317: // return (!u.out_or_in || u.out!=v.out); marci@317: // else marci@317: // return (u.out_or_in || u.in!=v.in); marci@317: // } marci@317: // operator GraphEdge() const { marci@317: // if (out_or_in) return(out); else return(in); marci@317: // } marci@317: // }; marci@317: class OutEdgeIt { marci@303: friend class ResGraphWrapper; marci@317: protected: marci@317: typename Graph::OutEdgeIt out; marci@317: typename Graph::InEdgeIt in; marci@317: bool forward; marci@155: public: marci@155: OutEdgeIt() { } marci@168: //FIXME marci@317: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@317: OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } marci@317: //the unique invalid iterator marci@317: OutEdgeIt(const ResGraphWrapper& resG, Node v) { marci@317: forward=true; marci@303: resG.graph->first(out, v); marci@317: while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } marci@303: if (!resG.graph->valid(out)) { marci@317: forward=false; marci@303: resG.graph->first(in, v); marci@317: while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } marci@155: } marci@155: } marci@317: operator Edge() const { marci@317: // Edge e; marci@317: // e.forward=this->forward; marci@317: // if (this->forward) e=out; else e=in; marci@317: // return e; marci@317: if (this->forward) marci@317: return Edge(out, this->forward); marci@317: else marci@317: return Edge(in, this->forward); marci@317: } marci@317: }; marci@317: // class OutEdgeIt : public Edge { marci@317: // friend class ResGraphWrapper; marci@317: // public: marci@317: // OutEdgeIt() { } marci@317: // //FIXME marci@317: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@317: // OutEdgeIt(const Invalid& i) : Edge(i) { } marci@317: // OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { marci@317: // resG.graph->first(out, v); marci@317: // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@317: // if (!resG.graph->valid(out)) { marci@317: // out_or_in=0; marci@317: // resG.graph->first(in, v); marci@317: // while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@317: // } marci@317: // } marci@168: // public: marci@168: // OutEdgeIt& operator++() { marci@168: // if (out_or_in) { marci@174: // Node v=/*resG->*/G->aNode(out); marci@168: // ++out; marci@269: // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@168: // if (!out.valid()) { marci@168: // out_or_in=0; marci@212: // G->first(in, v); marci@269: // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@168: // } marci@168: // } else { marci@168: // ++in; marci@269: // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@168: // } marci@168: // return *this; marci@168: // } marci@317: // }; marci@155: marci@263: //FIXME This is just for having InEdgeIt marci@311: // class InEdgeIt : public Edge { }; marci@263: marci@317: class InEdgeIt { marci@303: friend class ResGraphWrapper; marci@317: protected: marci@317: typename Graph::OutEdgeIt out; marci@317: typename Graph::InEdgeIt in; marci@317: bool forward; marci@317: public: marci@317: InEdgeIt() { } marci@317: //FIXME marci@317: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@317: InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } marci@317: //the unique invalid iterator marci@317: InEdgeIt(const ResGraphWrapper& resG, Node v) { marci@317: forward=true; marci@317: resG.graph->first(in, v); marci@317: while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } marci@317: if (!resG.graph->valid(in)) { marci@317: forward=false; marci@317: resG.graph->first(out, v); marci@317: while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } marci@317: } marci@317: } marci@317: operator Edge() const { marci@317: // Edge e; marci@317: // e.forward=this->forward; marci@317: // if (this->forward) e=out; else e=in; marci@317: // return e; marci@317: if (this->forward) marci@317: return Edge(in, this->forward); marci@317: else marci@317: return Edge(out, this->forward); marci@317: } marci@317: }; marci@317: marci@317: class EdgeIt { marci@317: friend class ResGraphWrapper; marci@317: protected: marci@317: typename Graph::EdgeIt e; marci@317: bool forward; marci@155: public: marci@174: EdgeIt() { } marci@317: EdgeIt(const Invalid& i) : e(i), forward(false) { } marci@317: EdgeIt(const ResGraphWrapper& resG) { marci@317: forward=true; marci@317: resG.graph->first(e); marci@317: while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); marci@317: if (!resG.graph->valid(e)) { marci@317: forward=false; marci@317: resG.graph->first(e); marci@317: while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); marci@155: } marci@155: } marci@317: operator Edge() const { marci@317: return Edge(e, this->forward); marci@317: } marci@317: }; marci@317: // class EdgeIt : public Edge { marci@317: // friend class ResGraphWrapper; marci@317: // NodeIt v; marci@317: // public: marci@317: // EdgeIt() { } marci@317: // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } marci@317: // EdgeIt(const Invalid& i) : Edge(i) { } marci@317: // EdgeIt(const ResGraphWrapper& resG) : Edge() { marci@317: // resG.graph->first(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; marci@317: // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@317: // while (resG.graph->valid(v) && !resG.graph->valid(out)) { marci@317: // resG.graph->next(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(out, v); marci@317: // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@317: // } marci@317: // if (!resG.graph->valid(out)) { marci@317: // out_or_in=0; marci@317: // resG.graph->first(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; marci@317: // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@317: // while (resG.graph->valid(v) && !resG.graph->valid(in)) { marci@317: // resG.graph->next(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(in, v); marci@317: // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@317: // } marci@317: // } marci@317: // } marci@174: // EdgeIt& operator++() { marci@168: // if (out_or_in) { marci@168: // ++out; marci@269: // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@168: // while (v.valid() && !out.valid()) { marci@168: // ++v; marci@212: // if (v.valid()) G->first(out, v); marci@269: // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@168: // } marci@168: // if (!out.valid()) { marci@168: // out_or_in=0; marci@212: // G->first(v); marci@303: // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); marci@269: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@168: // while (v.valid() && !in.valid()) { marci@168: // ++v; marci@212: // if (v.valid()) G->first(in, v); marci@269: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@168: // } marci@168: // } marci@168: // } else { marci@168: // ++in; marci@269: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@168: // while (v.valid() && !in.valid()) { marci@168: // ++v; marci@212: // if (v.valid()) G->first(in, v); marci@269: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@168: // } marci@168: // } marci@168: // return *this; marci@168: // } marci@317: // }; marci@155: marci@311: NodeIt& first(NodeIt& i) const { marci@317: i=NodeIt(*this); return i; marci@155: } marci@311: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@317: i=OutEdgeIt(*this, p); return i; marci@311: } marci@317: // FIXME not tested marci@317: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@317: i=InEdgeIt(*this, p); return i; marci@317: } marci@317: EdgeIt& first(EdgeIt& i) const { marci@317: i=EdgeIt(*this); return i; marci@155: } marci@155: marci@317: NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } marci@155: OutEdgeIt& next(OutEdgeIt& e) const { marci@317: if (e.forward) { marci@303: Node v=graph->aNode(e.out); marci@303: graph->next(e.out); marci@317: while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } marci@303: if (!graph->valid(e.out)) { marci@317: e.forward=false; marci@303: graph->first(e.in, v); marci@317: while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } marci@155: } marci@155: } else { marci@303: graph->next(e.in); marci@317: while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } marci@155: } marci@155: return e; marci@155: } marci@317: // FIXME Not tested marci@317: InEdgeIt& next(InEdgeIt& e) const { marci@317: if (e.forward) { marci@317: Node v=graph->aNode(e.in); marci@317: graph->next(e.in); marci@317: while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } marci@317: if (!graph->valid(e.in)) { marci@317: e.forward=false; marci@317: graph->first(e.out, v); marci@317: while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } marci@317: } marci@317: } else { marci@303: graph->next(e.out); marci@317: while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } marci@317: } marci@317: return e; marci@317: } marci@317: EdgeIt& next(EdgeIt& e) const { marci@317: if (e.forward) { marci@317: graph->next(e.e); marci@317: while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } marci@317: if (!graph->valid(e.e)) { marci@317: e.forward=false; marci@317: graph->first(e.e); marci@317: while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } marci@155: } marci@317: } else { marci@317: graph->next(e.e); marci@317: while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } marci@155: } marci@317: return e; marci@317: } marci@317: // EdgeIt& next(EdgeIt& e) const { marci@317: // if (e.out_or_in) { marci@317: // graph->next(e.out); marci@317: // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@317: // while (graph->valid(e.v) && !graph->valid(e.out)) { marci@317: // graph->next(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.out, e.v); marci@317: // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@317: // } marci@317: // if (!graph->valid(e.out)) { marci@317: // e.out_or_in=0; marci@317: // graph->first(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // while (graph->valid(e.v) && !graph->valid(e.in)) { marci@317: // graph->next(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.in, e.v); marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // } marci@317: // } marci@317: // } else { marci@317: // graph->next(e.in); marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // while (graph->valid(e.v) && !graph->valid(e.in)) { marci@317: // graph->next(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.in, e.v); marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // } marci@317: // } marci@317: // return e; marci@317: // } marci@76: marci@76: marci@155: template< typename It > marci@155: It first() const { marci@155: It e; marci@212: first(e); marci@155: return e; marci@155: } marci@76: marci@155: template< typename It > marci@174: It first(Node v) const { marci@155: It e; marci@212: first(e, v); marci@155: return e; marci@155: } marci@76: marci@174: Node tail(Edge e) const { marci@317: return ((e.forward) ? graph->tail(e) : graph->head(e)); } marci@174: Node head(Edge e) const { marci@317: return ((e.forward) ? graph->head(e) : graph->tail(e)); } marci@76: marci@174: Node aNode(OutEdgeIt e) const { marci@317: return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); } marci@174: Node bNode(OutEdgeIt e) const { marci@317: return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); } marci@76: marci@303: int nodeNum() const { return graph->nodeNum(); } marci@263: //FIXME marci@303: //int edgeNum() const { return graph->edgeNum(); } marci@263: marci@263: marci@317: // int id(Node v) const { return graph->id(v); } marci@155: marci@317: bool valid(Node n) const { return GraphWrapper::valid(n); } marci@174: bool valid(Edge e) const { marci@317: return graph->valid(e); marci@317: //return e.forward ? graph->valid(e.out) : graph->valid(e.in); marci@317: } marci@155: marci@174: void augment(const Edge& e, Number a) const { marci@317: if (e.forward) marci@303: // flow->set(e.out, flow->get(e.out)+a); marci@317: flow->set(e, (*flow)[e]+a); marci@168: else marci@303: // flow->set(e.in, flow->get(e.in)-a); marci@317: flow->set(e, (*flow)[e]-a); marci@168: } marci@168: marci@269: Number resCap(const Edge& e) const { marci@317: if (e.forward) marci@303: // return (capacity->get(e.out)-flow->get(e.out)); marci@317: return ((*capacity)[e]-(*flow)[e]); marci@168: else marci@303: // return (flow->get(e.in)); marci@317: return ((*flow)[e]); marci@168: } marci@168: marci@317: // Number resCap(typename Graph::OutEdgeIt out) const { marci@317: // // return (capacity->get(out)-flow->get(out)); marci@317: // return ((*capacity)[out]-(*flow)[out]); marci@317: // } marci@168: marci@317: // Number resCap(typename Graph::InEdgeIt in) const { marci@317: // // return (flow->get(in)); marci@317: // return ((*flow)[in]); marci@317: // } marci@168: marci@303: // template class NodeMap : public Graph::NodeMap { marci@266: // public: marci@303: // NodeMap(const ResGraphWrapper& _G) marci@303: // : Graph::NodeMap(_G.gw) { } marci@303: // NodeMap(const ResGraphWrapper& _G, marci@303: // T a) : Graph::NodeMap(_G.gw, a) { } marci@266: // }; marci@155: marci@155: // template marci@155: // class NodeMap { marci@155: // typename Graph::NodeMap node_map; marci@155: // public: marci@174: // NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.graph)) { } marci@174: // NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.graph), a) { } marci@174: // void set(Node nit, T a) { node_map.set(nit, a); } marci@174: // T get(Node nit) const { return node_map.get(nit); } marci@155: // }; marci@155: marci@155: template marci@155: class EdgeMap { marci@303: typename Graph::EdgeMap forward_map, backward_map; marci@155: public: marci@303: EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } marci@303: EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } marci@174: void set(Edge e, T a) { marci@317: if (e.forward) marci@155: forward_map.set(e.out, a); marci@155: else marci@155: backward_map.set(e.in, a); marci@155: } marci@303: T operator[](Edge e) const { marci@317: if (e.forward) marci@303: return forward_map[e.out]; marci@155: else marci@303: return backward_map[e.in]; marci@155: } marci@303: // T get(Edge e) const { marci@303: // if (e.out_or_in) marci@303: // return forward_map.get(e.out); marci@303: // else marci@303: // return backward_map.get(e.in); marci@303: // } marci@155: }; marci@168: }; marci@168: marci@317: marci@317: marci@317: // template marci@317: // class ResGraphWrapper : public GraphWrapper { marci@317: // protected: marci@317: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: // typedef typename Graph::Edge GraphEdge; marci@317: // FlowMap* flow; marci@317: // const CapacityMap* capacity; marci@317: // public: marci@317: marci@317: // ResGraphWrapper(Graph& _graph, FlowMap& _flow, marci@317: // const CapacityMap& _capacity) : marci@317: // GraphWrapper(_graph), flow(&_flow), capacity(&_capacity) { } marci@317: marci@317: // class Edge; marci@317: // class OutEdgeIt; marci@317: // friend class Edge; marci@317: // friend class OutEdgeIt; marci@317: marci@317: // typedef typename GraphWrapper::Node Node; marci@317: // typedef typename GraphWrapper::NodeIt NodeIt; marci@317: // class Edge { marci@317: // friend class ResGraphWrapper; marci@317: // protected: marci@317: // bool out_or_in; //true, iff out marci@317: // GraphOutEdgeIt out; marci@317: // GraphInEdgeIt in; marci@317: // public: marci@317: // Edge() : out_or_in(true) { } marci@317: // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } marci@317: // // bool valid() const { marci@317: // // return out_or_in && out.valid() || in.valid(); } marci@317: // friend bool operator==(const Edge& u, const Edge& v) { marci@317: // if (v.out_or_in) marci@317: // return (u.out_or_in && u.out==v.out); marci@317: // else marci@317: // return (!u.out_or_in && u.in==v.in); marci@317: // } marci@317: // friend bool operator!=(const Edge& u, const Edge& v) { marci@317: // if (v.out_or_in) marci@317: // return (!u.out_or_in || u.out!=v.out); marci@317: // else marci@317: // return (u.out_or_in || u.in!=v.in); marci@317: // } marci@317: // operator GraphEdge() const { marci@317: // if (out_or_in) return(out); else return(in); marci@317: // } marci@317: // }; marci@317: // class OutEdgeIt : public Edge { marci@317: // friend class ResGraphWrapper; marci@317: // public: marci@317: // OutEdgeIt() { } marci@317: // //FIXME marci@317: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@317: // OutEdgeIt(const Invalid& i) : Edge(i) { } marci@317: // OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { marci@317: // resG.graph->first(out, v); marci@317: // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@317: // if (!resG.graph->valid(out)) { marci@317: // out_or_in=0; marci@317: // resG.graph->first(in, v); marci@317: // while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@317: // } marci@317: // } marci@317: // // public: marci@317: // // OutEdgeIt& operator++() { marci@317: // // if (out_or_in) { marci@317: // // Node v=/*resG->*/G->aNode(out); marci@317: // // ++out; marci@317: // // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@317: // // if (!out.valid()) { marci@317: // // out_or_in=0; marci@317: // // G->first(in, v); marci@317: // // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@317: // // } marci@317: // // } else { marci@317: // // ++in; marci@317: // // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@317: // // } marci@317: // // return *this; marci@317: // // } marci@317: // }; marci@317: marci@317: // //FIXME This is just for having InEdgeIt marci@317: // // class InEdgeIt : public Edge { }; marci@317: marci@317: // class EdgeIt : public Edge { marci@317: // friend class ResGraphWrapper; marci@317: // NodeIt v; marci@317: // public: marci@317: // EdgeIt() { } marci@317: // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } marci@317: // EdgeIt(const Invalid& i) : Edge(i) { } marci@317: // EdgeIt(const ResGraphWrapper& resG) : Edge() { marci@317: // resG.graph->first(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; marci@317: // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@317: // while (resG.graph->valid(v) && !resG.graph->valid(out)) { marci@317: // resG.graph->next(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(out, v); marci@317: // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@317: // } marci@317: // if (!resG.graph->valid(out)) { marci@317: // out_or_in=0; marci@317: // resG.graph->first(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; marci@317: // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@317: // while (resG.graph->valid(v) && !resG.graph->valid(in)) { marci@317: // resG.graph->next(v); marci@317: // if (resG.graph->valid(v)) resG.graph->first(in, v); marci@317: // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@317: // } marci@317: // } marci@317: // } marci@317: // // EdgeIt& operator++() { marci@317: // // if (out_or_in) { marci@317: // // ++out; marci@317: // // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@317: // // while (v.valid() && !out.valid()) { marci@317: // // ++v; marci@317: // // if (v.valid()) G->first(out, v); marci@317: // // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@317: // // } marci@317: // // if (!out.valid()) { marci@317: // // out_or_in=0; marci@317: // // G->first(v); marci@317: // // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); marci@317: // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@317: // // while (v.valid() && !in.valid()) { marci@317: // // ++v; marci@317: // // if (v.valid()) G->first(in, v); marci@317: // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@317: // // } marci@317: // // } marci@317: // // } else { marci@317: // // ++in; marci@317: // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@317: // // while (v.valid() && !in.valid()) { marci@317: // // ++v; marci@317: // // if (v.valid()) G->first(in, v); marci@317: // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@317: // // } marci@317: // // } marci@317: // // return *this; marci@317: // // } marci@317: // }; marci@317: marci@317: // NodeIt& first(NodeIt& i) const { marci@317: // i=NodeIt(*this); marci@317: // return i; marci@317: // } marci@317: // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@317: // i=OutEdgeIt(*this, p); marci@317: // return i; marci@317: // } marci@317: // //FIXME Not yet implemented marci@317: // //InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@317: // //i=InEdgeIt(*this, p); marci@317: // // return i; marci@317: // //} marci@317: // EdgeIt& first(EdgeIt& e) const { marci@317: // e=EdgeIt(*this); marci@317: // return e; marci@317: // } marci@317: marci@317: // NodeIt& next(NodeIt& n) const { graph->next(n); return n; } marci@317: // OutEdgeIt& next(OutEdgeIt& e) const { marci@317: // if (e.out_or_in) { marci@317: // Node v=graph->aNode(e.out); marci@317: // graph->next(e.out); marci@317: // while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@317: // if (!graph->valid(e.out)) { marci@317: // e.out_or_in=0; marci@317: // graph->first(e.in, v); marci@317: // while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // } marci@317: // } else { marci@317: // graph->next(e.in); marci@317: // while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // } marci@317: // return e; marci@317: // } marci@317: // //FIXME Not yet implemented marci@317: // //InEdgeIt& next(InEdgeIt& e) const { marci@317: // // return e; marci@317: // //} marci@317: // EdgeIt& next(EdgeIt& e) const { marci@317: // if (e.out_or_in) { marci@317: // graph->next(e.out); marci@317: // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@317: // while (graph->valid(e.v) && !graph->valid(e.out)) { marci@317: // graph->next(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.out, e.v); marci@317: // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@317: // } marci@317: // if (!graph->valid(e.out)) { marci@317: // e.out_or_in=0; marci@317: // graph->first(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // while (graph->valid(e.v) && !graph->valid(e.in)) { marci@317: // graph->next(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.in, e.v); marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // } marci@317: // } marci@317: // } else { marci@317: // graph->next(e.in); marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // while (graph->valid(e.v) && !graph->valid(e.in)) { marci@317: // graph->next(e.v); marci@317: // if (graph->valid(e.v)) graph->first(e.in, e.v); marci@317: // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@317: // } marci@317: // } marci@317: // return e; marci@317: // } marci@317: marci@317: marci@317: // template< typename It > marci@317: // It first() const { marci@317: // It e; marci@317: // first(e); marci@317: // return e; marci@317: // } marci@317: marci@317: // template< typename It > marci@317: // It first(Node v) const { marci@317: // It e; marci@317: // first(e, v); marci@317: // return e; marci@317: // } marci@317: marci@317: // Node tail(Edge e) const { marci@317: // return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } marci@317: // Node head(Edge e) const { marci@317: // return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } marci@317: marci@317: // Node aNode(OutEdgeIt e) const { marci@317: // return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } marci@317: // Node bNode(OutEdgeIt e) const { marci@317: // return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } marci@317: marci@317: // int nodeNum() const { return graph->nodeNum(); } marci@317: // //FIXME marci@317: // //int edgeNum() const { return graph->edgeNum(); } marci@317: marci@317: marci@317: // int id(Node v) const { return graph->id(v); } marci@317: marci@317: // bool valid(Node n) const { return graph->valid(n); } marci@317: // bool valid(Edge e) const { marci@317: // return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } marci@317: marci@317: // void augment(const Edge& e, Number a) const { marci@317: // if (e.out_or_in) marci@317: // // flow->set(e.out, flow->get(e.out)+a); marci@317: // flow->set(e.out, (*flow)[e.out]+a); marci@317: // else marci@317: // // flow->set(e.in, flow->get(e.in)-a); marci@317: // flow->set(e.in, (*flow)[e.in]-a); marci@317: // } marci@317: marci@317: // Number resCap(const Edge& e) const { marci@317: // if (e.out_or_in) marci@317: // // return (capacity->get(e.out)-flow->get(e.out)); marci@317: // return ((*capacity)[e.out]-(*flow)[e.out]); marci@317: // else marci@317: // // return (flow->get(e.in)); marci@317: // return ((*flow)[e.in]); marci@317: // } marci@317: marci@317: // Number resCap(GraphOutEdgeIt out) const { marci@317: // // return (capacity->get(out)-flow->get(out)); marci@317: // return ((*capacity)[out]-(*flow)[out]); marci@317: // } marci@317: marci@317: // Number resCap(GraphInEdgeIt in) const { marci@317: // // return (flow->get(in)); marci@317: // return ((*flow)[in]); marci@317: // } marci@317: marci@317: // // template class NodeMap : public Graph::NodeMap { marci@317: // // public: marci@317: // // NodeMap(const ResGraphWrapper& _G) marci@317: // // : Graph::NodeMap(_G.gw) { } marci@317: // // NodeMap(const ResGraphWrapper& _G, marci@317: // // T a) : Graph::NodeMap(_G.gw, a) { } marci@317: // // }; marci@317: marci@317: // // template marci@317: // // class NodeMap { marci@317: // // typename Graph::NodeMap node_map; marci@317: // // public: marci@317: // // NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.graph)) { } marci@317: // // NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.graph), a) { } marci@317: // // void set(Node nit, T a) { node_map.set(nit, a); } marci@317: // // T get(Node nit) const { return node_map.get(nit); } marci@317: // // }; marci@317: marci@317: // template marci@317: // class EdgeMap { marci@317: // typename Graph::EdgeMap forward_map, backward_map; marci@317: // public: marci@317: // EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } marci@317: // EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } marci@317: // void set(Edge e, T a) { marci@317: // if (e.out_or_in) marci@317: // forward_map.set(e.out, a); marci@317: // else marci@317: // backward_map.set(e.in, a); marci@317: // } marci@317: // T operator[](Edge e) const { marci@317: // if (e.out_or_in) marci@317: // return forward_map[e.out]; marci@317: // else marci@317: // return backward_map[e.in]; marci@317: // } marci@317: // // T get(Edge e) const { marci@317: // // if (e.out_or_in) marci@317: // // return forward_map.get(e.out); marci@317: // // else marci@317: // // return backward_map.get(e.in); marci@317: // // } marci@317: // }; marci@317: // }; marci@317: marci@317: marci@303: //ErasingFirstGraphWrapper for blocking flows marci@303: template marci@303: class ErasingFirstGraphWrapper : public GraphWrapper { marci@269: protected: marci@269: FirstOutEdgesMap* first_out_edges; marci@269: public: marci@303: ErasingFirstGraphWrapper(Graph& _graph, marci@303: FirstOutEdgesMap& _first_out_edges) : marci@303: GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } marci@269: marci@317: typedef typename GraphWrapper::Node Node; marci@317: class NodeIt { marci@317: friend class GraphWrapper; marci@317: friend class ErasingFirstGraphWrapper; marci@317: typename Graph::NodeIt n; marci@317: public: marci@311: NodeIt() { } marci@317: NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } marci@317: NodeIt(const Invalid& i) : n(i) { } marci@311: NodeIt(const ErasingFirstGraphWrapper& _G) : marci@317: n(*(_G.graph)) { } marci@317: operator Node() const { return Node(typename Graph::Node(n)); } marci@311: }; marci@317: typedef typename GraphWrapper::Edge Edge; marci@317: class OutEdgeIt { marci@317: friend class GraphWrapper; marci@317: friend class ErasingFirstGraphWrapper; marci@317: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@317: typename Graph::OutEdgeIt e; marci@311: public: marci@311: OutEdgeIt() { } marci@317: OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@317: OutEdgeIt(const Invalid& i) : e(i) { } marci@311: OutEdgeIt(const ErasingFirstGraphWrapper& _G, marci@317: const Node& _n) : marci@317: e((*_G.first_out_edges)[_n]) { } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@311: }; marci@317: class InEdgeIt { marci@317: friend class GraphWrapper; marci@317: friend class ErasingFirstGraphWrapper; marci@317: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@317: typename Graph::InEdgeIt e; marci@311: public: marci@311: InEdgeIt() { } marci@317: InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@317: InEdgeIt(const Invalid& i) : e(i) { } marci@311: InEdgeIt(const ErasingFirstGraphWrapper& _G, marci@317: const Node& _n) : marci@317: e(*(_G.graph), typename Graph::Node(_n)) { } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@311: }; marci@311: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@317: class EdgeIt { marci@317: friend class GraphWrapper; marci@317: friend class ErasingFirstGraphWrapper; marci@317: // typedef typename Graph::EdgeIt GraphEdgeIt; marci@317: typename Graph::EdgeIt e; marci@311: public: marci@311: EdgeIt() { } marci@317: EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@317: EdgeIt(const Invalid& i) : e(i) { } marci@311: EdgeIt(const ErasingFirstGraphWrapper& _G) : marci@317: e(*(_G.graph)) { } marci@317: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@311: }; marci@311: marci@317: NodeIt& first(NodeIt& i) const { marci@317: i=NodeIt(*this); return i; marci@269: } marci@317: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@317: i=OutEdgeIt(*this, p); return i; marci@269: } marci@317: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@317: i=InEdgeIt(*this, p); return i; marci@311: } marci@317: EdgeIt& first(EdgeIt& i) const { marci@317: i=EdgeIt(*this); return i; marci@311: } marci@311: marci@311: // template I& first(I& i) const { marci@311: // graph->first(i); marci@311: // return i; marci@311: // } marci@311: // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { marci@311: // // e=first_out_edges->get(n); marci@311: // e=(*first_out_edges)[n]; marci@311: // return e; marci@311: // } marci@311: // template I& first(I& i, const P& p) const { marci@311: // graph->first(i, p); marci@311: // return i; marci@311: // } marci@269: marci@317: NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } marci@317: OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } marci@317: InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } marci@317: EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } marci@317: marci@317: Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@317: Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@317: Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@317: Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@311: marci@311: // template I& next(I &i) const { marci@311: // graph->next(i); marci@311: // return i; marci@311: // } marci@269: marci@269: template< typename It > It first() const { marci@269: It e; this->first(e); return e; } marci@269: marci@269: template< typename It > It first(const Node& v) const { marci@269: It e; this->first(e, v); return e; } marci@269: marci@269: void erase(const OutEdgeIt& e) const { marci@269: OutEdgeIt f=e; marci@269: this->next(f); marci@317: first_out_edges->set(this->tail(e), f.e); marci@269: } marci@269: }; marci@269: marci@317: // //ErasingFirstGraphWrapper for blocking flows marci@317: // template marci@317: // class ErasingFirstGraphWrapper : public GraphWrapper { marci@317: // protected: marci@317: // FirstOutEdgesMap* first_out_edges; marci@317: // public: marci@317: // ErasingFirstGraphWrapper(Graph& _graph, marci@317: // FirstOutEdgesMap& _first_out_edges) : marci@317: // GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } marci@317: marci@317: // typedef typename Graph::Node Node; marci@317: // class NodeIt : public Graph::NodeIt { marci@317: // public: marci@317: // NodeIt() { } marci@317: // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } marci@317: // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } marci@317: // NodeIt(const ErasingFirstGraphWrapper& _G) : marci@317: // Graph::NodeIt(*(_G.graph)) { } marci@317: // }; marci@317: // typedef typename Graph::Edge Edge; marci@317: // class OutEdgeIt : public Graph::OutEdgeIt { marci@317: // public: marci@317: // OutEdgeIt() { } marci@317: // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } marci@317: // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } marci@317: // OutEdgeIt(const ErasingFirstGraphWrapper& _G, marci@317: // const Node& n) : marci@317: // Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } marci@317: // }; marci@317: // class InEdgeIt : public Graph::InEdgeIt { marci@317: // public: marci@317: // InEdgeIt() { } marci@317: // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } marci@317: // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } marci@317: // InEdgeIt(const ErasingFirstGraphWrapper& _G, marci@317: // const Node& n) : marci@317: // Graph::InEdgeIt(*(_G.graph), n) { } marci@317: // }; marci@317: // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@317: // class EdgeIt : public Graph::EdgeIt { marci@317: // public: marci@317: // EdgeIt() { } marci@317: // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } marci@317: // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } marci@317: // EdgeIt(const ErasingFirstGraphWrapper& _G) : marci@317: // Graph::EdgeIt(*(_G.graph)) { } marci@317: // }; marci@317: marci@317: // NodeIt& first(NodeIt& i) const { marci@317: // i=NodeIt(*this); marci@317: // return i; marci@317: // } marci@317: // OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { marci@317: // i=OutEdgeIt(*this, n); marci@317: // // i=(*first_out_edges)[n]; marci@317: // return i; marci@317: // } marci@317: // InEdgeIt& first(InEdgeIt& i, const Node& n) const { marci@317: // i=InEdgeIt(*this, n); marci@317: // return i; marci@317: // } marci@317: // EdgeIt& first(EdgeIt& i) const { marci@317: // i=EdgeIt(*this); marci@317: // return i; marci@317: // } marci@317: marci@317: // // template I& first(I& i) const { marci@317: // // graph->first(i); marci@317: // // return i; marci@317: // // } marci@317: // // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { marci@317: // // // e=first_out_edges->get(n); marci@317: // // e=(*first_out_edges)[n]; marci@317: // // return e; marci@317: // // } marci@317: // // template I& first(I& i, const P& p) const { marci@317: // // graph->first(i, p); marci@317: // // return i; marci@317: // // } marci@317: marci@317: // NodeIt& next(NodeIt& i) const { marci@317: // graph->next(i); marci@317: // return i; marci@317: // } marci@317: // OutEdgeIt& next(OutEdgeIt& i) const { marci@317: // graph->next(i); marci@317: // return i; marci@317: // } marci@317: // InEdgeIt& next(InEdgeIt& i) const { marci@317: // graph->next(i); marci@317: // return i; marci@317: // } marci@317: // EdgeIt& next(EdgeIt& i) const { marci@317: // graph->next(i); marci@317: // return i; marci@317: // } marci@317: marci@317: // // template I& next(I &i) const { marci@317: // // graph->next(i); marci@317: // // return i; marci@317: // // } marci@317: marci@317: // template< typename It > It first() const { marci@317: // It e; this->first(e); return e; } marci@317: marci@317: // template< typename It > It first(const Node& v) const { marci@317: // It e; this->first(e, v); return e; } marci@317: marci@317: // void erase(const OutEdgeIt& e) const { marci@317: // OutEdgeIt f=e; marci@317: // this->next(f); marci@317: // first_out_edges->set(this->tail(e), f); marci@317: // } marci@317: // }; marci@317: marci@317: marci@148: // // FIXME: comparison should be made better!!! marci@148: // template marci@148: // class ResGraphWrapper marci@148: // { marci@148: // Graph* graph; marci@76: marci@148: // public: marci@303: // typedef Graph ParentGraph; marci@76: marci@174: // typedef typename Graph::Node Node; marci@174: // typedef typename Graph::Edge Edge; marci@174: marci@148: // typedef typename Graph::NodeIt NodeIt; marci@76: marci@148: // class OutEdgeIt { marci@148: // public: marci@174: // //Graph::Node n; marci@148: // bool out_or_in; marci@148: // typename Graph::OutEdgeIt o; marci@148: // typename Graph::InEdgeIt i; marci@148: // }; marci@148: // class InEdgeIt { marci@148: // public: marci@174: // //Graph::Node n; marci@148: // bool out_or_in; marci@148: // typename Graph::OutEdgeIt o; marci@148: // typename Graph::InEdgeIt i; marci@148: // }; marci@148: // typedef typename Graph::SymEdgeIt SymEdgeIt; marci@174: // typedef typename Graph::EdgeIt EdgeIt; marci@76: marci@259: // int nodeNum() const { return gw.nodeNum(); } marci@259: // int edgeNum() const { return gw.edgeNum(); } marci@76: marci@259: // Node& first(Node& n) const { return gw.first(n); } marci@76: marci@174: // // Edge and SymEdge is missing!!!! marci@174: // // Edge <-> In/OutEdgeIt conversion is missing!!!! marci@76: marci@148: // //FIXME marci@212: // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const marci@148: // { marci@148: // e.n=n; marci@259: // gw.first(e.o,n); marci@259: // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) marci@259: // gw.goNext(e.o); marci@259: // if(!gw.valid(e.o)) { marci@259: // gw.first(e.i,n); marci@259: // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) marci@259: // gw.goNext(e.i); marci@148: // } marci@148: // return e; marci@148: // } marci@148: // /* marci@148: // OutEdgeIt &goNext(OutEdgeIt &e) marci@148: // { marci@259: // if(gw.valid(e.o)) { marci@259: // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) marci@259: // gw.goNext(e.o); marci@259: // if(gw.valid(e.o)) return e; marci@259: // else gw.first(e.i,e.n); marci@148: // } marci@148: // else { marci@259: // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) marci@259: // gw.goNext(e.i); marci@148: // return e; marci@148: // } marci@148: // } marci@148: // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} marci@148: // */ marci@259: // //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);} marci@76: marci@148: // //FIXME marci@212: // InEdgeIt& first(InEdgeIt& e, const Node& n) const marci@148: // { marci@148: // e.n=n; marci@259: // gw.first(e.i,n); marci@259: // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) marci@259: // gw.goNext(e.i); marci@259: // if(!gw.valid(e.i)) { marci@259: // gw.first(e.o,n); marci@259: // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) marci@259: // gw.goNext(e.o); marci@148: // } marci@148: // return e; marci@148: // } marci@148: // /* marci@148: // InEdgeIt &goNext(InEdgeIt &e) marci@148: // { marci@259: // if(gw.valid(e.i)) { marci@259: // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) marci@259: // gw.goNext(e.i); marci@259: // if(gw.valid(e.i)) return e; marci@259: // else gw.first(e.o,e.n); marci@148: // } marci@148: // else { marci@259: // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) marci@259: // gw.goNext(e.o); marci@148: // return e; marci@148: // } marci@148: // } marci@148: // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} marci@148: // */ marci@259: // //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);} marci@76: marci@259: // //template I &goNext(I &i); { return gw.goNext(i); } marci@259: // //template I next(const I i); { return gw.goNext(i); } marci@76: marci@148: // template< typename It > It first() const { marci@212: // It e; first(e); return e; } marci@76: marci@174: // template< typename It > It first(Node v) const { marci@212: // It e; first(e, v); return e; } marci@76: marci@259: // Node head(const Edge& e) const { return gw.head(e); } marci@259: // Node tail(const Edge& e) const { return gw.tail(e); } marci@76: marci@174: // template Node aNode(const I& e) const { marci@259: // return gw.aNode(e); } marci@174: // template Node bNode(const I& e) const { marci@259: // return gw.bNode(e); } marci@76: marci@148: // //template bool valid(const I i); marci@259: // //{ return gw.valid(i); } marci@76: marci@148: // //template void setInvalid(const I &i); marci@259: // //{ return gw.setInvalid(i); } marci@76: marci@259: // Node addNode() { return gw.addNode(); } marci@174: // Edge addEdge(const Node& tail, const Node& head) { marci@259: // return gw.addEdge(tail, head); } marci@76: marci@259: // template void erase(const I& i) { gw.erase(i); } marci@76: marci@259: // void clear() { gw.clear(); } marci@76: marci@148: // template class NodeMap : public Graph::NodeMap { }; marci@148: // template class EdgeMap : public Graph::EdgeMap { }; marci@76: marci@148: // void setGraph(Graph& _graph) { graph = &_graph; } marci@148: // Graph& getGraph() { return (*graph); } marci@76: marci@148: // //ResGraphWrapper() : graph(0) { } marci@148: // ResGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@148: // }; marci@76: alpar@105: } //namespace hugo marci@76: marci@259: #endif //HUGO_GRAPH_WRAPPER_H marci@76: