diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/bits/undir_graph_extender.h --- a/src/lemon/bits/undir_graph_extender.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,278 +0,0 @@ -/* -*- C++ -*- - * - * src/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