lemon-0.x: src/work/alpar/smart_graph.h@924f9555711d

     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     struct NodeT

    16     {

    17       int first_in,first_out;

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

    19     };

    20     struct EdgeT

    21     {

    22       int head, tail, next_in, next_out;

    23       //FIXME: is this necessary?

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

    25     };

    27     std::vector<NodeT> nodes;

    29     std::vector<EdgeT> edges;

    31     template <typename Key> class DynMapBase

    32     {

    33     protected:

    34       SmartGraph* G;

    35     public:

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

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

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

    39       virtual ~DynMapBase() {}

    40       friend class SmartGraph;

    41     };

    42   public:

    43     template <typename T> class DynEdgeMap;

    44     template <typename T> class DynEdgeMap;

    46     class Node;

    47     class Edge;

    49   protected:

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

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

    53   public:

    55     class NodeIt;

    56     class EdgeIt;

    57     class OutEdgeIt;

    58     class InEdgeIt;

    60     //     class Node { int n; };

    61     //     class NodeIt : public Node { };

    62     //     class Edge { int n; };

    63     //     class EdgeIt : public Edge {};

    64     //     class OutEdgeIt : public Edge {};

    65     //     class InEdgeIt : public Edge {};

    66     //     class SymEdge;

    68     template <typename T> class NodeMap;

    69     template <typename T> class EdgeMap;

    71   public:

    73     /* default constructor */

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

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

    78     ~SmartGraph()

    79     {

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

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

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

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

    84     }

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

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

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

    90     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     // Marci

    97     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }

    98     Node aNode(InEdgeIt e) const { return edges[e.n].head; }

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

   101     // Marci

   102     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }

   103     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }

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

   106     NodeIt& first(NodeIt& v) const {

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

   108     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   115     template< typename It >

   116     It first() const { It e; first(e); return e; }

   118     template< typename It >

   119     It first(Node v) const { It e; first(e,v); return e; }

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

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

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

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

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

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

   130     NodeIt& next(NodeIt& it) const {

   131       it.n=(it.n+2)%(nodes.size()+1)-1;

   132       return it;

   133     }

   134     OutEdgeIt& next(OutEdgeIt& it) const

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

   136     InEdgeIt& next(InEdgeIt& it) const

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

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

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

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

   143     Node addNode() {

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

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

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

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

   150       return n;

   151     }

   153     Edge addEdge(Node u, Node v) {

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

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

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

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

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

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

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

   163       return e;

   164     }

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

   168     class Node {

   169       friend class SmartGraph;

   170       template <typename T> friend class NodeMap;

   171       template <typename T> friend class DynNodeMap;

   173       friend class Edge;

   174       friend class OutEdgeIt;

   175       friend class InEdgeIt;

   176       friend class SymEdge;

   178     protected:

   179       int n;

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

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

   182     public:

   183       Node() {}

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

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

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

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

   188     };

   190     class NodeIt : public Node {

   191       friend class SmartGraph;

   192     public:

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

   194       NodeIt() : Node() { }

   195     };

   197     class Edge {

   198       friend class SmartGraph;

   199       template <typename T> friend class EdgeMap;

   200       template <typename T> friend class DynEdgeMap;

   202       friend class Node;

   203       friend class NodeIt;

   204     protected:

   205       int n;

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

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

   209     public:

   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     };

   217     class EdgeIt : public Edge {

   218       friend class SmartGraph;

   219     public:

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

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

   222       EdgeIt() : Edge() { }

   223     };

   225     class OutEdgeIt : public Edge {

   226       friend class SmartGraph;

   227     public:

   228       OutEdgeIt() : Edge() { }

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

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

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

   233     };

   235     class InEdgeIt : public Edge {

   236       friend class SmartGraph;

   237     public:

   238       InEdgeIt() : Edge() { }

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

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

   241     };

   243     // Map types

   245     template <typename T>

   246     class NodeMap {

   247       const SmartGraph& G;

   248       std::vector<T> container;

   249     public:

   250       typedef T ValueType;

   251       typedef Node KeyType;

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

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

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

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

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

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

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

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

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

   261     };

   263     template <typename T>

   264     class EdgeMap {

   265       const SmartGraph& G;

   266       std::vector<T> container;

   267     public:

   268       typedef T ValueType;

   269       typedef Edge KeyType;

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

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

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

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

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

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

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

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

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

   279     };

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

   282     {

   283       std::vector<T> container;

   285     public:

   286       typedef T ValueType;

   287       typedef Node KeyType;

   289       DynNodeMap(const SmartGraph &_G) :

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

   291       {

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

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

   294 	G->dyn_node_maps.push_back(this);

   295       }

   296       ~DynNodeMap()

   297       {

   298 	if(G) {

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

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

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

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

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

   304 	  if(*i==this) {

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

   306 	    G->dyn_node_maps.pop_back();

   307 	  }

   308 	}

   309       }

   311       void add(const Node k)

   312       {

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

   314       }

   316 //       void erase(const Node k)

   317 //       {

   318 // 	//FIXME: Please implement me.

   319 //       }

   320 //       void erase(const Edge k)

   321 //       {

   322 // 	//FIXME: Please implement me.

   323 //       }

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

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

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

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

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

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

   332     };

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

   335     {

   336       std::vector<T> container;

   338     public:

   339       typedef T ValueType;

   340       typedef Edge KeyType;

   342       DynEdgeMap(const SmartGraph &_G) :

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

   344       {

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

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

   347 	G->dyn_edge_maps.push_back(this);

   348       }

   349       ~DynEdgeMap()

   350       {

   351 	if(G) {

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

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

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

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

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

   357 	  if(*i==this) {

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

   359 	    G->dyn_edge_maps.pop_back();

   360 	  }

   361 	}

   362       }

   364       void add(const Edge k)

   365       {

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

   367       }

   368       void erase(const Edge k)

   369       {

   370 	//FIXME: Please implement me.

   371       }

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

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

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

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

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

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

   380     };

   382   };

   383 } //namespace hugo

   388 #endif //SMART_GRAPH_H

author	alpar
	Fri, 12 Mar 2004 15:42:51 +0000
changeset 177	924f9555711d
parent 174	44700ed9ffaa
child 185	259540358bbf
permissions	-rw-r--r--