Changeset 617:dc17013b0e52 in lemon-0.x

Timestamp:

05/11/04 23:26:29 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@802

Message:

bip matching comparison

Location:

src/work

Files:

• makefile (modified) (1 diff)
• marci/leda/comparison.cc (added)
• marci/leda/leda_graph_wrapper.h (modified) (16 diffs)
• marci/leda/makefile (modified) (1 diff)

src/work/makefile

@@ -1 +1 @@
 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
-CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
 
 BINARIES ?= bin_heap_demo

src/work/marci/leda/leda_graph_wrapper.h

@@ -17 +17 @@
 #include <hugo/invalid.h>
 
-/// The namespace of HugoLib
 namespace hugo {
 
-  // @defgroup empty_graph The LedaGraphWrapper class
-  // @{
-
-  /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
-  
-  /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
-  /// and then the generic algorithms and wrappers of HUGO can be used 
+  /// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.
+  ///
+  /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
+  /// to satisfy HUGO graph concepts.
+  /// Then the generic HUGOlib algorithms and wrappers can be used 
   /// with LEDA graphs. 
-  /// This class provides all the common features of a grapf structure,
-  /// however completely without implementations or real data structures
-  /// behind the interface.
-  /// All graph algorithms should compile with this class, but it will not
-  /// run properly, of course.
-  ///
-  /// It can be used for checking the interface compatibility,
-  /// or it can serve as a skeleton of a new graph structure.
-  /// 
-  /// Also, you will find here the full documentation of a certain graph
-  /// feature, the documentation of a real graph imlementation
-  /// like @ref ListGraph or
-  /// @ref SmartGraph will just refer to this structure.
+  /// \ingroup gwrapper
   template<typename Graph>
   class LedaGraphWrapper
   {
   protected:
-    Graph* _graph;
-    LedaGraphWrapper() : _graph(0) { }
-    void setGraph(Graph& __graph) { _graph=&__graph; }
+    Graph* l_graph;
+    LedaGraphWrapper() : l_graph(0) { }
+    void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
   public:
    
         //LedaGraphWrapper() { }
-    LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
-    LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
+    LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
+    LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { }
 
     template <typename T> class NodeMap;
@@ -73 +58 @@
     protected:
       template <typename T> friend class NodeMap;
-      leda_node _n;
+      leda_node l_n;
     public: //FIXME
-      Node(leda_node __n) : _n(__n) { } 
+      Node(leda_node _l_n) : l_n(_l_n) { } 
     public:
       /// @warning The default constructor sets the iterator
@@ -81 +66 @@
       Node() {}   //FIXME
       /// Initialize the iterator to be invalid
-      Node(Invalid) : _n(0) { }
+      Node(Invalid) : l_n(0) { }
       //Node(const Node &) {} 
-      bool operator==(Node n) const { return _n==n._n; } //FIXME
-      bool operator!=(Node n) const { return _n!=n._n; } //FIXME
-      operator leda_node () { return _n; }
+      bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
+      bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
+      operator leda_node () { return l_n; }
     };
     
@@ -97 +82 @@
       NodeIt(Invalid i) : Node(i) {}
       /// Sets the iterator to the first node of \c G.
-      NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
+      NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
       //NodeIt(const NodeIt &) {} //FIXME
     };
@@ -106 +91 @@
     protected:
       template <typename T> friend class EdgeMap;
-      leda_edge _e;
+      leda_edge l_e;
     public: //FIXME
-      Edge(leda_edge __e) : _e(__e) { } 
+      Edge(leda_edge _l_e) : l_e(_l_e) { } 
     public:
       /// @warning The default constructor sets the iterator
@@ -114 +99 @@
       Edge() {}   //FIXME
       /// Initialize the iterator to be invalid
-      Edge(Invalid) : _e(0) {}
+      Edge(Invalid) : l_e(0) {}
       //Edge(const Edge &) {} 
-      bool operator==(Edge e) const { return _e==e._e; } //FIXME
-      bool operator!=(Edge e) const { return _e!=e._e; } //FIXME 
-      operator leda_edge () { return _e; }
+      bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
+      bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME 
+      operator leda_edge () { return l_e; }
     };
     
@@ -136 +121 @@
       ///@param n the node
       ///@param G the graph
-      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
+      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
     };
 
@@ -146 +131 @@
       /// Initialize the iterator to be invalid
       InEdgeIt(Invalid i) : Edge(i) {}
-      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
+      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
     };
 
@@ -157 +142 @@
       /// Initialize the iterator to be invalid
       EdgeIt(Invalid i) : Edge(i) {}
-      EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
+      EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
     };
 
@@ -190 +175 @@
     /// Go to the next node.
     NodeIt &next(NodeIt &i) const { 
-      i._n=_graph->succ_node(i._n); 
+      i.l_n=l_graph->succ_node(i.l_n); 
       return i; 
     }
     /// Go to the next incoming edge.
     InEdgeIt &next(InEdgeIt &i) const { 
-      i._e=_graph->in_succ(i._e); 
+      i.l_e=l_graph->in_succ(i.l_e); 
       return i;
     }
     /// Go to the next outgoing edge.
     OutEdgeIt &next(OutEdgeIt &i) const { 
-      i._e=_graph->adj_succ(i._e); 
+      i.l_e=l_graph->adj_succ(i.l_e); 
       return i;
     }
@@ -206 +191 @@
     /// Go to the next edge.
     EdgeIt &next(EdgeIt &i) const {      
-      i._e=_graph->succ_edge(i._e); 
+      i.l_e=l_graph->succ_edge(i.l_e); 
       return i; 
     }
@@ -226 +211 @@
     ///Gives back the head node of an edge.
     Node head(Edge e) const { 
-      return Node(_graph->target(e._e)); 
+      return Node(l_graph->target(e.l_e)); 
     }
     ///Gives back the tail node of an edge.
     Node tail(Edge e) const { 
-      return Node(_graph->source(e._e)); 
+      return Node(l_graph->source(e.l_e)); 
     }
   
@@ -242 +227 @@
 
     /// Checks if a node iterator is valid
-    bool valid(Node n) const { return n._n; }
+    bool valid(Node n) const { return n.l_n; }
     /// Checks if an edge iterator is valid
-    bool valid(Edge e) const { return e._e; }
+    bool valid(Edge e) const { return e.l_e; }
 
     ///Gives back the \e id of a node.
-    int id(Node n) const { return n._n->id(); }
+    int id(Node n) const { return n.l_n->id(); }
     ///Gives back the \e id of an edge.
-    int id(Edge e) const { return e._e->id(); }
+    int id(Edge e) const { return e.l_e->id(); }
 
     //void setInvalid(Node &) const {};
     //void setInvalid(Edge &) const {};
   
-    Node addNode() const { return Node(_graph->new_node()); }
+    Node addNode() const { return Node(l_graph->new_node()); }
     Edge addEdge(Node tail, Node head) const { 
-      return Edge(_graph->new_edge(tail._n, head._n));
-    }
-    
-    void erase(Node n) const { _graph->del_node(n._n); }
-    void erase(Edge e) const { _graph->del_edge(e._e); }
-
-    void clear() const { _graph->clear(); }
-
-    int nodeNum() const { return _graph->number_of_nodes(); }
-    int edgeNum() const { return _graph->number_of_edges(); }
+      return Edge(l_graph->new_edge(tail.l_n, head.l_n));
+    }
+    
+    void erase(Node n) const { l_graph->del_node(n.l_n); }
+    void erase(Edge e) const { l_graph->del_edge(e.l_e); }
+
+    void clear() const { l_graph->clear(); }
+
+    int nodeNum() const { return l_graph->number_of_nodes(); }
+    int edgeNum() const { return l_graph->number_of_edges(); }
 
     ///Read/write map from the nodes to type \c T.
@@ -275 +260 @@
       typedef Node KeyType;
 
-      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
-      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
-
-      void set(Node i, T t) { leda_stuff[i._n]=t; }
-      T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary
-      T &operator[](Node i) { return leda_stuff[i._n]; }
-      const T &operator[](Node i) const { return leda_stuff[i._n]; }
+      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
+      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
+
+      void set(Node i, T t) { leda_stuff[i.l_n]=t; }
+      T get(Node i) const { return leda_stuff[i.l_n]; }  //FIXME: Is it necessary
+      T &operator[](Node i) { return leda_stuff[i.l_n]; }
+      const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
 
       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
-      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
+      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
     };
 
@@ -295 +280 @@
       typedef Edge KeyType;
 
-      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
-      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
-
-      void set(Edge i, T t) { leda_stuff[i._e]=t; }
-      T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary
-      T &operator[](Edge i) { return leda_stuff[i._e]; }
-      const T &operator[](Edge i) const { return leda_stuff[i._e]; }
+      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
+      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
+
+      void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
+      T get(Edge i) const { return leda_stuff[i.l_e]; }  //FIXME: Is it necessary
+      T &operator[](Edge i) { return leda_stuff[i.l_e]; }
+      const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
 
       void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
-      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
+      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
     };
 
   };
 
+
+  /// \brief LEDA graph template.
+  ///
+  /// This graph stucture uses LEDA graphs for physical storage.
+  /// \ingroup graphs
   template<typename Graph>
   class LedaGraph : public LedaGraphWrapper<Graph> {
@@ -320 +310 @@
   };
 
-  // @}
-
 } //namespace hugo
 
-
-
-// class EmptyBipGraph : public EmptyGraph
-// {
-//   class ANode {};
-//   class BNode {};
-
-//   ANode &next(ANode &) {}
-//   BNode &next(BNode &) {}
-
-//   ANode &getFirst(ANode &) const {}
-//   BNode &getFirst(BNode &) const {}
-
-//   enum NodeClass { A = 0, B = 1 };
-//   NodeClass getClass(Node n) {}
-
-// }
-
 #endif // HUGO_LEDA_GRAPH_WRAPPER_H

src/work/marci/leda/makefile

@@ -5 +5 @@
 LDFLAGS = -L$(LEDAROOT) -lG -lL -lm
 
-BINARIES = bipartite_matching_leda bipartite_matching_leda_gen
+BINARIES = bipartite_matching_leda bipartite_matching_leda_gen comparison
 
 include ../../makefile