COIN-OR::LEMON - Graph Library

Changeset 1703:eb90e3d6bddc in lemon-0.x for lemon/full_graph.h


Ignore:
Timestamp:
10/05/05 15:15:47 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2230
Message:

Proper sized map type

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r1692 r1703  
    2323#include <lemon/bits/iterable_graph_extender.h>
    2424#include <lemon/bits/alteration_notifier.h>
    25 #include <lemon/bits/default_map.h>
     25#include <lemon/bits/static_map.h>
    2626
    2727#include <lemon/bits/undir_graph_extender.h>
     
    196196  typedef IterableGraphExtender<AlterableFullGraphBase>
    197197  IterableFullGraphBase;
    198   typedef MappableGraphExtender<
     198  typedef StaticMappableGraphExtender<
    199199    IterableGraphExtender<
    200200    AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
     
    299299    /// the next edge from \c u to \c v after \c prev.
    300300    /// \return The found edge or INVALID if there is no such an edge.
    301     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    302     {
    303       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    304     }
     301    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     302      if (prev.id != -1 || u.id <= v.id) return -1;
     303      return Edge(u.id * (u.id - 1) / 2 + v.id);
     304    }
     305
     306    typedef True FindEdgeTag;
    305307   
    306308     
     
    329331      Edge(int _id) : id(_id) {}
    330332
    331       Edge(const UndirFullGraphBase& _graph, int source, int target)
    332         : id(_graph._nodeNum * target+source) {}
    333333    public:
    334334      Edge() { }
     
    340340
    341341    void first(Node& node) const {
    342       node.id = _nodeNum-1;
     342      node.id = _nodeNum - 1;
    343343    }
    344344
     
    348348
    349349    void first(Edge& edge) const {
    350       edge.id = _edgeNum-1;
     350      edge.id = _edgeNum - 1;
    351351    }
    352352
     
    356356
    357357    void firstOut(Edge& edge, const Node& node) const {     
    358       edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
     358      int src = node.id;
     359      int trg = 0;
     360      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    359361    }
    360362
    361363    /// \todo with specialized iterators we can make faster iterating
    362     void nextOut(Edge& e) const {
    363       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    364       int target = e.id - (source) * (source - 1) / 2;
    365       ++target;
    366       e.id = target < source ? source * (source - 1) / 2 + target : -1;
     364    void nextOut(Edge& edge) const {
     365      int src = source(edge).id;
     366      int trg = target(edge).id;
     367      ++trg;
     368      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    367369    }
    368370
    369371    void firstIn(Edge& edge, const Node& node) const {
    370       edge.id = node.id * (node.id + 1) / 2 - 1;
    371     }
    372    
    373     void nextIn(Edge& e) const {
    374       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    375       int target = e.id - (source) * (source - 1) / 2; ++target;
    376       ++source;
    377       e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
     372      int src = node.id + 1;
     373      int trg = node.id;
     374      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
     375    }
     376   
     377    void nextIn(Edge& edge) const {
     378      int src = source(edge).id;
     379      int trg = target(edge).id;
     380      ++src;
     381      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    378382    }
    379383
    380384  };
    381385
    382   typedef MappableUndirGraphExtender<
     386  typedef StaticMappableUndirGraphExtender<
    383387    IterableUndirGraphExtender<
    384388    AlterableUndirGraphExtender<
Note: See TracChangeset for help on using the changeset viewer.