COIN-OR::LEMON - Graph Library

Changeset 1030:c8a41699e613 in lemon-0.x for src/lemon


Ignore:
Timestamp:
12/06/04 01:30:44 (19 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1420
Message:

Undirected graph documentation and concept refinements.

  • quite a few bug fixes
  • concept::UndirGraph? is almost complete and looks quite good.
Location:
src/lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/concept/graph.h

    r989 r1030  
    1818#define LEMON_CONCEPT_GRAPH_H
    1919
    20 ///\ingroup concept
     20///\ingroup graph_concepts
    2121///\file
    2222///\brief Declaration of Graph.
     
    3030  namespace concept {
    3131   
    32     /// \addtogroup concept
     32    /// \addtogroup graph_concepts
    3333    /// @{
    3434
  • src/lemon/concept/graph_component.h

    r1022 r1030  
    1515 */
    1616
    17 ///\ingroup concept
     17///\ingroup graph_concepts
    1818///\file
    1919///\brief The graph components.
     
    2929  namespace concept {
    3030
     31    /// \addtogroup graph_concepts
     32    /// @{
    3133
    3234    /****************   Graph iterator concepts   ****************/
    3335
    34     /// Skeleton class for graph Node and Edge
    35 
    36     /// \note Because Node and Edge are forbidden to inherit from the same
    37     /// base class, this is a template. For Node you should instantiate it
    38     /// with character 'n' and for Edge with 'e'.
    39 
    40     template<char _selector>
     36    /// Skeleton class for graph Node and Edge types
     37
     38    /// This class describes the interface of Node and Edge (and UndirEdge
     39    /// in undirected graphs) subtypes of graph types.
     40    ///
     41    /// \note This class is a template class so that we can use it to
     42    /// create graph skeleton classes. The reason for this is than Node
     43    /// and Edge types should \em not derive from the same base class.
     44    /// For Node you should instantiate it with character 'n' and for Edge
     45    /// with 'e'.
     46
     47#ifndef DOXYGEN
     48    template <char _selector = '0'>
     49#endif
    4150    class GraphItem {
    4251    public:
    4352      /// Default constructor.
    4453     
    45       /// @warning The default constructor sets the item
    46       /// to an undefined value.
     54      /// \warning The default constructor is not required to set
     55      /// the item to some well-defined value. So you should consider it
     56      /// as uninitialized.
    4757      GraphItem() {}
    4858      /// Copy constructor.
     
    7282      bool operator!=(GraphItem) const { return false; }
    7383
    74       // Technical requirement. Do we really need this?
    75       //      bool operator<(GraphItem) const { return false; }
    76 
     84      /// Artificial ordering operator.
     85
     86      /// To allow the use of graph descriptors as key type in std::map or
     87      /// similar associative container we require this.
     88      ///
     89      /// \note This operator only have to define some strict ordering of
     90      /// the items; this order has nothing to do with the iteration
     91      /// ordering of the items.
     92      ///
     93      /// \bug This is a technical requirement. Do we really need this?
     94      bool operator<(GraphItem) const { return false; }
    7795
    7896      template<typename _GraphItem>
     
    89107          b = (ia == ib) && (ia != ib);
    90108          b = (ia == INVALID) && (ib != INVALID);
     109          b = (ia < ib);
    91110        }
    92111
     
    95114      };
    96115    };
     116
     117    /// A type describing the concept of graph node
     118
     119    /// This is an instantiation of \ref GraphItem which can be used as a
     120    /// Node subtype in graph skeleton definitions
     121    typedef GraphItem<'n'> GraphNode;
     122
     123    /// A type describing the concept of graph edge
     124
     125    /// This is an instantiation of \ref GraphItem which can be used as a
     126    /// Edge subtype in graph skeleton definitions
     127    typedef GraphItem<'e'> GraphEdge;
     128
     129
     130    /**************** Basic features of graphs ****************/
    97131
    98132    /// An empty base graph class.
     
    630664
    631665
     666    /// Class describing the concept of graph maps
     667
     668    /// This class describes the common interface of the graph maps
     669    /// (NodeMap, EdgeMap), that is \ref maps "maps" which can be used to
     670    /// associate data to graph descriptors (nodes or edges).
    632671    template <typename Graph, typename Item, typename _Value>
    633672    class GraphMap : public ReadWriteMap<Item, _Value> {
     
    805844    };
    806845
     846    /// @}
     847
    807848  }
    808849
  • src/lemon/concept/undir_graph.h

    r1022 r1030  
    1818 */
    1919
    20 ///\ingroup concept
     20///\ingroup graph_concepts
    2121///\file
    2222///\brief Undirected graphs and components of.
     
    3131  namespace concept {
    3232
    33     /// \todo to be done
     33    /// \addtogroup graph_concepts
     34    /// @{
     35
     36
     37    /// Skeleton class which describes an edge with direction in \ref
     38    /// UndirGraph "undirected graph".
     39    template <typename UndirEdge>
     40    class UndirGraphEdge : public UndirEdge {
     41    public:
     42
     43      /// \e
     44      UndirGraphEdge() {}
     45
     46      /// \e
     47      UndirGraphEdge(const UndirGraphEdge&) {}
     48
     49      /// \e
     50      UndirGraphEdge(Invalid) {}
     51
     52      /// \brief Constructs a directed version of an undirected edge
     53      ///
     54      /// \param forward If \c true the direction of the contructed edge
     55      /// is the same as the inherent direction of the \c undir_edge; if
     56      /// \c false --- the opposite.
     57      UndirGraphEdge(UndirEdge undir_edge, bool forward) {
     58        ignore_unused_variable_warning(undir_edge);
     59        ignore_unused_variable_warning(forward);
     60      }
     61
     62      /// \e
     63      UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
     64
     65      /// \e
     66      bool operator==(UndirGraphEdge) const { return true; }
     67      /// \e
     68      bool operator!=(UndirGraphEdge) const { return false; }
     69
     70      /// \e
     71      bool operator<(UndirGraphEdge) const { return false; }
     72
     73      template <typename Edge>
     74      struct Constraints {
     75        void constraints() {
     76          /// \bug This should be is_base_and_derived ...
     77          UndirEdge ue = e;
     78          ue = e;
     79          Edge forward(ue, true);
     80          Edge backward(ue, false);
     81
     82          ignore_unused_variable_warning(forward);
     83          ignore_unused_variable_warning(backward);
     84        }
     85        Edge e;
     86      };
     87    };
     88   
    3489
    3590    struct BaseIterableUndirGraphConcept {
     
    4499        void constraints() {
    45100          checkConcept<BaseIterableGraphComponent, Graph>();
    46           checkConcept<GraphItem<'u'>, UndirEdge >();
    47 
    48           /// \bug this should be base_and_derived:
    49           UndirEdge ue = e;
    50           ue = e;
    51 
     101          checkConcept<GraphItem<>, UndirEdge>();
     102          checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
     103
     104          graph.first(ue);
     105          graph.next(ue);
     106
     107          const_constraints();
     108        }
     109        void const_constraints() {
    52110          Node n;
    53111          n = graph.target(ue);
    54112          n = graph.source(ue);
    55 
    56           graph.first(ue);
    57           graph.next(ue);
    58         }
    59         const Graph &graph;
     113          n = graph.oppositeNode(n0, ue);
     114
     115          bool b;
     116          b = graph.forward(e);
     117          ignore_unused_variable_warning(b);
     118        }
     119
     120        Graph graph;
    60121        Edge e;
     122        Node n0;
     123        UndirEdge ue;
    61124      };
    62125
     
    77140          typedef typename Graph::UndirEdge UndirEdge;
    78141          typedef typename Graph::UndirEdgeIt UndirEdgeIt;
    79           typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
     142          typedef typename Graph::IncEdgeIt IncEdgeIt;
    80143
    81144          checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
    82           checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
     145          checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
    83146        }
    84147      };
     
    146209    };
    147210
     211    /// Class describing the concept of Undirected Graphs.
     212
     213    /// This class describes the common interface of all Undirected
     214    /// Graphs.
     215    ///
     216    /// As all concept describing classes it provides only interface
     217    /// without any sensible implementation. So any algorithm for
     218    /// undirected graph should compile with this class, but it will not
     219    /// run properly, of couse.
     220    ///
     221    /// In LEMON undirected graphs also fulfill the concept of directed
     222    /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
     223    /// explanation of this and more see also the page \ref undir_graphs,
     224    /// a tutorial about undirected graphs.
     225
    148226    class UndirGraph {
    149227    public:
     228
     229      /// Type describing a node in the graph
     230      typedef GraphNode Node;
     231
     232      /// Type describing an undirected edge
     233      typedef GraphItem<'u'> UndirEdge;
     234
     235      /// Type describing an UndirEdge with direction
     236#ifndef DOXYGEN
     237      typedef UndirGraphEdge<UndirEdge> Edge;
     238#else
     239      typedef UndirGraphEdge Edge;
     240#endif
     241
     242      /// Iterator type which iterates over all nodes
     243#ifndef DOXYGEN
     244      typedef GraphIterator<UndirGraph, Node> NodeIt;
     245#else
     246      typedef GraphIterator NodeIt;
     247#endif
     248
     249      /// Iterator type which iterates over all undirected edges
     250#ifndef DOXYGEN
     251      typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
     252#else
     253      typedef GraphIterator UndirEdgeIt;
     254#endif
     255
     256      /// Iterator type which iterates over all directed edges.
     257
     258      /// Iterator type which iterates over all edges (each undirected
     259      /// edge occurs twice with both directions.
     260#ifndef DOXYGEN
     261      typedef GraphIterator<UndirGraph, Edge> EdgeIt;
     262#else
     263      typedef GraphIterator EdgeIt;
     264#endif
     265
     266
     267      /// Iterator of undirected edges incident to a node
     268#ifndef DOXYGEN
     269      typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
     270#else
     271      typedef GraphIncIterator IncEdgeIt;
     272#endif
     273
     274      /// Iterator of edges incoming to a node
     275#ifndef DOXYGEN
     276      typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
     277#else
     278      typedef GraphIncIterator InEdgeIt;
     279#endif
     280
     281      /// Iterator of edges outgoing from a node
     282#ifndef DOXYGEN
     283      typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
     284#else
     285      typedef GraphIncIterator OutEdgeIt;
     286#endif
     287
     288      /// NodeMap template
     289#ifdef DOXYGEN
     290      typedef GraphMap NodeMap<T>;
     291#endif
     292
     293      /// UndirEdgeMap template
     294#ifdef DOXYGEN
     295      typedef GraphMap UndirEdgeMap<T>;
     296#endif
     297
     298      /// EdgeMap template
     299#ifdef DOXYGEN
     300      typedef GraphMap EdgeMap<T>;
     301#endif
     302
     303      template <typename T>
     304      class NodeMap : public GraphMap<UndirGraph, Node, T> {
     305        typedef GraphMap<UndirGraph, Node, T> Parent;
     306      public:
     307
     308        explicit NodeMap(const UndirGraph &g) : Parent(g) {}
     309        NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
     310      };
     311
     312      template <typename T>
     313      class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
     314        typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
     315      public:
     316
     317        explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
     318        UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
     319      };
     320
     321      template <typename T>
     322      class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
     323        typedef GraphMap<UndirGraph, Edge, T> Parent;
     324      public:
     325
     326        explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
     327        EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
     328      };
     329
     330      /// Is the Edge oriented "forward"?
     331
     332      /// Returns whether the given directed edge is same orientation as
     333      /// the corresponding undirected edge.
     334      ///
     335      /// \todo "What does the direction of an undirected edge mean?"
     336      bool forward(Edge) const { return true; }
     337
     338      /// Opposite node on an edge
     339
     340      /// \return the opposite of the given Node on the given Edge
     341      ///
     342      /// \todo What should we do if given Node and Edge are not incident?
     343      Node oppositeNode(Node, UndirEdge) const { return INVALID; }
     344
     345      /// First node of the undirected edge.
     346
     347      /// \return the first node of the given UndirEdge.
     348      ///
     349      /// Naturally undirectected edges don't have direction and thus
     350      /// don't have source and target node. But we use these two methods
     351      /// to query the two endnodes of the edge. The direction of the edge
     352      /// which arises this way is called the inherent direction of the
     353      /// undirected edge, and is used to define the "forward" direction
     354      /// of the directed versions of the edges.
     355      /// \sa forward
     356      Node source(UndirEdge) const { return INVALID; }
     357
     358      /// Second node of the undirected edge.
     359      Node target(UndirEdge) const { return INVALID; }
     360
     361      /// Source node of the directed edge.
     362      Node source(Edge) const { return INVALID; }
     363
     364      /// Target node of the directed edge.
     365      Node target(Edge) const { return INVALID; }
     366
     367      /// First node of the graph
     368
     369      /// \note This method is part of so called \ref
     370      /// developpers_interface "Developpers' interface", so it shouldn't
     371      /// be used in an end-user program.
     372      void first(Node&) const {}
     373      /// Next node of the graph
     374
     375      /// \note This method is part of so called \ref
     376      /// developpers_interface "Developpers' interface", so it shouldn't
     377      /// be used in an end-user program.
     378      void next(Node&) const {}
     379
     380      /// First undirected edge of the graph
     381
     382      /// \note This method is part of so called \ref
     383      /// developpers_interface "Developpers' interface", so it shouldn't
     384      /// be used in an end-user program.
     385      void first(UndirEdge&) const {}
     386      /// Next undirected edge of the graph
     387
     388      /// \note This method is part of so called \ref
     389      /// developpers_interface "Developpers' interface", so it shouldn't
     390      /// be used in an end-user program.
     391      void next(UndirEdge&) const {}
     392
     393      /// First directed edge of the graph
     394
     395      /// \note This method is part of so called \ref
     396      /// developpers_interface "Developpers' interface", so it shouldn't
     397      /// be used in an end-user program.
     398      void first(Edge&) const {}
     399      /// Next directed edge of the graph
     400
     401      /// \note This method is part of so called \ref
     402      /// developpers_interface "Developpers' interface", so it shouldn't
     403      /// be used in an end-user program.
     404      void next(Edge&) const {}
     405
     406      /// First outgoing edge from a given node
     407
     408      /// \note This method is part of so called \ref
     409      /// developpers_interface "Developpers' interface", so it shouldn't
     410      /// be used in an end-user program.
     411      void firstOut(Edge&, Node) const {}
     412      /// Next outgoing edge to a node
     413
     414      /// \note This method is part of so called \ref
     415      /// developpers_interface "Developpers' interface", so it shouldn't
     416      /// be used in an end-user program.
     417      void nextOut(Edge&) const {}
     418
     419      /// First incoming edge to a given node
     420
     421      /// \note This method is part of so called \ref
     422      /// developpers_interface "Developpers' interface", so it shouldn't
     423      /// be used in an end-user program.
     424      void firstIn(Edge&, Node) const {}
     425      /// Next incoming edge to a node
     426
     427      /// \note This method is part of so called \ref
     428      /// developpers_interface "Developpers' interface", so it shouldn't
     429      /// be used in an end-user program.
     430      void nextIn(Edge&) const {}
     431
    150432
    151433      template <typename Graph>
     
    191473    };
    192474
     475    /// @}
     476
    193477  }
    194478
  • src/lemon/iterable_graph_extender.h

    r1022 r1030  
    158158    };
    159159
    160     class UndirIncEdgeIt : public UndirEdge {
     160    class IncEdgeIt : public UndirEdge {
    161161      const Graph* graph;
    162162      bool forward;
     
    166166    public:
    167167
    168       UndirIncEdgeIt() { }
    169 
    170       UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    171 
    172       explicit UndirIncEdgeIt(const Graph& _graph, const Node &n)
     168      IncEdgeIt() { }
     169
     170      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
     171
     172      explicit IncEdgeIt(const Graph& _graph, const Node &n)
    173173        : graph(&_graph)
    174174      {
     
    177177
    178178      // FIXME: Do we need this type of constructor here?
    179       // UndirIncEdgeIt(const Graph& _graph, const Edge& e) :
     179      // IncEdgeIt(const Graph& _graph, const Edge& e) :
    180180      //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
    181181      // or
    182       // UndirIncEdgeIt(const Graph& _graph, const Node& n,
     182      // IncEdgeIt(const Graph& _graph, const Node& n,
    183183      //    Const UndirEdge &e) ... ?
    184184
    185       UndirIncEdgeIt& operator++() {
     185      IncEdgeIt& operator++() {
    186186        graph->_dirNextOut(*this);
    187187        return *this;
     
    189189    };
    190190
    191     Node source(const UndirIncEdgeIt &e) const {
     191    Node source(const IncEdgeIt &e) const {
    192192      return _dirSource(e);
    193193    }
     
    198198
    199199    /// Target of the given Edge.
    200     Node target(const UndirIncEdgeIt &e) const {
     200    Node target(const IncEdgeIt &e) const {
    201201      return _dirTarget(e);
    202202    }
  • src/lemon/undir_graph_extender.h

    r1021 r1030  
    109109    bool forward(const Edge &e) const { return e.forward; }
    110110
    111     Node oppsiteNode(const Node &n, const Edge &e) const {
     111    Node oppositeNode(const Node &n, const UndirEdge &e) const {
    112112      if( n == Parent::source(e))
    113113        return Parent::target(e);
Note: See TracChangeset for help on using the changeset viewer.