# HG changeset patch # User deba # Date 1144057523 0 # Node ID 080d51024ac534b7f81c0fd5d417233e90b7cec9 # Parent d769d2eb4d5058f0cdc39cb85bc786495ffb58ce Correcting the structure of the graph's and adaptor's map. The template assign operators and map iterators can be used for adaptors also. Some bugfix in the adaptors New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph. diff -r d769d2eb4d50 -r 080d51024ac5 lemon/Makefile.am --- a/lemon/Makefile.am Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/Makefile.am Mon Apr 03 09:45:23 2006 +0000 @@ -27,6 +27,7 @@ bfs.h \ dfs.h \ bin_heap.h \ + bpugraph_adaptor.h \ color.h \ config.h \ counter.h \ diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/array_map.h --- a/lemon/bits/array_map.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/array_map.h Mon Apr 03 09:45:23 2006 +0000 @@ -23,6 +23,8 @@ #include #include +#include +#include /// \ingroup graphbits /// \file @@ -119,6 +121,35 @@ } } + /// \brief Assign operator. + /// + /// This operator assigns for each item in the map the + /// value mapped to the same item in the copied map. + /// The parameter map should be indiced with the same + /// itemset because this assign operator does not change + /// the container of the map. + ArrayMap& operator=(const ArrayMap& cmap) { + return operator=(cmap); + } + + + /// \brief Template assign operator. + /// + /// The given parameter should be conform to the ReadMap + /// concecpt and could be indiced by the current item set of + /// the NodeMap. In this case the value for each item + /// is assigned by the value of the given ReadMap. + template + ArrayMap& operator=(const CMap& cmap) { + checkConcept, CMap>(); + const typename Parent::Notifier* notifier = Parent::getNotifier(); + Item it; + for (notifier->first(it); it != INVALID; notifier->next(it)) { + set(it, cmap[it]); + } + return *this; + } + /// \brief The destructor of the map. /// /// The destructor of the map. @@ -129,10 +160,6 @@ } } - private: - - ArrayMap& operator=(const ArrayMap&); - protected: using Parent::attach; diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/base_extender.h --- a/lemon/bits/base_extender.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/base_extender.h Mon Apr 03 09:45:23 2006 +0000 @@ -466,6 +466,15 @@ Edge direct(const UEdge& edge, bool direction) const { return Edge(edge, direction); } + + int edgeNum() const { + return 2 * Parent::edgeNum(); + } + + int uEdgeNum() const { + return Parent::edgeNum(); + } + }; } diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/default_map.h --- a/lemon/bits/default_map.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/default_map.h Mon Apr 03 09:45:23 2006 +0000 @@ -163,6 +163,16 @@ DefaultMap(const Graph& graph, const Value& value) : Parent(graph, value) {} + DefaultMap& operator=(const DefaultMap& cmap) { + return operator=(cmap); + } + + template + DefaultMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; } diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/edge_set_extender.h --- a/lemon/bits/edge_set_extender.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/edge_set_extender.h Mon Apr 03 09:45:23 2006 +0000 @@ -101,7 +101,7 @@ NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) @@ -124,7 +124,7 @@ EdgeIt(Invalid i) : Edge(i) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : @@ -235,14 +235,10 @@ template EdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - Edge it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } + }; @@ -364,7 +360,7 @@ NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) @@ -387,7 +383,7 @@ EdgeIt(Invalid i) : Edge(i) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : @@ -458,7 +454,7 @@ UEdgeIt(Invalid i) : UEdge(i) { } explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } UEdgeIt(const Graph& _graph, const UEdge& e) : @@ -556,14 +552,10 @@ template EdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - Edge it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } + }; @@ -576,6 +568,7 @@ UEdgeMap(const Graph& _g) : Parent(_g) {} + UEdgeMap(const Graph& _g, const _Value& _v) : Parent(_g, _v) {} @@ -585,14 +578,10 @@ template UEdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - UEdge it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } + }; diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/graph_adaptor_extender.h --- a/lemon/bits/graph_adaptor_extender.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/graph_adaptor_extender.h Mon Apr 03 09:45:23 2006 +0000 @@ -33,12 +33,13 @@ /// \ingroup graphbits /// /// \brief Extender for the GraphAdaptors - template - class GraphAdaptorExtender : public Base { + template + class GraphAdaptorExtender : public _Graph { public: - typedef Base Parent; - typedef GraphAdaptorExtender Graph; + typedef _Graph Parent; + typedef _Graph Graph; + typedef GraphAdaptorExtender Adaptor; // Base extensions @@ -71,18 +72,18 @@ } class NodeIt : public Node { - const Graph* graph; + const Adaptor* graph; public: NodeIt() {} NodeIt(Invalid i) : Node(i) { } - explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + explicit NodeIt(const Adaptor& _graph) : graph(&_graph) { + _graph.first(static_cast(*this)); } - NodeIt(const Graph& _graph, const Node& node) + NodeIt(const Adaptor& _graph, const Node& node) : Node(node), graph(&_graph) {} NodeIt& operator++() { @@ -94,18 +95,18 @@ class EdgeIt : public Edge { - const Graph* graph; + const Adaptor* graph; public: EdgeIt() { } EdgeIt(Invalid i) : Edge(i) { } - explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) { + _graph.first(static_cast(*this)); } - EdgeIt(const Graph& _graph, const Edge& e) : + EdgeIt(const Adaptor& _graph, const Edge& e) : Edge(e), graph(&_graph) { } EdgeIt& operator++() { @@ -117,19 +118,19 @@ class OutEdgeIt : public Edge { - const Graph* graph; + const Adaptor* graph; public: OutEdgeIt() { } OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const Graph& _graph, const Node& node) + OutEdgeIt(const Adaptor& _graph, const Node& node) : graph(&_graph) { _graph.firstOut(*this, node); } - OutEdgeIt(const Graph& _graph, const Edge& edge) + OutEdgeIt(const Adaptor& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} OutEdgeIt& operator++() { @@ -141,19 +142,19 @@ class InEdgeIt : public Edge { - const Graph* graph; + const Adaptor* graph; public: InEdgeIt() { } InEdgeIt(Invalid i) : Edge(i) { } - InEdgeIt(const Graph& _graph, const Node& node) + InEdgeIt(const Adaptor& _graph, const Node& node) : graph(&_graph) { _graph.firstIn(*this, node); } - InEdgeIt(const Graph& _graph, const Edge& edge) : + InEdgeIt(const Adaptor& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} InEdgeIt& operator++() { @@ -197,12 +198,13 @@ /// \ingroup graphbits /// /// \brief Extender for the UGraphAdaptors - template - class UGraphAdaptorExtender : public Base { + template + class UGraphAdaptorExtender : public _UGraph { public: - typedef Base Parent; - typedef UGraphAdaptorExtender Graph; + typedef _UGraph Parent; + typedef _UGraph UGraph; + typedef UGraphAdaptorExtender Adaptor; typedef typename Parent::Node Node; typedef typename Parent::Edge Edge; @@ -254,18 +256,18 @@ class NodeIt : public Node { - const Graph* graph; + const Adaptor* graph; public: NodeIt() {} NodeIt(Invalid i) : Node(i) { } - explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + explicit NodeIt(const Adaptor& _graph) : graph(&_graph) { + _graph.first(static_cast(*this)); } - NodeIt(const Graph& _graph, const Node& node) + NodeIt(const Adaptor& _graph, const Node& node) : Node(node), graph(&_graph) {} NodeIt& operator++() { @@ -277,18 +279,18 @@ class EdgeIt : public Edge { - const Graph* graph; + const Adaptor* graph; public: EdgeIt() { } EdgeIt(Invalid i) : Edge(i) { } - explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) { + _graph.first(static_cast(*this)); } - EdgeIt(const Graph& _graph, const Edge& e) : + EdgeIt(const Adaptor& _graph, const Edge& e) : Edge(e), graph(&_graph) { } EdgeIt& operator++() { @@ -300,19 +302,19 @@ class OutEdgeIt : public Edge { - const Graph* graph; + const Adaptor* graph; public: OutEdgeIt() { } OutEdgeIt(Invalid i) : Edge(i) { } - OutEdgeIt(const Graph& _graph, const Node& node) + OutEdgeIt(const Adaptor& _graph, const Node& node) : graph(&_graph) { _graph.firstOut(*this, node); } - OutEdgeIt(const Graph& _graph, const Edge& edge) + OutEdgeIt(const Adaptor& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} OutEdgeIt& operator++() { @@ -324,19 +326,19 @@ class InEdgeIt : public Edge { - const Graph* graph; + const Adaptor* graph; public: InEdgeIt() { } InEdgeIt(Invalid i) : Edge(i) { } - InEdgeIt(const Graph& _graph, const Node& node) + InEdgeIt(const Adaptor& _graph, const Node& node) : graph(&_graph) { _graph.firstIn(*this, node); } - InEdgeIt(const Graph& _graph, const Edge& edge) : + InEdgeIt(const Adaptor& _graph, const Edge& edge) : Edge(edge), graph(&_graph) {} InEdgeIt& operator++() { @@ -347,18 +349,18 @@ }; class UEdgeIt : public Parent::UEdge { - const Graph* graph; + const Adaptor* graph; public: UEdgeIt() { } UEdgeIt(Invalid i) : UEdge(i) { } - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + explicit UEdgeIt(const Adaptor& _graph) : graph(&_graph) { + _graph.first(static_cast(*this)); } - UEdgeIt(const Graph& _graph, const UEdge& e) : + UEdgeIt(const Adaptor& _graph, const UEdge& e) : UEdge(e), graph(&_graph) { } UEdgeIt& operator++() { @@ -370,7 +372,7 @@ class IncEdgeIt : public Parent::UEdge { friend class UGraphAdaptorExtender; - const Graph* graph; + const Adaptor* graph; bool direction; public: @@ -378,11 +380,11 @@ IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { + IncEdgeIt(const Adaptor& _graph, const Node &n) : graph(&_graph) { _graph.firstInc(static_cast(*this), direction, n); } - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) + IncEdgeIt(const Adaptor& _graph, const UEdge &ue, const Node &n) : graph(&_graph), UEdge(ue) { direction = (_graph.source(ue) == n); } @@ -436,6 +438,290 @@ }; + /// \ingroup graphbits + /// + /// \brief Extender for the BpUGraphAdaptors + template + class BpUGraphAdaptorExtender : public Base { + public: + typedef Base Parent; + typedef BpUGraphAdaptorExtender Graph; + + typedef typename Parent::Node Node; + typedef typename Parent::BNode BNode; + typedef typename Parent::ANode ANode; + typedef typename Parent::Edge Edge; + typedef typename Parent::UEdge UEdge; + + Node oppositeNode(const UEdge& edge, const Node& node) const { + return source(edge) == node ? + target(edge) : source(edge); + } + + + int maxId(Node) const { + return Parent::maxNodeId(); + } + int maxId(BNode) const { + return Parent::maxBNodeId(); + } + int maxId(ANode) const { + return Parent::maxANodeId(); + } + int maxId(Edge) const { + return Parent::maxEdgeId(); + } + int maxId(UEdge) const { + return Parent::maxUEdgeId(); + } + + + Node fromId(int id, Node) const { + return Parent::nodeFromId(id); + } + ANode fromId(int id, ANode) const { + return Parent::fromANodeId(id); + } + BNode fromId(int id, BNode) const { + return Parent::fromBNodeId(id); + } + Edge fromId(int id, Edge) const { + return Parent::edgeFromId(id); + } + UEdge fromId(int id, UEdge) const { + return Parent::uEdgeFromId(id); + } + + class NodeIt : public Node { + const Graph* graph; + public: + + NodeIt() { } + + NodeIt(Invalid i) : Node(INVALID) { } + + explicit NodeIt(const Graph& _graph) : graph(&_graph) { + graph->first(static_cast(*this)); + } + + NodeIt(const Graph& _graph, const Node& node) + : Node(node), graph(&_graph) { } + + NodeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + class ANodeIt : public Node { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + public: + + ANodeIt() { } + + ANodeIt(Invalid i) : Node(INVALID) { } + + explicit ANodeIt(const Graph& _graph) : graph(&_graph) { + graph->firstANode(static_cast(*this)); + } + + ANodeIt(const Graph& _graph, const Node& node) + : Node(node), graph(&_graph) {} + + ANodeIt& operator++() { + graph->nextANode(*this); + return *this; + } + }; + + class BNodeIt : public Node { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + public: + + BNodeIt() { } + + BNodeIt(Invalid i) : Node(INVALID) { } + + explicit BNodeIt(const Graph& _graph) : graph(&_graph) { + graph->firstBNode(static_cast(*this)); + } + + BNodeIt(const Graph& _graph, const Node& node) + : Node(node), graph(&_graph) {} + + BNodeIt& operator++() { + graph->nextBNode(*this); + return *this; + } + }; + + class EdgeIt : public Edge { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + public: + + EdgeIt() { } + + EdgeIt(Invalid i) : Edge(INVALID) { } + + explicit EdgeIt(const Graph& _graph) : graph(&_graph) { + graph->first(static_cast(*this)); + } + + EdgeIt(const Graph& _graph, const Edge& edge) + : Edge(edge), graph(&_graph) { } + + EdgeIt& operator++() { + graph->next(*this); + return *this; + } + + }; + + class UEdgeIt : public UEdge { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + public: + + UEdgeIt() { } + + UEdgeIt(Invalid i) : UEdge(INVALID) { } + + explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { + graph->first(static_cast(*this)); + } + + UEdgeIt(const Graph& _graph, const UEdge& edge) + : UEdge(edge), graph(&_graph) { } + + UEdgeIt& operator++() { + graph->next(*this); + return *this; + } + }; + + class OutEdgeIt : public Edge { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + public: + + OutEdgeIt() { } + + OutEdgeIt(Invalid i) : Edge(i) { } + + OutEdgeIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + graph->firstOut(*this, node); + } + + OutEdgeIt(const Graph& _graph, const Edge& edge) + : Edge(edge), graph(&_graph) {} + + OutEdgeIt& operator++() { + graph->nextOut(*this); + return *this; + } + + }; + + + class InEdgeIt : public Edge { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + public: + + InEdgeIt() { } + + InEdgeIt(Invalid i) : Edge(i) { } + + InEdgeIt(const Graph& _graph, const Node& node) + : graph(&_graph) { + graph->firstIn(*this, node); + } + + InEdgeIt(const Graph& _graph, const Edge& edge) : + Edge(edge), graph(&_graph) {} + + InEdgeIt& operator++() { + graph->nextIn(*this); + return *this; + } + + }; + + /// \brief Base node of the iterator + /// + /// Returns the base node (ie. the source in this case) of the iterator + Node baseNode(const OutEdgeIt &e) const { + return Parent::source((Edge&)e); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (ie. the target in this case) of the + /// iterator + Node runningNode(const OutEdgeIt &e) const { + return Parent::target((Edge&)e); + } + + /// \brief Base node of the iterator + /// + /// Returns the base node (ie. the target in this case) of the iterator + Node baseNode(const InEdgeIt &e) const { + return Parent::target((Edge&)e); + } + /// \brief Running node of the iterator + /// + /// Returns the running node (ie. the source in this case) of the + /// iterator + Node runningNode(const InEdgeIt &e) const { + return Parent::source((Edge&)e); + } + + class IncEdgeIt : public Parent::UEdge { + friend class BpUGraphAdaptorExtender; + const Graph* graph; + bool direction; + public: + + IncEdgeIt() { } + + IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } + + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { + graph->firstInc(*this, direction, n); + } + + IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) + : graph(&_graph), UEdge(ue) { + direction = (graph->source(ue) == n); + } + + IncEdgeIt& operator++() { + graph->nextInc(*this, direction); + return *this; + } + }; + + + /// Base node of the iterator + /// + /// Returns the base node of the iterator + Node baseNode(const IncEdgeIt &e) const { + return e.direction ? source(e) : target(e); + } + + /// Running node of the iterator + /// + /// Returns the running node of the iterator + Node runningNode(const IncEdgeIt &e) const { + return e.direction ? target(e) : source(e); + } + + }; + } diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/graph_extender.h --- a/lemon/bits/graph_extender.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/graph_extender.h Mon Apr 03 09:45:23 2006 +0000 @@ -103,7 +103,7 @@ NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) @@ -126,7 +126,7 @@ EdgeIt(Invalid i) : Edge(i) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : @@ -232,21 +232,9 @@ return operator=(cmap); } - - /// \brief Template assign operator. - /// - /// The given parameter should be conform to the ReadMap - /// concecpt and could be indiced by the current item set of - /// the NodeMap. In this case the value for each item - /// is assigned by the value of the given ReadMap. template NodeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Node it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } @@ -270,12 +258,7 @@ template EdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Edge it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } }; @@ -431,7 +414,7 @@ NodeIt(Invalid i) : Node(i) { } explicit NodeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } NodeIt(const Graph& _graph, const Node& node) @@ -454,7 +437,7 @@ EdgeIt(Invalid i) : Edge(i) { } explicit EdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } EdgeIt(const Graph& _graph, const Edge& e) : @@ -525,7 +508,7 @@ UEdgeIt(Invalid i) : UEdge(i) { } explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { - _graph.first(*static_cast(this)); + _graph.first(static_cast(*this)); } UEdgeIt(const Graph& _graph, const UEdge& e) : @@ -622,21 +605,9 @@ return operator=(cmap); } - - /// \brief Template assign operator. - /// - /// The given parameter should be conform to the ReadMap - /// concecpt and could be indiced by the current item set of - /// the NodeMap. In this case the value for each item - /// is assigned by the value of the given ReadMap. template NodeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Node it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } @@ -660,12 +631,7 @@ template EdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Edge it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } }; @@ -680,6 +646,7 @@ UEdgeMap(const Graph& graph) : Parent(graph) {} + UEdgeMap(const Graph& graph, const _Value& value) : Parent(graph, value) {} @@ -689,14 +656,10 @@ template UEdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Edge it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } + }; // Alteration extension @@ -1104,21 +1067,9 @@ return operator=(cmap); } - - /// \brief Template assign operator. - /// - /// The given parameter should be conform to the ReadMap - /// concept and could be indiced by the current item set of - /// the ANodeMap. In this case the value for each item - /// is assigned by the value of the given ReadMap. template ANodeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - ANode it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } @@ -1140,30 +1091,18 @@ return operator=(cmap); } - - /// \brief Template assign operator. - /// - /// The given parameter should be conform to the ReadMap - /// concept and could be indiced by the current item set of - /// the BNodeMap. In this case the value for each item - /// is assigned by the value of the given ReadMap. template BNodeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - BNode it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } }; - protected: + public: template - class NodeMapBase { + class NodeMap { public: typedef BpUGraphExtender Graph; @@ -1177,10 +1116,25 @@ typedef True ReferenceMapTag; - NodeMapBase(const Graph& graph) - : aNodeMap(graph), bNodeMap(graph) {} - NodeMapBase(const Graph& graph, const _Value& value) - : aNodeMap(graph, value), bNodeMap(graph, value) {} + NodeMap(const Graph& _graph) + : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} + NodeMap(const Graph& _graph, const _Value& _value) + : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + checkConcept, CMap>(); + const typename Parent::Notifier* notifier = Parent::getNotifier(); + Edge it; + for (graph.first(it); it != INVALID; graph.next(it)) { + Parent::set(it, cmap[it]); + } + return *this; + } ConstReference operator[](const Key& node) const { if (Parent::aNode(node)) { @@ -1206,54 +1160,62 @@ } } - const Graph* getGraph() const { - return aNodeMap.getGraph(); - } + class MapIt : public NodeIt { + public: + typedef NodeIt Parent; + + explicit MapIt(NodeMap& _map) + : Parent(_map.graph), map(_map) {} + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + typename MapTraits::ReturnValue operator*() { + return map[*this]; + } + + void set(const Value& value) { + map.set(*this, value); + } + + private: + NodeMap& map; + }; + + class ConstMapIt : public NodeIt { + public: + + typedef NodeIt Parent; + + explicit ConstMapIt(const NodeMap& _map) + : Parent(_map.graph), map(_map) {} + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + private: + const NodeMap& map; + }; + + class ItemIt : public NodeIt { + public: + + typedef NodeIt Parent; + + explicit ItemIt(const NodeMap& _map) + : Parent(_map.graph) {} + + }; + private: + const Graph& graph; ANodeMap<_Value> aNodeMap; BNodeMap<_Value> bNodeMap; }; - public: - - template - class NodeMap - : public MapExtender > { - public: - typedef BpUGraphExtender Graph; - typedef MapExtender< NodeMapBase<_Value> > Parent; - - NodeMap(const Graph& graph) - : Parent(graph) {} - NodeMap(const Graph& graph, const _Value& value) - : Parent(graph, value) {} - - NodeMap& operator=(const NodeMap& cmap) { - return operator=(cmap); - } - - - /// \brief Template assign operator. - /// - /// The given parameter should be conform to the ReadMap - /// concept and could be indiced by the current item set of - /// the NodeMap. In this case the value for each item - /// is assigned by the value of the given ReadMap. - template - NodeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Edge it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } - return *this; - } - - }; - - template class EdgeMap @@ -1273,12 +1235,7 @@ template EdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Edge it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } }; @@ -1301,12 +1258,7 @@ template UEdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Notifier* notifier = Parent::getNotifier(); - Edge it; - for (notifier->first(it); it != INVALID; notifier->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } }; diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/map_extender.h --- a/lemon/bits/map_extender.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/map_extender.h Mon Apr 03 09:45:23 2006 +0000 @@ -23,6 +23,9 @@ #include +#include +#include + ///\file ///\brief Extenders for iterable maps. @@ -59,6 +62,15 @@ MapExtender(const Graph& graph, const Value& value) : Parent(graph, value) {} + MapExtender& operator=(const MapExtender& cmap) { + return operator=(cmap); + } + + template + MapExtender& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } class MapIt : public Item { public: @@ -130,7 +142,7 @@ const Map& map; }; - class ItemIt : Item { + class ItemIt : public Item { public: typedef Item Parent; @@ -140,7 +152,7 @@ ItemIt(Invalid i) : Parent(i) { } explicit ItemIt(Map& _map) : map(_map) { - map->getNotifier()->first(*this); + map.getNotifier()->first(*this); } ItemIt(const Map& _map, const Item& item) @@ -157,6 +169,153 @@ }; }; + /// \ingroup graphbits + /// + /// \brief Extender for maps which use a subset of the items. + template + class SubMapExtender : public _Map { + public: + + typedef _Map Parent; + typedef SubMapExtender Map; + + typedef _Graph Graph; + + typedef typename Parent::Key Item; + + typedef typename Parent::Key Key; + typedef typename Parent::Value Value; + + class MapIt; + class ConstMapIt; + + friend class MapIt; + friend class ConstMapIt; + + public: + + SubMapExtender(const Graph& _graph) + : Parent(_graph), graph(_graph) {} + + SubMapExtender(const Graph& _graph, const Value& _value) + : Parent(_graph, _value), graph(_graph) {} + + SubMapExtender& operator=(const SubMapExtender& cmap) { + return operator=(cmap); + } + + template + SubMapExtender& operator=(const CMap& cmap) { + checkConcept, CMap>(); + Item it; + for (graph.first(it); it != INVALID; graph.next(it)) { + Parent::set(it, cmap[it]); + } + return *this; + } + + class MapIt : public Item { + public: + + typedef Item Parent; + typedef typename Map::Value Value; + + MapIt() {} + + MapIt(Invalid i) : Parent(i) { } + + explicit MapIt(Map& _map) : map(_map) { + map.graph.first(*this); + } + + MapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + MapIt& operator++() { + map.graph.next(*this); + return *this; + } + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + typename MapTraits::ReturnValue operator*() { + return map[*this]; + } + + void set(const Value& value) { + map.set(*this, value); + } + + protected: + Map& map; + + }; + + class ConstMapIt : public Item { + public: + + typedef Item Parent; + + typedef typename Map::Value Value; + + ConstMapIt() {} + + ConstMapIt(Invalid i) : Parent(i) { } + + explicit ConstMapIt(Map& _map) : map(_map) { + map.graph.first(*this); + } + + ConstMapIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ConstMapIt& operator++() { + map.graph.next(*this); + return *this; + } + + typename MapTraits::ConstReturnValue operator*() const { + return map[*this]; + } + + protected: + const Map& map; + }; + + class ItemIt : public Item { + public: + + typedef Item Parent; + + ItemIt() {} + + ItemIt(Invalid i) : Parent(i) { } + + explicit ItemIt(Map& _map) : map(_map) { + map.graph.first(*this); + } + + ItemIt(const Map& _map, const Item& item) + : Parent(item), map(_map) {} + + ItemIt& operator++() { + map.graph.next(*this); + return *this; + } + + protected: + const Map& map; + + }; + + private: + + const Graph& graph; + + }; + } #endif diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bits/vector_map.h --- a/lemon/bits/vector_map.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/bits/vector_map.h Mon Apr 03 09:45:23 2006 +0000 @@ -27,6 +27,9 @@ #include +#include +#include + ///\ingroup graphbits /// ///\file @@ -112,10 +115,35 @@ } } - private: + /// \brief Assign operator. + /// + /// This operator assigns for each item in the map the + /// value mapped to the same item in the copied map. + /// The parameter map should be indiced with the same + /// itemset because this assign operator does not change + /// the container of the map. + VectorMap& operator=(const VectorMap& cmap) { + return operator=(cmap); + } - VectorMap& operator=(const VectorMap&); + /// \brief Template assign operator. + /// + /// The given parameter should be conform to the ReadMap + /// concecpt and could be indiced by the current item set of + /// the NodeMap. In this case the value for each item + /// is assigned by the value of the given ReadMap. + template + VectorMap& operator=(const CMap& cmap) { + checkConcept, CMap>(); + const typename Parent::Notifier* notifier = Parent::getNotifier(); + Item it; + for (notifier->first(it); it != INVALID; notifier->next(it)) { + set(it, cmap[it]); + } + return *this; + } + public: /// \brief The subcript operator. diff -r d769d2eb4d50 -r 080d51024ac5 lemon/bpugraph_adaptor.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/bpugraph_adaptor.h Mon Apr 03 09:45:23 2006 +0000 @@ -0,0 +1,412 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_BPUGRAPH_ADAPTOR_H +#define LEMON_BPUGRAPH_ADAPTOR_H + +#include +#include + +#include + +#include + +#include + +///\ingroup graph_adaptors +///\file +///\brief Several graph adaptors. +/// +///This file contains several useful bpugraph adaptor functions. +/// +///\author Balazs Dezso + +namespace lemon { + + /// \ingroup graph_adaptors + /// + /// \brief Base type for the Bipartite Undirected Graph Adaptors + /// + /// This is the base type for most of LEMON bpugraph adaptors. + /// This class implements a trivial graph adaptor i.e. it only wraps the + /// functions and types of the graph. The purpose of this class is to + /// make easier implementing graph adaptors. E.g. if an adaptor is + /// considered which differs from the wrapped graph only in some of its + /// functions or types, then it can be derived from BpUGraphAdaptor, and + /// only the differences should be implemented. + /// + /// \author Balazs Dezso + template + class BpUGraphAdaptorBase { + public: + typedef _BpUGraph Graph; + typedef Graph ParentGraph; + + protected: + Graph* graph; + + BpUGraphAdaptorBase() : graph(0) {} + + void setGraph(Graph& _graph) { graph = &_graph; } + + Graph& getGraph() { return *graph; } + const Graph& getGraph() const { return *graph; } + + public: + + BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {} + + typedef typename Graph::Node Node; + typedef typename Graph::ANode ANode; + typedef typename Graph::BNode BNode; + typedef typename Graph::Edge Edge; + typedef typename Graph::UEdge UEdge; + + void first(Node& i) const { graph->first(i); } + void firstANode(Node& i) const { graph->firstANode(i); } + void firstBNode(Node& i) const { graph->firstBNode(i); } + void first(Edge& i) const { graph->first(i); } + void first(UEdge& i) const { graph->first(i); } + void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); } + void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); } + void firstInc(UEdge &i, bool &d, const Node &n) const { + graph->firstInc(i, d, n); + } + + void next(Node& i) const { graph->next(i); } + void nextANode(Node& i) const { graph->nextANode(i); } + void nextBNode(Node& i) const { graph->nextBNode(i); } + void next(Edge& i) const { graph->next(i); } + void next(UEdge& i) const { graph->next(i); } + void nextIn(Edge& i) const { graph->nextIn(i); } + void nextOut(Edge& i) const { graph->nextOut(i); } + void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); } + + Node source(const UEdge& e) const { return graph->source(e); } + Node target(const UEdge& e) const { return graph->target(e); } + + Node source(const Edge& e) const { return graph->source(e); } + Node target(const Edge& e) const { return graph->target(e); } + + typedef NodeNumTagIndicator NodeNumTag; + int nodeNum() const { return graph->nodeNum(); } + int aNodeNum() const { return graph->aNodeNum(); } + int bNodeNum() const { return graph->bNodeNum(); } + + typedef EdgeNumTagIndicator EdgeNumTag; + int edgeNum() const { return graph->edgeNum(); } + int uEdgeNum() const { return graph->uEdgeNum(); } + + typedef FindEdgeTagIndicator FindEdgeTag; + Edge findEdge(const Node& source, const Node& target, + const Edge& prev = INVALID) { + return graph->findEdge(source, target, prev); + } + UEdge findUEdge(const Node& source, const Node& target, + const UEdge& prev = INVALID) { + return graph->findUEdge(source, target, prev); + } + + Node addNode() const { return graph->addNode(); } + UEdge addEdge(const Node& source, const Node& target) const { + return graph->addEdge(source, target); + } + + void erase(const Node& i) const { graph->erase(i); } + void erase(const UEdge& i) const { graph->erase(i); } + + void clear() const { graph->clear(); } + + bool direction(const Edge& e) const { return graph->direction(e); } + Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); } + + int id(const Node& v) const { return graph->id(v); } + int id(const ANode& v) const { return graph->id(v); } + int id(const BNode& v) const { return graph->id(v); } + int id(const Edge& e) const { return graph->id(e); } + int id(const UEdge& e) const { return graph->id(e); } + + Node fromNodeId(int id) const { return graph->fromNodeId(id); } + ANode fromANodeId(int id) const { return graph->fromANodeId(id); } + BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); } + Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); } + UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); } + + int maxNodeId() const { return graph->maxNodeId(); } + int maxANodeId() const { return graph->maxANodeId(); } + int maxBNodeId() const { return graph->maxBNodeId(); } + int maxEdgeId() const { return graph->maxEdgeId(); } + int maxUEdgeId() const { return graph->maxEdgeId(); } + + typedef typename ItemSetTraits::ItemNotifier NodeNotifier; + NodeNotifier& getNotifier(Node) const { + return graph->getNotifier(Node()); + } + + typedef typename ItemSetTraits::ItemNotifier ANodeNotifier; + ANodeNotifier& getNotifier(ANode) const { + return graph->getNotifier(ANode()); + } + + typedef typename ItemSetTraits::ItemNotifier BNodeNotifier; + BNodeNotifier& getNotifier(BNode) const { + return graph->getNotifier(BNode()); + } + + typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; + EdgeNotifier& getNotifier(Edge) const { + return graph->getNotifier(Edge()); + } + + typedef typename ItemSetTraits::ItemNotifier UEdgeNotifier; + UEdgeNotifier& getNotifier(UEdge) const { + return graph->getNotifier(UEdge()); + } + + template + class NodeMap : public Graph::template NodeMap<_Value> { + public: + typedef typename Graph::template NodeMap<_Value> Parent; + explicit NodeMap(const BpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + NodeMap(const BpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class ANodeMap : public Graph::template ANodeMap<_Value> { + public: + typedef typename Graph::template ANodeMap<_Value> Parent; + explicit ANodeMap(const BpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + ANodeMap& operator=(const ANodeMap& cmap) { + return operator=(cmap); + } + + template + ANodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class BNodeMap : public Graph::template BNodeMap<_Value> { + public: + typedef typename Graph::template BNodeMap<_Value> Parent; + explicit BNodeMap(const BpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + BNodeMap(const BpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + BNodeMap& operator=(const BNodeMap& cmap) { + return operator=(cmap); + } + + template + BNodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class EdgeMap : public Graph::template EdgeMap<_Value> { + public: + typedef typename Graph::template EdgeMap<_Value> Parent; + explicit EdgeMap(const BpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + EdgeMap(const BpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class UEdgeMap : public Graph::template UEdgeMap<_Value> { + public: + typedef typename Graph::template UEdgeMap<_Value> Parent; + explicit UEdgeMap(const BpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + UEdgeMap(const BpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + UEdgeMap& operator=(const UEdgeMap& cmap) { + return operator=(cmap); + } + + template + UEdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + }; + + /// \ingroup graph_adaptors + template + class BpUGraphAdaptor + : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > { + public: + typedef _BpUGraph Graph; + typedef BpUGraphAdaptorExtender > Parent; + protected: + BpUGraphAdaptor() : Parent() {} + + public: + explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } + }; + + template + class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> { + public: + + typedef _BpUGraph Graph; + typedef BpUGraphAdaptorBase<_BpUGraph> Parent; + + protected: + + SwapBpUGraphAdaptorBase() {} + + public: + + typedef typename Parent::Node Node; + typedef typename Parent::BNode ANode; + typedef typename Parent::ANode BNode; + + void firstANode(Node& i) const { Parent::firstBNode(i); } + void firstBNode(Node& i) const { Parent::firstANode(i); } + + void nextANode(Node& i) const { Parent::nextBNode(i); } + void nextBNode(Node& i) const { Parent::nextANode(i); } + + int id(const ANode& v) const { return Parent::id(v); } + int id(const BNode& v) const { return Parent::id(v); } + + ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); } + BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); } + + int maxANodeId() const { return Parent::maxBNodeId(); } + int maxBNodeId() const { return Parent::maxANodeId(); } + + int aNodeNum() const { return Parent::bNodeNum(); } + int bNodeNum() const { return Parent::aNodeNum(); } + + typedef typename Parent::BNodeNotifier ANodeNotifier; + ANodeNotifier& getNotifier(ANode) const { + return Parent::getNotifier(typename Parent::BNode()); + } + + typedef typename Parent::ANodeNotifier BNodeNotifier; + BNodeNotifier& getNotifier(BNode) const { + return Parent::getNotifier(typename Parent::ANode()); + } + + template + class ANodeMap : public Graph::template BNodeMap<_Value> { + public: + typedef typename Graph::template BNodeMap<_Value> Parent; + explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + ANodeMap& operator=(const ANodeMap& cmap) { + return operator=(cmap); + } + + template + ANodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class BNodeMap : public Graph::template ANodeMap<_Value> { + public: + typedef typename Graph::template ANodeMap<_Value> Parent; + explicit BNodeMap(const SwapBpUGraphAdaptorBase& ga) + : Parent(*ga.graph) {} + BNodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + BNodeMap& operator=(const BNodeMap& cmap) { + return operator=(cmap); + } + + template + BNodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + }; + + /// \ingroup graph_adaptors + /// + /// \brief Bipartite graph adaptor which swaps the two nodeset. + /// + /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's + /// a-nodeset will be the original graph's b-nodeset and the adaptor's + /// b-nodeset will be the original graph's a-nodeset. + template + class SwapBpUGraphAdaptor + : public BpUGraphAdaptorExtender > { + public: + + typedef _BpUGraph Graph; + typedef BpUGraphAdaptorExtender > + Parent; + + protected: + SwapBpUGraphAdaptor() : Parent() {} + + public: + + explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); } + + }; + + +} + +#endif diff -r d769d2eb4d50 -r 080d51024ac5 lemon/edge_set.h --- a/lemon/edge_set.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/edge_set.h Mon Apr 03 09:45:23 2006 +0000 @@ -206,11 +206,24 @@ template class NodeMap : public Graph::template NodeMap<_Value> { public: + typedef typename _Graph::template NodeMap<_Value> Parent; + explicit NodeMap(const ListEdgeSetBase& edgeset) - : Parent(*edgeset.graph) { } + : Parent(*edgeset.graph) {} + NodeMap(const ListEdgeSetBase& edgeset, const _Value& value) - : Parent(*edgeset.graph, value) { } + : Parent(*edgeset.graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } }; }; @@ -521,11 +534,24 @@ template class NodeMap : public Graph::template NodeMap<_Value> { public: + typedef typename _Graph::template NodeMap<_Value> Parent; + explicit NodeMap(const SmartEdgeSetBase& edgeset) : Parent(*edgeset.graph) { } + NodeMap(const SmartEdgeSetBase& edgeset, const _Value& value) : Parent(*edgeset.graph, value) { } + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } }; }; @@ -667,7 +693,7 @@ typedef typename Parent::NodesImplBase NodesImplBase; void eraseNode(const Node& node) { - if (Parent::IncEdgeIt(*this, node) == INVALID) { + if (typename Parent::IncEdgeIt(*this, node) == INVALID) { return; } throw UnsupportedOperation(); diff -r d769d2eb4d50 -r 080d51024ac5 lemon/full_graph.h --- a/lemon/full_graph.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/full_graph.h Mon Apr 03 09:45:23 2006 +0000 @@ -645,6 +645,14 @@ return Node((index << 1) + 1); } + typedef True NodeNumTag; + int nodeNum() const { return _aNodeNum + _bNodeNum; } + int aNodeNum() const { return _aNodeNum; } + int bNodeNum() const { return _bNodeNum; } + + typedef True EdgeNumTag; + int edgeNum() const { return _edgeNum; } + }; diff -r d769d2eb4d50 -r 080d51024ac5 lemon/graph_adaptor.h --- a/lemon/graph_adaptor.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/graph_adaptor.h Mon Apr 03 09:45:23 2006 +0000 @@ -19,13 +19,13 @@ #ifndef LEMON_GRAPH_ADAPTOR_H #define LEMON_GRAPH_ADAPTOR_H -///\ingroup graph_adaptors -///\file -///\brief Several graph adaptors. +/// \ingroup graph_adaptors +/// \file +/// \brief Several graph adaptors. /// -///This file contains several useful graph adaptor functions. +/// This file contains several useful graph adaptor functions. /// -///\author Marton Makai +/// \author Marton Makai and Balazs Dezso #include #include @@ -61,6 +61,7 @@ class GraphAdaptorBase { public: typedef _Graph Graph; + typedef GraphAdaptorBase Adaptor; typedef Graph ParentGraph; protected: @@ -115,6 +116,14 @@ int id(const Node& v) const { return graph->id(v); } int id(const Edge& e) const { return graph->id(e); } + Node fromNodeId(int id) const { + return graph->fromNodeId(id); + } + + Edge fromEdgeId(int id) const { + return graph->fromEdgeId(id); + } + int maxNodeId() const { return graph->maxNodeId(); } @@ -136,23 +145,51 @@ } template - class NodeMap : public _Graph::template NodeMap<_Value> { + class NodeMap : public Graph::template NodeMap<_Value> { public: - typedef typename _Graph::template NodeMap<_Value> Parent; - explicit NodeMap(const GraphAdaptorBase<_Graph>& ga) - : Parent(*ga.graph) { } - NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value) + + typedef typename Graph::template NodeMap<_Value> Parent; + + explicit NodeMap(const Adaptor& ga) + : Parent(*ga.graph) {} + + NodeMap(const Adaptor& ga, const _Value& value) : Parent(*ga.graph, value) { } + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; template - class EdgeMap : public _Graph::template EdgeMap<_Value> { + class EdgeMap : public Graph::template EdgeMap<_Value> { public: - typedef typename _Graph::template EdgeMap<_Value> Parent; - explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga) - : Parent(*ga.graph) { } - EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value) - : Parent(*ga.graph, value) { } + + typedef typename Graph::template EdgeMap<_Value> Parent; + + explicit EdgeMap(const Adaptor& ga) + : Parent(*ga.graph) {} + + EdgeMap(const Adaptor& ga, const _Value& value) + : Parent(*ga.graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; }; @@ -255,6 +292,7 @@ class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { public: typedef _Graph Graph; + typedef SubGraphAdaptorBase Adaptor; typedef GraphAdaptorBase<_Graph> Parent; protected: NodeFilterMap* node_filter_map; @@ -377,6 +415,59 @@ } return edge; } + + template + class NodeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + NodeMap(const Graph& graph) + : Parent(graph) {} + NodeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class EdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + EdgeMap(const Graph& graph) + : Parent(graph) {} + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + }; template @@ -384,6 +475,7 @@ : public GraphAdaptorBase<_Graph> { public: typedef _Graph Graph; + typedef SubGraphAdaptorBase Adaptor; typedef GraphAdaptorBase<_Graph> Parent; protected: NodeFilterMap* node_filter_map; @@ -496,6 +588,59 @@ } return edge; } + + template + class NodeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + NodeMap(const Graph& graph) + : Parent(graph) {} + NodeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class EdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + EdgeMap(const Graph& graph) + : Parent(graph) {} + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + }; /// \brief A graph adaptor for hiding nodes and edges from a graph. @@ -566,17 +711,21 @@ SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { public: typedef _Graph Graph; - typedef GraphAdaptorExtender< - SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; + typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap, + EdgeFilterMap, checked> > + Parent; + protected: SubGraphAdaptor() { } public: + SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, EdgeFilterMap& _edge_filter_map) { setGraph(_graph); setNodeFilterMap(_node_filter_map); setEdgeFilterMap(_edge_filter_map); } + }; /// \brief Just gives back a sub graph adaptor @@ -635,8 +784,11 @@ public SubGraphAdaptor, checked> { public: + typedef SubGraphAdaptor > Parent; + ConstMap, checked > + Parent; + protected: ConstMap const_true_map; @@ -645,12 +797,14 @@ } public: + NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : Parent(), const_true_map(true) { Parent::setGraph(_graph); Parent::setNodeFilterMap(_node_filter_map); Parent::setEdgeFilterMap(const_true_map); } + }; @@ -820,12 +974,14 @@ } public: + EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) : Parent(), const_true_map(true) { Parent::setGraph(_graph); Parent::setNodeFilterMap(const_true_map); Parent::setEdgeFilterMap(_edge_filter_map); } + }; /// \brief Just gives back an edge sub graph adaptor @@ -848,6 +1004,7 @@ public UGraphBaseExtender > { public: typedef _Graph Graph; + typedef UndirGraphAdaptorBase Adaptor; typedef UGraphBaseExtender > Parent; protected: @@ -859,9 +1016,10 @@ typedef typename Parent::UEdge UEdge; typedef typename Parent::Edge Edge; + private: template - class EdgeMap { + class EdgeMapBase { private: typedef typename _Graph::template EdgeMap<_Value> MapImpl; @@ -873,11 +1031,11 @@ typedef _Value Value; typedef Edge Key; - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : - forward_map(*(_g.graph)), backward_map(*(_g.graph)) {} + EdgeMapBase(const Adaptor& adaptor) : + forward_map(*adaptor.graph), backward_map(*adaptor.graph) {} - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) - : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {} + EdgeMapBase(const Adaptor& adaptor, const Value& v) + : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {} void set(const Edge& e, const Value& a) { if (Parent::direction(e)) { @@ -908,19 +1066,55 @@ MapImpl forward_map, backward_map; }; + + public: + + template + class EdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + EdgeMap(const Graph& graph) + : Parent(graph) {} + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; template - class UEdgeMap : public _Graph::template EdgeMap<_Value> { + class UEdgeMap : public Graph::template EdgeMap<_Value> { public: + + typedef typename Graph::template EdgeMap<_Value> Parent; + + explicit UEdgeMap(const Adaptor& ga) + : Parent(*ga.graph) {} - typedef typename _Graph::template EdgeMap<_Value> Parent; + UEdgeMap(const Adaptor& ga, const _Value& value) + : Parent(*ga.graph, value) {} - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) - : Parent(*(g.graph)) {} + UEdgeMap& operator=(const UEdgeMap& cmap) { + return operator=(cmap); + } - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) - : Parent(*(g.graph), a) {} - + template + UEdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; }; @@ -933,6 +1127,7 @@ public: typedef _Graph Graph; + typedef UndirGraphAdaptorBase Adaptor; typedef UGraphBaseExtender > Parent; protected: @@ -1033,11 +1228,10 @@ mutable EdgeNotifier edge_notifier; NotifierProxy edge_notifier_proxy; - public: - + private: template - class EdgeMap { + class EdgeMapBase { private: typedef typename _Graph::template EdgeMap<_Value> MapImpl; @@ -1049,11 +1243,11 @@ typedef _Value Value; typedef Edge Key; - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : - forward_map(*(_g.graph)), backward_map(*(_g.graph)) {} + EdgeMapBase(const Adaptor& adaptor) : + forward_map(*adaptor.graph), backward_map(*adaptor.graph) {} - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a) - : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {} + EdgeMapBase(const Adaptor& adaptor, const Value& v) + : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {} void set(const Edge& e, const Value& a) { if (Parent::direction(e)) { @@ -1063,8 +1257,7 @@ } } - typename MapTraits::ConstReturnValue - operator[](const Edge& e) const { + typename MapTraits::ConstReturnValue operator[](Edge e) const { if (Parent::direction(e)) { return forward_map[e]; } else { @@ -1072,8 +1265,7 @@ } } - typename MapTraits::ReturnValue - operator[](const Edge& e) { + typename MapTraits::ReturnValue operator[](Edge e) { if (Parent::direction(e)) { return forward_map[e]; } else { @@ -1086,19 +1278,55 @@ MapImpl forward_map, backward_map; }; + + public: + + template + class EdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + EdgeMap(const Graph& graph) + : Parent(graph) {} + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; template - class UEdgeMap : public _Graph::template EdgeMap<_Value> { + class UEdgeMap : public Graph::template EdgeMap<_Value> { public: + + typedef typename Graph::template EdgeMap<_Value> Parent; + + explicit UEdgeMap(const Adaptor& ga) + : Parent(*ga.graph) {} - typedef typename _Graph::template EdgeMap<_Value> Parent; + UEdgeMap(const Adaptor& ga, const _Value& value) + : Parent(*ga.graph, value) {} - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) - : Parent(*(g.graph)) {} + UEdgeMap& operator=(const UEdgeMap& cmap) { + return operator=(cmap); + } - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a) - : Parent(*(g.graph), a) {} - + template + UEdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; }; diff -r d769d2eb4d50 -r 080d51024ac5 lemon/graph_utils.h --- a/lemon/graph_utils.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/graph_utils.h Mon Apr 03 09:45:23 2006 +0000 @@ -48,8 +48,7 @@ ///This \c \#define creates convenience typedefs for the following types ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt, - ///\c OutEdgeIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, - ///\c BoolEdgeMap, \c IntEdgeMap, \c DoubleEdgeMap. + ///\c OutEdgeIt ///\note If \c G it a template parameter, it should be used in this way. ///\code /// GRAPH_TYPEDEFS(typename G) @@ -64,19 +63,12 @@ typedef Graph:: EdgeIt EdgeIt; \ typedef Graph:: InEdgeIt InEdgeIt; \ typedef Graph::OutEdgeIt OutEdgeIt; -// typedef Graph::template NodeMap BoolNodeMap; -// typedef Graph::template NodeMap IntNodeMap; -// typedef Graph::template NodeMap DoubleNodeMap; -// typedef Graph::template EdgeMap BoolEdgeMap; -// typedef Graph::template EdgeMap IntEdgeMap; -// typedef Graph::template EdgeMap DoubleEdgeMap; - + ///Creates convenience typedefs for the undirected graph types and iterators ///This \c \#define creates the same convenience typedefs as defined by ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates ///\c UEdge, \c UEdgeIt, \c IncEdgeIt, - ///\c BoolUEdgeMap, \c IntUEdgeMap, \c DoubleUEdgeMap. /// ///\note If \c G it a template parameter, it should be used in this way. ///\code @@ -93,8 +85,25 @@ // typedef Graph::template UEdgeMap BoolUEdgeMap; // typedef Graph::template UEdgeMap IntUEdgeMap; // typedef Graph::template UEdgeMap DoubleUEdgeMap; - + ///\brief Creates convenience typedefs for the bipartite undirected graph + ///types and iterators + + ///This \c \#define creates the same convenience typedefs as defined by + ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates + ///\c ANodeIt, \c BNodeIt, + /// + ///\note If \c G it a template parameter, it should be used in this way. + ///\code + /// BPUGRAPH_TYPEDEFS(typename G) + ///\endcode + /// + ///\warning There are no typedefs for the graph maps because of the lack of + ///template typedefs in C++. +#define BPUGRAPH_TYPEDEFS(Graph) \ + UGRAPH_TYPEDEFS(Graph) \ + typedef Graph::ANodeIt ANodeIt; \ + typedef Graph::BNodeIt BNodeIt; /// \brief Function to count the items in the graph. /// @@ -430,7 +439,7 @@ bool b; if (u != v) { if (e == INVALID) { - g.firstInc(e, u, b); + g.firstInc(e, b, u); } else { b = g.source(e) == u; g.nextInc(e, b); @@ -440,7 +449,7 @@ } } else { if (e == INVALID) { - g.firstInc(e, u, b); + g.firstInc(e, b, u); } else { b = true; g.nextInc(e, b); @@ -485,11 +494,11 @@ /// } ///\endcode template - inline typename Graph::UEdge findEdge(const Graph &g, - typename Graph::Node u, - typename Graph::Node v, - typename Graph::UEdge prev = INVALID) { - return _graph_utils_bits::FindUEdgeSelector::find(g, u, v, prev); + inline typename Graph::UEdge findUEdge(const Graph &g, + typename Graph::Node u, + typename Graph::Node v, + typename Graph::UEdge p = INVALID) { + return _graph_utils_bits::FindUEdgeSelector::find(g, u, v, p); } /// \brief Iterator for iterating on uedges connected the same nodes. diff -r d769d2eb4d50 -r 080d51024ac5 lemon/iterable_maps.h --- a/lemon/iterable_maps.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/iterable_maps.h Mon Apr 03 09:45:23 2006 +0000 @@ -20,6 +20,7 @@ #include #include +#include #include #include @@ -400,12 +401,11 @@ /// \param _Item One of the graph's item type, the key of the map. template class IterableIntMap - : protected DefaultMap<_Graph, _Item, _iterable_maps_bits:: - IterableIntMapNode<_Item> > { + : protected MapExtender > >{ public: - typedef DefaultMap<_Graph, _Item, _iterable_maps_bits:: - IterableIntMapNode<_Item> > - Parent; + typedef MapExtender > > Parent; /// The key type typedef _Item Key; @@ -689,11 +689,12 @@ /// \param _Value Any comparable value type. template class IterableValueMap - : protected DefaultMap<_Graph, _Item, _iterable_maps_bits:: - IterableValueMapNode<_Item, _Value> > { + : protected MapExtender > >{ public: - typedef DefaultMap<_Graph, _Item, _iterable_maps_bits:: - IterableValueMapNode<_Item, _Value> > Parent; + typedef MapExtender > > + Parent; /// The key type typedef _Item Key; @@ -702,10 +703,6 @@ /// The graph type typedef _Graph Graph; - protected: - - typedef typename ItemSetTraits<_Graph, Key>::ItemIt KeyIt; - public: /// \brief Constructor of the Map with a given value. @@ -715,7 +712,7 @@ const Value& value = Value()) : Parent(graph, _iterable_maps_bits:: IterableValueMapNode<_Item, _Value>(value)) { - for (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) { + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { lace(it); } } @@ -903,7 +900,7 @@ virtual void build() { Parent::build(); - for (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) { + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { lace(it); } } diff -r d769d2eb4d50 -r 080d51024ac5 lemon/list_graph.h --- a/lemon/list_graph.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/list_graph.h Mon Apr 03 09:45:23 2006 +0000 @@ -66,7 +66,7 @@ protected: int id; - Node(int pid) { id = pid;} + explicit Node(int pid) { id = pid;} public: Node() {} @@ -81,7 +81,7 @@ protected: int id; - Edge(int pid) { id = pid;} + explicit Edge(int pid) { id = pid;} public: Edge() {} @@ -110,8 +110,8 @@ ///\sa id(Edge) int maxEdgeId() const { return edges.size()-1; } - Node source(Edge e) const { return edges[e.id].source; } - Node target(Edge e) const { return edges[e.id].target; } + Node source(Edge e) const { return Node(edges[e.id].source); } + Node target(Edge e) const { return Node(edges[e.id].target); } void first(Node& node) const { @@ -676,7 +676,7 @@ protected: int id; - Node(int _id) : id(_id) {} + explicit Node(int _id) : id(_id) {} public: Node() {} Node(Invalid) { id = -1; } @@ -690,7 +690,7 @@ protected: int id; - Edge(int _id) { id = _id;} + explicit Edge(int _id) { id = _id;} public: Edge() {} Edge (Invalid) { id = -1; } diff -r d769d2eb4d50 -r 080d51024ac5 lemon/smart_graph.h --- a/lemon/smart_graph.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/smart_graph.h Mon Apr 03 09:45:23 2006 +0000 @@ -575,6 +575,14 @@ edges.clear(); } + typedef True NodeNumTag; + int nodeNum() const { return aNodes.size() + bNodes.size(); } + int aNodeNum() const { return aNodes.size(); } + int bNodeNum() const { return bNodes.size(); } + + typedef True EdgeNumTag; + int edgeNum() const { return edges.size(); } + }; diff -r d769d2eb4d50 -r 080d51024ac5 lemon/ugraph_adaptor.h --- a/lemon/ugraph_adaptor.h Mon Apr 03 09:24:38 2006 +0000 +++ b/lemon/ugraph_adaptor.h Mon Apr 03 09:45:23 2006 +0000 @@ -101,6 +101,7 @@ typedef EdgeNumTagIndicator EdgeNumTag; int edgeNum() const { return graph->edgeNum(); } + int uEdgeNum() const { return graph->uEdgeNum(); } typedef FindEdgeTagIndicator FindEdgeTag; Edge findEdge(const Node& source, const Node& target, @@ -118,15 +119,28 @@ } void erase(const Node& i) const { graph->erase(i); } - void erase(const Edge& i) const { graph->erase(i); } + void erase(const UEdge& i) const { graph->erase(i); } void clear() const { graph->clear(); } + bool direction(const Edge& e) const { return graph->direction(e); } + Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); } + int id(const Node& v) const { return graph->id(v); } + int id(const Edge& e) const { return graph->id(e); } int id(const UEdge& e) const { return graph->id(e); } - bool direction(const Edge& e) const { return graph->direction(e); } - Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); } + Node fromNodeId(int id) const { + return graph->fromNodeId(id); + } + + Edge fromEdgeId(int id) const { + return graph->fromEdgeId(id); + } + + UEdge fromUEdgeId(int id) const { + return graph->fromUEdgeId(id); + } int maxNodeId() const { return graph->maxNodeId(); @@ -173,14 +187,10 @@ template NodeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - Node it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } - return *this; + Parent::operator=(cmap); + return *this; } + }; template @@ -198,12 +208,7 @@ template EdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - Edge it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } + Parent::operator=(cmap); return *this; } }; @@ -223,13 +228,8 @@ template UEdgeMap& operator=(const CMap& cmap) { - checkConcept, CMap>(); - const typename Parent::Graph* graph = Parent::getGraph(); - UEdge it; - for (graph->first(it); it != INVALID; graph->next(it)) { - Parent::set(it, cmap[it]); - } - return *this; + Parent::operator=(cmap); + return *this; } }; @@ -254,6 +254,7 @@ class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> { public: typedef _UGraph Graph; + typedef SubUGraphAdaptorBase Adaptor; typedef UGraphAdaptorBase<_UGraph> Parent; protected: @@ -416,6 +417,85 @@ } return uedge; } + + template + class NodeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + NodeMap(const Graph& graph) + : Parent(graph) {} + NodeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class EdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + EdgeMap(const Graph& graph) + : Parent(graph) {} + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class UEdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + UEdgeMap(const Graph& graph) + : Parent(graph) {} + UEdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + UEdgeMap& operator=(const UEdgeMap& cmap) { + return operator=(cmap); + } + + template + UEdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + }; template @@ -423,6 +503,7 @@ : public UGraphAdaptorBase<_UGraph> { public: typedef _UGraph Graph; + typedef SubUGraphAdaptorBase Adaptor; typedef UGraphAdaptorBase<_UGraph> Parent; protected: NodeFilterMap* node_filter_map; @@ -559,6 +640,84 @@ } return uedge; } + + template + class NodeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + NodeMap(const Graph& graph) + : Parent(graph) {} + NodeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class EdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + EdgeMap(const Graph& graph) + : Parent(graph) {} + EdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; + + template + class UEdgeMap + : public SubMapExtender > + { + public: + typedef Adaptor Graph; + typedef SubMapExtender > Parent; + + UEdgeMap(const Graph& graph) + : Parent(graph) {} + UEdgeMap(const Graph& graph, const _Value& value) + : Parent(graph, value) {} + + UEdgeMap& operator=(const UEdgeMap& cmap) { + return operator=(cmap); + } + + template + UEdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; }; /// \ingroup graph_adaptors @@ -678,7 +837,6 @@ return NodeSubUGraphAdaptor(graph, nfm); } - /// \brief An adaptor for hiding undirected edges from an undirected graph. /// /// \warning Graph adaptors are in even more experimental state @@ -704,12 +862,14 @@ } public: + EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : Parent(), const_true_map(true) { Parent::setGraph(_graph); Parent::setNodeFilterMap(const_true_map); Parent::setUEdgeFilterMap(_uedge_filter_map); } + }; template @@ -837,21 +997,48 @@ template class NodeMap : public _UGraph::template NodeMap<_Value> { public: + typedef typename _UGraph::template NodeMap<_Value> Parent; + explicit NodeMap(const DirUGraphAdaptorBase& ga) - : Parent(*ga.graph) { } + : Parent(*ga.graph) {} + NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value) - : Parent(*ga.graph, value) { } + : Parent(*ga.graph, value) {} + + NodeMap& operator=(const NodeMap& cmap) { + return operator=(cmap); + } + + template + NodeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } + }; template class EdgeMap : public _UGraph::template UEdgeMap<_Value> { public: + typedef typename _UGraph::template UEdgeMap<_Value> Parent; + explicit EdgeMap(const DirUGraphAdaptorBase& ga) : Parent(*ga.graph) { } + EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value) : Parent(*ga.graph, value) { } + + EdgeMap& operator=(const EdgeMap& cmap) { + return operator=(cmap); + } + + template + EdgeMap& operator=(const CMap& cmap) { + Parent::operator=(cmap); + return *this; + } };