# HG changeset patch
# User klao
# Date 1099614709 0
# Node ID 1a770e9f80b274e49d51de758a4460adbf2404b3
# Parent  289d80c33f04b70a1ed3fa3f95daf59eed864d8e
Undirect graph implementation.
Not yet done, untested.

diff -r 289d80c33f04 -r 1a770e9f80b2 src/lemon/Makefile.am
--- a/src/lemon/Makefile.am	Thu Nov 04 22:04:51 2004 +0000
+++ b/src/lemon/Makefile.am	Fri Nov 05 00:31:49 2004 +0000
@@ -33,11 +33,13 @@
 	idmappable_graph_extender.h				   	\
 	extendable_graph_extender.h					\
 	clearable_graph_extender.h					\
-	erasable_graph_extender.h
+	erasable_graph_extender.h					\
+	undir_graph_extender.h
 
 noinst_HEADERS =							\
 	concept/graph.h							\
 	concept/graph_component.h					\
+	concept/undir_graph.h						\
 	concept/sym_graph.h						\
 	concept/maps.h							\
 	concept/path.h
diff -r 289d80c33f04 -r 1a770e9f80b2 src/lemon/alteration_observer_registry.h
--- a/src/lemon/alteration_observer_registry.h	Thu Nov 04 22:04:51 2004 +0000
+++ b/src/lemon/alteration_observer_registry.h	Fri Nov 05 00:31:49 2004 +0000
@@ -278,16 +278,22 @@
   };
 
 
-  /// Class to extend a graph functionality with the possibility of alteration observing.
-
-  /// AlterableGraphExtender extends the _Base graphs functionality with the possibility of 
-  /// alteration observing. It defines two observer registrys for the nodes and mapes.
+  /// \brief Class to extend a graph with the functionality of alteration
+  /// observing.
+  ///
+  /// AlterableGraphExtender extends the _Base graphs functionality with
+  /// the possibility of alteration observing. It defines two observer
+  /// registrys for the nodes and mapes.
+  /// 
+  /// \todo Document what "alteration observing" is. And probably find a
+  /// better (shorter) name.
   ///
   /// \param _Base is the base class to extend.
   ///
   /// \pre _Base is conform to the BaseGraphComponent concept.
   ///
-  /// \post AlterableGraphExtender<_Base> is conform to the AlterableGraphComponent concept.
+  /// \post AlterableGraphExtender<_Base> is conform to the
+  /// AlterableGraphComponent concept.
   ///
   /// \author Balazs Dezso
 
@@ -301,9 +307,9 @@
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
 
+    /// The edge observer registry.
+    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
     /// The node observer registry.
-    typedef AlterationObserverRegistry<Edge> EdgeObserverRegistry;
-    /// The edge observer registry.
     typedef AlterationObserverRegistry<Node> NodeObserverRegistry;
 
 
@@ -330,6 +336,42 @@
     
   };
 
+  /// \brief Class to extend an undirected graph with the functionality of
+  /// alteration observing.
+  ///
+  /// \todo Document.
+  ///
+  /// \sa AlterableGraphExtender
+  ///
+  /// \bug This should be done some other way. Possibilities: template
+  /// specialization (not very easy, if at all possible); some kind of
+  /// enable_if boost technique?
+
+  template <typename _Base> 
+  class AlterableUndirGraphExtender
+    : public AlterableGraphExtender<_Base> {
+  public:
+
+    typedef AlterableUndirGraphExtender Graph;
+    typedef AlterableGraphExtender<_Base> Parent;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    /// The edge observer registry.
+    typedef AlterationObserverRegistry<UndirEdge> UndirEdgeObserverRegistry;
+
+  protected:
+
+    mutable UndirEdgeObserverRegistry undir_edge_observers;
+
+    UndirEdgeObserverRegistry& getUndirEdgeObserverRegistry() const {
+      return undir_edge_observers;
+    }
+
+    ~AlterableUndirGraphExtender() {
+      undir_edge_observers.clear();
+    }
+  };
   
 /// @}
   
diff -r 289d80c33f04 -r 1a770e9f80b2 src/lemon/concept/graph_component.h
--- a/src/lemon/concept/graph_component.h	Thu Nov 04 22:04:51 2004 +0000
+++ b/src/lemon/concept/graph_component.h	Fri Nov 05 00:31:49 2004 +0000
@@ -263,15 +263,14 @@
 	function_requires< GraphItemConcept<Node> >();
 	function_requires< GraphItemConcept<Edge> >();
 	{
-	  const Graph& const_graph = graph;
 	  Node n;
 	  Edge e;
-	  n = const_graph.tail(e);
-	  n = const_graph.head(e);
+	  n = graph.tail(e);
+	  n = graph.head(e);
 	}      
       }
       
-      Graph& graph;
+      const Graph& graph;
     };
 
     /// An empty iterable base graph class.
@@ -645,7 +644,6 @@
     
     template <typename Graph> 
     struct IterableGraphComponentConcept {
-
       void constraints() {
   	function_requires< BaseIterableGraphComponentConcept<Graph> >();
 
@@ -661,7 +659,6 @@
 	function_requires< GraphIncIteratorConcept<OutEdgeIt, Graph> >();
 	function_requires< GraphIncIteratorConcept<InEdgeIt, Graph> >();
       }
-      Graph& graph;
     };
 
 
diff -r 289d80c33f04 -r 1a770e9f80b2 src/lemon/concept/undir_graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/concept/undir_graph.h	Fri Nov 05 00:31:49 2004 +0000
@@ -0,0 +1,78 @@
+/* -*- C++ -*-
+ *
+ * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic
+ * C++ optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
+ * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
+ * EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+///\ingroup concept
+///\file
+///\brief Undirected graphs and components of.
+
+
+#ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
+#define LEMON_CONCEPT_UNDIR_GRAPH_H
+
+#include <lemon/concept/graph_component.h>
+
+namespace lemon {
+  namespace concept {
+
+    /// \todo to be done
+    class BaseIterableUndirGraph;
+
+    template <typename Graph>
+    struct BaseIterableUndirGraphConcept {
+      typedef typename Graph::UndirEdge UndirEdge;
+      typedef typename Graph::Edge Edge;
+      typedef typename Graph::Node Node;
+      void constraints() {
+	function_requires< BaseIterableGraphComponentConcept<Graph> >();
+	function_requires< GraphItemConcept<UndirEdge> >();
+
+	/// \bug this should be base_and_derived:
+	UndirEdge ue = e;
+	ue = e;
+
+	Node n;
+	n = graph.head(ue);
+	n = graph.tail(ue);
+
+	graph.first(ue);
+	graph.next(ue);
+      }
+      const Graph &graph;
+      Edge e;
+    };
+
+    template <typename Graph>
+    struct IterableUndirGraphConcept {
+      void constraints() {
+	function_requires< BaseIterableUndirGraphConcept<Graph> > ();
+	function_requires< IterableGraphComponentConcept<Graph> > ();
+
+	typedef typename Graph::UndirEdge UndirEdge;
+	typedef typename Graph::UndirEdgeIt UndirEdgeIt;
+
+	function_requires<
+	  GraphIteratorConcept<UndirEdgeIt, Graph, UndirEdge> >();
+      }
+    };
+
+  }
+
+}
+
+#endif
diff -r 289d80c33f04 -r 1a770e9f80b2 src/lemon/iterable_graph_extender.h
--- a/src/lemon/iterable_graph_extender.h	Thu Nov 04 22:04:51 2004 +0000
+++ b/src/lemon/iterable_graph_extender.h	Fri Nov 05 00:31:49 2004 +0000
@@ -8,12 +8,11 @@
   
   template <typename _Base>
   class IterableGraphExtender : public _Base {
+  public:
 
     typedef _Base Parent;
     typedef IterableGraphExtender<_Base> Graph;
 
-  public:
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
 
@@ -26,7 +25,7 @@
 
       NodeIt(Invalid i) : Node(i) { }
 
-      explicit NodeIt(const Graph& _graph) : Node(), graph(&_graph) {
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
 	_graph.first(*static_cast<Node*>(this));
       }
 
@@ -49,7 +48,7 @@
 
       EdgeIt(Invalid i) : Edge(i) { }
 
-      explicit EdgeIt(const Graph& _graph) : Edge(), graph(&_graph) {
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
 	_graph.first(*static_cast<Edge*>(this));
       }
 
@@ -73,7 +72,7 @@
       OutEdgeIt(Invalid i) : Edge(i) { }
 
       OutEdgeIt(const Graph& _graph, const Node& node) 
-	: Edge(), graph(&_graph) {
+	: graph(&_graph) {
 	_graph.firstOut(*this, node);
       }
 
@@ -97,7 +96,7 @@
       InEdgeIt(Invalid i) : Edge(i) { }
 
       InEdgeIt(const Graph& _graph, const Node& node) 
-	: Edge(), graph(&_graph) {
+	: graph(&_graph) {
 	_graph.firstIn(*this, node);
       }
 
@@ -126,6 +125,39 @@
 
   };
   
+  template <typename _Base>
+  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
+  public:
+
+    typedef IterableGraphExtender<_Base> Parent;
+    typedef IterableUndirGraphExtender<_Base> Graph;
+
+    typedef typename Parent::UndirEdge UndirEdge;
+
+    class UndirEdgeIt : public UndirEdge { 
+      const Graph* graph;
+    public:
+
+      UndirEdgeIt() { }
+
+      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
+
+      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
+	_graph.first(*static_cast<UndirEdge*>(this));
+      }
+
+      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : 
+	UndirEdge(e), graph(&_graph) { }
+
+      UndirEdgeIt& operator++() { 
+	graph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+  };
 }
 
 #endif // LEMON_GRAPH_EXTENDER_H
diff -r 289d80c33f04 -r 1a770e9f80b2 src/lemon/undir_graph_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/undir_graph_extender.h	Fri Nov 05 00:31:49 2004 +0000
@@ -0,0 +1,193 @@
+/* -*- C++ -*-
+ *
+ * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
+ * optimization library
+ *
+ * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
+ * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
+ * EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
+#define LEMON_UNDIR_GRAPH_EXTENDER_H
+
+#include <lemon/invalid.h>
+
+namespace lemon {
+
+  template <typename _Base>
+  class UndirGraphExtender : public _Base {
+    typedef _Base Parent;
+    typedef UndirGraphExtender Graph;
+
+  public:
+
+    typedef typename Parent::Edge UndirEdge;
+    typedef typename Parent::Node Node;
+
+    class Edge : public UndirEdge {
+      friend class Graph;
+
+    protected:
+      // FIXME: Marci use opposite logic in his graph wrappers. It would
+      // be reasonable to syncronize...
+      bool forward;
+
+    public:
+      Edge() {}
+      /// Construct a direct edge from undirect edge and a direction.
+      Edge(const UndirEdge &ue, bool _forward) :
+	UndirEdge(ue), forward(_forward) {}
+      /// Invalid edge constructor
+      Edge(Invalid i) : UndirEdge(i), forward(false) {}
+
+      bool operator==(const Edge &that) const {
+	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
+      }
+      bool operator!=(const Edge &that) const {
+	return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
+      }
+      bool operator<(const Edge &that) const {
+	return forward<that.forward ||
+	  (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
+      }
+    };
+
+
+    /// \brief Returns the Edge of opposite direction.
+    ///
+    /// \bug Is this a good name for this? Or "reverse" is better?
+    Edge opposite(const Edge &e) const {
+      return Edge(e,!e.forward);
+    }
+
+    /// Tail of the given Edge.
+    Node tail(const Edge &e) const {
+      return e.forward ? Parent::tail(e) : Parent::head(e);
+    }
+
+    /// \todo Shouldn't the "tail" of an undirected edge be called "aNode"
+    /// or something???
+    using Parent::tail;
+
+    /// Head of the given Edge.
+    Node head(const Edge &e) const {
+      return e.forward ? Parent::head(e) : Parent::tail(e);
+    }
+
+    /// \todo Shouldn't the "head" of an undirected edge be called "bNode"
+    /// or something???
+    using Parent::head;
+
+    /// Returns whether the given directed edge is same orientation as the
+    /// corresponding undirected edge.
+    ///
+    /// \todo reference to the corresponding point of the undirected graph
+    /// concept. "What does the direction of an undirected edge mean?"
+    bool forward(const Edge &e) const { return e.forward; }
+
+    Node oppsiteNode(const Node &n, const Edge &e) const {
+      if( n == Parent::tail(e))
+	return Parent::head(e);
+      else if( n == Parent::head(e))
+	return Parent::tail(e);
+      else
+	return INVALID;
+    }
+
+
+    using Parent::first;
+    void first(Edge &e) const {
+      Parent::first(e);
+      e.forward=true;
+    }
+
+    using Parent::next;
+    void next(Edge &e) const {
+      if( e.forward ) {
+	e.forward = false;
+      }
+      else {
+	Parent::next(e);
+	e.forward = true;
+      }
+    }
+
+    void firstOut(Edge &e, const Node &n) const {
+      Parent::firstOut(e,n);
+      if( UndirEdge(e) != INVALID ) {
+	e.forward = true;
+      }
+      else {
+	Parent::firstIn(e,n);
+	e.forward = false;
+      }
+    }
+    void firstIn(Edge &e, const Node &n) const {
+      Parent::firstIn(e,n);
+      if( UndirEdge(e) != INVALID ) {
+	e.forward = true;
+      }
+      else {
+	Parent::firstOut(e,n);
+	e.forward = false;
+      }
+    }
+
+    void nextOut(Edge &e) const {
+      if( e.forward ) {
+	Parent::nextOut(e);
+	if( UndirEdge(e) == INVALID ) {
+	  Parent::firstIn(e, Parent::tail(e));
+	  e.forward = false;
+	}
+      }
+      else {
+	Parent::nextIn(e);
+      }
+    }
+    void nextIn(Edge &e) const {
+      if( e.forward ) {
+	Parent::nextIn(e);
+	if( UndirEdge(e) == INVALID ) {
+	  Parent::firstOut(e, Parent::head(e));
+	  e.forward = false;
+	}
+      }
+      else {
+	Parent::nextOut(e);
+      }
+    }
+
+    // Miscellaneous stuff:
+
+    /// \todo these methods (id, maxEdgeId) should be moved into separate
+    /// Extender
+
+    using Parent::id;
+
+    int id(const Edge &e) const {
+      return 2*Parent::id(e) + int(e.forward);
+    }
+
+    int maxEdgeId() const {
+      return 2*Parent::maxEdgeId() + 1;
+    }
+    int maxUndirEdgeId() const {
+      return Parent::maxEdgeId();
+    }
+
+  };
+
+}
+
+#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
diff -r 289d80c33f04 -r 1a770e9f80b2 src/test/Makefile.am
--- a/src/test/Makefile.am	Thu Nov 04 22:04:51 2004 +0000
+++ b/src/test/Makefile.am	Fri Nov 05 00:31:49 2004 +0000
@@ -24,6 +24,7 @@
 	test_tools_pass \
 	time_measure_test \
 	unionfind_test \
+	undir_graph_test \
 	xy_test
 
 TESTS = $(check_PROGRAMS)
@@ -45,4 +46,5 @@
 test_tools_pass_SOURCES = test_tools_pass.cc
 unionfind_test_SOURCES = unionfind_test.cc
 xy_test_SOURCES = xy_test.cc
+undir_graph_test_SOURCES = undir_graph_test.cc
 
diff -r 289d80c33f04 -r 1a770e9f80b2 src/test/undir_graph_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/undir_graph_test.cc	Fri Nov 05 00:31:49 2004 +0000
@@ -0,0 +1,27 @@
+// -*- C++ -*-
+
+#include <lemon/undir_graph_extender.h>
+#include <lemon/concept/undir_graph.h>
+#include <lemon/list_graph.h>
+#include <lemon/smart_graph.h>
+#include <lemon/full_graph.h>
+
+#include "test_tools.h"
+
+
+using namespace lemon;
+using namespace lemon::concept;
+
+
+int main() {
+  typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
+
+  function_requires< BaseIterableUndirGraphConcept<UndirListGraphBase> >();
+
+  typedef IterableUndirGraphExtender<
+    AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;
+
+  function_requires< IterableUndirGraphConcept<IterableUndirListGraph> >();
+
+  return 0;
+}