lemon-0.x: src/work/alpar/smart_graph.h@7949a29a334e

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

     3 #ifndef SMART_GRAPH_H

     4 #define SMART_GRAPH_H

     6 #include <vector>

     7 #include <limits.h>

     9 #include <invalid.h>

    11 namespace hugo {

    13   class SmartGraph {

    15 //     static const int INVALID=-1;

    16 //     static const int INVALID_NODE=INT_MAX;

    18     struct NodeT

    19     {

    20       int first_in,first_out;

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

    22     };

    23     struct EdgeT

    24     {

    25       int head, tail, next_in, next_out;

    26       //FIXME: is this necessary?

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

    28     };

    30     std::vector<NodeT> nodes;

    32     std::vector<EdgeT> edges;

    34     template <typename Key> class DynMapBase

    35     {

    36     protected:

    37       SmartGraph* G;

    38     public:

    39       virtual void add(const Key k) = NULL;

    40       virtual void erase(const Key k) = NULL;

    41       DynMapBase(const SmartGraph &_G) : G(&_G) {}

    42       virtual ~DynMapBase() {}

    43       friend class SmartGraph;

    44     };

    45   public:

    46     template <typename T> class DynEdgeMap;

    47     template <typename T> class DynEdgeMap;

    49     class Node;

    50     class Edge;

    52   protected:

    53     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;

    54     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;

    56   public:

    58     class NodeIt;

    59     class EdgeIt;

    60     class OutEdgeIt;

    61     class InEdgeIt;

    63     //     class Node { int n; };

    64     //     class NodeIt : public Node { };

    65     //     class Edge { int n; };

    66     //     class EdgeIt : public Edge {};

    67     //     class OutEdgeIt : public Edge {};

    68     //     class InEdgeIt : public Edge {};

    69     //     class SymEdge;

    71     template <typename T> class NodeMap;

    72     template <typename T> class EdgeMap;

    74   public:

    76     /* default constructor */

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

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

    81     ~SmartGraph()

    82     {

    83       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

    84 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

    85       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

    86 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

    87     }

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

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

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

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

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

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

    99 //     Node aNode(const OutEdgeIt& e) const { return tail(e); }

   100 //     Node aNode(const InEdgeIt& e) const { return head(e); }

   101 //     //Node aNode(const SymEdge& e) const { return e.aNode(); }

   103 //     Node bNode(const OutEdgeIt& e) const { return head(e); }

   104 //     Node bNode(const InEdgeIt& e) const { return tail(e); }

   105 //     //Node bNode(const SymEdge& e) const { return e.bNode(); }

   107     NodeIt& first(NodeIt& v) const {

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

   109     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   116     template< typename It >

   117     It first() const {

   118       It e;

   119       getFirst(e);

   120       return e;

   121     }

   123     template< typename It >

   124     It first(Node v) const {

   125       It e;

   126       getFirst(e, v);

   127       return e;

   128     }

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

   131     //    bool valid(EdgeIt e) const { return e.n<int(edges.size()); }

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

   134     void setInvalid(Edge &e) { e.n=-1; }

   135     void setInvalid(Node &n) { n.n=-1; }

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

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

   139     //{ It tmp; tmp.n=it.n+1; return tmp; }

   141     Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }

   142     OutEdgeIt& next(OutEdgeIt& it) const

   143     { it.n=edges[it.n].next_out; return it; }

   144     InEdgeIt& next(InEdgeIt& it) const

   145     { it.n=edges[it.n].next_in; return it; }

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

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

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

   151     Node addNode() {

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

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

   155       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   156 	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);

   158       return n;

   159     }

   161     Edge addEdge(Node u, Node v) {

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

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

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

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

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

   168       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

   169 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);

   171       return e;

   172     }

   174     void clear() {nodes.clear();edges.clear();}

   176     class Node {

   177       friend class SmartGraph;

   178       template <typename T> friend class NodeMap;

   179       template <typename T> friend class DynNodeMap;

   181       friend class Edge;

   182       friend class OutEdgeIt;

   183       friend class InEdgeIt;

   184       friend class SymEdge;

   186     protected:

   187       int n;

   188       friend int SmartGraph::id(Node v) const;

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

   190     public:

   191       Node() {}

   192       Node (Invalid i) { n=-1; }

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

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

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

   196     };

   198     class NodeIt : public Node {

   199       friend class SmartGraph;

   200     public:

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

   202       NodeIt() : Node() { }

   203     };

   205     class Edge {

   206       friend class SmartGraph;

   207       template <typename T> friend class EdgeMap;

   208       template <typename T> friend class DynEdgeMap;

   210       friend class Node;

   211       friend class NodeIt;

   212     protected:

   213       int n;

   214       friend int SmartGraph::id(Edge e) const;

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

   217     public:

   218       Edge() { }

   219       Edge (Invalid i) { n=-1; }

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

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

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

   223     };

   225     class EdgeIt : public Edge {

   226       friend class SmartGraph;

   227     public:

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

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

   230       EdgeIt() : Edge() { }

   231     };

   233     class OutEdgeIt : public Edge {

   234       friend class SmartGraph;

   235     public:

   236       OutEdgeIt() : Edge() { }

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

   239       OutEdgeIt(const SmartGraph& G,const Node v)

   240 	: Edge(G.nodes[v.n].first_out) {}

   241     };

   243     class InEdgeIt : public Edge {

   244       friend class SmartGraph;

   245     public:

   246       InEdgeIt() : Edge() { }

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

   248       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}

   249     };

   251     // Map types

   253     template <typename T>

   254     class NodeMap {

   255       const SmartGraph& G;

   256       std::vector<T> container;

   257     public:

   258       typedef T ValueType;

   259       typedef Node KeyType;

   260       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }

   261       NodeMap(const SmartGraph& _G, T a) :

   262 	G(_G), container(G.maxNodeId(), a) { }

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

   264       T get(Node n) const { return container[n.n]; }

   265       T& operator[](Node n) { return container[n.n]; }

   266       const T& operator[](Node n) const { return container[n.n]; }

   267       void update() { container.resize(G.maxNodeId()); }

   268       void update(T a) { container.resize(G.maxNodeId(), a); }

   269     };

   271     template <typename T>

   272     class EdgeMap {

   273       const SmartGraph& G;

   274       std::vector<T> container;

   275     public:

   276       typedef T ValueType;

   277       typedef Edge KeyType;

   278       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }

   279       EdgeMap(const SmartGraph& _G, T a) :

   280 	G(_G), container(G.maxEdgeId(), a) { }

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

   282       T get(Edge e) const { return container[e.n]; }

   283       T& operator[](Edge e) { return container[e.n]; }

   284       const T& operator[](Edge e) const { return container[e.n]; }

   285       void update() { container.resize(G.maxEdgeId()); }

   286       void update(T a) { container.resize(G.maxEdgeId(), a); }

   287     };

   289     template <typename T> class DynNodeMap : public DynMapBase<Node>

   290     {

   291       std::vector<T> container;

   293     public:

   294       typedef T ValueType;

   295       typedef Node KeyType;

   297       DynNodeMap(const SmartGraph &_G) :

   298 	DynMapBase<Node>(_G), container(_G.maxNodeId())

   299       {

   300 	//FIXME: What if there are empty Id's?

   301 	//FIXME: Can I use 'this' in a constructor?

   302 	G->dyn_node_maps.push_back(this);

   303       }

   304       ~DynNodeMap()

   305       {

   306 	if(G) {

   307 	  std::vector<DynMapBase<Node>* >::iterator i;

   308 	  for(i=G->dyn_node_maps.begin();

   309 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

   310 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

   311 	  //A better way to do that: (Is this really important?)

   312 	  if(*i==this) {

   313 	    *i=G->dyn_node_maps.back();

   314 	    G->dyn_node_maps.pop_back();

   315 	  }

   316 	}

   317       }

   319       void add(const Node k)

   320       {

   321 	if(k.n>=container.size()) container.resize(k.n+1);

   322       }

   323 //       void erase(const Node k)

   324 //       {

   325 // 	//FIXME: Please implement me.

   326 //       }

   327 //       void erase(const Edge k)

   328 //       {

   329 // 	//FIXME: Please implement me.

   330 //       }

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

   333       T get(Node n) const { return container[n.n]; }

   334       T& operator[](Node n) { return container[n.n]; }

   335       const T& operator[](Node n) const { return container[n.n]; }

   337       void update() {}    //Useless for DynMaps

   338       void update(T a) {}  //Useless for DynMaps

   339     };

   341     template <typename T> class DynEdgeMap : public DynMapBase<Edge>

   342     {

   343       std::vector<T> container;

   345     public:

   346       typedef T ValueType;

   347       typedef Edge KeyType;

   349       DynEdgeMap(const SmartGraph &_G) :

   350 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())

   351       {

   352 	//FIXME: What if there are empty Id's?

   353 	//FIXME: Can I use 'this' in a constructor?

   354 	G->dyn_edge_maps.push_back(this);

   355       }

   356       ~DynEdgeMap()

   357       {

   358 	if(G) {

   359 	  std::vector<DynMapBase<Edge>* >::iterator i;

   360 	  for(i=G->dyn_edge_maps.begin();

   361 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

   362 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   363 	  //A better way to do that: (Is this really important?)

   364 	  if(*i==this) {

   365 	    *i=G->dyn_edge_maps.back();

   366 	    G->dyn_edge_maps.pop_back();

   367 	  }

   368 	}

   369       }

   371       void add(const Edge k)

   372       {

   373 	if(k.n>=int(container.size())) container.resize(k.n+1);

   374       }

   375       void erase(const Edge k)

   376       {

   377 	//FIXME: Please implement me.

   378       }

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

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

   382       T& operator[](Edge n) { return container[n.n]; }

   383       const T& operator[](Edge n) const { return container[n.n]; }

   385       void update() {}    //Useless for DynMaps

   386       void update(T a) {}  //Useless for DynMaps

   387     };

   389   };

   390 } //namespace hugo

   395 #endif //SMART_GRAPH_H

author	jacint
	Thu, 11 Mar 2004 12:55:50 +0000
changeset 167	7949a29a334e
parent 157	ee17030e5f47
child 174	44700ed9ffaa
permissions	-rw-r--r--