# HG changeset patch
# User deba
# Date 1128086128 0
# Node ID 269f0cbfbcc80c748f32d98fb2f7635171590252
# Parent  a34203867181d4767a5a329dc0b0164ac257765f
Improving GridGraph and HyperCubeGraph

diff -r a34203867181 -r 269f0cbfbcc8 demo/grid_graph_demo.cc
--- a/demo/grid_graph_demo.cc	Fri Sep 30 13:13:42 2005 +0000
+++ b/demo/grid_graph_demo.cc	Fri Sep 30 13:15:28 2005 +0000
@@ -41,28 +41,21 @@
   std::cout << "The length of shortest path: " << 
     bfs.run(start, stop) << std::endl;
 
-  GridGraph::NodeMap<xy<double> > coord(graph);
-  for (int i = 0; i < graph.width(); ++i) {
-    for (int j = 0; j < graph.height(); ++j) {
-      coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
-    }
-  }
-  
-  FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
+  FilteredGraph::EdgeMap<bool> path(filtered, false);
   
   for (GridGraph::Node node = stop; 
        node != start; node = bfs.predNode(node)) {
-    color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
+    path[bfs.pred(node)] = true;
   }
   
   graphToEps(filtered, "grid_graph.eps").scaleToA4().
     title("Grid graph").
     copyright("(C) 2005 LEMON Project").
-    coords(coord).
+    coords(scaleMap(indexMap(graph), 10)).
     enableParallel().
-    nodeScale(.45).
+    nodeScale(0.5).
     drawArrows().
-    edgeColors(color).
+    edgeColors(composeMap(ColorSet(), path)).
     run();
   
   std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
diff -r a34203867181 -r 269f0cbfbcc8 lemon/Makefile.am
--- a/lemon/Makefile.am	Fri Sep 30 13:13:42 2005 +0000
+++ b/lemon/Makefile.am	Fri Sep 30 13:15:28 2005 +0000
@@ -34,6 +34,7 @@
 	graph_adaptor.h \
 	graph_utils.h \
 	graph_to_eps.h \
+	hypercube_graph.h \
 	invalid.h \
 	iterable_maps.h \
 	kruskal.h \
diff -r a34203867181 -r 269f0cbfbcc8 lemon/grid_graph.h
--- a/lemon/grid_graph.h	Fri Sep 30 13:13:42 2005 +0000
+++ b/lemon/grid_graph.h	Fri Sep 30 13:15:28 2005 +0000
@@ -27,8 +27,21 @@
 
 #include <lemon/bits/undir_graph_extender.h>
 
+#include <lemon/xy.h>
+
+///\ingroup graphs
+///\file
+///\brief GridGraph class.
+
 namespace lemon {
 
+  /// \brief Base graph for GridGraph.
+  ///
+  /// Base graph for grid graph. It describes some member functions
+  /// which can be used in the GridGraph.
+  ///
+  /// \warning Always use the GridGraph instead of this.
+  /// \see GridGraph
   class GridGraphBase {
 
   public:
@@ -356,9 +369,91 @@
   /// "Undirected Graph" concept.
   ///
   /// \author Balazs Dezso
+  /// \see GridGraphBase
   class GridGraph : public ExtendedGridGraphBase {
   public:
-    
+
+    /// \brief Map to get the indices of the nodes as xy<int>.
+    ///
+    /// Map to get the indices of the nodes as xy<int>.
+    class IndexMap {
+    public:
+      typedef True NeedCopy;
+      /// \brief The key type of the map
+      typedef GridGraph::Node Key;
+      /// \brief The value type of the map
+      typedef xy<int> Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor
+      IndexMap(const GridGraph& _graph) : graph(_graph) {}
+
+      /// \brief The subscript operator
+      ///
+      /// The subscript operator.
+      Value operator[](Key key) const {
+	return xy<int>(graph.row(key), graph.col(key));
+      }
+
+    private:
+      const GridGraph& graph;
+    };
+
+    /// \brief Map to get the row of the nodes.
+    ///
+    /// Map to get the row of the nodes.
+    class RowMap {
+    public:
+      typedef True NeedCopy;
+      /// \brief The key type of the map
+      typedef GridGraph::Node Key;
+      /// \brief The value type of the map
+      typedef int Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor
+      RowMap(const GridGraph& _graph) : graph(_graph) {}
+
+      /// \brief The subscript operator
+      ///
+      /// The subscript operator.
+      Value operator[](Key key) const {
+	return graph.row(key);
+      }
+
+    private:
+      const GridGraph& graph;
+    };
+
+    /// \brief Map to get the column of the nodes.
+    ///
+    /// Map to get the column of the nodes.
+    class ColMap {
+    public:
+      typedef True NeedCopy;
+      /// \brief The key type of the map
+      typedef GridGraph::Node Key;
+      /// \brief The value type of the map
+      typedef int Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor
+      ColMap(const GridGraph& _graph) : graph(_graph) {}
+
+      /// \brief The subscript operator
+      ///
+      /// The subscript operator.
+      Value operator[](Key key) const {
+	return graph.col(key);
+      }
+
+    private:
+      const GridGraph& graph;
+    };
+
     GridGraph(int n, int m) { construct(n, m); }
     
     /// \brief Gives back the edge goes down from the node.
@@ -398,5 +493,26 @@
     }
     
   };
+
+  /// \brief Index map of the grid graph
+  ///
+  /// Just returns an IndexMap for the grid graph.
+  GridGraph::IndexMap indexMap(const GridGraph& graph) {
+    return GridGraph::IndexMap(graph);
+  }
+
+  /// \brief Row map of the grid graph
+  ///
+  /// Just returns an RowMap for the grid graph.
+  GridGraph::RowMap rowMap(const GridGraph& graph) {
+    return GridGraph::RowMap(graph);
+  }
+
+  /// \brief Coloumn map of the grid graph
+  ///
+  /// Just returns an ColMap for the grid graph.
+  GridGraph::ColMap colMap(const GridGraph& graph) {
+    return GridGraph::ColMap(graph);
+  }
 }
 #endif
diff -r a34203867181 -r 269f0cbfbcc8 lemon/hypercube_graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/hypercube_graph.h	Fri Sep 30 13:15:28 2005 +0000
@@ -0,0 +1,339 @@
+/* -*- C++ -*-
+ * lemon/hypercube_graph.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 HYPERCUBE_GRAPH_H
+#define HYPERCUBE_GRAPH_H
+
+#include <iostream>
+#include <vector>
+#include <lemon/invalid.h>
+#include <lemon/utility.h>
+
+#include <lemon/bits/iterable_graph_extender.h>
+#include <lemon/bits/alteration_notifier.h>
+#include <lemon/bits/default_map.h>
+
+///\ingroup graphs
+///\file
+///\brief HyperCubeGraph class.
+
+namespace lemon {
+
+  /// \brief Base graph for HyperGraph.
+  ///
+  /// Base graph for hyper-cube graph. It describes some member functions
+  /// which can be used in the HyperCubeGraph.
+  ///
+  /// \warning Always use the HyperCubeGraph instead of this.
+  /// \see HyperCubeGraph
+  class HyperCubeGraphBase {
+
+  public:
+
+    typedef HyperCubeGraphBase Graph;
+
+    class Node;
+    class Edge;
+
+  public:
+
+    HyperCubeGraphBase() {}
+
+  protected:
+
+    /// \brief Creates a hypercube graph with the given size.
+    ///
+    /// Creates a hypercube graph with the given size.
+    void construct(int dim) {
+      _dim = dim;
+      _nodeNum = 1 << dim;
+    }
+
+  public:
+    
+
+    typedef True NodeNumTag;
+    typedef True EdgeNumTag;
+
+    ///Number of nodes.
+    int nodeNum() const { return _nodeNum; }
+    ///Number of edges.
+    int edgeNum() const { return _nodeNum * _dim; }
+
+    /// Maximum node ID.
+    
+    /// Maximum node ID.
+    ///\sa id(Node)
+    int maxId(Node = INVALID) const { return nodeNum() - 1; }
+    /// Maximum edge ID.
+    
+    /// Maximum edge ID.
+    ///\sa id(Edge)
+    int maxId(Edge = INVALID) const { return edgeNum() - 1; }
+
+    /// \brief Gives back the source node of an edge.
+    ///    
+    /// Gives back the source node of an edge.
+    Node source(Edge e) const {
+      return e.id / _dim;
+    }
+
+    /// \brief Gives back the target node of an edge.
+    ///    
+    /// Gives back the target node of an edge.
+    Node target(Edge e) const {
+      return (e.id / _dim) ^ ( 1 << (e.id % _dim));
+    }
+
+    /// Node ID.
+    
+    /// The ID of a valid Node is a nonnegative integer not greater than
+    /// \ref maxNodeId(). The range of the ID's is not surely continuous
+    /// and the greatest node ID can be actually less then \ref maxNodeId().
+    ///
+    /// The ID of the \ref INVALID node is -1.
+    ///\return The ID of the node \c v. 
+
+    static int id(Node v) { return v.id; }
+    /// Edge ID.
+    
+    /// The ID of a valid Edge is a nonnegative integer not greater than
+    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
+    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
+    ///
+    /// The ID of the \ref INVALID edge is -1.
+    ///\return The ID of the edge \c e. 
+    static int id(Edge e) { return e.id; }
+
+    static Node fromId(int id, Node) { return Node(id);}
+    
+    static Edge fromId(int id, Edge) { return Edge(id);}
+
+    class Node {
+      friend class HyperCubeGraphBase;
+
+    protected:
+      int id;
+      Node(int _id) { id = _id;}
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node node) const {return id == node.id;}
+      bool operator!=(const Node node) const {return id != node.id;}
+      bool operator<(const Node node) const {return id < node.id;}
+    };
+    
+    class Edge {
+      friend class HyperCubeGraphBase;
+      
+    protected:
+      int id; 
+
+      Edge(int _id) : id(_id) {}
+
+    public:
+      Edge() { }
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge edge) const {return id == edge.id;}
+      bool operator!=(const Edge edge) const {return id != edge.id;}
+      bool operator<(const Edge edge) const {return id < edge.id;}
+    };
+
+    void first(Node& node) const {
+      node.id = nodeNum() - 1;
+    }
+
+    static void next(Node& node) {
+      --node.id;
+    }
+
+    void first(Edge& edge) const {
+      edge.id = edgeNum() - 1;
+    }
+
+    static void next(Edge& edge) {
+      --edge.id;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      edge.id = node.id * _dim;
+    }
+
+    void nextOut(Edge& edge) const {
+      ++edge.id;
+      if (edge.id % _dim == 0) edge.id = -1;
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      edge.id = (node.id ^ 1) * _dim;
+    }
+    
+    void nextIn(Edge& edge) const {
+      int cnt = edge.id % _dim;
+      if ((cnt + 1) % _dim == 0) {
+	edge.id = -1;
+      } else {
+	edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; 
+      }
+    }
+
+    /// \brief Gives back the number of the dimensions.
+    ///
+    /// Gives back the number of the dimensions.
+    int dimension() const {
+      return _dim;
+    }
+
+    /// \brief Returns true if the n'th bit of the node is one.
+    ///
+    /// Returns true if the n'th bit of the node is one. 
+    bool projection(Node node, int n) const {
+      return (bool)(node.id & (1 << n));
+    }
+
+    /// \brief The dimension id of the edge.
+    ///
+    /// It returns the dimension id of the edge. It can
+    /// be in the ${0, 1, dim-1}$ intervall.
+    int dimension(Edge edge) const {
+      return edge.id % _dim;
+    }
+
+    /// \brief Gives back the index of the node.
+    ///
+    /// Gives back the index of the node. The lower bits of the
+    /// integer describe the node.
+    int index(Node node) const {
+      return node.id;
+    }
+
+    /// \brief Gives back the node by its index.
+    ///
+    ///  Gives back the node by its index.
+    Node node(int index) const {
+      return Node(index);
+    }
+    
+  private:
+    int _dim, _nodeNum;
+  };
+
+
+  typedef MappableGraphExtender<
+    IterableGraphExtender<
+    AlterableGraphExtender<
+    HyperCubeGraphBase > > > ExtendedHyperCubeGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief HyperCube graph class
+  ///
+  /// This class implements a special graph type. The nodes of the
+  /// graph can be indiced with integers with at most \c dim binary length.
+  /// Two nodes are connected in the graph if the indices differ only
+  /// on one position in the binary form. 
+  ///
+  /// \note The type of the \c ids is chosen to \c int because efficiency
+  /// reasons. This way the maximal dimension of this implementation
+  /// is 26. 
+  ///
+  /// The graph type is fully conform to the \ref concept::StaticGraph
+  /// concept but it does not conform to the \ref concept::UndirGraph.
+  ///
+  /// \see HyperCubeGraphBase
+  /// \author Balazs Dezso
+  class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
+  public:
+
+    /// \brief Construct a graph with \c dim dimension.
+    ///
+    /// Construct a graph with \c dim dimension.
+    HyperCubeGraph(int dim) { construct(dim); }
+
+    /// \brief Linear combination map.
+    ///
+    /// It makes possible to give back a linear combination
+    /// for each node. This function works like the \c std::accumulate
+    /// so it accumulates the \c bf binary function with the \c fv
+    /// first value. The map accumulates only on that dimensions where
+    /// the node's index is one. The accumulated values should be
+    /// given by the \c begin and \c end iterators and this range's length
+    /// should be the dimension number of the graph.
+    /// 
+    /// \code
+    /// const int DIM = 3;
+    /// HyperCubeGraph graph(DIM);
+    /// xy<double> base[DIM];
+    /// for (int k = 0; k < DIM; ++k) {
+    ///   base[k].x = rand() / (RAND_MAX + 1.0);
+    ///   base[k].y = rand() / (RAND_MAX + 1.0);
+    /// } 
+    /// HyperCubeGraph::HyperMap<xy<double> > 
+    ///   pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
+    /// \endcode
+    ///
+    /// \see HyperCubeGraph
+    template <typename T, typename BF = std::plus<T> >
+    class HyperMap {
+    public:
+
+      typedef Node Key;
+      typedef T Value;
+    
+      
+      /// \brief Constructor for HyperMap. 
+      ///
+      /// Construct a HyperMap for the given graph. The accumulated values 
+      /// should be given by the \c begin and \c end iterators and this 
+      /// range's length should be the dimension number of the graph.
+      ///
+      /// This function accumulates the \c bf binary function with 
+      /// the \c fv first value. The map accumulates only on that dimensions 
+      /// where the node's index is one.           
+      template <typename It>
+      HyperMap(const Graph& graph, It begin, It end, 
+		   T fv = 0.0, const BF& bf = BF()) 
+	: _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
+	if (_values.size() != graph.dimension()) {}
+      }
+
+      /// \brief Gives back the partial accumulated value.
+      ///
+      /// Gives back the partial accumulated value.
+      Value operator[](Key k) const {
+	Value val = _first_value;
+	int id = _graph.index(k); 
+	int n = 0;
+	while (id != 0) {
+	  if (id & 1) {
+	    val = _bin_func(_values[n], _first_value);
+	  }
+	  id >>= 1;
+	  ++n;
+	}
+	return val;
+      }
+      
+    private:
+      const Graph& _graph;
+      std::vector<T> _values;
+      T _first_value;
+      BF _bin_func;
+    };    
+  };
+}
+#endif
+