# HG changeset patch
# User deba
# Date 1129286991 0
# Node ID 578d8b2b76c6f8ad6fa86b49dcf0bf4e837f060a
# Parent  674182524bd9981626387c32e110f510d5f3c8fa
Matrixmaps moved to own file

diff -r 674182524bd9 -r 578d8b2b76c6 lemon/concept/matrix_maps.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/concept/matrix_maps.h	Fri Oct 14 10:49:51 2005 +0000
@@ -0,0 +1,205 @@
+/* -*- C++ -*-
+ * lemon/concept/matrix_maps.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, 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_CONCEPT_MATRIX_MAPS_H
+#define LEMON_CONCEPT_MATRIX_MAPS_H
+
+#include <lemon/utility.h>
+#include <lemon/concept_check.h>
+
+///\ingroup concept
+///\file
+///\brief MatrixMap concepts checking classes for testing and documenting.
+
+namespace lemon {
+
+  namespace concept {
+  
+    /// \addtogroup concept
+    /// @{
+
+    /// Readable matrix map concept
+    template <typename K1, typename K2, typename V>
+    class ReadMatrixMap
+    {
+    public:
+      /// Map's first key type.
+      typedef K1 FirstKey;    
+      /// Map's second key type.
+      typedef K2 SecondKey;    
+      /// \brief Map's value type. 
+      /// (The type of objects associated with the pairs of keys).
+      typedef V Value;
+
+      // \bug Value don't need to be default constructible.
+      /// Returns the value associated with a key.
+      Value operator()(const FirstKey&, const SecondKey&) const {
+	return Value();
+      }
+
+      template <typename _ReadMatrixMap>
+      struct Constraints {
+
+	void constraints() {
+	  Value val = m(first_key, second_key);
+	  val = m(first_key, second_key);
+	  typename _ReadMatrixMap::Value own_val = 
+	    m(own_first_key, own_second_key); 
+	  own_val = m(own_first_key, own_second_key);
+	  ignore_unused_variable_warning(val);
+	  ignore_unused_variable_warning(own_val);
+	}
+
+	FirstKey& first_key;
+	SecondKey& second_key;	
+	typename _ReadMatrixMap::FirstKey& own_first_key;
+	typename _ReadMatrixMap::SecondKey& own_second_key;
+	_ReadMatrixMap& m;
+      };
+      
+    };
+
+
+    /// Writable map concept
+    template <typename K1, typename K2, typename V>
+    class WriteMatrixMap {
+    public:
+      /// Map's first key type.
+      typedef K1 FirstKey;    
+      /// Map's second key type.
+      typedef K2 SecondKey;    
+      /// \brief Map's value type. 
+      /// (The type of objects associated with the pairs of keys).
+      typedef V Value;
+
+      /// Sets the value associated with the pair of keys.
+      void set(const FirstKey&, const SecondKey& ,const Value&) {}
+
+      template <typename _WriteMatrixMap>
+      struct Constraints {
+	void constraints() {
+	  // No constraints for constructor.
+	  m.set(first_key, second_key, val);
+	  m.set(own_first_key, own_second_key, own_val);
+	}
+
+	Value& val;
+	typename _WriteMatrixMap::Value own_val;
+	FirstKey& first_key;
+	SecondKey& second_key;
+	typename _WriteMatrixMap::FirstKey& own_first_key;
+	typename _WriteMatrixMap::SecondKey& own_second_key;
+	_WriteMatrixMap& m;
+
+      };
+    };
+
+    ///Read/Writable map concept
+    template<typename K1, typename K2, typename V>
+    class ReadWriteMatrixMap 
+      : public ReadMatrixMap<K1, K2, V>, public WriteMatrixMap<K1, K2, V> {
+    public:
+      /// Map's first key type.
+      typedef K1 FirstKey;    
+      /// Map's second key type.
+      typedef K2 SecondKey;    
+      /// \brief Map's value type. 
+      /// (The type of objects associated with the pairs of keys).
+      typedef V Value;
+
+      /// Returns the value associated with a pair of keys.
+      Value operator()(const FirstKey&, const SecondKey&) const { 
+	return Value(); 
+      }
+      /// Sets the value associated with the pair of keys.
+      void set(const FirstKey&, const SecondKey& ,const Value&) {}
+
+      template<typename _ReadWriteMatrixMap>
+      struct Constraints {
+	void constraints() {
+	  checkConcept<ReadMatrixMap<K1, K2, V>, _ReadWriteMatrixMap >();
+	  checkConcept<WriteMatrixMap<K1, K2, V>, _ReadWriteMatrixMap >();
+	}
+      };
+    };
+  
+  
+    ///Dereferable matrix map concept
+    template<typename K1, typename K2, typename V, typename R, typename CR>
+    class ReferenceMatrixMap : public ReadWriteMatrixMap<K1, K2, V>
+    {
+    public:
+      /// Tag for reference maps.
+      typedef True ReferenceMapTag;
+      /// Map's first key type.
+      typedef K1 FirstKey;    
+      /// Map's second key type.
+      typedef K1 SecondKey;    
+      /// Map's value type. (The type of objects associated with the keys).
+      typedef V Value;
+      /// Map's reference type.
+      typedef R Reference;
+      /// Map's const reference type.
+      typedef CR ConstReference;
+
+    protected:
+      Value tmp;
+    public:
+
+      ///Returns a reference to the value associated to a pair of keys.
+      Reference operator()(const FirstKey&, const SecondKey&) { 
+	return tmp; 
+      }
+      ///Returns a const reference to the value associated to a pair of keys.
+      ConstReference operator()(const FirstKey&, const SecondKey&) const { 
+	return tmp; 
+      }
+      /// Sets the value associated with the pair of keys.
+      void set(const FirstKey&, const SecondKey& ,const Value&) {}
+
+      // \todo rethink this concept
+      template<typename _ReferenceMatrixMap>
+      struct ReferenceMapConcept {
+
+	void constraints() {
+	  checkConcept<ReadWriteMatrixMap, _ReferenceMatrixMap >();
+	  m(first_key, second_key) = val;
+	  val  = m(first_key, second_key);
+	  m(first_key, second_key) = ref;
+	  ref = m(first_key, second_key);
+	  m(own_first_key, own_second_key) = own_val;
+	  own_val  = m(own_first_key, own_second_key);
+	  m(own_first_key, own_second_key) = own_ref;
+	  own_ref = m(own_first_key, own_second_key); 
+	}
+
+	typename _ReferenceMatrixMap::Key& own_first_key;
+	typename _ReferenceMatrixMap::Key& own_second_key;
+	typename _ReferenceMatrixMap::Value& own_val;
+	typename _ReferenceMatrixMap::Reference& own_ref;
+	FirstKey& first_key;
+	SecondKey& second_key;
+	Value& val;
+	Reference& ref;
+	_ReferenceMatrixMap& m;
+      };
+    };
+
+    // @}
+
+  } //namespace concept
+} //namespace lemon
+#endif // LEMON_CONCEPT_MATRIX_MAPS_H
diff -r 674182524bd9 -r 578d8b2b76c6 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Fri Oct 14 10:48:34 2005 +0000
+++ b/lemon/graph_utils.h	Fri Oct 14 10:49:51 2005 +0000
@@ -25,6 +25,7 @@
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
 #include <lemon/maps.h>
+#include <lemon/traits.h>
 #include <lemon/bits/alteration_notifier.h>
 
 ///\ingroup gutils
@@ -400,7 +401,6 @@
     }
   }
 
-
   /// \brief Class to copy a graph.
   ///
   /// Class to copy a graph to an other graph (duplicate a graph). The
@@ -515,6 +515,8 @@
       return edgeRefMap;
     }
 
+    void run() {}
+
   private:
     
     const Source& source;
@@ -542,101 +544,225 @@
     return GraphCopy<Target, Source>(target, source);
   }
 
-  template <typename _Graph, typename _Item>
-  class ItemSetTraits {};
-  
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Node> {
+  /// \brief Class to copy an undirected graph.
+  ///
+  /// Class to copy an undirected graph to an other graph (duplicate a graph).
+  /// The simplest way of using it is through the \c copyUndirGraph() function.
+  template <typename Target, typename Source>
+  class UndirGraphCopy {
+  public: 
+    typedef typename Source::Node Node;
+    typedef typename Source::NodeIt NodeIt;
+    typedef typename Source::Edge Edge;
+    typedef typename Source::EdgeIt EdgeIt;
+    typedef typename Source::UndirEdge UndirEdge;
+    typedef typename Source::UndirEdgeIt UndirEdgeIt;
+
+    typedef typename Source::
+    template NodeMap<typename Target::Node> NodeRefMap;
+    
+    typedef typename Source::
+    template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
+
+  private:
+
+    struct EdgeRefMap {
+      EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
+      typedef typename Source::Edge Key;
+      typedef typename Target::Edge Value;
+
+      Value operator[](const Key& key) {
+	return gc.target.direct(gc.undirEdgeRef[key], 
+				gc.target.direction(key));
+      }
+      
+      UndirGraphCopy& gc;
+    };
+    
   public:
+
+    /// \brief Constructor for the UndirGraphCopy.
+    ///
+    /// It copies the content of the \c _source graph into the
+    /// \c _target graph. It creates also two references, one beetween
+    /// the two nodeset and one beetween the two edgesets.
+    UndirGraphCopy(Target& _target, const Source& _source) 
+      : source(_source), target(_target), 
+	nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
+      for (NodeIt it(source); it != INVALID; ++it) {
+	nodeRefMap[it] = target.addNode();
+      }
+      for (UndirEdgeIt it(source); it != INVALID; ++it) {
+	undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
+					nodeRefMap[source.target(it)]);
+      }
+    }
+
+    /// \brief Copies the node references into the given map.
+    ///
+    /// Copies the node references into the given map.
+    template <typename NodeRef>
+    const UndirGraphCopy& nodeRef(NodeRef& map) const {
+      for (NodeIt it(source); it != INVALID; ++it) {
+	map.set(it, nodeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the node references into the given map.
+    ///
+    /// Reverse and copies the node references into the given map.
+    template <typename NodeRef>
+    const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
+      for (NodeIt it(source); it != INVALID; ++it) {
+	map.set(nodeRefMap[it], it);
+      }
+      return *this;
+    }
+
+    /// \brief Copies the edge references into the given map.
+    ///
+    /// Copies the edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& edgeRef(EdgeRef& map) const {
+      for (EdgeIt it(source); it != INVALID; ++it) {
+	map.set(edgeRefMap[it], it);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the undirected edge references into the 
+    /// given map.
+    ///
+    /// Reverse and copies the undirected edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
+      for (EdgeIt it(source); it != INVALID; ++it) {
+	map.set(it, edgeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Copies the undirected edge references into the given map.
+    ///
+    /// Copies the undirected edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
+      for (UndirEdgeIt it(source); it != INVALID; ++it) {
+	map.set(it, undirEdgeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the undirected edge references into the 
+    /// given map.
+    ///
+    /// Reverse and copies the undirected edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
+      for (UndirEdgeIt it(source); it != INVALID; ++it) {
+	map.set(undirEdgeRefMap[it], it);
+      }
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's node type,
+    /// and the copied map's key type is the source graph's node
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    const UndirGraphCopy& nodeMap(TargetMap& tMap, 
+				  const SourceMap& sMap) const {
+      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's edge type,
+    /// and the copied map's key type is the source graph's edge
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    const UndirGraphCopy& edgeMap(TargetMap& tMap, 
+				  const SourceMap& sMap) const {
+      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's edge type,
+    /// and the copied map's key type is the source graph's edge
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, 
+				  const SourceMap& sMap) const {
+      copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
+      return *this;
+    }
+
+    /// \brief Gives back the stored node references.
+    ///
+    /// Gives back the stored node references.
+    const NodeRefMap& nodeRef() const {
+      return nodeRefMap;
+    }
+
+    /// \brief Gives back the stored edge references.
+    ///
+    /// Gives back the stored edge references.
+    const EdgeRefMap& edgeRef() const {
+      return edgeRefMap;
+    }
+
+    /// \brief Gives back the stored undir edge references.
+    ///
+    /// Gives back the stored undir edge references.
+    const UndirEdgeRefMap& undirEdgeRef() const {
+      return undirEdgeRefMap;
+    }
+
+    void run() {}
+
+  private:
     
-    typedef _Graph Graph;
+    const Source& source;
+    Target& target;
 
-    typedef typename Graph::Node Item;
-    typedef typename Graph::NodeIt ItemIt;
-
-    template <typename _Value>
-    class Map : public Graph::template NodeMap<_Value> {
-    public:
-      typedef typename Graph::template NodeMap<_Value> Parent; 
-      typedef typename Parent::Value Value;
-
-      Map(const Graph& _graph) : Parent(_graph) {}
-      Map(const Graph& _graph, const Value& _value) 
-	: Parent(_graph, _value) {}
-    };
-
+    NodeRefMap nodeRefMap;
+    EdgeRefMap edgeRefMap;
+    UndirEdgeRefMap undirEdgeRefMap;
   };
 
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Edge> {
-  public:
-    
-    typedef _Graph Graph;
+  /// \brief Copy a graph to an other graph.
+  ///
+  /// Copy a graph to an other graph.
+  /// The usage of the function:
+  /// 
+  /// \code
+  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
+  /// \endcode
+  /// 
+  /// After the copy the \c nr map will contain the mapping from the
+  /// source graph's nodes to the target graph's nodes and the \c ecr will
+  /// contain the mapping from the target graph's edges to the source's
+  /// edges.
+  template <typename Target, typename Source>
+  UndirGraphCopy<Target, Source> 
+  copyUndirGraph(Target& target, const Source& source) {
+    return UndirGraphCopy<Target, Source>(target, source);
+  }
 
-    typedef typename Graph::Edge Item;
-    typedef typename Graph::EdgeIt ItemIt;
-
-    template <typename _Value>
-    class Map : public Graph::template EdgeMap<_Value> {
-    public:
-      typedef typename Graph::template EdgeMap<_Value> Parent; 
-      typedef typename Parent::Value Value;
-
-      Map(const Graph& _graph) : Parent(_graph) {}
-      Map(const Graph& _graph, const Value& _value) 
-	: Parent(_graph, _value) {}
-    };
-
-  };
-
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
-  public:
-    
-    typedef _Graph Graph;
-
-    typedef typename Graph::UndirEdge Item;
-    typedef typename Graph::UndirEdgeIt ItemIt;
-
-    template <typename _Value>
-    class Map : public Graph::template UndirEdgeMap<_Value> {
-    public:
-      typedef typename Graph::template UndirEdgeMap<_Value> Parent; 
-      typedef typename Parent::Value Value;
-
-      Map(const Graph& _graph) : Parent(_graph) {}
-      Map(const Graph& _graph, const Value& _value) 
-	: Parent(_graph, _value) {}
-    };
-
-  };
 
   /// @}
 
   /// \addtogroup graph_maps
   /// @{
 
-  template <typename Map, typename Enable = void>
-  struct ReferenceMapTraits {
-    typedef typename Map::Value Value;
-    typedef typename Map::Value& Reference;
-    typedef const typename Map::Value& ConstReference;
-    typedef typename Map::Value* Pointer;
-    typedef const typename Map::Value* ConstPointer;
-  };
-
-  template <typename Map>
-  struct ReferenceMapTraits<
-    Map, 
-    typename enable_if<typename Map::FullTypeTag, void>::type
-  > {
-    typedef typename Map::Value Value;
-    typedef typename Map::Reference Reference;
-    typedef typename Map::ConstReference ConstReference;
-    typedef typename Map::Pointer Pointer;
-    typedef typename Map::ConstPointer ConstPointer;
-  };
-
   /// Provides an immutable and unique id for each item in the graph.
 
   /// The IdMap class provides a unique and immutable id for each item of the
@@ -754,7 +880,7 @@
     /// \brief The getter function of the map.
     ///
     /// It gives back the value associated with the key.
-    const Value operator[](const Key& key) const {
+    Value operator[](const Key& key) const {
       return Map::operator[](key);
     }
 
@@ -1192,234 +1318,6 @@
     return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
   }
 
-  /// \brief Container for store values for each ordered pair of nodes
-  ///
-  /// Container for store values for each ordered pair of nodes.
-  template <typename _Graph, typename _Value>
-  class NodeMatrixMap 
-    : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
-  public:
-    typedef _Graph Graph;
-    typedef typename Graph::Node Node;
-    typedef Node Key;
-    typedef _Value Value;
-
-    /// \brief Creates a node matrix for the given graph
-    ///
-    /// Creates a node matrix for the given graph.
-    NodeMatrixMap(const Graph& _graph) 
-      : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
-
-    /// \brief Creates a node matrix for the given graph
-    ///
-    /// Creates a node matrix for the given graph and assigns each
-    /// initial value to the given parameter.
-    NodeMatrixMap(const Graph& _graph, const Value& _val) 
-      : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
-
-    /// \brief Gives back the value assigned to the \c left - \c right
-    /// ordered pair.
-    ///
-    /// Gives back the value assigned to the \c left - \c right ordered pair.
-    const Value& operator()(const Node& left, const Node& right) const {
-      return values[index(graph.id(left), graph.id(right))];
-    }
-    
-    /// \brief Gives back the value assigned to the \c left - \c right
-    /// ordered pair.
-    ///
-    /// Gives back the value assigned to the \c left - \c right ordered pair.
-    Value& operator()(const Node& left, const Node& right) {
-      return values[index(graph.id(left), graph.id(right))];
-    }
-
-    /// \brief Setter function for the matrix map.
-    ///
-    /// Setter function for the matrix map.
-    void set(const Node& left, const Node& right, const Value& val) {
-      values[index(graph.id(left), graph.id(right))] = val;
-    }
-
-    /// \brief Map for the coloumn view of the matrix
-    ///
-    /// Map for the coloumn view of the matrix.
-    class ColMap : public MapBase<Node, Value> {
-      friend class NodeMatrixMap;
-    private:
-      ColMap(NodeMatrixMap& _matrix, Node _col) 
-	: matrix(_matrix), col(_col) {}
-
-    public:
-      /// \brief Subscription operator
-      ///
-      /// Subscription operator.
-      Value& operator[](Node row) {
-	return matrix(col, row);
-      }
-
-      /// \brief Setter function
-      ///
-      /// Setter function.
-      void set(Node row, const Value& val) {
-	matrix.set(col, row, val);
-      }
-      
-      /// \brief Subscription operator
-      ///
-      /// Subscription operator.
-      const Value& operator[](Node row) const {
-	return matrix(col, row);
-      }
-
-    private:
-      NodeMatrixMap& matrix;
-      Node col;
-    };
-
-    /// \brief Map for the const coloumn view of the matrix
-    ///
-    /// Map for the const coloumn view of the matrix.
-    class ConstColMap : public MapBase<Node, Value> {
-      friend class NodeMatrixMap;
-    private:
-      ConstColMap(const NodeMatrixMap& _matrix, Node _col) 
-	: matrix(_matrix), col(_col) {}
-      
-    public:
-      /// \brief Subscription operator
-      ///
-      /// Subscription operator.
-      const Value& operator[](Node row) const {
-	return matrix(col, row);
-      }
-      
-    private:
-      const NodeMatrixMap& matrix;
-      Node col;
-    };
-
-    /// \brief Map for the row view of the matrix
-    ///
-    /// Map for the row view of the matrix.
-    class RowMap : public MapBase<Node, Value> {
-    public:
-      friend class NodeMatrixMap;
-    private:
-      RowMap(NodeMatrixMap& _matrix, Node _row) 
-	: matrix(_matrix), row(_row) {}
-      
-    public:
-      /// \brief Subscription operator
-      ///
-      /// Subscription operator.
-      Value& operator[](Node col) {
-	return matrix(col, row);
-      }
-
-      /// \brief Setter function
-      ///
-      /// Setter function.
-      void set(Node col, const Value& val) {
-	matrix.set(col, row, val);
-      }
-      
-      /// \brief Subscription operator
-      ///
-      /// Subscription operator.
-      const Value& operator[](Node col) const {
-	return matrix(col, row);
-      }
-
-    private:
-      NodeMatrixMap& matrix;
-      Node row;
-    };
-
-    /// \brief Map for the const row view of the matrix
-    ///
-    /// Map for the row const view of the matrix.
-    class ConstRowMap : public MapBase<Node, Value> {
-    public:
-      friend class NodeMatrixMap;
-    private:
-      ConstRowMap(const NodeMatrixMap& _matrix, Node _row) 
-	: matrix(_matrix), row(_row) {}
-      
-    public:
-      /// \brief Subscription operator
-      ///
-      /// Subscription operator.
-      const Value& operator[](Node col) const {
-	return matrix(col, row);
-      }
-      
-    private:
-      const NodeMatrixMap& matrix;
-      Node row;
-    };
-
-    /// \brief Gives back the column view for the given node
-    ///
-    /// Gives back the column view for the given node
-    ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
-    /// \brief Gives back the column view for the given node
-    ///
-    /// Gives back the column view for the given node
-    ColMap operator[](Node col) { return ColMap(*this, col); }
-
-    /// \brief Gives back the column view for the given node
-    ///
-    /// Gives back the column view for the given node
-    ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
-    /// \brief Gives back the column view for the given node
-    ///
-    /// Gives back the column view for the given node
-    ColMap colMap(Node col) { return ColMap(*this, col); }
-
-    /// \brief Gives back the row view for the given node
-    ///
-    /// Gives back the row view for the given node
-    ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
-    /// \brief Gives back the row view for the given node
-    ///
-    /// Gives back the row view for the given node
-    RowMap rowMap(Node row) { return RowMap(*this, row); }
-
-  protected:
-
-    static int index(int i, int j) {
-      if (i < j) {
-	return j * j + i;
-      } else {
-	return i * i + i + j;
-      }
-    }
-
-    static int size(int s) {
-      return s * s;
-    }
-
-    void add(const Node& node) {
-      if (size(graph.id(node) + 1) >= (int)values.size()) {
-	values.resize(size(graph.id(node) + 1));	
-      }
-    }
-
-    void erase(const Node&) {}
-
-    void build() {
-      values.resize(size(graph.maxId(Node()) + 1));
-    }
-
-    void clear() {
-      values.clear();
-    }   
-    
-  private:
-    const Graph& graph;
-    std::vector<Value> values;
-  };
-
   /// \brief Map of the node in-degrees.
   ///
   /// This map returns the in-degree of a node. Once it is constructed,
@@ -1427,14 +1325,6 @@
   /// in constant time. On the other hand, the values are updated automatically
   /// whenever the graph changes.
   ///
-  /// \warning Besides addNode() and addEdge(), a graph structure may provide
-  /// alternative ways to mogify the graph. The correct behavior of InDegMap
-  /// is not guarantied if these additional featureas are used. For example
-  /// the funstions \ref ListGraph::changeSource() "changeSource()",
-  /// \ref ListGraph::changeTarget() "changeTarget()" and
-  /// \ref ListGraph::reverseEdge() "reverseEdge()"
-  /// of \ref ListGraph will \e not update the degree values correctly.
-  ///
   /// \sa OutDegMap
 
   template <typename _Graph>
@@ -1501,6 +1391,13 @@
       --deg[graph.target(edge)];
     }
 
+    virtual void signalChange(const Edge& edge) {
+      erase(edge);
+    }
+
+    virtual void commitChange(const Edge& edge) {
+      add(edge);
+    }
 
     virtual void build() {
       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
@@ -1526,14 +1423,6 @@
   /// in constant time. On the other hand, the values are updated automatically
   /// whenever the graph changes.
   ///
-  /// \warning Besides addNode() and addEdge(), a graph structure may provide
-  /// alternative ways to mogify the graph. The correct behavior of OutDegMap
-  /// is not guarantied if these additional featureas are used. For example
-  /// the funstions \ref ListGraph::changeSource() "changeSource()",
-  /// \ref ListGraph::changeTarget() "changeTarget()" and
-  /// \ref ListGraph::reverseEdge() "reverseEdge()"
-  /// of \ref ListGraph will \e not update the degree values correctly.
-  ///
   /// \sa InDegMap
 
   template <typename _Graph>
@@ -1600,6 +1489,14 @@
       --deg[graph.source(edge)];
     }
 
+    virtual void signalChange(const Edge& edge) {
+      erase(edge);
+    }
+
+    virtual void commitChange(const Edge& edge) {
+      add(edge);
+    }
+
 
     virtual void build() {
       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
@@ -1618,47 +1515,6 @@
     AutoNodeMap deg;
   };
 
-  // Indicators for the tags
-
-  template <typename Graph, typename Enable = void>
-  struct NodeNumTagIndicator {
-    static const bool value = false;
-  };
-
-  template <typename Graph>
-  struct NodeNumTagIndicator<
-    Graph, 
-    typename enable_if<typename Graph::NodeNumTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
-  template <typename Graph, typename Enable = void>
-  struct EdgeNumTagIndicator {
-    static const bool value = false;
-  };
-
-  template <typename Graph>
-  struct EdgeNumTagIndicator<
-    Graph, 
-    typename enable_if<typename Graph::EdgeNumTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
-  template <typename Graph, typename Enable = void>
-  struct FindEdgeTagIndicator {
-    static const bool value = false;
-  };
-
-  template <typename Graph>
-  struct FindEdgeTagIndicator<
-    Graph, 
-    typename enable_if<typename Graph::FindEdgeTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
 
   /// @}
 
diff -r 674182524bd9 -r 578d8b2b76c6 lemon/matrix_maps.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/matrix_maps.h	Fri Oct 14 10:49:51 2005 +0000
@@ -0,0 +1,428 @@
+/* -*- C++ -*-
+ * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, 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_MATRIX_MAPS_H
+#define LEMON_MATRIX_MAPS_H
+
+
+#include <vector>
+#include <lemon/utility.h>
+#include <lemon/maps.h>
+
+
+/// \file
+/// \ingroup maps
+/// \brief Maps indexed with pairs of items.
+///
+/// \todo This file has the same name as the concept file in concept/,
+///  and this is not easily detectable in docs...
+namespace lemon {
+
+  /// \brief Map for the coloumn view of the matrix
+  ///
+  /// Map for the coloumn view of the matrix.
+  template <typename _MatrixMap>
+  class MatrixColMap : public MapTraits<_MatrixMap> {
+  public:
+    typedef _MatrixMap MatrixMap;
+    typedef typename MatrixMap::SecondKey Key;
+    typedef typename MatrixMap::Value Value;
+
+
+    MatrixColMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _col) 
+      : matrix(_matrix), col(_col) {}
+
+    /// \brief Subscription operator
+    ///
+    /// Subscription operator.
+    typename MapTraits<MatrixMap>::ReturnValue
+    operator[](Key row) {
+      return matrix(col, row);
+    }
+
+    /// \brief Setter function
+    ///
+    /// Setter function.
+    void set(Key row, const Value& val) {
+      matrix.set(col, row, val);
+    }
+      
+    /// \brief Subscription operator
+    ///
+    /// Subscription operator.
+    typename MapTraits<MatrixMap>::ConstReturnValue
+    operator[](Key row) const {
+      return matrix(col, row);
+    }
+
+  private:
+    MatrixMap& matrix;
+    typename MatrixMap::FirstKey col;
+  };
+
+  /// \brief Map for the coloumn view of the matrix
+  ///
+  /// Map for the coloumn view of the matrix.
+  template <typename _MatrixMap>
+  class ConstMatrixColMap : public MapTraits<_MatrixMap> {
+  public:
+    typedef _MatrixMap MatrixMap;
+    typedef typename MatrixMap::SecondKey Key;
+    typedef typename MatrixMap::Value Value;
+
+
+    ConstMatrixColMap(const MatrixMap& _matrix, 
+		      typename MatrixMap::FirstKey _col) 
+      : matrix(_matrix), col(_col) {}
+
+    /// \brief Subscription operator
+    ///
+    /// Subscription operator.
+    typename MapTraits<MatrixMap>::ConstReturnValue
+    operator[](Key row) const {
+      return matrix(col, row);
+    }
+
+  private:
+    const MatrixMap& matrix;
+    typename MatrixMap::FirstKey col;
+  };
+
+  /// \brief Gives back a coloumn view of the matrix map
+  ///
+  /// Gives back a coloumn view of the matrix map.
+  template <typename MatrixMap>
+  MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
+				       typename MatrixMap::FirstKey col) {
+    return MatrixColMap<MatrixMap>(matrixMap, col);
+  }
+
+  template <typename MatrixMap>
+  ConstMatrixColMap<MatrixMap>
+  matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey col) {
+    return ConstMatrixColMap<MatrixMap>(matrixMap, col);
+  }
+
+  /// \brief Map for the row view of the matrix
+  ///
+  /// Map for the row view of the matrix.
+  template <typename _MatrixMap>
+  class MatrixRowMap : public MapTraits<_MatrixMap> {
+  public:
+    typedef _MatrixMap MatrixMap;
+    typedef typename MatrixMap::FirstKey Key;
+    typedef typename MatrixMap::Value Value;
+
+    MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _row) 
+      : matrix(_matrix), row(_row) {}
+
+    /// \brief Subscription operator
+    ///
+    /// Subscription operator.
+    typename MapTraits<MatrixMap>::ReturnValue
+    operator[](Key col) {
+      return matrix(col, row);
+    }
+
+    /// \brief Setter function
+    ///
+    /// Setter function.
+    void set(Key col, const Value& val) {
+      matrix.set(col, row, val);
+    }
+      
+    /// \brief Subscription operator
+    ///
+    /// Subscription operator.
+    typename MapTraits<MatrixMap>::ConstReturnValue
+    operator[](Key col) const {
+      return matrix(col, row);
+    }
+
+  private:
+    MatrixMap& matrix;
+    typename MatrixMap::SecondKey row;
+  };
+
+  /// \brief Map for the row view of the matrix
+  ///
+  /// Map for the row view of the matrix.
+  template <typename _MatrixMap>
+  class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
+  public:
+    typedef _MatrixMap MatrixMap;
+    typedef typename MatrixMap::FirstKey Key;
+    typedef typename MatrixMap::Value Value;
+
+    ConstMatrixRowMap(const MatrixMap& _matrix, 
+		      typename MatrixMap::SecondKey _row) 
+      : matrix(_matrix), row(_row) {}
+
+    /// \brief Subscription operator
+    ///
+    /// Subscription operator.
+    typename MapTraits<MatrixMap>::ConstReturnValue
+    operator[](Key col) const {
+      return matrix(col, row);
+    }
+
+  private:
+    const MatrixMap& matrix;
+    typename MatrixMap::SecondKey row;
+  };
+
+  /// \brief Gives back a row view of the matrix map
+  ///
+  /// Gives back a row view of the matrix map.
+  template <typename MatrixMap>
+  MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
+				       typename MatrixMap::SecondKey row) {
+    return MatrixRowMap<MatrixMap>(matrixMap, row);
+  }
+
+  template <typename MatrixMap>
+  ConstMatrixRowMap<MatrixMap> 
+  matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey row) {
+    return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
+  }
+
+  /// \brief Container for store values for each ordered pair of graph items
+  ///
+  /// This data structure can strore for each pairs of the same item
+  /// type a value. It increase the size of the container when the 
+  /// associated graph modified, so it updated automaticly whenever
+  /// it is needed.
+  template <typename _Graph, typename _Item, typename _Value>
+  class DynamicMatrixMap 
+    : protected AlterationNotifier<_Item>::ObserverBase {
+  public:
+    typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
+
+    typedef _Graph Graph;
+    typedef _Item Key;
+
+    typedef _Item FirstKey;
+    typedef _Item SecondKey;
+    typedef _Value Value;
+
+    typedef True ReferenceMapTag;
+
+  private:
+		
+    typedef std::vector<Value> Container;
+
+  public:
+
+    typedef typename Container::reference Reference;
+    typedef typename Container::const_reference ConstReference;
+
+    /// \brief Creates an item matrix for the given graph
+    ///
+    /// Creates an item matrix for the given graph.
+    DynamicMatrixMap(const Graph& _graph) 
+      : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
+      Parent::attach(graph.getNotifier(Key()));
+    }
+
+    /// \brief Creates an item matrix for the given graph
+    ///
+    /// Creates an item matrix for the given graph and assigns for each
+    /// pairs of keys the given parameter.
+    DynamicMatrixMap(const Graph& _graph, const Value& _val) 
+      : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
+      Parent::attach(graph.getNotifier(Key()));
+    }
+
+    ~DynamicMatrixMap() {
+      if (Parent::attached()) {
+	Parent::detach();
+      }
+    }
+
+    /// \brief Gives back the value assigned to the \c first - \c second
+    /// ordered pair.
+    ///
+    /// Gives back the value assigned to the \c first - \c second ordered pair.
+    ConstReference operator()(const Key& first, const Key& second) const {
+      return values[index(graph.id(first), graph.id(second))];
+    }
+    
+    /// \brief Gives back the value assigned to the \c first - \c second
+    /// ordered pair.
+    ///
+    /// Gives back the value assigned to the \c first - \c second ordered pair.
+    Reference operator()(const Key& first, const Key& second) {
+      return values[index(graph.id(first), graph.id(second))];
+    }
+
+    /// \brief Setter function for the matrix map.
+    ///
+    /// Setter function for the matrix map.
+    void set(const Key& first, const Key& second, const Value& val) {
+      values[index(graph.id(first), graph.id(second))] = val;
+    }
+
+  protected:
+
+    static int index(int i, int j) {
+      if (i < j) {
+	return j * j + i;
+      } else {
+	return i * i + i + j;
+      }
+    }
+
+    static int size(int s) {
+      return s * s;
+    }
+
+    virtual void add(const Key& key) {
+      if (size(graph.id(key) + 1) >= (int)values.size()) {
+	values.resize(size(graph.id(key) + 1));	
+      }
+    }
+
+    virtual void erase(const Key&) {}
+
+    virtual void build() {
+      values.resize(size(graph.maxId(Key()) + 1));
+    }
+
+    virtual void clear() {
+      values.clear();
+    }   
+    
+  private:
+    const Graph& graph;
+    std::vector<Value> values;
+  };
+
+  /// \brief Container for store values for each unordered pair of graph items
+  ///
+  /// This data structure can strore for each pairs of the same item
+  /// type a value. It increase the size of the container when the 
+  /// associated graph modified, so it updated automaticly whenever
+  /// it is needed. 
+  template <typename _Graph, typename _Item, typename _Value>
+  class DynamicSymMatrixMap 
+    : protected AlterationNotifier<_Item>::ObserverBase {
+  public:
+    typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
+
+    typedef _Graph Graph;
+    typedef _Item Key;
+
+    typedef _Item FirstKey;
+    typedef _Item SecondKey;
+    typedef _Value Value;
+
+    typedef True ReferenceMapTag;
+
+  private:
+		
+    typedef std::vector<Value> Container;
+
+  public:
+
+    typedef typename Container::reference Reference;
+    typedef typename Container::const_reference ConstReference;
+
+    /// \brief Creates an item matrix for the given graph
+    ///
+    /// Creates an item matrix for the given graph.
+    DynamicSymMatrixMap(const Graph& _graph) 
+      : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
+      Parent::attach(graph.getNotifier(Key()));
+    }
+
+    /// \brief Creates an item matrix for the given graph
+    ///
+    /// Creates an item matrix for the given graph and assigns for each
+    /// pairs of keys the given parameter.
+    DynamicSymMatrixMap(const Graph& _graph, const Value& _val) 
+      : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
+      Parent::attach(graph.getNotifier(Key()));
+    }
+
+    ~DynamicSymMatrixMap() {
+      if (Parent::attached()) {
+	Parent::detach();
+      }
+    }
+
+    /// \brief Gives back the value assigned to the \c first - \c second
+    /// unordered pair.
+    ///
+    /// Gives back the value assigned to the \c first - \c second unordered 
+    /// pair.
+    ConstReference operator()(const Key& first, const Key& second) const {
+      return values[index(graph.id(first), graph.id(second))];
+    }
+    
+    /// \brief Gives back the value assigned to the \c first - \c second
+    /// unordered pair.
+    ///
+    /// Gives back the value assigned to the \c first - \c second unordered 
+    /// pair.
+    Reference operator()(const Key& first, const Key& second) {
+      return values[index(graph.id(first), graph.id(second))];
+    }
+
+    /// \brief Setter function for the matrix map.
+    ///
+    /// Setter function for the matrix map.
+    void set(const Key& first, const Key& second, const Value& val) {
+      values[index(graph.id(first), graph.id(second))] = val;
+    }
+
+  protected:
+
+    static int index(int i, int j) {
+      if (i < j) {
+	return j * (j + 1) / 2 + i;
+      } else {
+	return i * (i + 1) / 2 + j;
+      }
+    }
+
+    static int size(int s) {
+      return s * (s + 1) / 2;
+    }
+
+    virtual void add(const Key& key) {
+      if (size(graph.id(key) + 1) >= (int)values.size()) {
+	values.resize(size(graph.id(key) + 1));	
+      }
+    }
+
+    virtual void erase(const Key&) {}
+
+    virtual void build() {
+      values.resize(size(graph.maxId(Key()) + 1));
+    }
+
+    virtual void clear() {
+      values.clear();
+    }   
+    
+  private:
+    const Graph& graph;
+    std::vector<Value> values;
+  };
+
+}
+
+#endif