lemon-0.x: src/hugo/smart_graph.h@147eb3a58706

     1 // -*- mode:C++ -*-

     3 #ifndef HUGO_SMART_GRAPH_H

     4 #define HUGO_SMART_GRAPH_H

     6 ///\ingroup graphs

     7 ///\file

     8 ///\brief SmartGraph and SymSmartGraph classes.

    10 #include <vector>

    11 #include <climits>

    13 #include <hugo/invalid.h>

    15 #include <hugo/array_map_factory.h>

    16 #include <hugo/sym_map_factory.h>

    17 #include <hugo/map_registry.h>

    19 #include <hugo/map_defines.h>

    21 namespace hugo {

    23 /// \addtogroup graphs

    24 /// @{

    25 //  class SymSmartGraph;

    27   ///A smart graph class.

    29   ///This is a simple and fast graph implementation.

    30   ///It is also quite memory efficient, but at the price

    31   ///that <b> it does not support node and edge deletion</b>.

    32   ///It conforms to the graph interface documented under

    33   ///the description of \ref GraphSkeleton.

    34   ///\sa \ref GraphSkeleton.

    35   ///

    36   ///\todo Some member functions could be \c static.

    37   ///

    38   ///\todo A possibly useful functionality: a function saveState() would

    39   ///give back a data sturcture X and then the function restoreState(X)

    40   ///would remove the nodes and edges added after the call of saveState().

    41   ///Of course it should be used as a stack. (Maybe X is not necessary.)

    42   ///

    43   ///\author Alpar Juttner

    44   class SmartGraph {

    46     struct NodeT

    47     {

    48       int first_in,first_out;

    49       NodeT() : first_in(-1), first_out(-1) {}

    50     };

    51     struct EdgeT

    52     {

    53       int head, tail, next_in, next_out;

    54       //FIXME: is this necessary?

    55       EdgeT() : next_in(-1), next_out(-1) {}

    56     };

    58     std::vector<NodeT> nodes;

    60     std::vector<EdgeT> edges;

    63   public:

    65     typedef SmartGraph Graph;

    67     class Node;

    68     class Edge;

    70     class NodeIt;

    71     class EdgeIt;

    72     class OutEdgeIt;

    73     class InEdgeIt;

    75     CREATE_MAP_REGISTRIES;

    76     CREATE_MAPS(ArrayMapFactory);

    78   public:

    80     SmartGraph() : nodes(), edges() { }

    81     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }

    83     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?

    84     int edgeNum() const { return edges.size(); }  //FIXME: What is this?

    86     ///\bug This function does something different than

    87     ///its name would suggests...

    88     int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?

    89     ///\bug This function does something different than

    90     ///its name would suggests...

    91     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?

    93     Node tail(Edge e) const { return edges[e.n].tail; }

    94     Node head(Edge e) const { return edges[e.n].head; }

    96     NodeIt& first(NodeIt& v) const {

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

    98     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

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

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

   108     Node addNode() {

   109       Node n; n.n=nodes.size();

   110       nodes.push_back(NodeT()); //FIXME: Hmmm...

   113       node_maps.add(n);

   114       return n;

   115     }

   117     Edge addEdge(Node u, Node v) {

   118       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...

   119       edges[e.n].tail=u.n; edges[e.n].head=v.n;

   120       edges[e.n].next_out=nodes[u.n].first_out;

   121       edges[e.n].next_in=nodes[v.n].first_in;

   122       nodes[u.n].first_out=nodes[v.n].first_in=e.n;

   124       edge_maps.add(e);

   126       return e;

   127     }

   129     /// Finds an edge between two nodes.

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

   132     ///

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

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

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

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

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

   138     {

   139       int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;

   140       while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;

   141       prev.n=e;

   142       return prev;

   143     }

   145     void clear() {

   146       edge_maps.clear();

   147       edges.clear();

   148       node_maps.clear();

   149       nodes.clear();

   150     }

   152     class Node {

   153       friend class SmartGraph;

   154       template <typename T> friend class NodeMap;

   156       friend class Edge;

   157       friend class OutEdgeIt;

   158       friend class InEdgeIt;

   159       friend class SymEdge;

   161     protected:

   162       int n;

   163       friend int SmartGraph::id(Node v);

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

   165     public:

   166       Node() {}

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

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

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

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

   171       //      ///Validity check

   172       //      operator bool() { return n!=-1; }

   173     };

   175     class NodeIt : public Node {

   176       const SmartGraph *G;

   177       friend class SmartGraph;

   178     public:

   179       NodeIt() : Node() { }

   180       NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }

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

   182       NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }

   183       NodeIt &operator++() {

   184 	n=(n+2)%(G->nodes.size()+1)-1;

   185 	return *this;

   186       }

   187 //       ///Validity check

   188 //       operator bool() { return Node::operator bool(); }

   189     };

   191     class Edge {

   192       friend class SmartGraph;

   193       template <typename T> friend class EdgeMap;

   195       //template <typename T> friend class SymSmartGraph::SymEdgeMap;

   196       //friend Edge SymSmartGraph::opposite(Edge) const;

   198       friend class Node;

   199       friend class NodeIt;

   200     protected:

   201       int n;

   202       friend int SmartGraph::id(Edge e);

   204     public:

   205       /// An Edge with id \c n.

   207       /// \bug It should be

   208       /// obtained by a member function of the Graph.

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

   210       Edge() { }

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

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

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

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

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

   216       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge

   217       int &idref() {return n;}

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

   219 //       ///Validity check

   220 //       operator bool() { return n!=-1; }

   221    };

   223     class EdgeIt : public Edge {

   224       const SmartGraph *G;

   225       friend class SmartGraph;

   226     public:

   227       EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }

   228       EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }

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

   230       EdgeIt() : Edge() { }

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

   232       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge

   233       int &idref() {return n;}

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

   235 //       ///Validity check

   236 //       operator bool() { return Edge::operator bool(); }

   237     };

   239     class OutEdgeIt : public Edge {

   240       const SmartGraph *G;

   241       friend class SmartGraph;

   242     public:

   243       OutEdgeIt() : Edge() { }

   244       OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }

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

   247       OutEdgeIt(const SmartGraph& _G,const Node v)

   248 	: Edge(_G.nodes[v.n].first_out), G(&_G) {}

   249       OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }

   250 //       ///Validity check

   251 //       operator bool() { return Edge::operator bool(); }

   252     };

   254     class InEdgeIt : public Edge {

   255       const SmartGraph *G;

   256       friend class SmartGraph;

   257     public:

   258       InEdgeIt() : Edge() { }

   259       InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }

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

   261       InEdgeIt(const SmartGraph& _G,Node v)

   262 	: Edge(_G.nodes[v.n].first_in), G(&_G) { }

   263       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }

   264 //       ///Validity check

   265 //       operator bool() { return Edge::operator bool(); }

   266     };

   268   };

   270   ///Graph for bidirectional edges.

   272   ///The purpose of this graph structure is to handle graphs

   273   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair

   274   ///of oppositely directed edges.

   275   ///There is a new edge map type called

   276   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   277   ///that complements this

   278   ///feature by

   279   ///storing shared values for the edge pairs. The usual

   280   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   281   ///can be used

   282   ///as well.

   283   ///

   284   ///The oppositely directed edge can also be obtained easily

   285   ///using \ref opposite.

   286   ///\warning It shares the similarity with \ref SmartGraph that

   287   ///it is not possible to delete edges or nodes from the graph.

   288   //\sa \ref SmartGraph.

   290   class SymSmartGraph : public SmartGraph

   291   {

   292   public:

   293     typedef SymSmartGraph Graph;

   295     KEEP_NODE_MAP(SmartGraph);

   296     KEEP_EDGE_MAP(SmartGraph);

   298     CREATE_SYM_EDGE_MAP_REGISTRY;

   299     CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);

   300     IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);

   302     SymSmartGraph() : SmartGraph() { }

   303     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }

   304     ///Adds a pair of oppositely directed edges to the graph.

   305     Edge addEdge(Node u, Node v)

   306     {

   307       Edge e = SmartGraph::addEdge(u,v);

   308       SmartGraph::addEdge(v,u);

   309       return e;

   310     }

   312     ///The oppositely directed edge.

   314     ///Returns the oppositely directed

   315     ///pair of the edge \c e.

   316     static Edge opposite(Edge e)

   317     {

   318       Edge f;

   319       f.idref() = e.idref() - 2*(e.idref()%2) + 1;

   320       return f;

   321     }

   324   };

   326   /// @}

   327 } //namespace hugo

   332 #endif //HUGO_SMART_GRAPH_H

author	marci
	Thu, 02 Sep 2004 17:56:40 +0000
changeset 792	147eb3a58706
parent 774	4297098d9677
child 798	6d1abeb62dd3
permissions	-rw-r--r--