COIN-OR::LEMON - Graph Library

Changeset 1022:567f392d1d2e in lemon-0.x


Ignore:
Timestamp:
11/28/04 17:30:10 (19 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1412
Message:

UndirGraph? implementation nearly complete

Location:
src
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/alteration_observer_registry.h

    r980 r1022  
    365365    mutable UndirEdgeObserverRegistry undir_edge_observers;
    366366
    367     UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge = INVALID) const {
     367  public:
     368
     369    using Parent::getObserverRegistry;
     370    UndirEdgeObserverRegistry& getObserverRegistry(UndirEdge) const {
    368371      return undir_edge_observers;
    369372    }
  • src/lemon/clearable_graph_extender.h

    r980 r1022  
    2626  };
    2727
     28  template <typename _Base>
     29  class ClearableUndirGraphExtender : public _Base {
     30  public:
     31
     32    typedef ClearableUndirGraphExtender Graph;
     33    typedef _Base Parent;
     34    typedef typename Parent::Node Node;
     35    typedef typename Parent::UndirEdge UndirEdge;
     36    typedef typename Parent::Edge Edge;
     37
     38    void clear() {
     39      Parent::getObserverRegistry(Node()).clear();
     40      Parent::getObserverRegistry(UndirEdge()).clear();
     41      Parent::getObserverRegistry(Edge()).clear();
     42      Parent::clear();
     43    }
     44
     45  };
     46
    2847}
    2948
  • src/lemon/concept/graph_component.h

    r1021 r1022  
    407407    /// core clear functions for the graph structure.
    408408    /// The most of the base graphs should be conform to this concept.
    409     class BaseClearableGraphComponent : virtual public BaseGraphComponent {
     409    class ClearableGraphComponent : virtual public BaseGraphComponent {
    410410    public:
    411411
     
    419419      struct Constraints {
    420420        void constraints() {
    421           checkConcept< BaseGraphComponent, _Graph>();
     421          checkConcept<BaseGraphComponent, _Graph>();
    422422          graph.clear();
    423423        }
    424424
    425         _Graph& graph;
     425        _Graph graph;
    426426      };
    427427    };
     
    805805    };
    806806
    807     class ClearableGraphComponent : virtual public BaseGraphComponent {
    808     public:
    809 
    810       typedef ClearableGraphComponent Graph;
    811 
    812       typedef BaseGraphComponent::Node Node;
    813       typedef BaseGraphComponent::Edge Edge;
    814 
    815       void clear() {}   
    816 
    817 
    818       template <typename _Graph>
    819       struct ClearableGraphComponentConcept {
    820         void constraints() {
    821           checkConcept< BaseGraphComponent, _Graph >();
    822           graph.clear();
    823         }
    824         _Graph& graph;
    825       };
    826     };
    827 
    828807  }
    829808
  • src/lemon/concept/undir_graph.h

    r1021 r1022  
    3232
    3333    /// \todo to be done
    34     class BaseIterableUndirGraph;
    3534
    36     template <typename Graph>
    3735    struct BaseIterableUndirGraphConcept {
    38       typedef typename Graph::UndirEdge UndirEdge;
    39       typedef typename Graph::Edge Edge;
    40       typedef typename Graph::Node Node;
    4136
    42       void constraints() {
    43         checkConcept<BaseIterableGraphComponent, Graph>();
    44         checkConcept<GraphItem<'u'>, UndirEdge >();
     37      template <typename Graph>
     38      struct Constraints {
    4539
    46         /// \bug this should be base_and_derived:
    47         UndirEdge ue = e;
    48         ue = e;
     40        typedef typename Graph::UndirEdge UndirEdge;
     41        typedef typename Graph::Edge Edge;
     42        typedef typename Graph::Node Node;
    4943
    50         Node n;
    51         n = graph.target(ue);
    52         n = graph.source(ue);
     44        void constraints() {
     45          checkConcept<BaseIterableGraphComponent, Graph>();
     46          checkConcept<GraphItem<'u'>, UndirEdge >();
    5347
    54         graph.first(ue);
    55         graph.next(ue);
    56       }
    57       const Graph &graph;
    58       Edge e;
     48          /// \bug this should be base_and_derived:
     49          UndirEdge ue = e;
     50          ue = e;
     51
     52          Node n;
     53          n = graph.target(ue);
     54          n = graph.source(ue);
     55
     56          graph.first(ue);
     57          graph.next(ue);
     58        }
     59        const Graph &graph;
     60        Edge e;
     61      };
     62
    5963    };
    6064
    61     template <typename Graph>
     65
    6266    struct IterableUndirGraphConcept {
    63       void constraints() {
    64         /// \todo we don't need the iterable component should base iterable     
    65         //      checkConcept< BaseIterableUndirGraph, Graph > ();
    66         checkConcept< IterableGraphComponent, Graph > ();
    6767
    68         typedef typename Graph::UndirEdge UndirEdge;
    69         typedef typename Graph::UndirEdgeIt UndirEdgeIt;
    70         typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
     68      template <typename Graph>
     69      struct Constraints {
     70        void constraints() {
     71          /// \todo we don't need the iterable component to be base iterable
     72          /// Don't we really???
     73          //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
    7174
    72         checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >();
     75          checkConcept<IterableGraphComponent, Graph> ();
    7376
    74         checkConcept<
    75           GraphIncIterator<Graph, UndirEdge>,
    76           UndirIncEdgeIt >();
    77       }
     77          typedef typename Graph::UndirEdge UndirEdge;
     78          typedef typename Graph::UndirEdgeIt UndirEdgeIt;
     79          typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
     80
     81          checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
     82          checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
     83        }
     84      };
     85
     86    };
     87
     88    struct MappableUndirGraphConcept {
     89
     90      template <typename Graph>
     91      struct Constraints {
     92
     93        struct Dummy {
     94          int value;
     95          Dummy() : value(0) {}
     96          Dummy(int _v) : value(_v) {}
     97        };
     98
     99        void constraints() {
     100          checkConcept<MappableGraphComponent, Graph>();
     101
     102          typedef typename Graph::template UndirEdgeMap<int> IntMap;
     103          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
     104            IntMap >();
     105
     106          typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
     107          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
     108            BoolMap >();
     109
     110          typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
     111          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
     112            DummyMap >();
     113        }
     114      };
     115
     116    };
     117
     118    struct ExtendableUndirGraphConcept {
     119
     120      template <typename Graph>
     121      struct Constraints {
     122        void constraints() {
     123          node_a = graph.addNode();
     124          uedge = graph.addEdge(node_a, node_b);
     125        }
     126        typename Graph::Node node_a, node_b;
     127        typename Graph::UndirEdge uedge;
     128        Graph graph;
     129      };
     130
     131    };
     132
     133    struct ErasableUndirGraphConcept {
     134
     135      template <typename Graph>
     136      struct Constraints {
     137        void constraints() {
     138          graph.erase(n);
     139          graph.erase(e);
     140        }
     141        Graph graph;
     142        typename Graph::Node n;
     143        typename Graph::UndirEdge e;
     144      };
     145
     146    };
     147
     148    class UndirGraph {
     149    public:
     150
     151      template <typename Graph>
     152      struct Constraints {
     153        void constraints() {
     154          checkConcept<BaseIterableUndirGraphConcept, Graph>();
     155          checkConcept<IterableUndirGraphConcept, Graph>();
     156          checkConcept<MappableUndirGraphConcept, Graph>();
     157        }
     158      };
     159
     160    };
     161
     162    class ExtendableUndirGraph : public UndirGraph {
     163    public:
     164
     165      template <typename Graph>
     166      struct Constraints {
     167        void constraints() {
     168          checkConcept<BaseIterableUndirGraphConcept, Graph>();
     169          checkConcept<IterableUndirGraphConcept, Graph>();
     170          checkConcept<MappableUndirGraphConcept, Graph>();
     171
     172          checkConcept<UndirGraph, Graph>();
     173          checkConcept<ExtendableUndirGraphConcept, Graph>();
     174          checkConcept<ClearableGraphComponent, Graph>();
     175        }
     176      };
     177
     178    };
     179
     180    class ErasableUndirGraph : public ExtendableUndirGraph {
     181    public:
     182
     183      template <typename Graph>
     184      struct Constraints {
     185        void constraints() {
     186          checkConcept<ExtendableUndirGraph, Graph>();
     187          checkConcept<ErasableUndirGraphConcept, Graph>();
     188        }
     189      };
     190
    78191    };
    79192
  • src/lemon/concept_check.h

    r989 r1022  
    4242  template <typename Concept, typename Type>
    4343  inline void checkConcept() {
    44     function_requires<typename Concept::template Constraints<Type> >();
     44#if !defined(NDEBUG)
     45    typedef typename Concept::template Constraints<Type> ConceptCheck;
     46    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
     47    ignore_unused_variable_warning(x);
     48#endif
    4549  }
    4650
  • src/lemon/default_map.h

    r987 r1022  
    173173    class NodeMap : public DefaultMap<Graph, Node, NodeIt, _Value> {
    174174    public:
    175       typedef DefaultMappableGraphExtender<_Base> Graph;
    176 
    177       typedef typename Graph::Node Node;
    178       typedef typename Graph::NodeIt NodeIt;
    179 
     175      typedef DefaultMappableGraphExtender Graph;
    180176      typedef DefaultMap<Graph, Node, NodeIt, _Value> Parent;
    181 
    182       //typedef typename Parent::Graph Graph;
    183       typedef typename Parent::Value Value;
    184177
    185178      NodeMap(const Graph& _g)
    186179        : Parent(_g) {}
    187       NodeMap(const Graph& _g, const Value& _v)
     180      NodeMap(const Graph& _g, const _Value& _v)
    188181        : Parent(_g, _v) {}
    189 
    190182    };
    191183
     
    193185    class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, _Value> {
    194186    public:
    195       typedef DefaultMappableGraphExtender<_Base> Graph;
    196 
    197       typedef typename Graph::Edge Edge;
    198       typedef typename Graph::EdgeIt EdgeIt;
    199 
     187      typedef DefaultMappableGraphExtender Graph;
    200188      typedef DefaultMap<Graph, Edge, EdgeIt, _Value> Parent;
    201 
    202       //typedef typename Parent::Graph Graph;
    203       typedef typename Parent::Value Value;
    204189
    205190      EdgeMap(const Graph& _g)
    206191        : Parent(_g) {}
    207       EdgeMap(const Graph& _g, const Value& _v)
     192      EdgeMap(const Graph& _g, const _Value& _v)
    208193        : Parent(_g, _v) {}
    209 
    210194    };
    211195   
    212196  };
    213197
     198  template <typename _Base>
     199  class MappableUndirGraphExtender :
     200    public DefaultMappableGraphExtender<_Base> {
     201  public:
     202
     203    typedef MappableUndirGraphExtender Graph;
     204    typedef DefaultMappableGraphExtender<_Base> Parent;
     205
     206    typedef typename Parent::UndirEdge UndirEdge;
     207    typedef typename Parent::UndirEdgeIt UndirEdgeIt;
     208
     209    template <typename _Value>
     210    class UndirEdgeMap :
     211      public DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> {
     212    public:
     213      typedef MappableUndirGraphExtender Graph;
     214      typedef DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> Parent;
     215
     216      UndirEdgeMap(const Graph& _g)
     217        : Parent(_g) {}
     218      UndirEdgeMap(const Graph& _g, const _Value& _v)
     219        : Parent(_g, _v) {}
     220    };
     221
     222
     223  };
    214224
    215225}
  • src/lemon/erasable_graph_extender.h

    r980 r1022  
    4444  };
    4545
     46  template <typename _Base>
     47  class ErasableUndirGraphExtender : public _Base {
     48  public:
     49
     50    typedef ErasableUndirGraphExtender Graph;
     51    typedef _Base Parent;
     52
     53    typedef typename Parent::Node Node;
     54    typedef typename Parent::UndirEdge UndirEdge;
     55    typedef typename Parent::Edge Edge;
     56
     57    void erase(const Node& node) {
     58      Edge edge;
     59      Parent::firstOut(edge, node);
     60      while (edge != INVALID ) {
     61        erase(edge);
     62        Parent::firstOut(edge, node);
     63      }
     64
     65      Parent::getObserverRegistry(Node()).erase(node);
     66      Parent::erase(node);
     67    }
     68   
     69    void erase(const UndirEdge& uedge) {
     70      Parent::getObserverRegistry(Edge()).erase(Edge(uedge,true));
     71      Parent::getObserverRegistry(Edge()).erase(Edge(uedge,false));
     72      Parent::getObserverRegistry(UndirEdge()).erase(uedge);
     73      Parent::erase(uedge);
     74    }
     75
     76  };
     77
    4678}
    4779
  • src/lemon/extendable_graph_extender.h

    r980 r1022  
    3030  };
    3131
     32  template <typename _Base>
     33  class ExtendableUndirGraphExtender : public _Base {
     34  public:
     35
     36    typedef ExtendableUndirGraphExtender Graph;
     37    typedef _Base Parent;
     38
     39    typedef typename Parent::Node Node;
     40    typedef typename Parent::Edge Edge;
     41    typedef typename Parent::UndirEdge UndirEdge;
     42
     43    Node addNode() {
     44      Node node = Parent::addNode();
     45      Parent::getObserverRegistry(Node()).add(node);
     46      return node;
     47    }
     48
     49    UndirEdge addEdge(const Node& from, const Node& to) {
     50      UndirEdge uedge = Parent::addEdge(from, to);
     51      Parent::getObserverRegistry(UndirEdge()).add(uedge);
     52
     53      Edge edge_forward(uedge, true);
     54      Edge edge_backward(uedge, false);
     55      Parent::getObserverRegistry(Edge()).add(edge_forward);
     56      Parent::getObserverRegistry(Edge()).add(edge_backward);
     57
     58      return uedge;
     59    }
     60
     61  };
     62
    3263}
    3364
  • src/lemon/iterable_graph_extender.h

    r1021 r1022  
    177177
    178178      // FIXME: Do we need this type of constructor here?
    179       // UndirIncEdgeIt(const Graph& _graph, const UndirEdge& e) :
    180       //   UndirEdge(e), graph(&_graph) { }
     179      // UndirIncEdgeIt(const Graph& _graph, const Edge& e) :
     180      //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
     181      // or
     182      // UndirIncEdgeIt(const Graph& _graph, const Node& n,
     183      //    Const UndirEdge &e) ... ?
    181184
    182185      UndirIncEdgeIt& operator++() {
  • src/test/graph_test.cc

    r989 r1022  
    3030    checkConcept<BaseExtendableGraphComponent, BaseExtendableGraphComponent >();
    3131    checkConcept<BaseErasableGraphComponent, BaseErasableGraphComponent >();
    32     checkConcept<BaseClearableGraphComponent, BaseClearableGraphComponent >();
    3332
    3433    checkConcept<IterableGraphComponent, IterableGraphComponent >();
  • src/test/undir_graph_test.cc

    r962 r1022  
    1717  typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
    1818
    19   function_requires< BaseIterableUndirGraphConcept<UndirListGraphBase> >();
    20 
    2119  typedef IterableUndirGraphExtender<
    2220    AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;
    2321
    24   function_requires< IterableUndirGraphConcept<IterableUndirListGraph> >();
     22  typedef MappableUndirGraphExtender<IterableUndirListGraph>
     23    MappableUndirListGraph;
     24
     25  typedef ErasableUndirGraphExtender<
     26    ClearableUndirGraphExtender<
     27    ExtendableUndirGraphExtender<MappableUndirListGraph> > > Graph;
     28
     29  checkConcept<BaseIterableUndirGraphConcept, Graph>();
     30  checkConcept<IterableUndirGraphConcept, Graph>();
     31  checkConcept<MappableUndirGraphConcept, Graph>();
     32
     33  checkConcept<UndirGraph, Graph>();
     34  checkConcept<ErasableUndirGraph, Graph>();
    2535
    2636  return 0;
Note: See TracChangeset for help on using the changeset viewer.