COIN-OR::LEMON - Graph Library

Changeset 962:1a770e9f80b2 in lemon-0.x


Ignore:
Timestamp:
11/05/04 01:31:49 (19 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1345
Message:

Undirect graph implementation.
Not yet done, untested.

Location:
src
Files:
3 added
5 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/Makefile.am

    r959 r962  
    3434        extendable_graph_extender.h                                     \
    3535        clearable_graph_extender.h                                      \
    36         erasable_graph_extender.h
     36        erasable_graph_extender.h                                       \
     37        undir_graph_extender.h
    3738
    3839noinst_HEADERS =                                                        \
    3940        concept/graph.h                                                 \
    4041        concept/graph_component.h                                       \
     42        concept/undir_graph.h                                           \
    4143        concept/sym_graph.h                                             \
    4244        concept/maps.h                                                  \
  • src/lemon/alteration_observer_registry.h

    r946 r962  
    279279
    280280
    281   /// Class to extend a graph functionality with the possibility of alteration observing.
    282 
    283   /// AlterableGraphExtender extends the _Base graphs functionality with the possibility of
    284   /// alteration observing. It defines two observer registrys for the nodes and mapes.
     281  /// \brief Class to extend a graph with the functionality of alteration
     282  /// observing.
     283  ///
     284  /// AlterableGraphExtender extends the _Base graphs functionality with
     285  /// the possibility of alteration observing. It defines two observer
     286  /// registrys for the nodes and mapes.
     287  ///
     288  /// \todo Document what "alteration observing" is. And probably find a
     289  /// better (shorter) name.
    285290  ///
    286291  /// \param _Base is the base class to extend.
     
    288293  /// \pre _Base is conform to the BaseGraphComponent concept.
    289294  ///
    290   /// \post AlterableGraphExtender<_Base> is conform to the AlterableGraphComponent concept.
     295  /// \post AlterableGraphExtender<_Base> is conform to the
     296  /// AlterableGraphComponent concept.
    291297  ///
    292298  /// \author Balazs Dezso
     
    302308    typedef typename Parent::Edge Edge;
    303309
     310    /// The edge observer registry.
     311    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
    304312    /// The node observer registry.
    305     typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
    306     /// The edge observer registry.
    307313    typedef AlterationObserverRegistry<Node> NodeObserverRegistry;
    308314
     
    331337  };
    332338
     339  /// \brief Class to extend an undirected graph with the functionality of
     340  /// alteration observing.
     341  ///
     342  /// \todo Document.
     343  ///
     344  /// \sa AlterableGraphExtender
     345  ///
     346  /// \bug This should be done some other way. Possibilities: template
     347  /// specialization (not very easy, if at all possible); some kind of
     348  /// enable_if boost technique?
     349
     350  template <typename _Base>
     351  class AlterableUndirGraphExtender
     352    : public AlterableGraphExtender<_Base> {
     353  public:
     354
     355    typedef AlterableUndirGraphExtender Graph;
     356    typedef AlterableGraphExtender<_Base> Parent;
     357
     358    typedef typename Parent::UndirEdge UndirEdge;
     359
     360    /// The edge observer registry.
     361    typedef AlterationObserverRegistry<UndirEdge> UndirEdgeObserverRegistry;
     362
     363  protected:
     364
     365    mutable UndirEdgeObserverRegistry undir_edge_observers;
     366
     367    UndirEdgeObserverRegistry& getUndirEdgeObserverRegistry() const {
     368      return undir_edge_observers;
     369    }
     370
     371    ~AlterableUndirGraphExtender() {
     372      undir_edge_observers.clear();
     373    }
     374  };
    333375 
    334376/// @}
  • src/lemon/concept/graph_component.h

    r961 r962  
    264264        function_requires< GraphItemConcept<Edge> >();
    265265        {
    266           const Graph& const_graph = graph;
    267266          Node n;
    268267          Edge e;
    269           n = const_graph.tail(e);
    270           n = const_graph.head(e);
     268          n = graph.tail(e);
     269          n = graph.head(e);
    271270        }     
    272271      }
    273272     
    274       Graph& graph;
     273      const Graph& graph;
    275274    };
    276275
     
    646645    template <typename Graph>
    647646    struct IterableGraphComponentConcept {
    648 
    649647      void constraints() {
    650648        function_requires< BaseIterableGraphComponentConcept<Graph> >();
     
    662660        function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
    663661      }
    664       Graph& graph;
    665662    };
    666663
  • src/lemon/iterable_graph_extender.h

    r946 r962  
    99  template <typename _Base>
    1010  class IterableGraphExtender : public _Base {
     11  public:
    1112
    1213    typedef _Base Parent;
    1314    typedef IterableGraphExtender<_Base> Graph;
    14 
    15   public:
    1615
    1716    typedef typename Parent::Node Node;
     
    2726      NodeIt(Invalid i) : Node(i) { }
    2827
    29       explicit NodeIt(const Graph& _graph) : Node(), graph(&_graph) {
     28      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    3029        _graph.first(*static_cast<Node*>(this));
    3130      }
     
    5049      EdgeIt(Invalid i) : Edge(i) { }
    5150
    52       explicit EdgeIt(const Graph& _graph) : Edge(), graph(&_graph) {
     51      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    5352        _graph.first(*static_cast<Edge*>(this));
    5453      }
     
    7473
    7574      OutEdgeIt(const Graph& _graph, const Node& node)
    76         : Edge(), graph(&_graph) {
     75        : graph(&_graph) {
    7776        _graph.firstOut(*this, node);
    7877      }
     
    9897
    9998      InEdgeIt(const Graph& _graph, const Node& node)
    100         : Edge(), graph(&_graph) {
     99        : graph(&_graph) {
    101100        _graph.firstIn(*this, node);
    102101      }
     
    127126  };
    128127 
     128  template <typename _Base>
     129  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
     130  public:
     131
     132    typedef IterableGraphExtender<_Base> Parent;
     133    typedef IterableUndirGraphExtender<_Base> Graph;
     134
     135    typedef typename Parent::UndirEdge UndirEdge;
     136
     137    class UndirEdgeIt : public UndirEdge {
     138      const Graph* graph;
     139    public:
     140
     141      UndirEdgeIt() { }
     142
     143      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
     144
     145      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
     146        _graph.first(*static_cast<UndirEdge*>(this));
     147      }
     148
     149      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
     150        UndirEdge(e), graph(&_graph) { }
     151
     152      UndirEdgeIt& operator++() {
     153        graph->next(*this);
     154        return *this;
     155      }
     156
     157    };
     158
     159
     160  };
    129161}
    130162
  • src/test/Makefile.am

    r961 r962  
    2525        time_measure_test \
    2626        unionfind_test \
     27        undir_graph_test \
    2728        xy_test
    2829
     
    4647unionfind_test_SOURCES = unionfind_test.cc
    4748xy_test_SOURCES = xy_test.cc
     49undir_graph_test_SOURCES = undir_graph_test.cc
    4850
Note: See TracChangeset for help on using the changeset viewer.