lemon-0.x: src/hugo/full_graph.h@a5e9303a5511

     1 // -*- c++ -*-

     3 #ifndef HUGO_FULL_GRAPH_H

     4 #define HUGO_FULL_GRAPH_H

     6 ///\ingroup graphs

     7 ///\file

     8 ///\brief FullGraph and SymFullGraph classes.

    10 #include <vector>

    11 #include <limits.h>

    13 #include <hugo/invalid.h>

    15 namespace hugo {

    17 /// \addtogroup graphs

    18 /// @{

    20   ///A full graph class.

    22   ///This is a simple and fast directed full graph implementation.

    23   ///It is completely static, so you can neither add nor delete either

    24   ///edges or nodes.

    25   ///Otherwise it conforms to the graph interface documented under

    26   ///the description of \ref GraphSkeleton.

    27   ///\sa \ref GraphSkeleton.

    28   ///\todo What about loops?

    29   ///\todo Don't we need SymEdgeMap?

    30   ///

    31   ///\author Alpar Juttner

    32   class FullGraph {

    33     int NodeNum;

    34     int EdgeNum;

    35   public:

    36     template <typename T> class EdgeMap;

    37     template <typename T> class NodeMap;

    39     class Node;

    40     class Edge;

    41     class NodeIt;

    42     class EdgeIt;

    43     class OutEdgeIt;

    44     class InEdgeIt;

    46     template <typename T> class NodeMap;

    47     template <typename T> class EdgeMap;

    49   public:

    51     ///Creates a full graph with \c n nodes.

    52     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }

    53     ///

    54     FullGraph(const FullGraph &_g)

    55       : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }

    57     int nodeNum() const { return NodeNum; }  //FIXME: What is this?

    58     int edgeNum() const { return EdgeNum; }  //FIXME: What is this?

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

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

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

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

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

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

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

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

    72     NodeIt& first(NodeIt& v) const {

    73       v=NodeIt(*this); return v; }

    74     EdgeIt& first(EdgeIt& e) const {

    75       e=EdgeIt(*this); return e; }

    76     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {

    77       e=OutEdgeIt(*this,v); return e; }

    78     InEdgeIt& first(InEdgeIt& e, const Node v) const {

    79       e=InEdgeIt(*this,v); return e; }

    81     static bool valid(Edge e) { return e.n!=-1; }

    82     static bool valid(Node n) { return n.n!=-1; }

    84     template <typename It> It getNext(It it) const

    85     { It tmp(it); return next(tmp); }

    87     NodeIt& next(NodeIt& it) const {

    88       it.n=(it.n+2)%(NodeNum+1)-1;

    89       return it;

    90     }

    91     OutEdgeIt& next(OutEdgeIt& it) const

    92     { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }

    93     InEdgeIt& next(InEdgeIt& it) const

    94     { if(!((++it.n)%NodeNum)) it.n=-1; return it; }

    95     static EdgeIt& next(EdgeIt& it) { --it.n; return it; }

    97     static int id(Node v) { return v.n; }

    98     static int id(Edge e) { return e.n; }

   100     class Node {

   101       friend class FullGraph;

   102       template <typename T> friend class NodeMap;

   104       friend class Edge;

   105       friend class OutEdgeIt;

   106       friend class InEdgeIt;

   107       friend class SymEdge;

   109     protected:

   110       int n;

   111       friend int FullGraph::id(Node v);

   112       Node(int nn) {n=nn;}

   113     public:

   114       Node() {}

   115       Node (Invalid) { n=-1; }

   116       bool operator==(const Node i) const {return n==i.n;}

   117       bool operator!=(const Node i) const {return n!=i.n;}

   118       bool operator<(const Node i) const {return n<i.n;}

   119     };

   121     class NodeIt : public Node {

   122       friend class FullGraph;

   123     public:

   124       NodeIt() : Node() { }

   125       NodeIt(Invalid i) : Node(i) { }

   126       NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }

   127       ///\todo Undocumented conversion Node -\> NodeIt.

   128       NodeIt(const FullGraph& G, const Node &n) : Node(n) { }

   129     };

   131     class Edge {

   132       friend class FullGraph;

   133       template <typename T> friend class EdgeMap;

   135       friend class Node;

   136       friend class NodeIt;

   137     protected:

   138       int n; //NodeNum*head+tail;

   139       friend int FullGraph::id(Edge e);

   141       Edge(int nn) {n=nn;}

   142     public:

   143       Edge() { }

   144       Edge (Invalid) { n=-1; }

   145       bool operator==(const Edge i) const {return n==i.n;}

   146       bool operator!=(const Edge i) const {return n!=i.n;}

   147       bool operator<(const Edge i) const {return n<i.n;}

   148       ///\bug This is a workaround until somebody tells me how to

   149       ///make class \c SymFullGraph::SymEdgeMap friend of Edge

   150       int &idref() {return n;}

   151       const int &idref() const {return n;}

   152     };

   154     class EdgeIt : public Edge {

   155       friend class FullGraph;

   156     public:

   157       EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }

   158       EdgeIt (Invalid i) : Edge(i) { }

   159       EdgeIt() : Edge() { }

   160       ///\bug This is a workaround until somebody tells me how to

   161       ///make class \c SymFullGraph::SymEdgeMap friend of Edge

   162       int &idref() {return n;}

   163     };

   165     class OutEdgeIt : public Edge {

   166       friend class FullGraph;

   167     public:

   168       OutEdgeIt() : Edge() { }

   169       OutEdgeIt (Invalid i) : Edge(i) { }

   171       OutEdgeIt(const FullGraph& G,const Node v)

   172 	: Edge(v.n) {}

   173     };

   175     class InEdgeIt : public Edge {

   176       friend class FullGraph;

   177     public:

   178       InEdgeIt() : Edge() { }

   179       InEdgeIt (Invalid i) : Edge(i) { }

   180       InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}

   181     };

   183     template <typename T> class NodeMap

   184     {

   185       std::vector<T> container;

   187     public:

   188       typedef T ValueType;

   189       typedef Node KeyType;

   191       NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }

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

   193       NodeMap(const NodeMap<T> &m) : container(m.container) { }

   195       template<typename TT> friend class NodeMap;

   196       ///\todo It can copy between different types.

   197       template<typename TT> NodeMap(const NodeMap<TT> &m)

   198 	: container(m.container.size())

   199       {

   200 	typename std::vector<TT>::const_iterator i;

   201 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   202 	    i!=m.container.end();

   203 	    i++)

   204 	  container.push_back(*i);

   205       }

   206       void set(Node n, T a) { container[n.n]=a; }

   207       //'T& operator[](Node n)' would be wrong here

   208       typename std::vector<T>::reference

   209       operator[](Node n) { return container[n.n]; }

   210       //'const T& operator[](Node n)' would be wrong here

   211       typename std::vector<T>::const_reference

   212       operator[](Node n) const { return container[n.n]; }

   214       ///\warning There is no safety check at all!

   215       ///Using operator = between maps attached to different graph may

   216       ///cause serious problem.

   217       ///\todo Is this really so?

   218       ///\todo It can copy between different types.

   219       const NodeMap<T>& operator=(const NodeMap<T> &m)

   220       {

   221 	container = m.container;

   222 	return *this;

   223       }

   224       template<typename TT>

   225       const NodeMap<T>& operator=(const NodeMap<TT> &m)

   226       {

   227 	std::copy(m.container.begin(), m.container.end(), container.begin());

   228 	return *this;

   229       }

   231       void update() {}    //Useless for Dynamic Maps

   232       void update(T a) {}  //Useless for Dynamic Maps

   233     };

   235     template <typename T> class EdgeMap

   236     {

   237       std::vector<T> container;

   239     public:

   240       typedef T ValueType;

   241       typedef Edge KeyType;

   243       EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }

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

   245       EdgeMap(const EdgeMap<T> &m) : container(m.container) { }

   247       template<typename TT> friend class EdgeMap;

   248       ///\todo It can copy between different types.

   249       ///\todo We could use 'copy'

   250       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :

   251 	container(m.container.size())

   252       {

   253 	typename std::vector<TT>::const_iterator i;

   254 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   255 	    i!=m.container.end();

   256 	    i++)

   257 	  container.push_back(*i);

   258       }

   259       void set(Edge n, T a) { container[n.n]=a; }

   260       //T get(Edge n) const { return container[n.n]; }

   261       typename std::vector<T>::reference

   262       operator[](Edge n) { return container[n.n]; }

   263       typename std::vector<T>::const_reference

   264       operator[](Edge n) const { return container[n.n]; }

   266       ///\warning There is no safety check at all!

   267       ///Using operator = between maps attached to different graph may

   268       ///cause serious problem.

   269       ///\todo Is this really so?

   270       ///\todo It can copy between different types.

   271       const EdgeMap<T>& operator=(const EdgeMap<T> &m)

   272       {

   273 	container = m.container;

   274 	return *this;

   275       }

   276       template<typename TT>

   277       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)

   278       {

   279 	std::copy(m.container.begin(), m.container.end(), container.begin());

   280 	return *this;

   281       }

   283       void update() {}

   284       void update(T a) {}

   285     };

   287   };

   289   /// @}

   291 } //namespace hugo

   296 #endif //HUGO_FULL_GRAPH_H

author	marci
	Mon, 23 Aug 2004 11:06:00 +0000
changeset 768	a5e9303a5511
parent 722	be8712e1fe07
child 774	4297098d9677
permissions	-rw-r--r--