source: lemon-0.x/src/hugo/full_graph.h @ 636:e59b0c363a9e

// -*- c++ -*-

#ifndef HUGO_FULL_GRAPH_H
#define HUGO_FULL_GRAPH_H

///\ingroup graphs
///\file
///\brief FullGraph and SymFullGraph classes.

#include <vector>
#include <limits.h>

#include <hugo/invalid.h>

namespace hugo {

/// \addtogroup graphs
/// @{

  ///A full graph class.

  ///This is a simple and fast directed full graph implementation.
  ///It is completely static, so you can neither add nor delete either
  ///edges or nodes.
  ///Otherwise it conforms to the graph interface documented under
  ///the description of \ref GraphSkeleton.
  ///\sa \ref GraphSkeleton.
  ///\todo Shouldn't we avoid loops?
  ///
  ///\author Alpar Juttner
  class FullGraph {
    int NodeNum;
    int EdgeNum;
  public:
    template <typename T> class EdgeMap;
    template <typename T> class NodeMap;

    class Node;
    class Edge;
    class NodeIt;
    class EdgeIt;
    class OutEdgeIt;
    class InEdgeIt;
    
    template <typename T> class NodeMap;
    template <typename T> class EdgeMap;
    
  public:

    ///Creates a full graph with \c n nodes.
    FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
    ///
    FullGraph(const FullGraph &_g)
      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    
    int nodeNum() const { return NodeNum; }  //FIXME: What is this?
    int edgeNum() const { return EdgeNum; }  //FIXME: What is this?

    int maxNodeId() const { return NodeNum; }  //FIXME: What is this?
    int maxEdgeId() const { return EdgeNum; }  //FIXME: What is this?

    Node tail(Edge e) const { return e.n%NodeNum; }
    Node head(Edge e) const { return e.n/NodeNum; }

    Node aNode(OutEdgeIt e) const { return tail(e); }
    Node aNode(InEdgeIt e) const { return head(e); }

    Node bNode(OutEdgeIt e) const { return head(e); }
    Node bNode(InEdgeIt e) const { return tail(e); }

    NodeIt& first(NodeIt& v) const {
      v=NodeIt(*this); return v; }
    EdgeIt& first(EdgeIt& e) const { 
      e=EdgeIt(*this); return e; }
    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
      e=OutEdgeIt(*this,v); return e; }
    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
      e=InEdgeIt(*this,v); return e; }

    bool valid(Edge e) const { return e.n!=-1; }
    bool valid(Node n) const { return n.n!=-1; }
    
    template <typename It> It getNext(It it) const
    { It tmp(it); return next(tmp); }

    NodeIt& next(NodeIt& it) const { 
      it.n=(it.n+2)%(NodeNum+1)-1; 
      return it; 
    }
    OutEdgeIt& next(OutEdgeIt& it) const
    { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
    InEdgeIt& next(InEdgeIt& it) const
    { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }

    int id(Node v) const { return v.n; }
    int id(Edge e) const { return e.n; }

    class Node {
      friend class FullGraph;
      template <typename T> friend class NodeMap;

      friend class Edge;
      friend class OutEdgeIt;
      friend class InEdgeIt;
      friend class SymEdge;

    protected:
      int n;
      friend int FullGraph::id(Node v) const; 
      Node(int nn) {n=nn;}
    public:
      Node() {}
      Node (Invalid) { n=-1; }
      bool operator==(const Node i) const {return n==i.n;}
      bool operator!=(const Node i) const {return n!=i.n;}
      bool operator<(const Node i) const {return n<i.n;}
    };
    
    class NodeIt : public Node {
      friend class FullGraph;
    public:
      NodeIt() : Node() { }
      NodeIt(Invalid i) : Node(i) { }
      NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
      ///\todo Undocumented conversion Node -\> NodeIt.
      NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
    };

    class Edge {
      friend class FullGraph;
      template <typename T> friend class EdgeMap;
      
      friend class Node;
      friend class NodeIt;
    protected:
      int n; //NodeNum*head+tail;
      friend int FullGraph::id(Edge e) const;

      Edge(int nn) {n=nn;}
    public:
      Edge() { }
      Edge (Invalid) { n=-1; }
      bool operator==(const Edge i) const {return n==i.n;}
      bool operator!=(const Edge i) const {return n!=i.n;}
      bool operator<(const Edge i) const {return n<i.n;}
      ///\bug This is a workaround until somebody tells me how to
      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
      int &idref() {return n;}
      const int &idref() const {return n;}
    };
    
    class EdgeIt : public Edge {
      friend class FullGraph;
    public:
      EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
      EdgeIt (Invalid i) : Edge(i) { }
      EdgeIt() : Edge() { }
      ///\bug This is a workaround until somebody tells me how to
      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
      int &idref() {return n;}
    };
    
    class OutEdgeIt : public Edge {
      friend class FullGraph;
    public: 
      OutEdgeIt() : Edge() { }
      OutEdgeIt (Invalid i) : Edge(i) { }

      OutEdgeIt(const FullGraph& G,const Node v)
        : Edge(v.n) {}
    };
    
    class InEdgeIt : public Edge {
      friend class FullGraph;
    public: 
      InEdgeIt() : Edge() { }
      InEdgeIt (Invalid i) : Edge(i) { }
      InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
    };

    template <typename T> class NodeMap
    {
      std::vector<T> container;

    public:
      typedef T ValueType;
      typedef Node KeyType;

      NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
      NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
      NodeMap(const NodeMap<T> &m) : container(m.container) { }

      template<typename TT> friend class NodeMap;
      ///\todo It can copy between different types.
      template<typename TT> NodeMap(const NodeMap<TT> &m)
        : container(m.container.size())
      {
        typename std::vector<TT>::const_iterator i;
        for(typename std::vector<TT>::const_iterator i=m.container.begin();
            i!=m.container.end();
            i++)
          container.push_back(*i);
      }
      void set(Node n, T a) { container[n.n]=a; }
      //'T& operator[](Node n)' would be wrong here
      typename std::vector<T>::reference
      operator[](Node n) { return container[n.n]; }
      //'const T& operator[](Node n)' would be wrong here
      typename std::vector<T>::const_reference 
      operator[](Node n) const { return container[n.n]; }

      ///\warning There is no safety check at all!
      ///Using operator = between maps attached to different graph may
      ///cause serious problem.
      ///\todo Is this really so?
      ///\todo It can copy between different types.
      const NodeMap<T>& operator=(const NodeMap<T> &m)
      {
        container = m.container;
        return *this;
      }
      template<typename TT>
      const NodeMap<T>& operator=(const NodeMap<TT> &m)
      {
        std::copy(m.container.begin(), m.container.end(), container.begin());
        return *this;
      }
      
      void update() {}    //Useless for Dynamic Maps
      void update(T a) {}  //Useless for Dynamic Maps
    };
    
    template <typename T> class EdgeMap
    {
      std::vector<T> container;

    public:
      typedef T ValueType;
      typedef Edge KeyType;

      EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
      EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { } 
      EdgeMap(const EdgeMap<T> &m) : container(m.container) { }

      template<typename TT> friend class EdgeMap;
      ///\todo It can copy between different types. 
      ///\todo We could use 'copy'
      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
        container(m.container.size())
      {
        typename std::vector<TT>::const_iterator i;
        for(typename std::vector<TT>::const_iterator i=m.container.begin();
            i!=m.container.end();
            i++)
          container.push_back(*i);
      }
      void set(Edge n, T a) { container[n.n]=a; }
      //T get(Edge n) const { return container[n.n]; }
      typename std::vector<T>::reference
      operator[](Edge n) { return container[n.n]; }
      typename std::vector<T>::const_reference
      operator[](Edge n) const { return container[n.n]; }

      ///\warning There is no safety check at all!
      ///Using operator = between maps attached to different graph may
      ///cause serious problem.
      ///\todo Is this really so?
      ///\todo It can copy between different types.
      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
      {
        container = m.container;
        return *this;
      }
      template<typename TT>
      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
      {
        std::copy(m.container.begin(), m.container.end(), container.begin());
        return *this;
      }
      
      void update() {}
      void update(T a) {}
    };

  };

  /// @}  

} //namespace hugo




#endif //HUGO_FULL_GRAPH_H