COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2111:ea1fa1bc3f6d in lemon-0.x for lemon/concept/ugraph.h


Ignore:
Timestamp:
06/28/06 17:06:24 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2817
Message:

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/concept/ugraph.h

    r2021 r2111  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief Undirected graphs and components of.
     21///\brief The concept of the undirected graphs.
    2222
    2323
    … …  
    3131namespace lemon {
    3232  namespace concept {
    33 
    34 //     /// Skeleton class which describes an edge with direction in \ref
    35 //     /// UGraph "undirected graph".
    36     template <typename UGraph>
    37     class UGraphEdge : public UGraph::UEdge {
    38       typedef typename UGraph::UEdge UEdge;
    39       typedef typename UGraph::Node Node;
    40     public:
    41 
    42       /// \e
    43       UGraphEdge() {}
    44 
    45       /// \e
    46       UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
    47 
    48       /// \e
    49       UGraphEdge(Invalid) {}
    50 
    51       /// \brief Directed edge from undirected edge and a source node.
    52       ///
    53       /// Constructs a directed edge from undirected edge and a source node.
    54       ///
    55       /// \note You have to specify the graph for this constructor.
    56       UGraphEdge(const UGraph &g,
    57                      UEdge u_edge, Node n) {
    58         ignore_unused_variable_warning(u_edge);
    59         ignore_unused_variable_warning(g);
    60         ignore_unused_variable_warning(n);
    61       }
    62 
    63       /// \e
    64       UGraphEdge& operator=(UGraphEdge) { return *this; }
    65 
    66       /// \e
    67       bool operator==(UGraphEdge) const { return true; }
    68       /// \e
    69       bool operator!=(UGraphEdge) const { return false; }
    70 
    71       /// \e
    72       bool operator<(UGraphEdge) const { return false; }
    73 
    74       template <typename Edge>
    75       struct Constraints {
    76         void constraints() {
    77           const_constraints();
    78         }
    79         void const_constraints() const {
    80           /// \bug This should be is_base_and_derived ...
    81           UEdge ue = e;
    82           ue = e;
    83 
    84           Edge e_with_source(graph,ue,n);
    85           ignore_unused_variable_warning(e_with_source);
    86         }
    87         Edge e;
    88         UEdge ue;
    89         UGraph graph;
    90         Node n;
    91       };
    92     };
    93    
    94 
    95     struct BaseIterableUGraphConcept {
    96 
    97       template <typename Graph>
    98       struct Constraints {
    99 
    100         typedef typename Graph::UEdge UEdge;
    101         typedef typename Graph::Edge Edge;
    102         typedef typename Graph::Node Node;
    103 
    104         void constraints() {
    105           checkConcept<BaseIterableGraphComponent, Graph>();
    106           checkConcept<GraphItem<>, UEdge>();
    107           //checkConcept<UGraphEdge<Graph>, Edge>();
    108 
    109           graph.first(ue);
    110           graph.next(ue);
    111 
    112           const_constraints();
    113         }
    114         void const_constraints() {
    115           Node n;
    116           n = graph.target(ue);
    117           n = graph.source(ue);
    118           n = graph.oppositeNode(n0, ue);
    119 
    120           bool b;
    121           b = graph.direction(e);
    122           Edge e = graph.direct(UEdge(), true);
    123           e = graph.direct(UEdge(), n);
    124  
    125           ignore_unused_variable_warning(b);
    126         }
    127 
    128         Graph graph;
    129         Edge e;
    130         Node n0;
    131         UEdge ue;
    132       };
    133 
    134     };
    135 
    136 
    137     struct IterableUGraphConcept {
    138 
    139       template <typename Graph>
    140       struct Constraints {
    141         void constraints() {
    142           /// \todo we don't need the iterable component to be base iterable
    143           /// Don't we really???
    144           //checkConcept< BaseIterableUGraphConcept, Graph > ();
    145 
    146           checkConcept<IterableGraphComponent, Graph> ();
    147 
    148           typedef typename Graph::UEdge UEdge;
    149           typedef typename Graph::UEdgeIt UEdgeIt;
    150           typedef typename Graph::IncEdgeIt IncEdgeIt;
    151 
    152           checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
    153           checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
    154         }
    155       };
    156 
    157     };
    158 
    159     struct MappableUGraphConcept {
    160 
    161       template <typename Graph>
    162       struct Constraints {
    163 
    164         struct Dummy {
    165           int value;
    166           Dummy() : value(0) {}
    167           Dummy(int _v) : value(_v) {}
    168         };
    169 
    170         void constraints() {
    171           checkConcept<MappableGraphComponent, Graph>();
    172 
    173           typedef typename Graph::template UEdgeMap<int> IntMap;
    174           checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
    175             IntMap >();
    176 
    177           typedef typename Graph::template UEdgeMap<bool> BoolMap;
    178           checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
    179             BoolMap >();
    180 
    181           typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
    182           checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
    183             DummyMap >();
    184         }
    185       };
    186 
    187     };
    188 
    189     struct ExtendableUGraphConcept {
    190 
    191       template <typename Graph>
    192       struct Constraints {
    193         void constraints() {
    194           node_a = graph.addNode();
    195           uedge = graph.addEdge(node_a, node_b);
    196         }
    197         typename Graph::Node node_a, node_b;
    198         typename Graph::UEdge uedge;
    199         Graph graph;
    200       };
    201 
    202     };
    203 
    204     struct ErasableUGraphConcept {
    205 
    206       template <typename Graph>
    207       struct Constraints {
    208         void constraints() {
    209           graph.erase(n);
    210           graph.erase(e);
    211         }
    212         Graph graph;
    213         typename Graph::Node n;
    214         typename Graph::UEdge e;
    215       };
    216 
    217     };
    21833
    21934    /// \addtogroup graph_concepts
    … …  
    23247    ///
    23348    /// In LEMON undirected graphs also fulfill the concept of directed
    234     /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
    235     /// explanation of this and more see also the page \ref ugraphs,
    236     /// a tutorial about undirected graphs.
     49    /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
     50    /// explanation of this and more see also the page \ref graphs,
     51    /// a tutorial about graphs.
    23752    ///
    23853    /// You can assume that all undirected graph can be handled
    239     /// as a static directed graph. This way it is fully conform
    240     /// to the StaticGraph concept.
     54    /// as a directed graph. This way it is fully conform
     55    /// to the Graph concept.
    24156
    24257    class UGraph {
    … …  
    800615      Node target(Edge) const { return INVALID; }
    801616
    802 //       /// \brief First node of the graph
    803 //       ///
    804 //       /// \note This method is part of so called \ref
    805 //       /// developpers_interface "Developpers' interface", so it shouldn't
    806 //       /// be used in an end-user program.
    807617      void first(Node&) const {}
    808 //       /// \brief Next node of the graph
    809 //       ///
    810 //       /// \note This method is part of so called \ref
    811 //       /// developpers_interface "Developpers' interface", so it shouldn't
    812 //       /// be used in an end-user program.
    813618      void next(Node&) const {}
    814619
    815 //       /// \brief First undirected edge of the graph
    816 //       ///
    817 //       /// \note This method is part of so called \ref
    818 //       /// developpers_interface "Developpers' interface", so it shouldn't
    819 //       /// be used in an end-user program.
    820620      void first(UEdge&) const {}
    821 //       /// \brief Next undirected edge of the graph
    822 //       ///
    823 //       /// \note This method is part of so called \ref
    824 //       /// developpers_interface "Developpers' interface", so it shouldn't
    825 //       /// be used in an end-user program.
    826621      void next(UEdge&) const {}
    827622
    828 //       /// \brief First directed edge of the graph
    829 //       ///
    830 //       /// \note This method is part of so called \ref
    831 //       /// developpers_interface "Developpers' interface", so it shouldn't
    832 //       /// be used in an end-user program.
    833623      void first(Edge&) const {}
    834 //       /// \brief Next directed edge of the graph
    835 //       ///
    836 //       /// \note This method is part of so called \ref
    837 //       /// developpers_interface "Developpers' interface", so it shouldn't
    838 //       /// be used in an end-user program.
    839624      void next(Edge&) const {}
    840625
    841 //       /// \brief First outgoing edge from a given node
    842 //       ///
    843 //       /// \note This method is part of so called \ref
    844 //       /// developpers_interface "Developpers' interface", so it shouldn't
    845 //       /// be used in an end-user program.
    846626      void firstOut(Edge&, Node) const {}
    847 //       /// \brief Next outgoing edge to a node
    848 //       ///
    849 //       /// \note This method is part of so called \ref
    850 //       /// developpers_interface "Developpers' interface", so it shouldn't
    851 //       /// be used in an end-user program.
    852627      void nextOut(Edge&) const {}
    853628
    854 //       /// \brief First incoming edge to a given node
    855 //       ///
    856 //       /// \note This method is part of so called \ref
    857 //       /// developpers_interface "Developpers' interface", so it shouldn't
    858 //       /// be used in an end-user program.
    859629      void firstIn(Edge&, Node) const {}
    860 //       /// \brief Next incoming edge to a node
    861 //       ///
    862 //       /// \note This method is part of so called \ref
    863 //       /// developpers_interface "Developpers' interface", so it shouldn't
    864 //       /// be used in an end-user program.
    865630      void nextIn(Edge&) const {}
    866631
    867632
    868633      void firstInc(UEdge &, bool &, const Node &) const {}
    869 
    870634      void nextInc(UEdge &, bool &) const {}
    871635
    … …  
    923687    };
    924688
    925     /// \brief An empty non-static undirected graph class.
    926     ///   
    927     /// This class provides everything that \ref UGraph does.
    928     /// Additionally it enables building graphs from scratch.
    929     class ExtendableUGraph : public UGraph {
    930     public:
    931      
    932       /// \brief Add a new node to the graph.
    933       ///
    934       /// Add a new node to the graph.
    935       /// \return the new node.
    936       Node addNode();
    937 
    938       /// \brief Add a new undirected edge to the graph.
    939       ///
    940       /// Add a new undirected edge to the graph.
    941       /// \return the new edge.
    942       UEdge addEdge(const Node& from, const Node& to);
    943 
    944       /// \brief Resets the graph.
    945       ///
    946       /// This function deletes all undirected edges and nodes of the graph.
    947       /// It also frees the memory allocated to store them.
    948       void clear() { }
    949 
    950       template <typename Graph>
    951       struct Constraints {
    952         void constraints() {
    953           checkConcept<BaseIterableUGraphConcept, Graph>();
    954           checkConcept<IterableUGraphConcept, Graph>();
    955           checkConcept<MappableUGraphConcept, Graph>();
    956 
    957           checkConcept<UGraph, Graph>();
    958           checkConcept<ExtendableUGraphConcept, Graph>();
    959           checkConcept<ClearableGraphComponent, Graph>();
    960         }
    961       };
    962 
    963     };
    964 
    965     /// \brief An empty erasable undirected graph class.
    966     ///
    967     /// This class is an extension of \ref ExtendableUGraph. It makes it
    968     /// possible to erase undirected edges or nodes.
    969     class ErasableUGraph : public ExtendableUGraph {
    970     public:
    971 
    972       /// \brief Deletes a node.
    973       ///
    974       /// Deletes a node.
    975       ///
    976       void erase(Node) { }
    977       /// \brief Deletes an undirected edge.
    978       ///
    979       /// Deletes an undirected edge.
    980       ///
    981       void erase(UEdge) { }
    982 
    983       template <typename Graph>
    984       struct Constraints {
    985         void constraints() {
    986           checkConcept<ExtendableUGraph, Graph>();
    987           checkConcept<ErasableUGraphConcept, Graph>();
    988         }
    989       };
    990 
    991     };
    992 
    993689    /// @}
    994690
Note: See TracChangeset for help on using the changeset viewer.