/* -*- C++ -*- * * lemon/undir_graph_extender.h - Part of LEMON, a generic C++ * optimization library * * Copyright (C) 2005 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_UNDIR_GRAPH_EXTENDER_H #define LEMON_UNDIR_GRAPH_EXTENDER_H #include namespace lemon { template class UndirGraphExtender : public _Base { typedef _Base Parent; typedef UndirGraphExtender Graph; public: typedef typename Parent::Edge UndirEdge; typedef typename Parent::Node Node; class Edge : public UndirEdge { friend class UndirGraphExtender; protected: // FIXME: Marci use opposite logic in his graph adaptors. It would // be reasonable to syncronize... bool forward; public: Edge() {} /// \brief Directed edge from undirected edge and a direction. /// /// This constructor is not a part of the concept interface of /// undirected graph, so please avoid using it if possible! Edge(const UndirEdge &ue, bool _forward) : UndirEdge(ue), forward(_forward) {} /// \brief Directed edge from undirected edge and a source node. /// /// Constructs a directed edge from undirected edge and a source node. /// /// \note You have to specify the graph for this constructor. Edge(const Graph &g, const UndirEdge &ue, const Node &n) : UndirEdge(ue) { forward = (g.source(ue) == n); } /// Invalid edge constructor Edge(Invalid i) : UndirEdge(i), forward(true) {} bool operator==(const Edge &that) const { return forward==that.forward && UndirEdge(*this)==UndirEdge(that); } bool operator!=(const Edge &that) const { return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that); } bool operator<(const Edge &that) const { return forward Node _dirSource(const E &e) const { return e.forward ? Parent::source(e) : Parent::target(e); } template Node _dirTarget(const E &e) const { return e.forward ? Parent::target(e) : Parent::source(e); } public: /// \todo Shouldn't the "source" of an undirected edge be called "aNode" /// or something??? using Parent::source; /// Source of the given Edge. Node source(const Edge &e) const { return _dirSource(e); } /// \todo Shouldn't the "target" of an undirected edge be called "bNode" /// or something??? using Parent::target; /// Target of the given Edge. Node target(const Edge &e) const { return _dirTarget(e); } /// Returns whether the given directed edge is same orientation as the /// corresponding undirected edge. /// /// \todo reference to the corresponding point of the undirected graph /// concept. "What does the direction of an undirected edge mean?" bool forward(const Edge &e) const { return e.forward; } Node oppositeNode(const Node &n, const UndirEdge &e) const { if( n == Parent::source(e)) return Parent::target(e); else if( n == Parent::target(e)) return Parent::source(e); else return INVALID; } /// Directed edge from an undirected edge and a source node. /// /// Returns a (directed) Edge corresponding to the specified UndirEdge /// and source Node. /// ///\todo Do we need this? /// ///\todo Better name... Edge edgeWithSource(const UndirEdge &ue, const Node &s) const { return Edge(*this, ue, s); } using Parent::first; void first(Edge &e) const { Parent::first(e); e.forward=true; } using Parent::next; void next(Edge &e) const { if( e.forward ) { e.forward = false; } else { Parent::next(e); e.forward = true; } } protected: template void _dirFirstOut(E &e, const Node &n) const { Parent::firstIn(e,n); if( UndirEdge(e) != INVALID ) { e.forward = false; } else { Parent::firstOut(e,n); e.forward = true; } } template void _dirFirstIn(E &e, const Node &n) const { Parent::firstOut(e,n); if( UndirEdge(e) != INVALID ) { e.forward = false; } else { Parent::firstIn(e,n); e.forward = true; } } template void _dirNextOut(E &e) const { if( ! e.forward ) { Node n = Parent::target(e); Parent::nextIn(e); if( UndirEdge(e) == INVALID ) { Parent::firstOut(e, n); e.forward = true; } } else { Parent::nextOut(e); } } template void _dirNextIn(E &e) const { if( ! e.forward ) { Node n = Parent::source(e); Parent::nextOut(e); if( UndirEdge(e) == INVALID ) { Parent::firstIn(e, n); e.forward = true; } } else { Parent::nextIn(e); } } public: void firstOut(Edge &e, const Node &n) const { _dirFirstOut(e, n); } void firstIn(Edge &e, const Node &n) const { _dirFirstIn(e, n); } void nextOut(Edge &e) const { _dirNextOut(e); } void nextIn(Edge &e) const { _dirNextIn(e); } // Miscellaneous stuff: /// \todo these methods (id, maxEdgeId) should be moved into separate /// Extender // using Parent::id; // Using "using" is not a good idea, cause it could be that there is // no "id" in Parent... int id(const Node &n) const { return Parent::id(n); } int id(const UndirEdge &e) const { return Parent::id(e); } int id(const Edge &e) const { return 2 * Parent::id(e) + int(e.forward); } int maxId(Node) const { return Parent::maxId(Node()); } int maxId(Edge) const { return 2 * Parent::maxId(typename Parent::Edge()) + 1; } int maxId(UndirEdge) const { return Parent::maxId(typename Parent::Edge()); } int edgeNum() const { return 2 * Parent::edgeNum(); } int undirEdgeNum() const { return Parent::edgeNum(); } }; } #endif // LEMON_UNDIR_GRAPH_EXTENDER_H