lemon-0.x: src/work/marci/leda/leda_graph

     1 // -*- c++ -*-

     2 #ifndef HUGO_LEDA_GRAPH_WRAPPER_H

     3 #define HUGO_LEDA_GRAPH_WRAPPER_H

     5 #include <LEDA/graph.h>

     6 #include <LEDA/node_array.h>

     7 #include <LEDA/edge_array.h>

     8 #include <LEDA/node_map.h>

     9 #include <LEDA/edge_map.h>

    10 //#include <LEDA/graph_alg.h>

    11 //#include <LEDA/dimacs.h>

    13 //#if defined(LEDA_NAMESPACE)

    14 //using namespace leda;

    15 //#endif

    17 #include <hugo/invalid.h>

    19 namespace hugo {

    21   /// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.

    22   ///

    23   /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs

    24   /// to satisfy HUGO graph concepts.

    25   /// Then the generic HUGOlib algorithms and wrappers can be used

    26   /// with LEDA graphs.

    27   /// \ingroup gwrapper

    28   template<typename Graph>

    29   class LedaGraphWrapper

    30   {

    31   protected:

    32     Graph* l_graph;

    33     LedaGraphWrapper() : l_graph(0) { }

    34     void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }

    35   public:

    37         //LedaGraphWrapper() { }

    38     LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }

    39     LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { }

    41     template <typename T> class NodeMap;

    42     template <typename T> class EdgeMap;

    43     template <typename T> class NodeMapWrapper;

    44     template <typename T> class EdgeMapWrapper;

    46     class Node;

    47     class NodeIt;

    48     class Edge;

    49     class EdgeIt;

    50     class OutEdgeIt;

    51     class InEdgeIt;

    53     /// The base type of the node iterators.

    54     class Node {

    55       friend class LedaGraphWrapper<Graph>;

    56       //friend class Edge;

    57       friend class EdgeIt;

    58       friend class InEdgeIt;

    59       friend class OutEdgeIt;

    60     protected:

    61       template <typename T> friend class NodeMap;

    62       leda_node l_n;

    63     public: //FIXME

    64       Node(leda_node _l_n) : l_n(_l_n) { }

    65     public:

    66       /// @warning The default constructor sets the iterator

    67       /// to an undefined value.

    68       Node() {}   //FIXME

    69       /// Initialize the iterator to be invalid

    70       Node(Invalid) : l_n(0) { }

    71       //Node(const Node &) {}

    72       bool operator==(Node n) const { return l_n==n.l_n; } //FIXME

    73       bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME

    74       operator leda_node () { return l_n; }

    75     };

    77     /// This iterator goes through each node.

    78     class NodeIt : public Node {

    79     public:

    80       /// @warning The default constructor sets the iterator

    81       /// to an undefined value.

    82       NodeIt() {} //FIXME

    83       /// Initialize the iterator to be invalid

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

    85       /// Sets the iterator to the first node of \c G.

    86       NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }

    87       //NodeIt(const NodeIt &) {} //FIXME

    88     };

    90     /// The base type of the edge iterators.

    91     class Edge {

    92       friend class LedaGraphWrapper;

    93     protected:

    94       template <typename T> friend class EdgeMap;

    95       leda_edge l_e;

    96     public: //FIXME

    97       Edge(leda_edge _l_e) : l_e(_l_e) { }

    98     public:

    99       /// @warning The default constructor sets the iterator

   100       /// to an undefined value.

   101       Edge() {}   //FIXME

   102       /// Initialize the iterator to be invalid

   103       Edge(Invalid) : l_e(0) {}

   104       //Edge(const Edge &) {}

   105       bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME

   106       bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME

   107       operator leda_edge () { return l_e; }

   108     };

   110     /// This iterator goes trought the outgoing edges of a certain graph.

   112     class OutEdgeIt : public Edge {

   113     public:

   114       /// @warning The default constructor sets the iterator

   115       /// to an undefined value.

   116       OutEdgeIt() {}

   117       /// Initialize the iterator to be invalid

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

   119       /// This constructor sets the iterator to first outgoing edge.

   121       /// This constructor set the iterator to the first outgoing edge of

   122       /// node

   123       ///@param n the node

   124       ///@param G the graph

   125       OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }

   126     };

   128     class InEdgeIt : public Edge {

   129     public:

   130       /// @warning The default constructor sets the iterator

   131       /// to an undefined value.

   132       InEdgeIt() {}

   133       /// Initialize the iterator to be invalid

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

   135       InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }

   136     };

   138     //  class SymEdgeIt : public Edge {};

   139     class EdgeIt : public Edge {

   140     public:

   141       /// @warning The default constructor sets the iterator

   142       /// to an undefined value.

   143       EdgeIt() {}

   144       /// Initialize the iterator to be invalid

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

   146       EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }

   147     };

   149     /// First node of the graph.

   151     /// \post \c i and the return value will be the first node.

   152     ///

   153     NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }

   155     /// The first outgoing edge.

   156     InEdgeIt &first(InEdgeIt &i, Node n) const {

   157       i=InEdgeIt(*this, n);

   158       return i;

   159     }

   160     /// The first incoming edge.

   161     OutEdgeIt &first(OutEdgeIt &i, Node n) const {

   162       i=OutEdgeIt(*this, n);

   163       return i;

   164     }

   165     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}

   166     /// The first edge of the Graph.

   167     EdgeIt &first(EdgeIt &i) const {

   168       i=EdgeIt(*this);

   169       return i; }

   171 //     Node getNext(Node) const {}

   172 //     InEdgeIt getNext(InEdgeIt) const {}

   173 //     OutEdgeIt getNext(OutEdgeIt) const {}

   174 //     //SymEdgeIt getNext(SymEdgeIt) const {}

   175 //     EdgeIt getNext(EdgeIt) const {}

   177     /// Go to the next node.

   178     NodeIt &next(NodeIt &i) const {

   179       i.l_n=l_graph->succ_node(i.l_n);

   180       return i;

   181     }

   182     /// Go to the next incoming edge.

   183     InEdgeIt &next(InEdgeIt &i) const {

   184       i.l_e=l_graph->in_succ(i.l_e);

   185       return i;

   186     }

   187     /// Go to the next outgoing edge.

   188     OutEdgeIt &next(OutEdgeIt &i) const {

   189       i.l_e=l_graph->adj_succ(i.l_e);

   190       return i;

   191     }

   192     //SymEdgeIt &next(SymEdgeIt &) const {}

   193     /// Go to the next edge.

   194     EdgeIt &next(EdgeIt &i) const {

   195       i.l_e=l_graph->succ_edge(i.l_e);

   196       return i;

   197     }

   199 //     template< typename It >

   200 //     It first() const {

   201 //       It e;

   202 //       first(e);

   203 //       return e;

   204 //     }

   206 //     template< typename It >

   207 //     It first(Node v) const {

   208 //       It e;

   209 //       first(e, v);

   210 //       return e;

   211 //     }

   213     ///Gives back the head node of an edge.

   214     Node head(Edge e) const {

   215       return Node(l_graph->target(e.l_e));

   216     }

   217     ///Gives back the tail node of an edge.

   218     Node tail(Edge e) const {

   219       return Node(l_graph->source(e.l_e));

   220     }

   222     Node aNode(InEdgeIt e) const { return head(e); }

   223     Node aNode(OutEdgeIt e) const { return tail(e); }

   224     //   Node aNode(SymEdgeIt) const {}

   226     Node bNode(InEdgeIt e) const { return tail(e); }

   227     Node bNode(OutEdgeIt e) const { return head(e); }

   228     //   Node bNode(SymEdgeIt) const {}

   230     /// Checks if a node iterator is valid

   231     bool valid(Node n) const { return n.l_n; }

   232     /// Checks if an edge iterator is valid

   233     bool valid(Edge e) const { return e.l_e; }

   235     ///Gives back the \e id of a node.

   236     int id(Node n) const { return n.l_n->id(); }

   237     ///Gives back the \e id of an edge.

   238     int id(Edge e) const { return e.l_e->id(); }

   240     //void setInvalid(Node &) const {};

   241     //void setInvalid(Edge &) const {};

   243     Node addNode() const { return Node(l_graph->new_node()); }

   244     Edge addEdge(Node tail, Node head) const {

   245       return Edge(l_graph->new_edge(tail.l_n, head.l_n));

   246     }

   248     void erase(Node n) const { l_graph->del_node(n.l_n); }

   249     void erase(Edge e) const { l_graph->del_edge(e.l_e); }

   251     void clear() const { l_graph->clear(); }

   253     int nodeNum() const { return l_graph->number_of_nodes(); }

   254     int edgeNum() const { return l_graph->number_of_edges(); }

   256     ///Read/write map from the nodes to type \c T.

   257     template<typename T> class NodeMap

   258     {

   259       leda_node_map<T> leda_stuff;

   260     public:

   261       typedef T ValueType;

   262       typedef Node KeyType;

   264       NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}

   265       NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}

   267       void set(Node i, T t) { leda_stuff[i.l_n]=t; }

   268       T get(Node i) const { return leda_stuff[i.l_n]; }  //FIXME: Is it necessary

   269       T &operator[](Node i) { return leda_stuff[i.l_n]; }

   270       const T &operator[](Node i) const { return leda_stuff[i.l_n]; }

   272       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }

   273       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary

   274     };

   276     ///Read/write map from the edges to type \c T.

   277     template<typename T> class EdgeMap

   278     {

   279       leda_edge_map<T> leda_stuff;

   280     public:

   281       typedef T ValueType;

   282       typedef Edge KeyType;

   284       EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}

   285       EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}

   287       void set(Edge i, T t) { leda_stuff[i.l_e]=t; }

   288       T get(Edge i) const { return leda_stuff[i.l_e]; }  //FIXME: Is it necessary

   289       T &operator[](Edge i) { return leda_stuff[i.l_e]; }

   290       const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }

   292       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }

   293       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary

   294     };

   297     ///Read/write map from the nodes to type \c T.

   298     template<typename T> class NodeMapWrapper

   299     {

   300       leda_node_map<T>* leda_stuff;

   301     public:

   302       typedef T ValueType;

   303       typedef Node KeyType;

   305       NodeMapWrapper(leda_node_map<T>& _leda_stuff) :

   306 	leda_stuff(&_leda_stuff) { }

   307       //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}

   309       void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }

   310       T get(Node i) const { return (*leda_stuff)[i.l_n]; }  //FIXME: Is it necessary

   311       T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }

   312       const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }

   314       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }

   315       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary

   316     };

   318     ///Read/write map from the edges to type \c T.

   319     template<typename T> class EdgeMapWrapper

   320     {

   321       leda_edge_map<T>* leda_stuff;

   322     public:

   323       typedef T ValueType;

   324       typedef Edge KeyType;

   326       EdgeMapWrapper(leda_edge_map<T>& _leda_stuff) :

   327 	leda_stuff(_leda_stuff) { }

   328       //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}

   330       void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }

   331       T get(Edge i) const { return (*leda_stuff)[i.l_e]; }  //FIXME: Is it necessary

   332       T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }

   333       const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }

   335       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }

   336       //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary

   337     };

   339   };

   342   /// \brief LEDA graph template.

   343   ///

   344   /// This graph stucture uses LEDA graphs for physical storage.

   345   /// \ingroup graphs

   346   template<typename Graph>

   347   class LedaGraph : public LedaGraphWrapper<Graph> {

   348     typedef LedaGraphWrapper<Graph> Parent;

   349   protected:

   350     Graph gr;

   351   public:

   352     LedaGraph() {

   353       Parent::setGraph(gr);

   354     }

   355   };

   357 } //namespace hugo

   359 #endif // HUGO_LEDA_GRAPH_WRAPPER_H

author	marci
	Wed, 19 May 2004 16:06:57 +0000
changeset 646	bd7a69231cf8
parent 617	dc17013b0e52
child 650	588ff2ca55bd
permissions	-rw-r--r--