COIN-OR::LEMON - Graph Library

Changeset 1030:c8a41699e613 in lemon-0.x


Ignore:
Timestamp:
12/06/04 01:30:44 (15 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.
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed
  • doc/Doxyfile

    r991 r1030  
    426426INPUT                  = mainpage.dox \
    427427                         graphs.dox \
     428                         undir_graphs.dox \
    428429                         named-param.dox \
    429430                         maps.dox \
     
    432433                         namespaces.dox \
    433434                         license.dox \
     435                         developpers_interface.dox \
    434436                         ../src/lemon \
    435437                         ../src/lemon/concept \
  • doc/groups.dox

    r959 r1030  
    8181
    8282/**
    83 @defgroup concept Concept
     83@defgroup concept Concepts
    8484\brief Skeleton classes and concept checking classes
    8585
    8686This group describes the data/algorithm skeletons and concept checking
    87 classes implemented in LEMON. These classes exist in order to make it
    88 easier to check if a certain template class or template function is
    89 correctly implemented.
     87classes implemented in LEMON.
     88
     89One aim of these classes is to make it easier to check if a certain
     90class or template function is correctly implemented.
     91
     92The other (sometimes even more important) aim is to document the concepts.
     93
    9094*/
    9195
     96/**
     97@defgroup graph_concepts Graph Structure Concepts
     98@ingroup concept
     99\brief Skeleton and concept checking classes for graph structures
     100
     101This group contains the skeletons and concept checking classes of LEMON's
     102graph structures and helper classes used to implement these.
     103*/
    92104
    93105/**
  • 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);
  • src/test/undir_graph_test.cc

    r1022 r1030  
    3434  checkConcept<ErasableUndirGraph, Graph>();
    3535
     36  checkConcept<UndirGraph, UndirGraph>();
     37
    3638  return 0;
    3739}
Note: See TracChangeset for help on using the changeset viewer.