1.1 --- a/lemon/full_graph.h	Mon Oct 03 14:22:10 2005 +0000
     1.2 +++ b/lemon/full_graph.h	Wed Oct 05 13:15:47 2005 +0000
     1.3 @@ -22,7 +22,7 @@
     1.4  
     1.5  #include <lemon/bits/iterable_graph_extender.h>
     1.6  #include <lemon/bits/alteration_notifier.h>
     1.7 -#include <lemon/bits/default_map.h>
     1.8 +#include <lemon/bits/static_map.h>
     1.9  
    1.10  #include <lemon/bits/undir_graph_extender.h>
    1.11  
    1.12 @@ -195,7 +195,7 @@
    1.13    AlterableFullGraphBase;
    1.14    typedef IterableGraphExtender<AlterableFullGraphBase> 
    1.15    IterableFullGraphBase;
    1.16 -  typedef MappableGraphExtender<
    1.17 +  typedef StaticMappableGraphExtender<
    1.18      IterableGraphExtender<
    1.19      AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
    1.20  
    1.21 @@ -298,10 +298,12 @@
    1.22      /// It finds the first edge from \c u to \c v. Otherwise it looks for
    1.23      /// the next edge from \c u to \c v after \c prev.
    1.24      /// \return The found edge or INVALID if there is no such an edge.
    1.25 -    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
    1.26 -    {
    1.27 -      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    1.28 +    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
    1.29 +      if (prev.id != -1 || u.id <= v.id) return -1;
    1.30 +      return Edge(u.id * (u.id - 1) / 2 + v.id);
    1.31      }
    1.32 +
    1.33 +    typedef True FindEdgeTag;
    1.34      
    1.35        
    1.36      class Node {
    1.37 @@ -328,8 +330,6 @@
    1.38  
    1.39        Edge(int _id) : id(_id) {}
    1.40  
    1.41 -      Edge(const UndirFullGraphBase& _graph, int source, int target) 
    1.42 -	: id(_graph._nodeNum * target+source) {}
    1.43      public:
    1.44        Edge() { }
    1.45        Edge (Invalid) { id = -1; }
    1.46 @@ -339,7 +339,7 @@
    1.47      };
    1.48  
    1.49      void first(Node& node) const {
    1.50 -      node.id = _nodeNum-1;
    1.51 +      node.id = _nodeNum - 1;
    1.52      }
    1.53  
    1.54      static void next(Node& node) {
    1.55 @@ -347,7 +347,7 @@
    1.56      }
    1.57  
    1.58      void first(Edge& edge) const {
    1.59 -      edge.id = _edgeNum-1;
    1.60 +      edge.id = _edgeNum - 1;
    1.61      }
    1.62  
    1.63      static void next(Edge& edge) {
    1.64 @@ -355,31 +355,35 @@
    1.65      }
    1.66  
    1.67      void firstOut(Edge& edge, const Node& node) const {      
    1.68 -      edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
    1.69 +      int src = node.id;
    1.70 +      int trg = 0;
    1.71 +      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    1.72      }
    1.73  
    1.74      /// \todo with specialized iterators we can make faster iterating
    1.75 -    void nextOut(Edge& e) const {
    1.76 -      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    1.77 -      int target = e.id - (source) * (source - 1) / 2; 
    1.78 -      ++target;
    1.79 -      e.id = target < source ? source * (source - 1) / 2 + target : -1;
    1.80 +    void nextOut(Edge& edge) const {
    1.81 +      int src = source(edge).id;
    1.82 +      int trg = target(edge).id;
    1.83 +      ++trg;
    1.84 +      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    1.85      }
    1.86  
    1.87      void firstIn(Edge& edge, const Node& node) const {
    1.88 -      edge.id = node.id * (node.id + 1) / 2 - 1;
    1.89 +      int src = node.id + 1;
    1.90 +      int trg = node.id;
    1.91 +      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    1.92      }
    1.93      
    1.94 -    void nextIn(Edge& e) const {
    1.95 -      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    1.96 -      int target = e.id - (source) * (source - 1) / 2; ++target;
    1.97 -      ++source;
    1.98 -      e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
    1.99 +    void nextIn(Edge& edge) const {
   1.100 +      int src = source(edge).id;
   1.101 +      int trg = target(edge).id;
   1.102 +      ++src;
   1.103 +      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
   1.104      }
   1.105  
   1.106    };
   1.107  
   1.108 -  typedef MappableUndirGraphExtender<
   1.109 +  typedef StaticMappableUndirGraphExtender<
   1.110      IterableUndirGraphExtender<
   1.111      AlterableUndirGraphExtender<
   1.112      UndirGraphExtender<UndirFullGraphBase> > > > ExtendedUndirFullGraphBase;