deba@1979: /* -*- C++ -*- deba@1979: * deba@1979: * This file is a part of LEMON, a generic C++ optimization library deba@1979: * deba@1979: * Copyright (C) 2003-2006 deba@1979: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1979: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1979: * deba@1979: * Permission to use, modify and distribute this software is granted deba@1979: * provided that this copyright notice appears in all copies. For deba@1979: * precise terms see the accompanying LICENSE file. deba@1979: * deba@1979: * This software is provided "AS IS" with no warranty of any kind, deba@1979: * express or implied, and with no claim as to its suitability for any deba@1979: * purpose. deba@1979: * deba@1979: */ deba@1979: deba@1979: #ifndef LEMON_UGRAPH_ADAPTOR_H deba@1979: #define LEMON_UGRAPH_ADAPTOR_H deba@1979: deba@1979: ///\ingroup graph_adaptors deba@1979: ///\file deba@1979: ///\brief Several graph adaptors. deba@1979: /// deba@1979: ///This file contains several useful ugraph adaptor functions. deba@1979: /// deba@1979: ///\author Balazs Dezso deba@1979: deba@1993: #include deba@1979: #include deba@1979: deba@1979: #include deba@1979: deba@1993: #include deba@1979: deba@1979: #include deba@1979: deba@1979: namespace lemon { deba@1979: deba@1979: /// \brief Base type for the Graph Adaptors deba@1979: /// deba@1979: /// This is the base type for most of LEMON graph adaptors. deba@1979: /// This class implements a trivial graph adaptor i.e. it only wraps the deba@1979: /// functions and types of the graph. The purpose of this class is to deba@1979: /// make easier implementing graph adaptors. E.g. if an adaptor is deba@1979: /// considered which differs from the wrapped graph only in some of its deba@1979: /// functions or types, then it can be derived from GraphAdaptor, and only deba@1979: /// the differences should be implemented. deba@1979: /// deba@1979: /// \author Balazs Dezso deba@1979: template deba@1979: class UGraphAdaptorBase { deba@1979: public: deba@1979: typedef _UGraph Graph; deba@1979: typedef Graph ParentGraph; deba@1979: deba@1979: protected: deba@1979: Graph* graph; deba@1979: deba@1979: UGraphAdaptorBase() : graph(0) {} deba@1979: deba@1979: void setGraph(Graph& _graph) { graph=&_graph; } deba@1979: deba@1979: public: deba@1979: UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {} deba@1979: deba@1979: typedef typename Graph::Node Node; deba@1979: typedef typename Graph::Edge Edge; deba@1979: typedef typename Graph::UEdge UEdge; deba@1979: deba@1979: void first(Node& i) const { graph->first(i); } deba@1979: void first(Edge& i) const { graph->first(i); } deba@1979: void first(UEdge& i) const { graph->first(i); } deba@1979: void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); } deba@1979: void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); } deba@1979: void firstInc(UEdge &i, bool &d, const Node &n) const { deba@1979: graph->firstInc(i, d, n); deba@1979: } deba@1979: deba@1979: void next(Node& i) const { graph->next(i); } deba@1979: void next(Edge& i) const { graph->next(i); } deba@1979: void next(UEdge& i) const { graph->next(i); } deba@1979: void nextIn(Edge& i) const { graph->nextIn(i); } deba@1979: void nextOut(Edge& i) const { graph->nextOut(i); } deba@1979: void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); } deba@1979: deba@1979: Node source(const UEdge& e) const { return graph->source(e); } deba@1979: Node target(const UEdge& e) const { return graph->target(e); } deba@1979: deba@1979: Node source(const Edge& e) const { return graph->source(e); } deba@1979: Node target(const Edge& e) const { return graph->target(e); } deba@1979: deba@1979: typedef NodeNumTagIndicator NodeNumTag; deba@1979: int nodeNum() const { return graph->nodeNum(); } deba@1979: deba@1979: typedef EdgeNumTagIndicator EdgeNumTag; deba@1979: int edgeNum() const { return graph->edgeNum(); } deba@2031: int uEdgeNum() const { return graph->uEdgeNum(); } deba@1979: deba@1979: typedef FindEdgeTagIndicator FindEdgeTag; deba@1979: Edge findEdge(const Node& source, const Node& target, deba@1979: const Edge& prev = INVALID) { deba@1979: return graph->findEdge(source, target, prev); deba@1979: } deba@1979: UEdge findUEdge(const Node& source, const Node& target, deba@1979: const UEdge& prev = INVALID) { deba@1979: return graph->findUEdge(source, target, prev); deba@1979: } deba@1979: deba@1979: Node addNode() const { return graph->addNode(); } deba@1979: UEdge addEdge(const Node& source, const Node& target) const { deba@1979: return graph->addEdge(source, target); deba@1979: } deba@1979: deba@1979: void erase(const Node& i) const { graph->erase(i); } deba@2031: void erase(const UEdge& i) const { graph->erase(i); } deba@1979: deba@1979: void clear() const { graph->clear(); } deba@1979: deba@2031: bool direction(const Edge& e) const { return graph->direction(e); } deba@2031: Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); } deba@2031: deba@1979: int id(const Node& v) const { return graph->id(v); } deba@2031: int id(const Edge& e) const { return graph->id(e); } deba@1979: int id(const UEdge& e) const { return graph->id(e); } deba@1979: deba@2031: Node fromNodeId(int id) const { deba@2031: return graph->fromNodeId(id); deba@2031: } deba@2031: deba@2031: Edge fromEdgeId(int id) const { deba@2031: return graph->fromEdgeId(id); deba@2031: } deba@2031: deba@2031: UEdge fromUEdgeId(int id) const { deba@2031: return graph->fromUEdgeId(id); deba@2031: } deba@1991: deba@1991: int maxNodeId() const { deba@1991: return graph->maxNodeId(); deba@1979: } deba@1979: deba@1991: int maxEdgeId() const { deba@1991: return graph->maxEdgeId(); deba@1979: } deba@1979: deba@1991: int maxUEdgeId() const { deba@1991: return graph->maxEdgeId(); deba@1979: } deba@1979: deba@1991: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@1991: deba@1991: NodeNotifier& getNotifier(Node) const { deba@1991: return graph->getNotifier(Node()); deba@1991: } deba@1991: deba@1991: typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; deba@1991: deba@1991: EdgeNotifier& getNotifier(Edge) const { deba@1991: return graph->getNotifier(Edge()); deba@1991: } deba@1991: deba@1991: typedef typename ItemSetTraits::ItemNotifier UEdgeNotifier; deba@1991: deba@1991: UEdgeNotifier& getNotifier(UEdge) const { deba@1991: return graph->getNotifier(UEdge()); deba@1991: } deba@1979: deba@1979: template deba@1979: class NodeMap : public Graph::template NodeMap<_Value> { deba@1979: public: deba@1979: typedef typename Graph::template NodeMap<_Value> Parent; deba@1979: explicit NodeMap(const UGraphAdaptorBase& ga) deba@1979: : Parent(*ga.graph) {} deba@1979: NodeMap(const UGraphAdaptorBase& ga, const _Value& value) deba@1979: : Parent(*ga.graph, value) {} deba@1979: deba@1979: NodeMap& operator=(const NodeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@1979: } deba@2031: deba@1979: }; deba@1979: deba@1979: template deba@1979: class EdgeMap : public Graph::template EdgeMap<_Value> { deba@1979: public: deba@1979: typedef typename Graph::template EdgeMap<_Value> Parent; deba@1979: explicit EdgeMap(const UGraphAdaptorBase& ga) deba@1979: : Parent(*ga.graph) {} deba@1979: EdgeMap(const UGraphAdaptorBase& ga, const _Value& value) deba@1979: : Parent(*ga.graph, value) {} deba@1979: deba@1979: EdgeMap& operator=(const EdgeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@1979: return *this; deba@1979: } deba@1979: }; deba@1979: deba@1979: template deba@1979: class UEdgeMap : public Graph::template UEdgeMap<_Value> { deba@1979: public: deba@1979: typedef typename Graph::template UEdgeMap<_Value> Parent; deba@1979: explicit UEdgeMap(const UGraphAdaptorBase& ga) deba@1979: : Parent(*ga.graph) {} deba@1979: UEdgeMap(const UGraphAdaptorBase& ga, const _Value& value) deba@1979: : Parent(*ga.graph, value) {} deba@1979: deba@1979: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: UEdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@1979: } deba@1979: }; deba@1979: deba@1979: }; deba@1979: deba@1979: /// \ingroup graph_adaptors deba@2084: /// deba@2084: /// \brief Trivial undirected graph adaptor deba@2084: /// deba@2084: /// This class is an adaptor which does not change the adapted undirected deba@2084: /// graph. It can be used only to test the undirected graph adaptors. deba@1979: template deba@1979: class UGraphAdaptor deba@1979: : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > { deba@1979: public: deba@1979: typedef _UGraph Graph; deba@1979: typedef UGraphAdaptorExtender > Parent; deba@1979: protected: deba@1979: UGraphAdaptor() : Parent() {} deba@1979: deba@1979: public: deba@1979: explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); } deba@1979: }; deba@1979: deba@1979: template deba@1979: class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> { deba@1979: public: deba@1979: typedef _UGraph Graph; deba@2031: typedef SubUGraphAdaptorBase Adaptor; deba@1979: typedef UGraphAdaptorBase<_UGraph> Parent; deba@1979: protected: deba@1979: deba@1979: NodeFilterMap* node_filter_map; deba@1979: UEdgeFilterMap* uedge_filter_map; deba@1979: deba@1979: SubUGraphAdaptorBase() deba@1979: : Parent(), node_filter_map(0), uedge_filter_map(0) { } deba@1979: deba@1979: void setNodeFilterMap(NodeFilterMap& _node_filter_map) { deba@1979: node_filter_map=&_node_filter_map; deba@1979: } deba@1979: void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) { deba@1979: uedge_filter_map=&_uedge_filter_map; deba@1979: } deba@1979: deba@1979: public: deba@1979: deba@1979: typedef typename Parent::Node Node; deba@1979: typedef typename Parent::Edge Edge; deba@1979: typedef typename Parent::UEdge UEdge; deba@1979: deba@1979: void first(Node& i) const { deba@1979: Parent::first(i); deba@1979: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: deba@1979: void first(Edge& i) const { deba@1979: Parent::first(i); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); deba@1979: } deba@1979: deba@1979: void first(UEdge& i) const { deba@1979: Parent::first(i); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); deba@1979: } deba@1979: deba@1979: void firstIn(Edge& i, const Node& n) const { deba@1979: Parent::firstIn(i, n); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); deba@1979: } deba@1979: deba@1979: void firstOut(Edge& i, const Node& n) const { deba@1979: Parent::firstOut(i, n); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); deba@1979: } deba@1979: deba@1979: void firstInc(UEdge& i, bool& d, const Node& n) const { deba@1979: Parent::firstInc(i, d, n); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); deba@1979: } deba@1979: deba@1979: void next(Node& i) const { deba@1979: Parent::next(i); deba@1979: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: deba@1979: void next(Edge& i) const { deba@1979: Parent::next(i); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); deba@1979: } deba@1979: deba@1979: void next(UEdge& i) const { deba@1979: Parent::next(i); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); deba@1979: } deba@1979: deba@1979: void nextIn(Edge& i) const { deba@1979: Parent::nextIn(i); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); deba@1979: } deba@1979: deba@1979: void nextOut(Edge& i) const { deba@1979: Parent::nextOut(i); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); deba@1979: } deba@1979: deba@1979: void nextInc(UEdge& i, bool& d) const { deba@1979: Parent::nextInc(i, d); deba@1979: while (i!=INVALID && (!(*uedge_filter_map)[i] deba@1979: || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d); deba@1979: } deba@1979: deba@2084: /// \brief Hide the given node in the graph. deba@2084: /// deba@1979: /// This function hides \c n in the graph, i.e. the iteration deba@1979: /// jumps over it. This is done by simply setting the value of \c n deba@1979: /// to be false in the corresponding node-map. deba@1979: void hide(const Node& n) const { node_filter_map->set(n, false); } deba@1979: deba@2084: /// \brief Hide the given undirected edge in the graph. deba@2084: /// deba@1979: /// This function hides \c e in the graph, i.e. the iteration deba@1979: /// jumps over it. This is done by simply setting the value of \c e deba@2084: /// to be false in the corresponding uedge-map. deba@1979: void hide(const UEdge& e) const { uedge_filter_map->set(e, false); } deba@1979: deba@2084: /// \brief Unhide the given node in the graph. deba@2084: /// deba@1979: /// The value of \c n is set to be true in the node-map which stores deba@1979: /// hide information. If \c n was hidden previuosly, then it is shown deba@1979: /// again deba@1979: void unHide(const Node& n) const { node_filter_map->set(n, true); } deba@1979: deba@2084: /// \brief Hide the given undirected edge in the graph. deba@2084: /// deba@2084: /// The value of \c e is set to be true in the uedge-map which stores deba@1979: /// hide information. If \c e was hidden previuosly, then it is shown deba@1979: /// again deba@1979: void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); } deba@1979: deba@2084: /// \brief Returns true if \c n is hidden. deba@2084: /// deba@1979: /// Returns true if \c n is hidden. deba@1979: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } deba@1979: deba@2084: /// \brief Returns true if \c e is hidden. deba@1979: /// deba@2084: /// Returns true if \c e is hidden. deba@1979: bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; } deba@1979: deba@1979: typedef False NodeNumTag; deba@1979: typedef False EdgeNumTag; deba@1991: deba@1991: typedef FindEdgeTagIndicator FindEdgeTag; deba@1991: Edge findEdge(const Node& source, const Node& target, deba@1991: const Edge& prev = INVALID) { deba@1991: if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { deba@1991: return INVALID; deba@1991: } deba@1991: Edge edge = Parent::findEdge(source, target, prev); deba@1991: while (edge != INVALID && !(*uedge_filter_map)[edge]) { deba@1991: edge = Parent::findEdge(source, target, edge); deba@1991: } deba@1991: return edge; deba@1991: } deba@1991: UEdge findUEdge(const Node& source, const Node& target, deba@1991: const UEdge& prev = INVALID) { deba@1991: if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) { deba@1991: return INVALID; deba@1991: } deba@1991: UEdge uedge = Parent::findUEdge(source, target, prev); deba@1991: while (uedge != INVALID && !(*uedge_filter_map)[uedge]) { deba@1991: uedge = Parent::findUEdge(source, target, uedge); deba@1991: } deba@1991: return uedge; deba@1991: } deba@2031: deba@2031: template deba@2031: class NodeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: NodeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: NodeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@2031: template deba@2031: class EdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: EdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: EdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@2031: template deba@2031: class UEdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: UEdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: UEdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: UEdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@1979: }; deba@1979: deba@1979: template deba@1979: class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false> deba@1979: : public UGraphAdaptorBase<_UGraph> { deba@1979: public: deba@1979: typedef _UGraph Graph; deba@2031: typedef SubUGraphAdaptorBase Adaptor; deba@1979: typedef UGraphAdaptorBase<_UGraph> Parent; deba@1979: protected: deba@1979: NodeFilterMap* node_filter_map; deba@1979: UEdgeFilterMap* uedge_filter_map; deba@1979: SubUGraphAdaptorBase() : Parent(), deba@1979: node_filter_map(0), uedge_filter_map(0) { } deba@1979: deba@1979: void setNodeFilterMap(NodeFilterMap& _node_filter_map) { deba@1979: node_filter_map=&_node_filter_map; deba@1979: } deba@1979: void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) { deba@1979: uedge_filter_map=&_uedge_filter_map; deba@1979: } deba@1979: deba@1979: public: deba@1979: deba@1979: typedef typename Parent::Node Node; deba@1979: typedef typename Parent::Edge Edge; deba@1979: typedef typename Parent::UEdge UEdge; deba@1979: deba@1979: void first(Node& i) const { deba@1979: Parent::first(i); deba@1979: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: deba@1979: void first(Edge& i) const { deba@1979: Parent::first(i); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: deba@1979: void first(UEdge& i) const { deba@1979: Parent::first(i); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: deba@1979: void firstIn(Edge& i, const Node& n) const { deba@1979: Parent::firstIn(i, n); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); deba@1979: } deba@1979: deba@1979: void firstOut(Edge& i, const Node& n) const { deba@1979: Parent::firstOut(i, n); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); deba@1979: } deba@1979: deba@1979: void firstInc(UEdge& i, bool& d, const Node& n) const { deba@1979: Parent::firstInc(i, d, n); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); deba@1979: } deba@1979: deba@1979: void next(Node& i) const { deba@1979: Parent::next(i); deba@1979: while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: void next(Edge& i) const { deba@1979: Parent::next(i); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: void next(UEdge& i) const { deba@1979: Parent::next(i); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); deba@1979: } deba@1979: void nextIn(Edge& i) const { deba@1979: Parent::nextIn(i); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); deba@1979: } deba@1979: deba@1979: void nextOut(Edge& i) const { deba@1979: Parent::nextOut(i); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); deba@1979: } deba@1979: void nextInc(UEdge& i, bool& d) const { deba@1979: Parent::nextInc(i, d); deba@1979: while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); deba@1979: } deba@1979: deba@2084: /// \brief Hide the given node in the graph. deba@2084: /// deba@1979: /// This function hides \c n in the graph, i.e. the iteration deba@1979: /// jumps over it. This is done by simply setting the value of \c n deba@1979: /// to be false in the corresponding node-map. deba@1979: void hide(const Node& n) const { node_filter_map->set(n, false); } deba@1979: deba@2084: /// \brief Hide the given undirected edge in the graph. deba@2084: /// deba@1979: /// This function hides \c e in the graph, i.e. the iteration deba@1979: /// jumps over it. This is done by simply setting the value of \c e deba@2084: /// to be false in the corresponding uedge-map. deba@1979: void hide(const UEdge& e) const { uedge_filter_map->set(e, false); } deba@1979: deba@2084: /// \brief Unhide the given node in the graph. deba@2084: /// deba@1979: /// The value of \c n is set to be true in the node-map which stores deba@1979: /// hide information. If \c n was hidden previuosly, then it is shown deba@1979: /// again deba@1979: void unHide(const Node& n) const { node_filter_map->set(n, true); } deba@1979: deba@2084: /// \brief Hide the given undirected edge in the graph. deba@2084: /// deba@2084: /// The value of \c e is set to be true in the uedge-map which stores deba@1979: /// hide information. If \c e was hidden previuosly, then it is shown deba@1979: /// again deba@1979: void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); } deba@1979: deba@2084: /// \brief Returns true if \c n is hidden. deba@2084: /// deba@1979: /// Returns true if \c n is hidden. deba@1979: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } deba@1979: deba@2084: /// \brief Returns true if \c e is hidden. deba@1979: /// deba@2084: /// Returns true if \c e is hidden. deba@1979: bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; } deba@1979: deba@1979: typedef False NodeNumTag; deba@1979: typedef False EdgeNumTag; deba@1991: deba@1991: typedef FindEdgeTagIndicator FindEdgeTag; deba@1991: Edge findEdge(const Node& source, const Node& target, deba@1991: const Edge& prev = INVALID) { deba@1991: Edge edge = Parent::findEdge(source, target, prev); deba@1991: while (edge != INVALID && !(*uedge_filter_map)[edge]) { deba@1991: edge = Parent::findEdge(source, target, edge); deba@1991: } deba@1991: return edge; deba@1991: } deba@1991: UEdge findUEdge(const Node& source, const Node& target, deba@1991: const UEdge& prev = INVALID) { deba@1991: UEdge uedge = Parent::findUEdge(source, target, prev); deba@1991: while (uedge != INVALID && !(*uedge_filter_map)[uedge]) { deba@1991: uedge = Parent::findUEdge(source, target, uedge); deba@1991: } deba@1991: return uedge; deba@1991: } deba@2031: deba@2031: template deba@2031: class NodeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: NodeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: NodeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@2031: template deba@2031: class EdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: EdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: EdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@2031: deba@2031: template deba@2031: class UEdgeMap deba@2031: : public SubMapExtender > deba@2031: { deba@2031: public: deba@2031: typedef Adaptor Graph; deba@2031: typedef SubMapExtender > Parent; deba@2031: deba@2031: UEdgeMap(const Graph& graph) deba@2031: : Parent(graph) {} deba@2031: UEdgeMap(const Graph& graph, const _Value& value) deba@2031: : Parent(graph, value) {} deba@2031: deba@2031: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: UEdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: }; deba@1979: }; deba@1979: deba@1979: /// \ingroup graph_adaptors deba@1979: /// deba@1979: /// \brief A graph adaptor for hiding nodes and edges from an undirected deba@1979: /// graph. deba@1979: /// deba@1979: /// SubUGraphAdaptor shows the undirected graph with filtered node-set and deba@1979: /// edge-set. If the \c checked parameter is true then it filters the edgeset deba@1979: /// to do not get invalid edges without source or target. deba@1979: /// deba@1979: /// If the \c checked template parameter is false then we have to note that deba@1979: /// the node-iterator cares only the filter on the node-set, and the deba@1979: /// edge-iterator cares only the filter on the edge-set. deba@1979: /// This way the edge-map deba@1979: /// should filter all edges which's source or target is filtered by the deba@1979: /// node-filter. deba@1979: /// deba@1979: template deba@1979: class SubUGraphAdaptor : deba@1979: public UGraphAdaptorExtender< deba@1979: SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > { deba@1979: public: deba@1979: typedef _UGraph Graph; deba@1979: typedef UGraphAdaptorExtender< deba@1979: SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent; deba@1979: protected: deba@1979: SubUGraphAdaptor() { } deba@1979: public: deba@1979: SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map, deba@1979: UEdgeFilterMap& _uedge_filter_map) { deba@1979: setGraph(_graph); deba@1979: setNodeFilterMap(_node_filter_map); deba@1979: setUEdgeFilterMap(_uedge_filter_map); deba@1979: } deba@1979: }; deba@1979: deba@1980: template deba@1980: SubUGraphAdaptor deba@1980: subUGraphAdaptor(const UGraph& graph, deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1980: return SubUGraphAdaptor deba@1980: (graph, nfm, efm); deba@1980: } deba@1980: deba@1980: template deba@1980: SubUGraphAdaptor deba@1980: subUGraphAdaptor(const UGraph& graph, deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1980: return SubUGraphAdaptor deba@1980: (graph, nfm, efm); deba@1980: } deba@1980: deba@1980: template deba@1980: SubUGraphAdaptor deba@1980: subUGraphAdaptor(const UGraph& graph, deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1980: return SubUGraphAdaptor deba@1980: (graph, nfm, efm); deba@1980: } deba@1980: deba@1980: template deba@1980: SubUGraphAdaptor deba@1980: subUGraphAdaptor(const UGraph& graph, deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) { deba@1980: return SubUGraphAdaptor(graph, nfm, efm); deba@1980: } deba@1980: deba@1979: /// \ingroup graph_adaptors deba@1979: /// deba@1980: /// \brief An adaptor for hiding nodes from an undirected graph. deba@1979: /// deba@1979: /// An adaptor for hiding nodes from an undirected graph. deba@1979: /// This adaptor specializes SubUGraphAdaptor in the way that only deba@1979: /// the node-set deba@1979: /// can be filtered. In usual case the checked parameter is true, we get the deba@1979: /// induced subgraph. But if the checked parameter is false then we can only deba@1979: /// filter only isolated nodes. deba@1979: template deba@1979: class NodeSubUGraphAdaptor : deba@1979: public SubUGraphAdaptor<_UGraph, NodeFilterMap, deba@1979: ConstMap, checked> { deba@1979: public: deba@1979: typedef SubUGraphAdaptor<_UGraph, NodeFilterMap, deba@1979: ConstMap > Parent; deba@1979: typedef _UGraph Graph; deba@1979: protected: deba@1985: ConstMap const_true_map; deba@1991: deba@1991: NodeSubUGraphAdaptor() : const_true_map(true) { deba@1991: Parent::setUEdgeFilterMap(const_true_map); deba@1991: } deba@1991: deba@1979: public: deba@1979: NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : deba@1979: Parent(), const_true_map(true) { deba@1979: Parent::setGraph(_graph); deba@1979: Parent::setNodeFilterMap(_node_filter_map); deba@1979: Parent::setUEdgeFilterMap(const_true_map); deba@1979: } deba@1979: }; deba@1979: deba@1979: template deba@1979: NodeSubUGraphAdaptor deba@1979: nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) { deba@1979: return NodeSubUGraphAdaptor(graph, nfm); deba@1979: } deba@1979: deba@1979: template deba@1979: NodeSubUGraphAdaptor deba@1979: nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) { deba@1979: return NodeSubUGraphAdaptor(graph, nfm); deba@1979: } deba@1979: deba@2042: /// \ingroup graph_adaptors deba@2042: /// deba@1979: /// \brief An adaptor for hiding undirected edges from an undirected graph. deba@1979: /// deba@1979: /// \warning Graph adaptors are in even more experimental state deba@1979: /// than the other parts of the lib. Use them at you own risk. deba@1979: /// deba@1979: /// An adaptor for hiding undirected edges from an undirected graph. deba@1979: /// This adaptor specializes SubUGraphAdaptor in the way that deba@1979: /// only the edge-set deba@1979: /// can be filtered. deba@1979: template deba@1979: class EdgeSubUGraphAdaptor : deba@1979: public SubUGraphAdaptor<_UGraph, ConstMap, deba@1979: UEdgeFilterMap, false> { deba@1979: public: deba@1979: typedef SubUGraphAdaptor<_UGraph, ConstMap, deba@1979: UEdgeFilterMap, false> Parent; deba@1979: typedef _UGraph Graph; deba@1979: protected: deba@1979: ConstMap const_true_map; deba@1991: deba@1991: EdgeSubUGraphAdaptor() : const_true_map(true) { deba@1991: Parent::setNodeFilterMap(const_true_map); deba@1991: } deba@1991: deba@1979: public: deba@2031: deba@1979: EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : deba@1979: Parent(), const_true_map(true) { deba@1979: Parent::setGraph(_graph); deba@1979: Parent::setNodeFilterMap(const_true_map); deba@1979: Parent::setUEdgeFilterMap(_uedge_filter_map); deba@1979: } deba@2031: deba@1979: }; deba@1979: deba@1979: template deba@1979: EdgeSubUGraphAdaptor deba@1979: edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) { deba@1979: return EdgeSubUGraphAdaptor(graph, efm); deba@1979: } deba@1979: deba@1979: template deba@1979: EdgeSubUGraphAdaptor deba@1979: edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) { deba@1979: return EdgeSubUGraphAdaptor(graph, efm); deba@1979: } deba@1979: deba@2087: /// \brief Base of direct undirected graph adaptor deba@2087: /// deba@2087: /// Base class of the direct undirected graph adaptor. All public member deba@2087: /// of this class can be used with the DirUGraphAdaptor too. deba@2087: /// \sa DirUGraphAdaptor deba@1979: template deba@1980: class DirUGraphAdaptorBase { deba@1979: public: deba@1979: deba@1979: typedef _UGraph Graph; deba@1979: typedef _DirectionMap DirectionMap; deba@1979: deba@1979: typedef typename _UGraph::Node Node; deba@1979: typedef typename _UGraph::UEdge Edge; deba@1979: deba@2087: /// \brief Reverse edge deba@2087: /// deba@2087: /// It reverse the given edge. It simply negate the direction in the map. deba@1991: void reverseEdge(const Edge& edge) { deba@1991: direction->set(edge, !(*direction)[edge]); deba@1991: } deba@1991: deba@1979: void first(Node& i) const { graph->first(i); } deba@1979: void first(Edge& i) const { graph->first(i); } deba@1979: void firstIn(Edge& i, const Node& n) const { deba@1979: bool d; deba@1979: graph->firstInc(i, d, n); deba@1979: while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d); deba@1979: } deba@1979: void firstOut(Edge& i, const Node& n ) const { deba@1979: bool d; deba@1979: graph->firstInc(i, d, n); deba@1979: while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d); deba@1979: } deba@1979: deba@1979: void next(Node& i) const { graph->next(i); } deba@1979: void next(Edge& i) const { graph->next(i); } deba@1979: void nextIn(Edge& i) const { deba@1979: bool d = !(*direction)[i]; deba@1979: graph->nextInc(i, d); deba@1979: while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d); deba@1979: } deba@1979: void nextOut(Edge& i) const { deba@1979: bool d = (*direction)[i]; deba@1979: graph->nextInc(i, d); deba@1979: while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d); deba@1979: } deba@1979: deba@1979: Node source(const Edge& e) const { deba@1979: return (*direction)[e] ? graph->source(e) : graph->target(e); deba@1979: } deba@1979: Node target(const Edge& e) const { deba@1979: return (*direction)[e] ? graph->target(e) : graph->source(e); deba@1979: } deba@1979: deba@1979: typedef NodeNumTagIndicator NodeNumTag; deba@1979: int nodeNum() const { return graph->nodeNum(); } deba@1979: deba@1979: typedef EdgeNumTagIndicator EdgeNumTag; deba@1979: int edgeNum() const { return graph->uEdgeNum(); } deba@1979: deba@1979: typedef FindEdgeTagIndicator FindEdgeTag; deba@1979: Edge findEdge(const Node& source, const Node& target, deba@1979: const Edge& prev = INVALID) { deba@1979: Edge edge = prev; deba@1979: bool d = edge == INVALID ? true : (*direction)[edge]; deba@1979: if (d) { deba@1979: edge = graph->findUEdge(source, target, edge); deba@1979: while (edge != INVALID && !(*direction)[edge]) { deba@1979: graph->findUEdge(source, target, edge); deba@1979: } deba@1979: if (edge != INVALID) return edge; deba@1979: } deba@1979: graph->findUEdge(target, source, edge); deba@1979: while (edge != INVALID && (*direction)[edge]) { deba@1979: graph->findUEdge(source, target, edge); deba@1979: } deba@1979: return edge; deba@1979: } deba@1979: deba@1979: Node addNode() const { deba@1979: return Node(graph->addNode()); deba@1979: } deba@1979: deba@1979: Edge addEdge(const Node& source, const Node& target) const { deba@1979: Edge edge = graph->addEdge(source, target); deba@2069: direction->set(edge, graph->source(edge) == source); deba@1979: return edge; deba@1979: } deba@1979: deba@1979: void erase(const Node& i) const { graph->erase(i); } deba@1979: void erase(const Edge& i) const { graph->erase(i); } deba@1979: deba@1979: void clear() const { graph->clear(); } deba@1979: deba@1979: int id(const Node& v) const { return graph->id(v); } deba@1979: int id(const Edge& e) const { return graph->id(e); } deba@1979: deba@1991: int maxNodeId() const { deba@1991: return graph->maxNodeId(); deba@1979: } deba@1979: deba@1991: int maxEdgeId() const { deba@1991: return graph->maxEdgeId(); deba@1991: } deba@1991: deba@1991: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@1991: deba@1991: NodeNotifier& getNotifier(Node) const { deba@1991: return graph->getNotifier(Node()); deba@1991: } deba@1991: deba@1991: typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; deba@1991: deba@1991: EdgeNotifier& getNotifier(Edge) const { deba@1991: return graph->getNotifier(Edge()); deba@1991: } deba@1991: deba@1979: template deba@1979: class NodeMap : public _UGraph::template NodeMap<_Value> { deba@1979: public: deba@2031: deba@1979: typedef typename _UGraph::template NodeMap<_Value> Parent; deba@2031: deba@1980: explicit NodeMap(const DirUGraphAdaptorBase& ga) deba@2031: : Parent(*ga.graph) {} deba@2031: deba@1980: NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value) deba@2031: : Parent(*ga.graph, value) {} deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@2031: deba@1979: }; deba@1979: deba@1979: template deba@1979: class EdgeMap : public _UGraph::template UEdgeMap<_Value> { deba@1979: public: deba@2031: deba@1980: typedef typename _UGraph::template UEdgeMap<_Value> Parent; deba@2031: deba@1980: explicit EdgeMap(const DirUGraphAdaptorBase& ga) deba@1979: : Parent(*ga.graph) { } deba@2031: deba@1980: EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value) deba@1979: : Parent(*ga.graph, value) { } deba@2031: deba@2031: EdgeMap& operator=(const EdgeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template deba@2031: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@2031: return *this; deba@2031: } deba@1979: }; deba@1979: deba@1979: deba@1979: deba@1979: protected: deba@1979: Graph* graph; deba@1979: DirectionMap* direction; deba@1979: deba@1979: void setDirectionMap(DirectionMap& _direction) { deba@1979: direction = &_direction; deba@1979: } deba@1979: deba@1979: void setGraph(Graph& _graph) { deba@1979: graph = &_graph; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1980: /// \ingroup graph_adaptors deba@1991: /// deba@1991: /// \brief A directed graph is made from an undirected graph by an adaptor deba@1980: /// deba@2087: /// This adaptor gives a direction for each uedge in the undirected deba@2087: /// graph. The direction of the edges stored in the deba@2087: /// DirectionMap. This map is a bool map on the undirected edges. If deba@2087: /// the uedge is mapped to true then the direction of the directed deba@2087: /// edge will be the same as the default direction of the uedge. The deba@2087: /// edges can be easily reverted by the \ref deba@2087: /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the deba@2087: /// adaptor. deba@2087: /// deba@2087: /// It can be used to solve orientation problems on directed graphs. deba@2087: /// By example how can we orient an undirected graph to get the minimum deba@2087: /// number of strongly connected components. If we orient the edges with deba@2087: /// the dfs algorithm out from the source then we will get such an deba@2087: /// orientation. deba@2087: /// deba@2087: /// We use the \ref DfsVisitor "visitor" interface of the deba@2087: /// \ref DfsVisit "dfs" algorithm: deba@2087: ///\code deba@2087: /// template deba@2087: /// class OrientVisitor : public DfsVisitor { deba@2087: /// public: deba@2087: /// deba@2087: /// OrientVisitor(const UGraph& ugraph, DirMap& dirMap) deba@2087: /// : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {} deba@2087: /// deba@2087: /// void discover(const Edge& edge) { deba@2087: /// _processed.set(edge, true); deba@2087: /// _dirMap.set(edge, _ugraph.direction(edge)); deba@2087: /// } deba@2087: /// deba@2087: /// void examine(const Edge& edge) { deba@2087: /// if (_processed[edge]) return; deba@2087: /// _processed.set(edge, true); deba@2087: /// _dirMap.set(edge, _ugraph.direction(edge)); deba@2087: /// } deba@2087: /// deba@2087: /// private: deba@2087: /// const UGraph& _ugraph; deba@2087: /// DirMap& _dirMap; deba@2087: /// UGraph::UEdgeMap _processed; deba@2087: /// }; deba@2087: ///\endcode deba@2087: /// deba@2087: /// And now we can use the orientation: deba@2087: ///\code deba@2087: /// UGraph::UEdgeMap dmap(ugraph); deba@2087: /// deba@2087: /// typedef OrientVisitor > Visitor; deba@2087: /// Visitor visitor(ugraph, dmap); deba@2087: /// deba@2087: /// DfsVisit dfs(ugraph, visitor); deba@2087: /// deba@2087: /// dfs.run(); deba@2087: /// deba@2087: /// typedef DirUGraphAdaptor DGraph; deba@2087: /// DGraph dgraph(ugraph, dmap); deba@2087: /// deba@2087: /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == deba@2087: /// countBiEdgeConnectedComponents(ugraph), "Wrong Orientation"); deba@2087: ///\endcode deba@2087: /// deba@2087: /// The number of the bi-connected components is a lower bound for deba@2087: /// the number of the strongly connected components in the directed deba@2087: /// graph because if we contract the bi-connected components to deba@2087: /// nodes we will get a tree therefore we cannot orient edges in deba@2087: /// both direction between bi-connected components. In the other way deba@2087: /// the algorithm will orient one component to be strongly deba@2087: /// connected. The two relations proof that the assertion will deba@2087: /// be always true and the found solution is optimal. deba@2087: /// deba@2087: /// \sa DirUGraphAdaptorBase deba@2087: /// \sa dirUGraphAdaptor deba@1980: template > deba@1980: class DirUGraphAdaptor : deba@1979: public GraphAdaptorExtender< deba@1980: DirUGraphAdaptorBase<_Graph, DirectionMap> > { deba@1979: public: deba@1979: typedef _Graph Graph; deba@1979: typedef GraphAdaptorExtender< deba@1980: DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent; deba@1979: protected: deba@1980: DirUGraphAdaptor() { } deba@1979: public: deba@2087: deba@2087: /// \brief Constructor of the adaptor deba@2087: /// deba@2087: /// Constructor of the adaptor deba@1980: DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { deba@1979: setGraph(_graph); deba@1979: setDirectionMap(_direction_map); deba@1979: } deba@1979: }; deba@1979: deba@2087: /// \brief Just gives back a DirUGraphAdaptor deba@2087: /// deba@2087: /// Just gives back a DirUGraphAdaptor deba@1979: template deba@1980: DirUGraphAdaptor deba@1980: dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) { deba@1980: return DirUGraphAdaptor(graph, dm); deba@1979: } deba@1979: deba@1979: template deba@1980: DirUGraphAdaptor deba@1980: dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) { deba@1980: return DirUGraphAdaptor(graph, dm); deba@1979: } deba@1979: deba@1979: } deba@1979: deba@1979: #endif