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     /// Constructor for wrapping LEDA graphs.

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

    39     /// Copy constructor

    40     LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { }

    42     template <typename T> class NodeMap;

    43     template <typename T> class EdgeMap;

    44     template <typename T> class NodeMapWrapper;

    45     template <typename T> class EdgeMapWrapper;

    47     class Node;

    48     class NodeIt;

    49     class Edge;

    50     class EdgeIt;

    51     class OutEdgeIt;

    52     class InEdgeIt;

    54     /// Trivial node-iterator

    55     class Node {

    56       friend class LedaGraphWrapper<Graph>;

    57       //friend class Edge;

    58       friend class EdgeIt;

    59       friend class InEdgeIt;

    60       friend class OutEdgeIt;

    61     protected:

    62       template <typename T> friend class NodeMap;

    63       leda_node l_n;

    64     public: //FIXME

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

    66     public:

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

    68       /// to an undefined value.

    69       Node() { }   //FIXME

    70       /// Initialize the iterator to be invalid

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

    72       //Node(const Node &) {}

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

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

    75       operator leda_node () { return l_n; }

    76     };

    78     /// This iterator goes through each node.

    79     class NodeIt : public Node {

    80     public:

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

    82       /// to an undefined value.

    83       NodeIt() { } //FIXME

    84       /// Initialize the iterator to be invalid

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

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

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

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

    89     };

    91     /// Trivial edge-iterator.

    92     class Edge {

    93       friend class LedaGraphWrapper;

    94     protected:

    95       template <typename T> friend class EdgeMap;

    96       leda_edge l_e;

    97     public: //FIXME

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

    99     public:

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

   101       /// to an undefined value.

   102       Edge() { }   //FIXME

   103       /// Initialize the iterator to be invalid

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

   105       //Edge(const Edge &) {}

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

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

   108       operator leda_edge () { return l_e; }

   109     };

   111     /// This iterator goes trought the outgoing edges of a certain node.

   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     /// This iterator goes trought the incoming edges of a certain node.

   129     class InEdgeIt : public Edge {

   130     public:

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

   132       /// to an undefined value.

   133       InEdgeIt() { }

   134       /// Initialize the iterator to be invalid

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

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

   137     };

   139     //  class SymEdgeIt : public Edge {};

   141     /// This iterator goes trought the edges of the graph.

   142     class EdgeIt : public Edge {

   143     public:

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

   145       /// to an undefined value.

   146       EdgeIt() { }

   147       /// Initialize the iterator to be invalid

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

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

   150     };

   152     /// First node of the graph.

   153     ///

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

   155     ///

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

   158     /// The first outgoing edge.

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

   160       i=InEdgeIt(*this, n);

   161       return i;

   162     }

   163     /// The first incoming edge.

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

   165       i=OutEdgeIt(*this, n);

   166       return i;

   167     }

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

   169     /// The first edge of the graph.

   170     EdgeIt &first(EdgeIt &i) const {

   171       i=EdgeIt(*this);

   172       return i; }

   174 //     Node getNext(Node) const {}

   175 //     InEdgeIt getNext(InEdgeIt) const {}

   176 //     OutEdgeIt getNext(OutEdgeIt) const {}

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

   178 //     EdgeIt getNext(EdgeIt) const {}

   180     /// Go to the next node.

   181     NodeIt &next(NodeIt &i) const {

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

   183       return i;

   184     }

   185     /// Go to the next incoming edge.

   186     InEdgeIt &next(InEdgeIt &i) const {

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

   188       return i;

   189     }

   190     /// Go to the next outgoing edge.

   191     OutEdgeIt &next(OutEdgeIt &i) const {

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

   193       return i;

   194     }

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

   196     /// Go to the next edge.

   197     EdgeIt &next(EdgeIt &i) const {

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

   199       return i;

   200     }

   202 //     template< typename It >

   203 //     It first() const {

   204 //       It e;

   205 //       first(e);

   206 //       return e;

   207 //     }

   209 //     template< typename It >

   210 //     It first(Node v) const {

   211 //       It e;

   212 //       first(e, v);

   213 //       return e;

   214 //     }

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

   217     Node head(Edge e) const {

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

   219     }

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

   221     Node tail(Edge e) const {

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

   223     }

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

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

   227     //   Node aNode(SymEdgeIt) const {}

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

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

   231     //   Node bNode(SymEdgeIt) const {}

   233     /// Checks if a node iterator is valid

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

   235     /// Checks if an edge iterator is valid

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

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

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

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

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

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

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

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

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

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

   249     }

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

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

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

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

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

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

   260     template<typename T> class NodeMap

   261     {

   262       leda_node_map<T> leda_stuff;

   263     public:

   264       typedef T ValueType;

   265       typedef Node KeyType;

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

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

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

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

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

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

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

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

   277     };

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

   280     template<typename T> class EdgeMap

   281     {

   282       leda_edge_map<T> leda_stuff;

   283     public:

   284       typedef T ValueType;

   285       typedef Edge KeyType;

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

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

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

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

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

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

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

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

   297     };

   300     /// This class is to wrap existing

   301     /// LEDA node-maps to HUGO ones.

   302     template<typename T> class NodeMapWrapper

   303     {

   304       leda_node_array<T>* leda_stuff;

   305     public:

   306       typedef T ValueType;

   307       typedef Node KeyType;

   309       NodeMapWrapper(leda_node_array<T>& _leda_stuff) :

   310 	leda_stuff(&_leda_stuff) { }

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

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

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

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

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

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

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

   320     };

   322     /// This class is to wrap existing

   323     /// LEDA edge-maps to HUGO ones.

   324     template<typename T> class EdgeMapWrapper

   325     {

   326       leda_edge_array<T>* leda_stuff;

   327     public:

   328       typedef T ValueType;

   329       typedef Edge KeyType;

   331       EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) :

   332 	leda_stuff(_leda_stuff) { }

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

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

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

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

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

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

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

   342     };

   344     /// This class is used for access node-data of

   345     /// LEDA parametrized graphs.

   346     template<typename T>

   347     class NodeDataMap : public NodeMapWrapper<T>

   348     {

   349     public:

   350       NodeDataMap(LedaGraphWrapper<Graph>& LGW) :

   351 	NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { }

   352     };

   354     /// This class is used for access edge-data of

   355     /// LEDA parametrized graphs.

   356     template<typename T>

   357     class EdgeDataMap : public EdgeMapWrapper<T>

   358     {

   359     public:

   360       EdgeDataMap(LedaGraphWrapper<Graph>& LGW) :

   361 	EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { }

   362     };

   364   };

   367   /// \brief LEDA graph template.

   368   ///

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

   370   /// \ingroup graphs

   371   template<typename Graph>

   372   class LedaGraph : public LedaGraphWrapper<Graph> {

   373     typedef LedaGraphWrapper<Graph> Parent;

   374   protected:

   375     Graph gr;

   376   public:

   377     LedaGraph() {

   378       Parent::setGraph(gr);

   379     }

   380   };

   382 } //namespace hugo

   384 #endif // HUGO_LEDA_GRAPH_WRAPPER_H

author	alpar
	Sun, 19 Sep 2004 12:24:48 +0000
changeset 881	a9f19f38970b
parent 646	bd7a69231cf8
child 921	818510fa3d99
permissions	-rw-r--r--