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 <lemon/bits/invalid.h>
deba@1979: #include <lemon/maps.h>
deba@1979:
deba@1979: #include <lemon/bits/graph_adaptor_extender.h>
deba@1979:
deba@1993: #include <lemon/bits/traits.h>
deba@1979:
deba@1979: #include <iostream>
deba@1979:
deba@1979: namespace lemon {
deba@1979:
deba@1979: /// \ingroup graph_adaptors
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<typename _UGraph>
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: Graph& getGraph() { return *graph; }
deba@1979: const Graph& getGraph() const { return *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<Graph> NodeNumTag;
deba@1979: int nodeNum() const { return graph->nodeNum(); }
deba@1979:
deba@1979: typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@1979: int edgeNum() const { return graph->edgeNum(); }
deba@1979:
deba@1979: typedef FindEdgeTagIndicator<Graph> 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@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 UEdge& e) const { return graph->id(e); }
deba@1979:
deba@1979: bool direction(const Edge& e) const { return graph->direction(e); }
deba@1979: Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
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<Graph, Node>::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<Graph, Edge>::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<Graph, UEdge>::ItemNotifier UEdgeNotifier;
deba@1991:
deba@1991: UEdgeNotifier& getNotifier(UEdge) const {
deba@1991: return graph->getNotifier(UEdge());
deba@1991: }
deba@1979:
deba@1979: template <typename _Value>
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<Graph>& ga)
deba@1979: : Parent(*ga.graph) {}
deba@1979: NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@1979: : Parent(*ga.graph, value) {}
deba@1979:
deba@1979: NodeMap& operator=(const NodeMap& cmap) {
deba@1979: return operator=<NodeMap>(cmap);
deba@1979: }
deba@1979:
deba@1979: template <typename CMap>
deba@1979: NodeMap& operator=(const CMap& cmap) {
deba@1979: checkConcept<concept::ReadMap<Node, _Value>, CMap>();
deba@1979: const typename Parent::Graph* graph = Parent::getGraph();
deba@1979: Node it;
deba@1979: for (graph->first(it); it != INVALID; graph->next(it)) {
deba@1979: Parent::set(it, cmap[it]);
deba@1979: }
deba@1979: return *this;
deba@1979: }
deba@1979: };
deba@1979:
deba@1979: template <typename _Value>
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<Graph>& ga)
deba@1979: : Parent(*ga.graph) {}
deba@1979: EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@1979: : Parent(*ga.graph, value) {}
deba@1979:
deba@1979: EdgeMap& operator=(const EdgeMap& cmap) {
deba@1979: return operator=<EdgeMap>(cmap);
deba@1979: }
deba@1979:
deba@1979: template <typename CMap>
deba@1979: EdgeMap& operator=(const CMap& cmap) {
deba@1979: checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
deba@1979: const typename Parent::Graph* graph = Parent::getGraph();
deba@1979: Edge it;
deba@1979: for (graph->first(it); it != INVALID; graph->next(it)) {
deba@1979: Parent::set(it, cmap[it]);
deba@1979: }
deba@1979: return *this;
deba@1979: }
deba@1979: };
deba@1979:
deba@1979: template <typename _Value>
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<Graph>& ga)
deba@1979: : Parent(*ga.graph) {}
deba@1979: UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
deba@1979: : Parent(*ga.graph, value) {}
deba@1979:
deba@1979: UEdgeMap& operator=(const UEdgeMap& cmap) {
deba@1979: return operator=<UEdgeMap>(cmap);
deba@1979: }
deba@1979:
deba@1979: template <typename CMap>
deba@1979: UEdgeMap& operator=(const CMap& cmap) {
deba@1979: checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
deba@1979: const typename Parent::Graph* graph = Parent::getGraph();
deba@1979: UEdge it;
deba@1979: for (graph->first(it); it != INVALID; graph->next(it)) {
deba@1979: Parent::set(it, cmap[it]);
deba@1979: }
deba@1979: return *this;
deba@1979: }
deba@1979: };
deba@1979:
deba@1979: };
deba@1979:
deba@1979: /// \ingroup graph_adaptors
deba@1979: template <typename _UGraph>
deba@1979: class UGraphAdaptor
deba@1979: : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
deba@1979: public:
deba@1979: typedef _UGraph Graph;
deba@1979: typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > 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 <typename _UGraph, typename NodeFilterMap,
deba@1979: typename UEdgeFilterMap, bool checked = true>
deba@1979: class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
deba@1979: public:
deba@1979: typedef _UGraph Graph;
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@1979: ///\e
deba@1979:
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@1979: ///\e
deba@1979:
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@1979: /// to be false in the corresponding edge-map.
deba@1979: void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
deba@1979:
deba@1979: ///\e
deba@1979:
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@1979: ///\e
deba@1979:
deba@1979: /// The value of \c e is set to be true in the edge-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@1979: /// Returns true if \c n is hidden.
deba@1979:
deba@1979: ///\e
deba@1979: ///
deba@1979: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1979:
deba@1979: /// Returns true if \c n is hidden.
deba@1979:
deba@1979: ///\e
deba@1979: ///
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<Graph> 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@1979: };
deba@1979:
deba@1979: template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
deba@1979: class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
deba@1979: : public UGraphAdaptorBase<_UGraph> {
deba@1979: public:
deba@1979: typedef _UGraph Graph;
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@1979: ///\e
deba@1979:
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@1979: ///\e
deba@1979:
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@1979: /// to be false in the corresponding edge-map.
deba@1979: void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
deba@1979:
deba@1979: ///\e
deba@1979:
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@1979: ///\e
deba@1979:
deba@1979: /// The value of \c e is set to be true in the edge-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@1979: /// Returns true if \c n is hidden.
deba@1979:
deba@1979: ///\e
deba@1979: ///
deba@1979: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
deba@1979:
deba@1979: /// Returns true if \c n is hidden.
deba@1979:
deba@1979: ///\e
deba@1979: ///
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<Graph> 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@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: /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
deba@1979: /// \c Graph::Node that is why \c g.id(n) can be applied.
deba@1979: ///
deba@1979: template<typename _UGraph, typename NodeFilterMap,
deba@1979: typename UEdgeFilterMap, bool checked = true>
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<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980: SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
deba@1980: subUGraphAdaptor(const UGraph& graph,
deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980: return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
deba@1980: (graph, nfm, efm);
deba@1980: }
deba@1980:
deba@1980: template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980: SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
deba@1980: subUGraphAdaptor(const UGraph& graph,
deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980: return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
deba@1980: (graph, nfm, efm);
deba@1980: }
deba@1980:
deba@1980: template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980: SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
deba@1980: subUGraphAdaptor(const UGraph& graph,
deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980: return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
deba@1980: (graph, nfm, efm);
deba@1980: }
deba@1980:
deba@1980: template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
deba@1980: SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
deba@1980: subUGraphAdaptor(const UGraph& graph,
deba@1980: NodeFilterMap& nfm, EdgeFilterMap& efm) {
deba@1980: return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
deba@1980: const EdgeFilterMap>(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<typename _UGraph, typename NodeFilterMap, bool checked = true>
deba@1979: class NodeSubUGraphAdaptor :
deba@1979: public SubUGraphAdaptor<_UGraph, NodeFilterMap,
deba@1979: ConstMap<typename _UGraph::UEdge, bool>, checked> {
deba@1979: public:
deba@1979: typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
deba@1979: ConstMap<typename _UGraph::UEdge, bool> > Parent;
deba@1979: typedef _UGraph Graph;
deba@1979: protected:
deba@1985: ConstMap<typename _UGraph::UEdge, bool> 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<typename UGraph, typename NodeFilterMap>
deba@1979: NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
deba@1979: nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
deba@1979: return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
deba@1979: }
deba@1979:
deba@1979: template<typename UGraph, typename NodeFilterMap>
deba@1979: NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
deba@1979: nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
deba@1979: return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
deba@1979: }
deba@1979:
deba@1979:
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<typename _UGraph, typename UEdgeFilterMap>
deba@1979: class EdgeSubUGraphAdaptor :
deba@1979: public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
deba@1979: UEdgeFilterMap, false> {
deba@1979: public:
deba@1979: typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
deba@1979: UEdgeFilterMap, false> Parent;
deba@1979: typedef _UGraph Graph;
deba@1979: protected:
deba@1979: ConstMap<typename Graph::Node, bool> 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@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@1979: };
deba@1979:
deba@1979: template<typename UGraph, typename EdgeFilterMap>
deba@1979: EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
deba@1979: edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
deba@1979: return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
deba@1979: }
deba@1979:
deba@1979: template<typename UGraph, typename EdgeFilterMap>
deba@1979: EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
deba@1979: edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
deba@1979: return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
deba@1979: }
deba@1979:
deba@1979: template <typename _UGraph, typename _DirectionMap>
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@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<Graph> NodeNumTag;
deba@1979: int nodeNum() const { return graph->nodeNum(); }
deba@1979:
deba@1979: typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
deba@1979: int edgeNum() const { return graph->uEdgeNum(); }
deba@1979:
deba@1979: typedef FindEdgeTagIndicator<Graph> 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@1979: (*direction)[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<Graph, Node>::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<Graph, Edge>::ItemNotifier EdgeNotifier;
deba@1991:
deba@1991: EdgeNotifier& getNotifier(Edge) const {
deba@1991: return graph->getNotifier(Edge());
deba@1991: }
deba@1991:
deba@1979: template <typename _Value>
deba@1979: class NodeMap : public _UGraph::template NodeMap<_Value> {
deba@1979: public:
deba@1979: typedef typename _UGraph::template NodeMap<_Value> Parent;
deba@1980: explicit NodeMap(const DirUGraphAdaptorBase& ga)
deba@1979: : Parent(*ga.graph) { }
deba@1980: NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
deba@1979: : Parent(*ga.graph, value) { }
deba@1979: };
deba@1979:
deba@1979: template <typename _Value>
deba@1979: class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
deba@1979: public:
deba@1980: typedef typename _UGraph::template UEdgeMap<_Value> Parent;
deba@1980: explicit EdgeMap(const DirUGraphAdaptorBase& ga)
deba@1979: : Parent(*ga.graph) { }
deba@1980: EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
deba@1979: : Parent(*ga.graph, value) { }
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@1980: /// This adaptor gives a direction for each uedge in the undirected graph.
deba@1980: /// The direction of the edges stored in the DirectionMap. This map is
deba@1980: /// a bool map on the undirected edges. If the uedge is mapped to true
deba@1980: /// then the direction of the directed edge will be the same as the
deba@1980: /// default direction of the uedge. The edges can be easily reverted
deba@1980: /// by the reverseEdge member in the adaptor.
deba@1980: template<typename _Graph,
deba@1980: typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
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@1980: DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
deba@1979: setGraph(_graph);
deba@1979: setDirectionMap(_direction_map);
deba@1979: }
deba@1979: };
deba@1979:
deba@1979: template<typename UGraph, typename DirectionMap>
deba@1980: DirUGraphAdaptor<const UGraph, DirectionMap>
deba@1980: dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
deba@1980: return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
deba@1979: }
deba@1979:
deba@1979: template<typename UGraph, typename DirectionMap>
deba@1980: DirUGraphAdaptor<const UGraph, const DirectionMap>
deba@1980: dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
deba@1980: return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
deba@1979: }
deba@1979:
deba@1979: }
deba@1979:
deba@1979: #endif