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@591:   ///\todo Shouldn't we avoid loops?
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:     Node aNode(OutEdgeIt e) const { return tail(e); }
alpar@591:     Node aNode(InEdgeIt e) const { return head(e); }
alpar@591: 
alpar@591:     Node bNode(OutEdgeIt e) const { return head(e); }
alpar@591:     Node bNode(InEdgeIt e) const { return tail(e); }
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@591:     bool valid(Edge e) const { return e.n!=-1; }
alpar@591:     bool valid(Node n) const { return n.n!=-1; }
alpar@591:     
alpar@591:     template <typename It> It getNext(It it) const
alpar@591:     { It tmp(it); return next(tmp); }
alpar@591: 
alpar@591:     NodeIt& next(NodeIt& it) const { 
alpar@591:       it.n=(it.n+2)%(NodeNum+1)-1; 
alpar@591:       return it; 
alpar@591:     }
alpar@591:     OutEdgeIt& next(OutEdgeIt& it) const
alpar@591:     { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
alpar@591:     InEdgeIt& next(InEdgeIt& it) const
alpar@591:     { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
alpar@591:     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
alpar@591: 
alpar@591:     int id(Node v) const { return v.n; }
alpar@591:     int id(Edge e) const { return e.n; }
alpar@591: 
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@591:       friend int FullGraph::id(Node v) const; 
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@591:       friend class FullGraph;
alpar@591:     public:
alpar@591:       NodeIt() : Node() { }
alpar@591:       NodeIt(Invalid i) : Node(i) { }
alpar@591:       NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
alpar@591:       ///\todo Undocumented conversion Node -\> NodeIt.
alpar@591:       NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
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@591:       friend int FullGraph::id(Edge e) const;
alpar@591: 
alpar@591:       Edge(int nn) {n=nn;}
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@591:       EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
alpar@591:       EdgeIt (Invalid i) : Edge(i) { }
alpar@591:       EdgeIt() : Edge() { }
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@591:       friend class FullGraph;
alpar@591:     public: 
alpar@591:       OutEdgeIt() : Edge() { }
alpar@591:       OutEdgeIt (Invalid i) : Edge(i) { }
alpar@591: 
alpar@591:       OutEdgeIt(const FullGraph& G,const Node v)
alpar@591: 	: Edge(v.n) {}
alpar@591:     };
alpar@591:     
alpar@591:     class InEdgeIt : public Edge {
alpar@591:       friend class FullGraph;
alpar@591:     public: 
alpar@591:       InEdgeIt() : Edge() { }
alpar@591:       InEdgeIt (Invalid i) : Edge(i) { }
alpar@591:       InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
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@591:       
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