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

     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 Shouldn't we avoid loops?

    29   ///

    30   ///\author Alpar Juttner

    31   class FullGraph {

    32     int NodeNum;

    33     int EdgeNum;

    34   public:

    35     template <typename T> class EdgeMap;

    36     template <typename T> class NodeMap;

    38     class Node;

    39     class Edge;

    40     class NodeIt;

    41     class EdgeIt;

    42     class OutEdgeIt;

    43     class InEdgeIt;

    45     template <typename T> class NodeMap;

    46     template <typename T> class EdgeMap;

    48   public:

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

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

    52     ///

    53     FullGraph(const FullGraph &_g)

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

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

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

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

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

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

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

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

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

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

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

    71     NodeIt& first(NodeIt& v) const {

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

    73     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

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

    81     bool valid(Node n) const { return n.n!=-1; }

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

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

    86     NodeIt& next(NodeIt& it) const {

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

    88       return it;

    89     }

    90     OutEdgeIt& next(OutEdgeIt& it) const

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

    92     InEdgeIt& next(InEdgeIt& it) const

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

    94     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }

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

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

    99     class Node {

   100       friend class FullGraph;

   101       template <typename T> friend class NodeMap;

   103       friend class Edge;

   104       friend class OutEdgeIt;

   105       friend class InEdgeIt;

   106       friend class SymEdge;

   108     protected:

   109       int n;

   110       friend int FullGraph::id(Node v) const;

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

   112     public:

   113       Node() {}

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

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

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

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

   118     };

   120     class NodeIt : public Node {

   121       friend class FullGraph;

   122     public:

   123       NodeIt() : Node() { }

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

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

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

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

   128     };

   130     class Edge {

   131       friend class FullGraph;

   132       template <typename T> friend class EdgeMap;

   134       friend class Node;

   135       friend class NodeIt;

   136     protected:

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

   138       friend int FullGraph::id(Edge e) const;

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

   141     public:

   142       Edge() { }

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

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

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

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

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

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

   149       int &idref() {return n;}

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

   151     };

   153     class EdgeIt : public Edge {

   154       friend class FullGraph;

   155     public:

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

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

   158       EdgeIt() : Edge() { }

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

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

   161       int &idref() {return n;}

   162     };

   164     class OutEdgeIt : public Edge {

   165       friend class FullGraph;

   166     public:

   167       OutEdgeIt() : Edge() { }

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

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

   171 	: Edge(v.n) {}

   172     };

   174     class InEdgeIt : public Edge {

   175       friend class FullGraph;

   176     public:

   177       InEdgeIt() : Edge() { }

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

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

   180     };

   182     template <typename T> class NodeMap

   183     {

   184       std::vector<T> container;

   186     public:

   187       typedef T ValueType;

   188       typedef Node KeyType;

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

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

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

   194       template<typename TT> friend class NodeMap;

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

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

   197 	: container(m.container.size())

   198       {

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

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

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

   202 	    i++)

   203 	  container.push_back(*i);

   204       }

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

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

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

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

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

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

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

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

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

   215       ///cause serious problem.

   216       ///\todo Is this really so?

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

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

   219       {

   220 	container = m.container;

   221 	return *this;

   222       }

   223       template<typename TT>

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

   225       {

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

   227 	return *this;

   228       }

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

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

   232     };

   234     template <typename T> class EdgeMap

   235     {

   236       std::vector<T> container;

   238     public:

   239       typedef T ValueType;

   240       typedef Edge KeyType;

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

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

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

   246       template<typename TT> friend class EdgeMap;

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

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

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

   250 	container(m.container.size())

   251       {

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

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

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

   255 	    i++)

   256 	  container.push_back(*i);

   257       }

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

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

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

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

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

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

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

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

   267       ///cause serious problem.

   268       ///\todo Is this really so?

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

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

   271       {

   272 	container = m.container;

   273 	return *this;

   274       }

   275       template<typename TT>

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

   277       {

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

   279 	return *this;

   280       }

   282       void update() {}

   283       void update(T a) {}

   284     };

   286   };

   288   /// @}

   290 } //namespace hugo

   295 #endif //HUGO_FULL_GRAPH_H

author	marci
	Tue, 11 May 2004 17:02:32 +0000
changeset 612	0856a9a87eb9
parent 592	5961cce7ec53
child 710	891f99700ea1
permissions	-rw-r--r--