Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 2284)
+++ lemon/Makefile.am	(revision 2293)
@@ -91,4 +91,5 @@
 	lemon/smart_graph.h \
 	lemon/ssp_min_cost_flow.h \
+	lemon/static_graph.h \
 	lemon/sub_graph.h \
 	lemon/suurballe.h \
Index: lemon/static_graph.h
===================================================================
--- lemon/static_graph.h	(revision 2293)
+++ lemon/static_graph.h	(revision 2293)
@@ -0,0 +1,262 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * 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_STATIC_GRAPH_H
+#define LEMON_STATIC_GRAPH_H
+
+#include <lemon/bits/graph_extender.h>
+#include <lemon/graph_utils.h>
+
+namespace lemon {
+
+  class StaticGraphBase {
+  public:
+
+    StaticGraphBase() 
+      : node_num(-1), edge_num(0), 
+        node_first_out(0), node_first_in(0),
+        edge_source(0), edge_target(0), 
+        edge_next_in(0), edge_next_out(0) {}
+    
+    ~StaticGraphBase() {
+      if (node_num != -1) {
+        delete[] node_first_out;
+        delete[] node_first_in;
+        delete[] edge_source;
+        delete[] edge_target;
+        delete[] edge_next_out;
+        delete[] edge_next_in;
+      }
+    }
+
+    class Node {
+      friend class StaticGraphBase;
+    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 StaticGraphBase;      
+    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;}
+    };
+
+    Node source(const Edge& e) const { return Node(edge_source[e.id]); }
+    Node target(const Edge& e) const { return Node(edge_target[e.id]); }
+
+    void first(Node& n) const { n.id = node_num - 1; }
+    void next(Node& n) const { --n.id; }
+
+    void first(Edge& n) const { n.id = edge_num - 1; }
+    void next(Edge& n) const { --n.id; }
+
+    void firstOut(Edge& e, const Node& n) const { 
+      e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? 
+        node_first_out[n.id] : -1;
+    }
+    void nextOut(Edge& e) const { e.id = edge_next_out[e.id]; }
+
+    void firstIn(Edge& e, const Node& n) const { e.id = node_first_in[n.id]; }
+    void nextIn(Edge& e) const { e.id = edge_next_in[e.id]; }
+    
+
+    int id(const Node& n) const { return n.id; }
+    Node nodeFromId(int id) const { return Node(id); }
+    int maxNodeId() const { return node_num - 1; }
+
+    int id(const Edge& e) const { return e.id; }
+    Edge edgeFromId(int id) const { return Edge(id); }
+    int maxEdgeId() const { return edge_num - 1; }
+
+    typedef True NodeNumTag;
+    int nodeNum() const { return node_num; }
+    typedef True EdgeNumTag;
+    int edgeNum() const { return edge_num; }
+
+  private:
+
+    template <typename Graph, typename NodeRefMap>
+    class EdgeLess {
+    public:
+      typedef typename Graph::Edge Edge;
+
+      EdgeLess(const Graph &_graph, const NodeRefMap& _nodeRef) 
+        : graph(_graph), nodeRef(_nodeRef) {}
+      
+      bool operator()(const Edge& left, const Edge& right) const {
+	return nodeRef[graph.target(left)] < nodeRef[graph.target(right)];
+      }
+    private:
+      const Graph& graph;
+      const NodeRefMap& nodeRef;
+    };
+    
+  public:
+
+    typedef True CloneableTag;
+    
+    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
+    void clone(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
+
+      if (node_num != -1) {
+        delete[] node_first_out;
+        delete[] node_first_in;
+        delete[] edge_source;
+        delete[] edge_target;
+        delete[] edge_next_out;
+        delete[] edge_next_in;
+      }
+
+      typedef typename Graph::Node GNode;
+      typedef typename Graph::Edge GEdge;
+
+      node_num = countNodes(graph);
+      edge_num = countEdges(graph);
+
+      node_first_out = new int[node_num + 1];
+      node_first_in = new int[node_num];
+
+      edge_source = new int[edge_num];
+      edge_target = new int[edge_num];
+      edge_next_out = new int[edge_num];
+      edge_next_in = new int[edge_num];
+
+      int node_index = 0;
+      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+        nodeRef[n] = Node(node_index);
+        node_first_in[node_index] = -1;
+        ++node_index;
+      }
+
+      EdgeLess<Graph, NodeRefMap> edgeLess(graph, nodeRef);
+
+      int edge_index = 0;
+      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+        int source = nodeRef[n].id;
+        std::vector<GEdge> edges;
+        for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
+          edges.push_back(e);
+        }
+        if (!edges.empty()) {
+          node_first_out[source] = edge_index;
+          std::sort(edges.begin(), edges.end(), edgeLess);
+          for (typename std::vector<GEdge>::iterator it = edges.begin();
+               it != edges.end(); ++it) {
+            int target = nodeRef[graph.target(*it)].id;
+            edgeRef[*it] = Edge(edge_index);
+            edge_source[edge_index] = source; 
+            edge_target[edge_index] = target;
+            edge_next_in[edge_index] = node_first_in[target];
+            node_first_in[target] = edge_index;
+            edge_next_out[edge_index] = edge_index + 1;
+            ++edge_index;
+          }
+          edge_next_out[edge_index - 1] = -1;
+        } else {
+          node_first_out[source] = edge_index;
+        }
+      }
+      node_first_out[node_num] = edge_num;
+    }
+
+  protected:
+
+    void fastFirstOut(Edge& e, const Node& n) const {
+      e.id = node_first_out[n.id];
+    }
+
+    static void fastNextOut(Edge& e) {
+      ++e.id;
+    }
+    void fastLastOut(Edge& e, const Node& n) const {
+      e.id = node_first_out[n.id + 1];
+    }
+    
+  private:
+    int node_num;
+    int edge_num;
+    int *node_first_out;
+    int *node_first_in;
+    int *edge_source;
+    int *edge_target;
+    int *edge_next_in;
+    int *edge_next_out;
+  };
+
+  typedef GraphExtender<StaticGraphBase> ExtendedStaticGraphBase;
+
+
+  class StaticGraph : public ExtendedStaticGraphBase {
+  public:
+
+    typedef ExtendedStaticGraphBase Parent;
+
+  protected:
+
+    using Parent::fastFirstOut;
+    using Parent::fastNextOut;
+    using Parent::fastLastOut;
+    
+  public:
+    
+    class OutEdgeIt : public Edge {
+    public:
+
+      OutEdgeIt() { }
+
+      OutEdgeIt(Invalid i) : Edge(i) { }
+
+      OutEdgeIt(const StaticGraph& graph, const Node& node) {
+	graph.fastFirstOut(*this, node);
+	graph.fastLastOut(last, node);
+        if (last == *this) *this = INVALID;
+      }
+
+      OutEdgeIt(const StaticGraph& graph, const Edge& edge) : Edge(edge) {
+        graph.fastLastOut(last, graph.source(edge));
+      }
+
+      OutEdgeIt& operator++() { 
+        StaticGraph::fastNextOut(*this);
+        if (last == *this) *this = INVALID;
+        return *this; 
+      }
+
+    private:
+      Edge last;
+    };
+    
+  };
+
+}
+
+#endif
