marci@606: // -*- c++ -*-
alpar@591: 
alpar@591: #ifndef HUGO_FULL_GRAPH_H
alpar@591: #define HUGO_FULL_GRAPH_H
alpar@591: 
alpar@591: ///\ingroup graphs
alpar@591: ///\file
alpar@591: ///\brief FullGraph and SymFullGraph classes.
alpar@591: 
alpar@591: #include <vector>
deba@782: #include <climits>
alpar@591: 
alpar@591: #include <hugo/invalid.h>
alpar@591: 
deba@782: #include <hugo/map_registry.h>
deba@798: #include <hugo/default_map_factory.h>
deba@782: 
alpar@591: namespace hugo {
alpar@591: 
alpar@591: /// \addtogroup graphs
alpar@591: /// @{
alpar@591: 
alpar@591:   ///A full graph class.
alpar@591: 
alpar@591:   ///This is a simple and fast directed full graph implementation.
marci@606:   ///It is completely static, so you can neither add nor delete either
alpar@591:   ///edges or nodes.
alpar@591:   ///Otherwise it conforms to the graph interface documented under
alpar@591:   ///the description of \ref GraphSkeleton.
alpar@591:   ///\sa \ref GraphSkeleton.
alpar@752:   ///\todo What about loops?
alpar@752:   ///\todo Don't we need SymEdgeMap?
alpar@591:   ///
alpar@591:   ///\author Alpar Juttner
alpar@591:   class FullGraph {
alpar@591:     int NodeNum;
alpar@591:     int EdgeNum;
alpar@591:   public:
deba@782: 
deba@782:     typedef FullGraph Graph;
alpar@591: 
alpar@591:     class Node;
alpar@591:     class Edge;
deba@782: 
alpar@591:     class NodeIt;
alpar@591:     class EdgeIt;
alpar@591:     class OutEdgeIt;
alpar@591:     class InEdgeIt;
alpar@591:     
deba@782:     CREATE_MAP_REGISTRIES;
deba@798:     CREATE_MAPS(DefaultMapFactory);
alpar@591:     
alpar@591:   public:
alpar@591: 
alpar@591:     ///Creates a full graph with \c n nodes.
alpar@591:     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
alpar@591:     ///
alpar@591:     FullGraph(const FullGraph &_g)
alpar@591:       : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
alpar@591:     
alpar@813:     ///Number of nodes.
alpar@813:     int nodeNum() const { return NodeNum; }
alpar@813:     ///Number of edges.
alpar@813:     int edgeNum() const { return EdgeNum; }
alpar@591: 
alpar@813:     /// Maximum node ID.
alpar@813:     
alpar@813:     /// Maximum node ID.
alpar@813:     ///\sa id(Node)
alpar@813:     int maxNodeId() const { return NodeNum-1; }
alpar@813:     /// Maximum edge ID.
alpar@813:     
alpar@813:     /// Maximum edge ID.
alpar@813:     ///\sa id(Edge)
alpar@813:     int maxEdgeId() const { return EdgeNum-1; }
alpar@591: 
alpar@591:     Node tail(Edge e) const { return e.n%NodeNum; }
alpar@591:     Node head(Edge e) const { return e.n/NodeNum; }
alpar@591: 
alpar@591:     NodeIt& first(NodeIt& v) const {
alpar@591:       v=NodeIt(*this); return v; }
alpar@591:     EdgeIt& first(EdgeIt& e) const { 
alpar@591:       e=EdgeIt(*this); return e; }
alpar@591:     OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
alpar@591:       e=OutEdgeIt(*this,v); return e; }
alpar@591:     InEdgeIt& first(InEdgeIt& e, const Node v) const { 
alpar@591:       e=InEdgeIt(*this,v); return e; }
alpar@591: 
alpar@813:     /// Node ID.
alpar@813:     
alpar@813:     /// The ID of a valid Node is a nonnegative integer not greater than
alpar@813:     /// \ref maxNodeId(). The range of the ID's is not surely continuous
alpar@813:     /// and the greatest node ID can be actually less then \ref maxNodeId().
alpar@813:     ///
alpar@813:     /// The ID of the \ref INVALID node is -1.
alpar@813:     ///\return The ID of the node \c v. 
alpar@713:     static int id(Node v) { return v.n; }
alpar@813:     /// Edge ID.
alpar@813:     
alpar@813:     /// The ID of a valid Edge is a nonnegative integer not greater than
alpar@813:     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
alpar@813:     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
alpar@813:     ///
alpar@813:     /// The ID of the \ref INVALID edge is -1.
alpar@813:     ///\return The ID of the edge \c e. 
alpar@713:     static int id(Edge e) { return e.n; }
alpar@591: 
alpar@774:     /// Finds an edge between two nodes.
alpar@774:     
alpar@774:     /// Finds an edge from node \c u to node \c v.
alpar@774:     ///
alpar@774:     /// If \c prev is \ref INVALID (this is the default value), then
alpar@774:     /// It finds the first edge from \c u to \c v. Otherwise it looks for
alpar@774:     /// the next edge from \c u to \c v after \c prev.
alpar@774:     /// \return The found edge or INVALID if there is no such an edge.
alpar@774:     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
alpar@774:     {
deba@782:       return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
alpar@774:     }
alpar@774:     
alpar@774:       
alpar@591:     class Node {
alpar@591:       friend class FullGraph;
alpar@591:       template <typename T> friend class NodeMap;
alpar@591: 
alpar@591:       friend class Edge;
alpar@591:       friend class OutEdgeIt;
alpar@591:       friend class InEdgeIt;
alpar@591:       friend class SymEdge;
alpar@591: 
alpar@591:     protected:
alpar@591:       int n;
alpar@722:       friend int FullGraph::id(Node v); 
alpar@591:       Node(int nn) {n=nn;}
alpar@591:     public:
alpar@591:       Node() {}
alpar@591:       Node (Invalid) { n=-1; }
alpar@591:       bool operator==(const Node i) const {return n==i.n;}
alpar@591:       bool operator!=(const Node i) const {return n!=i.n;}
alpar@591:       bool operator<(const Node i) const {return n<i.n;}
alpar@591:     };
alpar@591:     
alpar@591:     class NodeIt : public Node {
alpar@774:       const FullGraph *G;
alpar@591:       friend class FullGraph;
alpar@591:     public:
alpar@591:       NodeIt() : Node() { }
alpar@774:       NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
alpar@591:       NodeIt(Invalid i) : Node(i) { }
alpar@774:       NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
alpar@591:       ///\todo Undocumented conversion Node -\> NodeIt.
alpar@774:       NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
alpar@591:     };
alpar@591: 
alpar@591:     class Edge {
alpar@591:       friend class FullGraph;
alpar@591:       template <typename T> friend class EdgeMap;
alpar@591:       
alpar@591:       friend class Node;
alpar@591:       friend class NodeIt;
alpar@591:     protected:
alpar@591:       int n; //NodeNum*head+tail;
alpar@722:       friend int FullGraph::id(Edge e);
alpar@591: 
alpar@774:       Edge(int nn) : n(nn) {}
alpar@774:       Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
alpar@591:     public:
alpar@591:       Edge() { }
alpar@591:       Edge (Invalid) { n=-1; }
alpar@591:       bool operator==(const Edge i) const {return n==i.n;}
alpar@591:       bool operator!=(const Edge i) const {return n!=i.n;}
alpar@591:       bool operator<(const Edge i) const {return n<i.n;}
alpar@591:       ///\bug This is a workaround until somebody tells me how to
alpar@591:       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
alpar@591:       int &idref() {return n;}
alpar@591:       const int &idref() const {return n;}
alpar@591:     };
alpar@591:     
alpar@591:     class EdgeIt : public Edge {
alpar@591:       friend class FullGraph;
alpar@591:     public:
alpar@774:       EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
alpar@774:       EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
alpar@591:       EdgeIt (Invalid i) : Edge(i) { }
alpar@591:       EdgeIt() : Edge() { }
alpar@774:       EdgeIt& operator++() { --n; return *this; }
alpar@774: 
alpar@591:       ///\bug This is a workaround until somebody tells me how to
alpar@591:       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
alpar@591:       int &idref() {return n;}
alpar@591:     };
alpar@591:     
alpar@591:     class OutEdgeIt : public Edge {
alpar@774:       const FullGraph *G;
alpar@591:       friend class FullGraph;
alpar@591:     public: 
alpar@591:       OutEdgeIt() : Edge() { }
alpar@774:       OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
alpar@591:       OutEdgeIt (Invalid i) : Edge(i) { }
alpar@591: 
alpar@774:       OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
alpar@774:       
alpar@774:       OutEdgeIt& operator++()
alpar@774:       { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
alpar@774: 
alpar@591:     };
alpar@591:     
alpar@591:     class InEdgeIt : public Edge {
alpar@774:       const FullGraph *G;
alpar@591:       friend class FullGraph;
alpar@591:     public: 
alpar@591:       InEdgeIt() : Edge() { }
alpar@774:       InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
alpar@591:       InEdgeIt (Invalid i) : Edge(i) { }
alpar@774:       InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
alpar@774:       InEdgeIt& operator++()
alpar@774:       { if(!((++n)%G->NodeNum)) n=-1; return *this; }
alpar@591:     };
alpar@591: 
alpar@591:   };
alpar@591: 
alpar@591:   /// @}  
alpar@591: 
alpar@591: } //namespace hugo
alpar@591: 
alpar@591: 
alpar@591: 
alpar@591: 
alpar@591: #endif //HUGO_FULL_GRAPH_H