src/hugo/full_graph.h
author alpar
Mon, 13 Sep 2004 11:24:35 +0000
changeset 835 eb9587f09b42
parent 813 65144c52969c
child 880 9d0bfd35b97c
permissions -rw-r--r--
Remove one remaining range checking.
     1 // -*- c++ -*-
     2 
     3 #ifndef HUGO_FULL_GRAPH_H
     4 #define HUGO_FULL_GRAPH_H
     5 
     6 ///\ingroup graphs
     7 ///\file
     8 ///\brief FullGraph and SymFullGraph classes.
     9 
    10 #include <vector>
    11 #include <climits>
    12 
    13 #include <hugo/invalid.h>
    14 
    15 #include <hugo/map_registry.h>
    16 #include <hugo/default_map.h>
    17 
    18 #include <hugo/map_defines.h>
    19 
    20 namespace hugo {
    21 
    22 /// \addtogroup graphs
    23 /// @{
    24 
    25   ///A full graph class.
    26 
    27   ///This is a simple and fast directed full graph implementation.
    28   ///It is completely static, so you can neither add nor delete either
    29   ///edges or nodes.
    30   ///Otherwise it conforms to the graph interface documented under
    31   ///the description of \ref GraphSkeleton.
    32   ///\sa \ref GraphSkeleton.
    33   ///\todo What about loops?
    34   ///\todo Don't we need SymEdgeMap?
    35   ///
    36   ///\author Alpar Juttner
    37   class FullGraph {
    38     int NodeNum;
    39     int EdgeNum;
    40   public:
    41 
    42     typedef FullGraph Graph;
    43 
    44     class Node;
    45     class Edge;
    46 
    47     class NodeIt;
    48     class EdgeIt;
    49     class OutEdgeIt;
    50     class InEdgeIt;
    51     
    52 
    53     /// Creating map registries.
    54     CREATE_MAP_REGISTRIES;
    55     /// Creating node and edge maps.
    56     CREATE_MAPS(DefaultMap);
    57     
    58   public:
    59 
    60     ///Creates a full graph with \c n nodes.
    61     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
    62     ///
    63     FullGraph(const FullGraph &_g)
    64       : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    65     
    66     ///Number of nodes.
    67     int nodeNum() const { return NodeNum; }
    68     ///Number of edges.
    69     int edgeNum() const { return EdgeNum; }
    70 
    71     /// Maximum node ID.
    72     
    73     /// Maximum node ID.
    74     ///\sa id(Node)
    75     int maxNodeId() const { return NodeNum-1; }
    76     /// Maximum edge ID.
    77     
    78     /// Maximum edge ID.
    79     ///\sa id(Edge)
    80     int maxEdgeId() const { return EdgeNum-1; }
    81 
    82     Node tail(Edge e) const { return e.n%NodeNum; }
    83     Node head(Edge e) const { return e.n/NodeNum; }
    84 
    85     NodeIt& first(NodeIt& v) const {
    86       v=NodeIt(*this); return v; }
    87     EdgeIt& first(EdgeIt& e) const { 
    88       e=EdgeIt(*this); return e; }
    89     OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
    90       e=OutEdgeIt(*this,v); return e; }
    91     InEdgeIt& first(InEdgeIt& e, const Node v) const { 
    92       e=InEdgeIt(*this,v); return e; }
    93 
    94     /// Node ID.
    95     
    96     /// The ID of a valid Node is a nonnegative integer not greater than
    97     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    98     /// and the greatest node ID can be actually less then \ref maxNodeId().
    99     ///
   100     /// The ID of the \ref INVALID node is -1.
   101     ///\return The ID of the node \c v. 
   102     static int id(Node v) { return v.n; }
   103     /// Edge ID.
   104     
   105     /// The ID of a valid Edge is a nonnegative integer not greater than
   106     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
   107     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
   108     ///
   109     /// The ID of the \ref INVALID edge is -1.
   110     ///\return The ID of the edge \c e. 
   111     static int id(Edge e) { return e.n; }
   112 
   113     /// Finds an edge between two nodes.
   114     
   115     /// Finds an edge from node \c u to node \c v.
   116     ///
   117     /// If \c prev is \ref INVALID (this is the default value), then
   118     /// It finds the first edge from \c u to \c v. Otherwise it looks for
   119     /// the next edge from \c u to \c v after \c prev.
   120     /// \return The found edge or INVALID if there is no such an edge.
   121     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
   122     {
   123       return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
   124     }
   125     
   126       
   127     class Node {
   128       friend class FullGraph;
   129       template <typename T> friend class NodeMap;
   130 
   131       friend class Edge;
   132       friend class OutEdgeIt;
   133       friend class InEdgeIt;
   134       friend class SymEdge;
   135 
   136     protected:
   137       int n;
   138       friend int FullGraph::id(Node v); 
   139       Node(int nn) {n=nn;}
   140     public:
   141       Node() {}
   142       Node (Invalid) { n=-1; }
   143       bool operator==(const Node i) const {return n==i.n;}
   144       bool operator!=(const Node i) const {return n!=i.n;}
   145       bool operator<(const Node i) const {return n<i.n;}
   146     };
   147     
   148     class NodeIt : public Node {
   149       const FullGraph *G;
   150       friend class FullGraph;
   151     public:
   152       NodeIt() : Node() { }
   153       NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
   154       NodeIt(Invalid i) : Node(i) { }
   155       NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
   156       ///\todo Undocumented conversion Node -\> NodeIt.
   157       NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
   158     };
   159 
   160     class Edge {
   161       friend class FullGraph;
   162       template <typename T> friend class EdgeMap;
   163       
   164       friend class Node;
   165       friend class NodeIt;
   166     protected:
   167       int n; //NodeNum*head+tail;
   168       friend int FullGraph::id(Edge e);
   169 
   170       Edge(int nn) : n(nn) {}
   171       Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
   172     public:
   173       Edge() { }
   174       Edge (Invalid) { n=-1; }
   175       bool operator==(const Edge i) const {return n==i.n;}
   176       bool operator!=(const Edge i) const {return n!=i.n;}
   177       bool operator<(const Edge i) const {return n<i.n;}
   178       ///\bug This is a workaround until somebody tells me how to
   179       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
   180       int &idref() {return n;}
   181       const int &idref() const {return n;}
   182     };
   183     
   184     class EdgeIt : public Edge {
   185       friend class FullGraph;
   186     public:
   187       EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
   188       EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
   189       EdgeIt (Invalid i) : Edge(i) { }
   190       EdgeIt() : Edge() { }
   191       EdgeIt& operator++() { --n; return *this; }
   192 
   193       ///\bug This is a workaround until somebody tells me how to
   194       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
   195       int &idref() {return n;}
   196     };
   197     
   198     class OutEdgeIt : public Edge {
   199       const FullGraph *G;
   200       friend class FullGraph;
   201     public: 
   202       OutEdgeIt() : Edge() { }
   203       OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
   204       OutEdgeIt (Invalid i) : Edge(i) { }
   205 
   206       OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
   207       
   208       OutEdgeIt& operator++()
   209       { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
   210 
   211     };
   212     
   213     class InEdgeIt : public Edge {
   214       const FullGraph *G;
   215       friend class FullGraph;
   216     public: 
   217       InEdgeIt() : Edge() { }
   218       InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
   219       InEdgeIt (Invalid i) : Edge(i) { }
   220       InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
   221       InEdgeIt& operator++()
   222       { if(!((++n)%G->NodeNum)) n=-1; return *this; }
   223     };
   224 
   225   };
   226 
   227   /// @}  
   228 
   229 } //namespace hugo
   230 
   231 
   232 
   233 
   234 #endif //HUGO_FULL_GRAPH_H