COIN-OR::LEMON - Graph Library

Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/full_graph.h


Ignore:
Timestamp:
10/28/04 00:38:50 (15 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/full_graph.h

    r921 r946  
    1818#define LEMON_FULL_GRAPH_H
    1919
     20
     21#include <lemon/idmappable_graph_extender.h>
     22
     23#include <lemon/iterable_graph_extender.h>
     24
     25#include <lemon/alteration_observer_registry.h>
     26#include <lemon/default_map.h>
     27
    2028///\ingroup graphs
    2129///\file
    2230///\brief FullGraph and SymFullGraph classes.
    2331
    24 #include <vector>
    25 #include <climits>
    2632
    2733#include <lemon/invalid.h>
    28 
    29 #include <lemon/map_registry.h>
    30 #include <lemon/array_map.h>
    31 
    32 #include <lemon/map_defines.h>
    3334
    3435namespace lemon {
     
    4950  ///
    5051  ///\author Alpar Juttner
    51   class FullGraph {
     52  class FullGraphBase {
    5253    int NodeNum;
    5354    int EdgeNum;
    5455  public:
    5556
    56     typedef FullGraph Graph;
     57    typedef FullGraphBase Graph;
    5758
    5859    class Node;
    5960    class Edge;
    6061
    61     class NodeIt;
    62     class EdgeIt;
    63     class OutEdgeIt;
    64     class InEdgeIt;
    65    
    66 
    67     // Create map registries.
    68     CREATE_MAP_REGISTRIES;
    69     // Create node and edge maps.
    70     CREATE_MAPS(ArrayMap);
    71    
    7262  public:
    7363
     64    FullGraphBase() {}
     65
     66
    7467    ///Creates a full graph with \c n nodes.
    75     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
    76     ///
    77     FullGraph(const FullGraph &_g)
    78       : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     68    void construct(int n) { NodeNum = n; EdgeNum = n * n; }
     69    ///
     70    //    FullGraphBase(const FullGraphBase &_g)
     71    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    7972   
    8073    ///Number of nodes.
     
    9487    int maxEdgeId() const { return EdgeNum-1; }
    9588
    96     Node tail(Edge e) const { return e.n%NodeNum; }
    97     Node head(Edge e) const { return e.n/NodeNum; }
    98 
    99     NodeIt& first(NodeIt& v) const {
    100       v=NodeIt(*this); return v; }
    101     EdgeIt& first(EdgeIt& e) const {
    102       e=EdgeIt(*this); return e; }
    103     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    104       e=OutEdgeIt(*this,v); return e; }
    105     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    106       e=InEdgeIt(*this,v); return e; }
     89    Node tail(Edge e) const { return e.id % NodeNum; }
     90    Node head(Edge e) const { return e.id / NodeNum; }
     91
    10792
    10893    /// Node ID.
     
    11499    /// The ID of the \ref INVALID node is -1.
    115100    ///\return The ID of the node \c v.
    116     static int id(Node v) { return v.n; }
     101
     102    static int id(Node v) { return v.id; }
    117103    /// Edge ID.
    118104   
     
    123109    /// The ID of the \ref INVALID edge is -1.
    124110    ///\return The ID of the edge \c e.
    125     static int id(Edge e) { return e.n; }
     111    static int id(Edge e) { return e.id; }
    126112
    127113    /// Finds an edge between two nodes.
     
    135121    Edge findEdge(Node u,Node v, Edge prev = INVALID)
    136122    {
    137       return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
     123      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    138124    }
    139125   
    140126     
    141127    class Node {
    142       friend class FullGraph;
    143       template <typename T> friend class NodeMap;
    144 
    145       friend class Edge;
    146       friend class OutEdgeIt;
    147       friend class InEdgeIt;
    148       friend class SymEdge;
     128      friend class FullGraphBase;
    149129
    150130    protected:
    151       int n;
    152       friend int FullGraph::id(Node v);
    153       Node(int nn) {n=nn;}
     131      int id;
     132      Node(int _id) { id = _id;}
    154133    public:
    155134      Node() {}
    156       Node (Invalid) { n=-1; }
    157       bool operator==(const Node i) const {return n==i.n;}
    158       bool operator!=(const Node i) const {return n!=i.n;}
    159       bool operator<(const Node i) const {return n<i.n;}
     135      Node (Invalid) { id = -1; }
     136      bool operator==(const Node node) const {return id == node.id;}
     137      bool operator!=(const Node node) const {return id != node.id;}
     138      bool operator<(const Node node) const {return id < node.id;}
    160139    };
    161140   
    162     class NodeIt : public Node {
    163       const FullGraph *G;
    164       friend class FullGraph;
    165     public:
    166       NodeIt() : Node() { }
    167       NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
    168       NodeIt(Invalid i) : Node(i) { }
    169       NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
    170       ///\todo Undocumented conversion Node -\> NodeIt.
    171       NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
    172     };
     141
    173142
    174143    class Edge {
    175       friend class FullGraph;
    176       template <typename T> friend class EdgeMap;
     144      friend class FullGraphBase;
    177145     
    178       friend class Node;
    179       friend class NodeIt;
    180146    protected:
    181       int n; //NodeNum*head+tail;
    182       friend int FullGraph::id(Edge e);
    183 
    184       Edge(int nn) : n(nn) {}
    185       Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
     147      int id;  // NodeNum * head + tail;
     148
     149      Edge(int _id) : id(_id) {}
     150
     151      Edge(const FullGraphBase& _graph, int tail, int head)
     152        : id(_graph.NodeNum * head+tail) {}
    186153    public:
    187154      Edge() { }
    188       Edge (Invalid) { n=-1; }
    189       bool operator==(const Edge i) const {return n==i.n;}
    190       bool operator!=(const Edge i) const {return n!=i.n;}
    191       bool operator<(const Edge i) const {return n<i.n;}
    192       ///\bug This is a workaround until somebody tells me how to
    193       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
    194       int &idref() {return n;}
    195       const int &idref() const {return n;}
     155      Edge (Invalid) { id = -1; }
     156      bool operator==(const Edge edge) const {return id == edge.id;}
     157      bool operator!=(const Edge edge) const {return id != edge.id;}
     158      bool operator<(const Edge edge) const {return id < edge.id;}
    196159    };
    197    
    198     class EdgeIt : public Edge {
    199       friend class FullGraph;
    200     public:
    201       EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
    202       EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
    203       EdgeIt (Invalid i) : Edge(i) { }
    204       EdgeIt() : Edge() { }
    205       EdgeIt& operator++() { --n; return *this; }
    206 
    207       ///\bug This is a workaround until somebody tells me how to
    208       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
    209       int &idref() {return n;}
    210     };
    211    
    212     class OutEdgeIt : public Edge {
    213       const FullGraph *G;
    214       friend class FullGraph;
    215     public:
    216       OutEdgeIt() : Edge() { }
    217       OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
    218       OutEdgeIt (Invalid i) : Edge(i) { }
    219 
    220       OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
    221      
    222       OutEdgeIt& operator++()
    223       { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
    224 
    225     };
    226    
    227     class InEdgeIt : public Edge {
    228       const FullGraph *G;
    229       friend class FullGraph;
    230     public:
    231       InEdgeIt() : Edge() { }
    232       InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
    233       InEdgeIt (Invalid i) : Edge(i) { }
    234       InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
    235       InEdgeIt& operator++()
    236       { if(!((++n)%G->NodeNum)) n=-1; return *this; }
    237     };
     160
     161    void first(Node& node) const {
     162      node.id = NodeNum-1;
     163    }
     164
     165    static void next(Node& node) {
     166      --node.id;
     167    }
     168
     169    void first(Edge& edge) const {
     170      edge.id = EdgeNum-1;
     171    }
     172
     173    static void next(Edge& edge) {
     174      --edge.id;
     175    }
     176
     177    void firstOut(Edge& edge, const Node& node) const {
     178      edge.id = EdgeNum + node.id - NodeNum;
     179    }
     180
     181    void nextOut(Edge& edge) const {
     182      edge.id -= NodeNum;
     183      if (edge.id < 0) edge.id = -1;
     184    }
     185
     186    void firstIn(Edge& edge, const Node& node) const {
     187      edge.id = node.id * NodeNum;
     188    }
     189   
     190    void nextIn(Edge& edge) const {
     191      ++edge.id;
     192      if (edge.id % NodeNum == 0) edge.id = -1;
     193    }
    238194
    239195  };
    240196
     197
     198  typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
     199  typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
     200  typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
     201  typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
     202
     203  class FullGraph : public MappableFullGraphBase {
     204  public:
     205
     206    FullGraph(int n) { construct(n); }
     207  };
     208
     209  template <>
     210  int countNodes<FullGraph>(const FullGraph& graph) {
     211    return graph.nodeNum();
     212  }
     213
     214  template <>
     215  int countEdges<FullGraph>(const FullGraph& graph) {
     216    return graph.edgeNum();
     217  }
     218
    241219  /// @} 
    242220
Note: See TracChangeset for help on using the changeset viewer.