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

     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     NodeIt& first(NodeIt& v) const {

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

    68     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

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

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

    78     /// Finds an edge between two nodes.

    80     /// Finds an edge from node \c u to node \c v.

    81     ///

    82     /// If \c prev is \ref INVALID (this is the default value), then

    83     /// It finds the first edge from \c u to \c v. Otherwise it looks for

    84     /// the next edge from \c u to \c v after \c prev.

    85     /// \return The found edge or INVALID if there is no such an edge.

    86     Edge findEdge(Node u,Node v, Edge prev = INVALID)

    87     {

    88       return prev.n==-1?Edge(*this,u.n,v.n):INVALID;

    89     }

    92     class Node {

    93       friend class FullGraph;

    94       template <typename T> friend class NodeMap;

    96       friend class Edge;

    97       friend class OutEdgeIt;

    98       friend class InEdgeIt;

    99       friend class SymEdge;

   101     protected:

   102       int n;

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

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

   105     public:

   106       Node() {}

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

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

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

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

   111     };

   113     class NodeIt : public Node {

   114       const FullGraph *G;

   115       friend class FullGraph;

   116     public:

   117       NodeIt() : Node() { }

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

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

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

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

   122       NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }

   123     };

   125     class Edge {

   126       friend class FullGraph;

   127       template <typename T> friend class EdgeMap;

   129       friend class Node;

   130       friend class NodeIt;

   131     protected:

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

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

   135       Edge(int nn) : n(nn) {}

   136       Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}

   137     public:

   138       Edge() { }

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

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

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

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

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

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

   145       int &idref() {return n;}

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

   147     };

   149     class EdgeIt : public Edge {

   150       friend class FullGraph;

   151     public:

   152       EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }

   153       EdgeIt(const FullGraph&, Edge e) : Edge(e) { }

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

   155       EdgeIt() : Edge() { }

   156       EdgeIt& operator++() { --n; return *this; }

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

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

   160       int &idref() {return n;}

   161     };

   163     class OutEdgeIt : public Edge {

   164       const FullGraph *G;

   165       friend class FullGraph;

   166     public:

   167       OutEdgeIt() : Edge() { }

   168       OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }

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

   171       OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}

   173       OutEdgeIt& operator++()

   174       { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }

   176     };

   178     class InEdgeIt : public Edge {

   179       const FullGraph *G;

   180       friend class FullGraph;

   181     public:

   182       InEdgeIt() : Edge() { }

   183       InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }

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

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

   186       InEdgeIt& operator++()

   187       { if(!((++n)%G->NodeNum)) n=-1; return *this; }

   188     };

   190     template <typename T> class NodeMap

   191     {

   192       std::vector<T> container;

   194     public:

   195       typedef T ValueType;

   196       typedef Node KeyType;

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

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

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

   202       template<typename TT> friend class NodeMap;

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

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

   205 	: container(m.container.size())

   206       {

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

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

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

   210 	    i++)

   211 	  container.push_back(*i);

   212       }

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

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

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

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

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

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

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

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

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

   223       ///cause serious problem.

   224       ///\todo Is this really so?

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

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

   227       {

   228 	container = m.container;

   229 	return *this;

   230       }

   231       template<typename TT>

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

   233       {

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

   235 	return *this;

   236       }

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

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

   240     };

   242     template <typename T> class EdgeMap

   243     {

   244       std::vector<T> container;

   246     public:

   247       typedef T ValueType;

   248       typedef Edge KeyType;

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

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

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

   254       template<typename TT> friend class EdgeMap;

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

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

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

   258 	container(m.container.size())

   259       {

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

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

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

   263 	    i++)

   264 	  container.push_back(*i);

   265       }

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

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

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

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

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

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

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

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

   275       ///cause serious problem.

   276       ///\todo Is this really so?

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

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

   279       {

   280 	container = m.container;

   281 	return *this;

   282       }

   283       template<typename TT>

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

   285       {

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

   287 	return *this;

   288       }

   290       void update() {}

   291       void update(T a) {}

   292     };

   294   };

   296   /// @}

   298 } //namespace hugo

   303 #endif //HUGO_FULL_GRAPH_H

author	marci
	Tue, 31 Aug 2004 11:26:59 +0000
changeset 775	e46a1f0623a0
parent 752	327c2f67a066
child 782	df2e45e09652
permissions	-rw-r--r--