lemon-0.x: src/work/alpar/smart_graph.h@44700ed9ffaa

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

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

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

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

   104     // Marci

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

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

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

   109     NodeIt& first(NodeIt& v) const {

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

   111     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   118     template< typename It >

   119     It first() const {

   120       It e;

   121       //Marci

   122       /*getF*/first(e);

   123       return e;

   124     }

   126     template< typename It >

   127     It first(Node v) const {

   128       It e;

   129       //Marci

   130       /*getF*/first(e, v);

   131       return e;

   132     }

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

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

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

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

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

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

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

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

   145     //FIXME correction Marci: I changed to NodeIt from Node

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

   147     NodeIt& next(NodeIt& it) const {

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

   149       return it;

   150     }

   151     OutEdgeIt& next(OutEdgeIt& it) const

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

   153     InEdgeIt& next(InEdgeIt& it) const

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

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

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

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

   160     Node addNode() {

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

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

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

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

   167       return n;

   168     }

   170     Edge addEdge(Node u, Node v) {

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

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

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

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

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

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

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

   180       return e;

   181     }

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

   185     class Node {

   186       friend class SmartGraph;

   187       template <typename T> friend class NodeMap;

   188       template <typename T> friend class DynNodeMap;

   190       friend class Edge;

   191       friend class OutEdgeIt;

   192       friend class InEdgeIt;

   193       friend class SymEdge;

   195     protected:

   196       int n;

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

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

   199     public:

   200       Node() {}

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

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

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

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

   205     };

   207     class NodeIt : public Node {

   208       friend class SmartGraph;

   209     public:

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

   211       NodeIt() : Node() { }

   212     };

   214     class Edge {

   215       friend class SmartGraph;

   216       template <typename T> friend class EdgeMap;

   217       template <typename T> friend class DynEdgeMap;

   219       friend class Node;

   220       friend class NodeIt;

   221     protected:

   222       int n;

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

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

   226     public:

   227       Edge() { }

   228       // Marci: kiszedtem az Invalid i-bol az i-t

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

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

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

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

   233     };

   235     class EdgeIt : public Edge {

   236       friend class SmartGraph;

   237     public:

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

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

   240       EdgeIt() : Edge() { }

   241     };

   243     class OutEdgeIt : public Edge {

   244       friend class SmartGraph;

   245     public:

   246       OutEdgeIt() : Edge() { }

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

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

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

   251     };

   253     class InEdgeIt : public Edge {

   254       friend class SmartGraph;

   255     public:

   256       InEdgeIt() : Edge() { }

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

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

   259     };

   261     // Map types

   263     template <typename T>

   264     class NodeMap {

   265       const SmartGraph& G;

   266       std::vector<T> container;

   267     public:

   268       typedef T ValueType;

   269       typedef Node KeyType;

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

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

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

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

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

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

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

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

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

   279     };

   281     template <typename T>

   282     class EdgeMap {

   283       const SmartGraph& G;

   284       std::vector<T> container;

   285     public:

   286       typedef T ValueType;

   287       typedef Edge KeyType;

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

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

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

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

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

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

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

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

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

   297     };

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

   300     {

   301       std::vector<T> container;

   303     public:

   304       typedef T ValueType;

   305       typedef Node KeyType;

   307       DynNodeMap(const SmartGraph &_G) :

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

   309       {

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

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

   312 	G->dyn_node_maps.push_back(this);

   313       }

   314       ~DynNodeMap()

   315       {

   316 	if(G) {

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

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

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

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

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

   322 	  if(*i==this) {

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

   324 	    G->dyn_node_maps.pop_back();

   325 	  }

   326 	}

   327       }

   329       void add(const Node k)

   330       {

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

   332       }

   333 //       void erase(const Node k)

   334 //       {

   335 // 	//FIXME: Please implement me.

   336 //       }

   337 //       void erase(const Edge k)

   338 //       {

   339 // 	//FIXME: Please implement me.

   340 //       }

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

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

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

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

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

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

   349     };

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

   352     {

   353       std::vector<T> container;

   355     public:

   356       typedef T ValueType;

   357       typedef Edge KeyType;

   359       DynEdgeMap(const SmartGraph &_G) :

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

   361       {

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

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

   364 	G->dyn_edge_maps.push_back(this);

   365       }

   366       ~DynEdgeMap()

   367       {

   368 	if(G) {

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

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

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

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

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

   374 	  if(*i==this) {

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

   376 	    G->dyn_edge_maps.pop_back();

   377 	  }

   378 	}

   379       }

   381       void add(const Edge k)

   382       {

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

   384       }

   385       void erase(const Edge k)

   386       {

   387 	//FIXME: Please implement me.

   388       }

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

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

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

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

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

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

   397     };

   399   };

   400 } //namespace hugo

   405 #endif //SMART_GRAPH_H

author	marci
	Fri, 12 Mar 2004 09:19:54 +0000
changeset 174	44700ed9ffaa
parent 164	970b265696b0
child 177	924f9555711d
permissions	-rw-r--r--