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>
alpar@591: #include <limits.h>
alpar@591: 
alpar@591: #include <hugo/invalid.h>
alpar@591: 
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:
alpar@591:     template <typename T> class EdgeMap;
alpar@591:     template <typename T> class NodeMap;
alpar@591: 
alpar@591:     class Node;
alpar@591:     class Edge;
alpar@591:     class NodeIt;
alpar@591:     class EdgeIt;
alpar@591:     class OutEdgeIt;
alpar@591:     class InEdgeIt;
alpar@591:     
alpar@591:     template <typename T> class NodeMap;
alpar@591:     template <typename T> class EdgeMap;
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@591:     int nodeNum() const { return NodeNum; }  //FIXME: What is this?
alpar@591:     int edgeNum() const { return EdgeNum; }  //FIXME: What is this?
alpar@591: 
alpar@591:     int maxNodeId() const { return NodeNum; }  //FIXME: What is this?
alpar@591:     int maxEdgeId() const { return EdgeNum; }  //FIXME: What is this?
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@713:     static int id(Node v) { return v.n; }
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:     {
alpar@774:       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:     template <typename T> class NodeMap
alpar@591:     {
alpar@591:       std::vector<T> container;
alpar@591: 
alpar@591:     public:
alpar@591:       typedef T ValueType;
alpar@591:       typedef Node KeyType;
alpar@591: 
alpar@591:       NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
alpar@591:       NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
alpar@591:       NodeMap(const NodeMap<T> &m) : container(m.container) { }
alpar@591: 
alpar@591:       template<typename TT> friend class NodeMap;
alpar@591:       ///\todo It can copy between different types.
alpar@591:       template<typename TT> NodeMap(const NodeMap<TT> &m)
alpar@591: 	: container(m.container.size())
alpar@591:       {
alpar@591: 	typename std::vector<TT>::const_iterator i;
alpar@591: 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
alpar@591: 	    i!=m.container.end();
alpar@591: 	    i++)
alpar@591: 	  container.push_back(*i);
alpar@591:       }
alpar@591:       void set(Node n, T a) { container[n.n]=a; }
alpar@591:       //'T& operator[](Node n)' would be wrong here
alpar@591:       typename std::vector<T>::reference
alpar@591:       operator[](Node n) { return container[n.n]; }
alpar@591:       //'const T& operator[](Node n)' would be wrong here
alpar@591:       typename std::vector<T>::const_reference 
alpar@591:       operator[](Node n) const { return container[n.n]; }
alpar@591: 
alpar@591:       ///\warning There is no safety check at all!
alpar@591:       ///Using operator = between maps attached to different graph may
alpar@591:       ///cause serious problem.
alpar@591:       ///\todo Is this really so?
alpar@591:       ///\todo It can copy between different types.
alpar@591:       const NodeMap<T>& operator=(const NodeMap<T> &m)
alpar@591:       {
alpar@591: 	container = m.container;
alpar@591: 	return *this;
alpar@591:       }
alpar@591:       template<typename TT>
alpar@591:       const NodeMap<T>& operator=(const NodeMap<TT> &m)
alpar@591:       {
alpar@591: 	std::copy(m.container.begin(), m.container.end(), container.begin());
alpar@591: 	return *this;
alpar@591:       }
alpar@591:       
alpar@591:       void update() {}    //Useless for Dynamic Maps
alpar@591:       void update(T a) {}  //Useless for Dynamic Maps
alpar@591:     };
alpar@591:     
alpar@591:     template <typename T> class EdgeMap
alpar@591:     {
alpar@591:       std::vector<T> container;
alpar@591: 
alpar@591:     public:
alpar@591:       typedef T ValueType;
alpar@591:       typedef Edge KeyType;
alpar@591: 
alpar@591:       EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
alpar@591:       EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { } 
alpar@591:       EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
alpar@591: 
alpar@591:       template<typename TT> friend class EdgeMap;
alpar@591:       ///\todo It can copy between different types. 
alpar@591:       ///\todo We could use 'copy'
alpar@591:       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
alpar@591: 	container(m.container.size())
alpar@591:       {
alpar@591: 	typename std::vector<TT>::const_iterator i;
alpar@591: 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
alpar@591: 	    i!=m.container.end();
alpar@591: 	    i++)
alpar@591: 	  container.push_back(*i);
alpar@591:       }
alpar@591:       void set(Edge n, T a) { container[n.n]=a; }
alpar@591:       //T get(Edge n) const { return container[n.n]; }
alpar@591:       typename std::vector<T>::reference
alpar@591:       operator[](Edge n) { return container[n.n]; }
alpar@591:       typename std::vector<T>::const_reference
alpar@591:       operator[](Edge n) const { return container[n.n]; }
alpar@591: 
alpar@591:       ///\warning There is no safety check at all!
alpar@591:       ///Using operator = between maps attached to different graph may
alpar@591:       ///cause serious problem.
alpar@591:       ///\todo Is this really so?
alpar@591:       ///\todo It can copy between different types.
alpar@591:       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
alpar@591:       {
alpar@591: 	container = m.container;
alpar@591: 	return *this;
alpar@591:       }
alpar@591:       template<typename TT>
alpar@591:       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
alpar@591:       {
alpar@591: 	std::copy(m.container.begin(), m.container.end(), container.begin());
alpar@591: 	return *this;
alpar@591:       }
alpar@774: 
alpar@591:       void update() {}
alpar@591:       void update(T a) {}
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