1.1 --- a/src/lemon/Makefile.am	Thu Nov 04 22:04:51 2004 +0000
     1.2 +++ b/src/lemon/Makefile.am	Fri Nov 05 00:31:49 2004 +0000
     1.3 @@ -33,11 +33,13 @@
     1.4  	idmappable_graph_extender.h				   	\
     1.5  	extendable_graph_extender.h					\
     1.6  	clearable_graph_extender.h					\
     1.7 -	erasable_graph_extender.h
     1.8 +	erasable_graph_extender.h					\
     1.9 +	undir_graph_extender.h
    1.10  
    1.11  noinst_HEADERS =							\
    1.12  	concept/graph.h							\
    1.13  	concept/graph_component.h					\
    1.14 +	concept/undir_graph.h						\
    1.15  	concept/sym_graph.h						\
    1.16  	concept/maps.h							\
    1.17  	concept/path.h

     2.1 --- a/src/lemon/alteration_observer_registry.h	Thu Nov 04 22:04:51 2004 +0000
     2.2 +++ b/src/lemon/alteration_observer_registry.h	Fri Nov 05 00:31:49 2004 +0000
     2.3 @@ -278,16 +278,22 @@
     2.4    };
     2.5  
     2.6  
     2.7 -  /// Class to extend a graph functionality with the possibility of alteration observing.
     2.8 -
     2.9 -  /// AlterableGraphExtender extends the _Base graphs functionality with the possibility of 
    2.10 -  /// alteration observing. It defines two observer registrys for the nodes and mapes.
    2.11 +  /// \brief Class to extend a graph with the functionality of alteration
    2.12 +  /// observing.
    2.13 +  ///
    2.14 +  /// AlterableGraphExtender extends the _Base graphs functionality with
    2.15 +  /// the possibility of alteration observing. It defines two observer
    2.16 +  /// registrys for the nodes and mapes.
    2.17 +  /// 
    2.18 +  /// \todo Document what "alteration observing" is. And probably find a
    2.19 +  /// better (shorter) name.
    2.20    ///
    2.21    /// \param _Base is the base class to extend.
    2.22    ///
    2.23    /// \pre _Base is conform to the BaseGraphComponent concept.
    2.24    ///
    2.25 -  /// \post AlterableGraphExtender<_Base> is conform to the AlterableGraphComponent concept.
    2.26 +  /// \post AlterableGraphExtender<_Base> is conform to the
    2.27 +  /// AlterableGraphComponent concept.
    2.28    ///
    2.29    /// \author Balazs Dezso
    2.30  
    2.31 @@ -301,9 +307,9 @@
    2.32      typedef typename Parent::Node Node;
    2.33      typedef typename Parent::Edge Edge;
    2.34  
    2.35 +    /// The edge observer registry.
    2.36 +    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
    2.37      /// The node observer registry.
    2.38 -    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
    2.39 -    /// The edge observer registry.
    2.40      typedef AlterationObserverRegistry<Node> NodeObserverRegistry;
    2.41  
    2.42  
    2.43 @@ -330,6 +336,42 @@
    2.44      
    2.45    };
    2.46  
    2.47 +  /// \brief Class to extend an undirected graph with the functionality of
    2.48 +  /// alteration observing.
    2.49 +  ///
    2.50 +  /// \todo Document.
    2.51 +  ///
    2.52 +  /// \sa AlterableGraphExtender
    2.53 +  ///
    2.54 +  /// \bug This should be done some other way. Possibilities: template
    2.55 +  /// specialization (not very easy, if at all possible); some kind of
    2.56 +  /// enable_if boost technique?
    2.57 +
    2.58 +  template <typename _Base> 
    2.59 +  class AlterableUndirGraphExtender
    2.60 +    : public AlterableGraphExtender<_Base> {
    2.61 +  public:
    2.62 +
    2.63 +    typedef AlterableUndirGraphExtender Graph;
    2.64 +    typedef AlterableGraphExtender<_Base> Parent;
    2.65 +
    2.66 +    typedef typename Parent::UndirEdge UndirEdge;
    2.67 +
    2.68 +    /// The edge observer registry.
    2.69 +    typedef AlterationObserverRegistry<UndirEdge> UndirEdgeObserverRegistry;
    2.70 +
    2.71 +  protected:
    2.72 +
    2.73 +    mutable UndirEdgeObserverRegistry undir_edge_observers;
    2.74 +
    2.75 +    UndirEdgeObserverRegistry& getUndirEdgeObserverRegistry() const {
    2.76 +      return undir_edge_observers;
    2.77 +    }
    2.78 +
    2.79 +    ~AlterableUndirGraphExtender() {
    2.80 +      undir_edge_observers.clear();
    2.81 +    }
    2.82 +  };
    2.83    
    2.84  /// @}
    2.85    

     3.1 --- a/src/lemon/concept/graph_component.h	Thu Nov 04 22:04:51 2004 +0000
     3.2 +++ b/src/lemon/concept/graph_component.h	Fri Nov 05 00:31:49 2004 +0000
     3.3 @@ -263,15 +263,14 @@
     3.4  	function_requires< GraphItemConcept<Node> >();
     3.5  	function_requires< GraphItemConcept<Edge> >();
     3.6  	{
     3.7 -	  const Graph& const_graph = graph;
     3.8  	  Node n;
     3.9  	  Edge e;
    3.10 -	  n = const_graph.tail(e);
    3.11 -	  n = const_graph.head(e);
    3.12 +	  n = graph.tail(e);
    3.13 +	  n = graph.head(e);
    3.14  	}      
    3.15        }
    3.16        
    3.17 -      Graph& graph;
    3.18 +      const Graph& graph;
    3.19      };
    3.20  
    3.21      /// An empty iterable base graph class.
    3.22 @@ -645,7 +644,6 @@
    3.23      
    3.24      template <typename Graph> 
    3.25      struct IterableGraphComponentConcept {
    3.26 -
    3.27        void constraints() {
    3.28    	function_requires< BaseIterableGraphComponentConcept<Graph> >();
    3.29  
    3.30 @@ -661,7 +659,6 @@
    3.31  	function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
    3.32  	function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
    3.33        }
    3.34 -      Graph& graph;
    3.35      };
    3.36  
    3.37  

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/lemon/concept/undir_graph.h	Fri Nov 05 00:31:49 2004 +0000
     4.3 @@ -0,0 +1,78 @@
     4.4 +/* -*- C++ -*-
     4.5 + *
     4.6 + * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic
     4.7 + * C++ optimization library
     4.8 + *
     4.9 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
    4.10 + * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    4.11 + * EGRES).
    4.12 + *
    4.13 + * Permission to use, modify and distribute this software is granted
    4.14 + * provided that this copyright notice appears in all copies. For
    4.15 + * precise terms see the accompanying LICENSE file.
    4.16 + *
    4.17 + * This software is provided "AS IS" with no warranty of any kind,
    4.18 + * express or implied, and with no claim as to its suitability for any
    4.19 + * purpose.
    4.20 + *
    4.21 + */
    4.22 +
    4.23 +///\ingroup concept
    4.24 +///\file
    4.25 +///\brief Undirected graphs and components of.
    4.26 +
    4.27 +
    4.28 +#ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
    4.29 +#define LEMON_CONCEPT_UNDIR_GRAPH_H
    4.30 +
    4.31 +#include <lemon/concept/graph_component.h>
    4.32 +
    4.33 +namespace lemon {
    4.34 +  namespace concept {
    4.35 +
    4.36 +    /// \todo to be done
    4.37 +    class BaseIterableUndirGraph;
    4.38 +
    4.39 +    template <typename Graph>
    4.40 +    struct BaseIterableUndirGraphConcept {
    4.41 +      typedef typename Graph::UndirEdge UndirEdge;
    4.42 +      typedef typename Graph::Edge Edge;
    4.43 +      typedef typename Graph::Node Node;
    4.44 +      void constraints() {
    4.45 +	function_requires< BaseIterableGraphComponentConcept<Graph> >();
    4.46 +	function_requires< GraphItemConcept<UndirEdge> >();
    4.47 +
    4.48 +	/// \bug this should be base_and_derived:
    4.49 +	UndirEdge ue = e;
    4.50 +	ue = e;
    4.51 +
    4.52 +	Node n;
    4.53 +	n = graph.head(ue);
    4.54 +	n = graph.tail(ue);
    4.55 +
    4.56 +	graph.first(ue);
    4.57 +	graph.next(ue);
    4.58 +      }
    4.59 +      const Graph &graph;
    4.60 +      Edge e;
    4.61 +    };
    4.62 +
    4.63 +    template <typename Graph>
    4.64 +    struct IterableUndirGraphConcept {
    4.65 +      void constraints() {
    4.66 +	function_requires< BaseIterableUndirGraphConcept<Graph> > ();
    4.67 +	function_requires< IterableGraphComponentConcept<Graph> > ();
    4.68 +
    4.69 +	typedef typename Graph::UndirEdge UndirEdge;
    4.70 +	typedef typename Graph::UndirEdgeIt UndirEdgeIt;
    4.71 +
    4.72 +	function_requires<
    4.73 +	  GraphIteratorConcept<UndirEdgeIt, Graph, UndirEdge> >();
    4.74 +      }
    4.75 +    };
    4.76 +
    4.77 +  }
    4.78 +
    4.79 +}
    4.80 +
    4.81 +#endif

     5.1 --- a/src/lemon/iterable_graph_extender.h	Thu Nov 04 22:04:51 2004 +0000
     5.2 +++ b/src/lemon/iterable_graph_extender.h	Fri Nov 05 00:31:49 2004 +0000
     5.3 @@ -8,12 +8,11 @@
     5.4    
     5.5    template <typename _Base>
     5.6    class IterableGraphExtender : public _Base {
     5.7 +  public:
     5.8  
     5.9      typedef _Base Parent;
    5.10      typedef IterableGraphExtender<_Base> Graph;
    5.11  
    5.12 -  public:
    5.13 -
    5.14      typedef typename Parent::Node Node;
    5.15      typedef typename Parent::Edge Edge;
    5.16  
    5.17 @@ -26,7 +25,7 @@
    5.18  
    5.19        NodeIt(Invalid i) : Node(i) { }
    5.20  
    5.21 -      explicit NodeIt(const Graph& _graph) : Node(), graph(&_graph) {
    5.22 +      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    5.23  	_graph.first(*static_cast<Node*>(this));
    5.24        }
    5.25  
    5.26 @@ -49,7 +48,7 @@
    5.27  
    5.28        EdgeIt(Invalid i) : Edge(i) { }
    5.29  
    5.30 -      explicit EdgeIt(const Graph& _graph) : Edge(), graph(&_graph) {
    5.31 +      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    5.32  	_graph.first(*static_cast<Edge*>(this));
    5.33        }
    5.34  
    5.35 @@ -73,7 +72,7 @@
    5.36        OutEdgeIt(Invalid i) : Edge(i) { }
    5.37  
    5.38        OutEdgeIt(const Graph& _graph, const Node& node) 
    5.39 -	: Edge(), graph(&_graph) {
    5.40 +	: graph(&_graph) {
    5.41  	_graph.firstOut(*this, node);
    5.42        }
    5.43  
    5.44 @@ -97,7 +96,7 @@
    5.45        InEdgeIt(Invalid i) : Edge(i) { }
    5.46  
    5.47        InEdgeIt(const Graph& _graph, const Node& node) 
    5.48 -	: Edge(), graph(&_graph) {
    5.49 +	: graph(&_graph) {
    5.50  	_graph.firstIn(*this, node);
    5.51        }
    5.52  
    5.53 @@ -126,6 +125,39 @@
    5.54  
    5.55    };
    5.56    
    5.57 +  template <typename _Base>
    5.58 +  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
    5.59 +  public:
    5.60 +
    5.61 +    typedef IterableGraphExtender<_Base> Parent;
    5.62 +    typedef IterableUndirGraphExtender<_Base> Graph;
    5.63 +
    5.64 +    typedef typename Parent::UndirEdge UndirEdge;
    5.65 +
    5.66 +    class UndirEdgeIt : public UndirEdge { 
    5.67 +      const Graph* graph;
    5.68 +    public:
    5.69 +
    5.70 +      UndirEdgeIt() { }
    5.71 +
    5.72 +      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
    5.73 +
    5.74 +      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
    5.75 +	_graph.first(*static_cast<UndirEdge*>(this));
    5.76 +      }
    5.77 +
    5.78 +      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : 
    5.79 +	UndirEdge(e), graph(&_graph) { }
    5.80 +
    5.81 +      UndirEdgeIt& operator++() { 
    5.82 +	graph->next(*this);
    5.83 +	return *this; 
    5.84 +      }
    5.85 +
    5.86 +    };
    5.87 +
    5.88 +
    5.89 +  };
    5.90  }
    5.91  
    5.92  #endif // LEMON_GRAPH_EXTENDER_H

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/src/lemon/undir_graph_extender.h	Fri Nov 05 00:31:49 2004 +0000
     6.3 @@ -0,0 +1,193 @@
     6.4 +/* -*- C++ -*-
     6.5 + *
     6.6 + * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
     6.7 + * optimization library
     6.8 + *
     6.9 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
    6.10 + * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    6.11 + * EGRES).
    6.12 + *
    6.13 + * Permission to use, modify and distribute this software is granted
    6.14 + * provided that this copyright notice appears in all copies. For
    6.15 + * precise terms see the accompanying LICENSE file.
    6.16 + *
    6.17 + * This software is provided "AS IS" with no warranty of any kind,
    6.18 + * express or implied, and with no claim as to its suitability for any
    6.19 + * purpose.
    6.20 + *
    6.21 + */
    6.22 +
    6.23 +#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
    6.24 +#define LEMON_UNDIR_GRAPH_EXTENDER_H
    6.25 +
    6.26 +#include <lemon/invalid.h>
    6.27 +
    6.28 +namespace lemon {
    6.29 +
    6.30 +  template <typename _Base>
    6.31 +  class UndirGraphExtender : public _Base {
    6.32 +    typedef _Base Parent;
    6.33 +    typedef UndirGraphExtender Graph;
    6.34 +
    6.35 +  public:
    6.36 +
    6.37 +    typedef typename Parent::Edge UndirEdge;
    6.38 +    typedef typename Parent::Node Node;
    6.39 +
    6.40 +    class Edge : public UndirEdge {
    6.41 +      friend class Graph;
    6.42 +
    6.43 +    protected:
    6.44 +      // FIXME: Marci use opposite logic in his graph wrappers. It would
    6.45 +      // be reasonable to syncronize...
    6.46 +      bool forward;
    6.47 +
    6.48 +    public:
    6.49 +      Edge() {}
    6.50 +      /// Construct a direct edge from undirect edge and a direction.
    6.51 +      Edge(const UndirEdge &ue, bool _forward) :
    6.52 +	UndirEdge(ue), forward(_forward) {}
    6.53 +      /// Invalid edge constructor
    6.54 +      Edge(Invalid i) : UndirEdge(i), forward(false) {}
    6.55 +
    6.56 +      bool operator==(const Edge &that) const {
    6.57 +	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
    6.58 +      }
    6.59 +      bool operator!=(const Edge &that) const {
    6.60 +	return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
    6.61 +      }
    6.62 +      bool operator<(const Edge &that) const {
    6.63 +	return forward<that.forward ||
    6.64 +	  (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
    6.65 +      }
    6.66 +    };
    6.67 +
    6.68 +
    6.69 +    /// \brief Returns the Edge of opposite direction.
    6.70 +    ///
    6.71 +    /// \bug Is this a good name for this? Or "reverse" is better?
    6.72 +    Edge opposite(const Edge &e) const {
    6.73 +      return Edge(e,!e.forward);
    6.74 +    }
    6.75 +
    6.76 +    /// Tail of the given Edge.
    6.77 +    Node tail(const Edge &e) const {
    6.78 +      return e.forward ? Parent::tail(e) : Parent::head(e);
    6.79 +    }
    6.80 +
    6.81 +    /// \todo Shouldn't the "tail" of an undirected edge be called "aNode"
    6.82 +    /// or something???
    6.83 +    using Parent::tail;
    6.84 +
    6.85 +    /// Head of the given Edge.
    6.86 +    Node head(const Edge &e) const {
    6.87 +      return e.forward ? Parent::head(e) : Parent::tail(e);
    6.88 +    }
    6.89 +
    6.90 +    /// \todo Shouldn't the "head" of an undirected edge be called "bNode"
    6.91 +    /// or something???
    6.92 +    using Parent::head;
    6.93 +
    6.94 +    /// Returns whether the given directed edge is same orientation as the
    6.95 +    /// corresponding undirected edge.
    6.96 +    ///
    6.97 +    /// \todo reference to the corresponding point of the undirected graph
    6.98 +    /// concept. "What does the direction of an undirected edge mean?"
    6.99 +    bool forward(const Edge &e) const { return e.forward; }
   6.100 +
   6.101 +    Node oppsiteNode(const Node &n, const Edge &e) const {
   6.102 +      if( n == Parent::tail(e))
   6.103 +	return Parent::head(e);
   6.104 +      else if( n == Parent::head(e))
   6.105 +	return Parent::tail(e);
   6.106 +      else
   6.107 +	return INVALID;
   6.108 +    }
   6.109 +
   6.110 +
   6.111 +    using Parent::first;
   6.112 +    void first(Edge &e) const {
   6.113 +      Parent::first(e);
   6.114 +      e.forward=true;
   6.115 +    }
   6.116 +
   6.117 +    using Parent::next;
   6.118 +    void next(Edge &e) const {
   6.119 +      if( e.forward ) {
   6.120 +	e.forward = false;
   6.121 +      }
   6.122 +      else {
   6.123 +	Parent::next(e);
   6.124 +	e.forward = true;
   6.125 +      }
   6.126 +    }
   6.127 +
   6.128 +    void firstOut(Edge &e, const Node &n) const {
   6.129 +      Parent::firstOut(e,n);
   6.130 +      if( UndirEdge(e) != INVALID ) {
   6.131 +	e.forward = true;
   6.132 +      }
   6.133 +      else {
   6.134 +	Parent::firstIn(e,n);
   6.135 +	e.forward = false;
   6.136 +      }
   6.137 +    }
   6.138 +    void firstIn(Edge &e, const Node &n) const {
   6.139 +      Parent::firstIn(e,n);
   6.140 +      if( UndirEdge(e) != INVALID ) {
   6.141 +	e.forward = true;
   6.142 +      }
   6.143 +      else {
   6.144 +	Parent::firstOut(e,n);
   6.145 +	e.forward = false;
   6.146 +      }
   6.147 +    }
   6.148 +
   6.149 +    void nextOut(Edge &e) const {
   6.150 +      if( e.forward ) {
   6.151 +	Parent::nextOut(e);
   6.152 +	if( UndirEdge(e) == INVALID ) {
   6.153 +	  Parent::firstIn(e, Parent::tail(e));
   6.154 +	  e.forward = false;
   6.155 +	}
   6.156 +      }
   6.157 +      else {
   6.158 +	Parent::nextIn(e);
   6.159 +      }
   6.160 +    }
   6.161 +    void nextIn(Edge &e) const {
   6.162 +      if( e.forward ) {
   6.163 +	Parent::nextIn(e);
   6.164 +	if( UndirEdge(e) == INVALID ) {
   6.165 +	  Parent::firstOut(e, Parent::head(e));
   6.166 +	  e.forward = false;
   6.167 +	}
   6.168 +      }
   6.169 +      else {
   6.170 +	Parent::nextOut(e);
   6.171 +      }
   6.172 +    }
   6.173 +
   6.174 +    // Miscellaneous stuff:
   6.175 +
   6.176 +    /// \todo these methods (id, maxEdgeId) should be moved into separate
   6.177 +    /// Extender
   6.178 +
   6.179 +    using Parent::id;
   6.180 +
   6.181 +    int id(const Edge &e) const {
   6.182 +      return 2*Parent::id(e) + int(e.forward);
   6.183 +    }
   6.184 +
   6.185 +    int maxEdgeId() const {
   6.186 +      return 2*Parent::maxEdgeId() + 1;
   6.187 +    }
   6.188 +    int maxUndirEdgeId() const {
   6.189 +      return Parent::maxEdgeId();
   6.190 +    }
   6.191 +
   6.192 +  };
   6.193 +
   6.194 +}
   6.195 +
   6.196 +#endif // LEMON_UNDIR_GRAPH_EXTENDER_H

     7.1 --- a/src/test/Makefile.am	Thu Nov 04 22:04:51 2004 +0000
     7.2 +++ b/src/test/Makefile.am	Fri Nov 05 00:31:49 2004 +0000
     7.3 @@ -24,6 +24,7 @@
     7.4  	test_tools_pass \
     7.5  	time_measure_test \
     7.6  	unionfind_test \
     7.7 +	undir_graph_test \
     7.8  	xy_test
     7.9  
    7.10  TESTS = $(check_PROGRAMS)
    7.11 @@ -45,4 +46,5 @@
    7.12  test_tools_pass_SOURCES = test_tools_pass.cc
    7.13  unionfind_test_SOURCES = unionfind_test.cc
    7.14  xy_test_SOURCES = xy_test.cc
    7.15 +undir_graph_test_SOURCES = undir_graph_test.cc
    7.16  

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/src/test/undir_graph_test.cc	Fri Nov 05 00:31:49 2004 +0000
     8.3 @@ -0,0 +1,27 @@
     8.4 +// -*- C++ -*-
     8.5 +
     8.6 +#include <lemon/undir_graph_extender.h>
     8.7 +#include <lemon/concept/undir_graph.h>
     8.8 +#include <lemon/list_graph.h>
     8.9 +#include <lemon/smart_graph.h>
    8.10 +#include <lemon/full_graph.h>
    8.11 +
    8.12 +#include "test_tools.h"
    8.13 +
    8.14 +
    8.15 +using namespace lemon;
    8.16 +using namespace lemon::concept;
    8.17 +
    8.18 +
    8.19 +int main() {
    8.20 +  typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
    8.21 +
    8.22 +  function_requires< BaseIterableUndirGraphConcept<UndirListGraphBase> >();
    8.23 +
    8.24 +  typedef IterableUndirGraphExtender<
    8.25 +    AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;
    8.26 +
    8.27 +  function_requires< IterableUndirGraphConcept<IterableUndirListGraph> >();
    8.28 +
    8.29 +  return 0;
    8.30 +}