# HG changeset patch
# User marci
# Date 1084310789 0
# Node ID dc17013b0e5207c3a54a377ba58957f51d00bbed
# Parent  31879aac4dc3db7abfd047077f9f00d10d61d139
bip matching comparison

diff -r 31879aac4dc3 -r dc17013b0e52 src/work/makefile
--- a/src/work/makefile	Tue May 11 20:20:41 2004 +0000
+++ b/src/work/makefile	Tue May 11 21:26:29 2004 +0000
@@ -1,5 +1,5 @@
 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
 
diff -r 31879aac4dc3 -r dc17013b0e52 src/work/marci/leda/comparison.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/leda/comparison.cc	Tue May 11 21:26:29 2004 +0000
@@ -0,0 +1,170 @@
+// -*- c++ -*-
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <cstdlib>
+
+#include <LEDA/graph.h>
+#include <LEDA/mcb_matching.h>
+#include <LEDA/list.h>
+#include <LEDA/graph_gen.h>
+
+#include <leda_graph_wrapper.h>
+#include <list_graph.h>
+//#include <smart_graph.h>
+//#include <dimacs.h>
+#include <hugo/time_measure.h>
+#include <for_each_macros.h>
+#include <hugo/graph_wrapper.h>
+#include <bipartite_graph_wrapper.h>
+#include <hugo/maps.h>
+#include <max_flow.h>
+
+/**
+ * Inicializalja a veletlenszamgeneratort.
+ * Figyelem, ez nem jo igazi random szamokhoz,
+ * erre ne bizzad a titkaidat!
+ */
+void random_init()
+{
+	unsigned int seed = getpid();
+	seed |= seed << 15;
+	seed ^= time(0);
+
+	srand(seed);
+}
+
+/**
+ * Egy veletlen int-et ad vissza 0 es m-1 kozott.
+ */
+int random(int m)
+{
+  return int( double(m) * rand() / (RAND_MAX + 1.0) );
+}
+
+using namespace hugo;
+
+int main() {
+  //for leda graph
+  leda::graph lg;
+  //lg.make_undirected();
+  typedef LedaGraphWrapper<leda::graph> Graph;
+  Graph g(lg);
+
+  //for UndirListGraph
+  //typedef UndirListGraph Graph; 
+  //Graph g;
+
+  typedef Graph::Node Node;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::Edge Edge;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::OutEdgeIt OutEdgeIt;
+
+  std::vector<Graph::Node> s_nodes;
+  std::vector<Graph::Node> t_nodes;
+
+  int a;
+  std::cout << "number of nodes in the first color class=";
+  std::cin >> a; 
+  int b;
+  std::cout << "number of nodes in the second color class=";
+  std::cin >> b; 
+  int m;
+  std::cout << "number of edges=";
+  std::cin >> m; 
+  int k;
+  std::cout << "A bipartite graph is a random group graph if the color classes \nA and B are partitiones to A_0, A_1, ..., A_{k-1} and B_0, B_1, ..., B_{k-1} \nas equally as possible \nand the edges from A_i goes to A_{i-1 mod k} and A_{i+1 mod k}.\n";
+  std::cout << "number of groups in LEDA random group graph=";
+  std::cin >> k; 
+  std::cout << std::endl;
+  
+  leda_list<leda_node> lS;
+  leda_list<leda_node> lT;
+  random_bigraph(lg, a, b, m, lS, lT, k);
+
+  Graph::NodeMap<int> ref_map(g, -1);
+  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
+
+  //generating leda random group graph
+  leda_node ln;
+  forall(ln, lS) bipartite_map.insert(ln, false);
+  forall(ln, lT) bipartite_map.insert(ln, true);
+
+  //making bipartite graph
+  typedef BipartiteGraphWrapper<Graph> BGW;
+  BGW bgw(g, bipartite_map);
+
+
+  //st-wrapper
+  typedef stGraphWrapper<BGW> stGW;
+  stGW stgw(bgw);
+  ConstMap<stGW::Edge, int> const1map(1);
+  stGW::EdgeMap<int> flow(stgw);
+
+  Timer ts;
+
+  ts.reset();
+  FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
+  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
+    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow/*, true*/);
+  max_flow_test.run();
+  std::cout << "HUGO max matching algorithm based on preflow." << std::endl 
+	    << "Size of matching: " 
+	    << max_flow_test.flowValue() << std::endl;
+  std::cout << "elapsed time: " << ts << std::endl << std::endl;
+
+  ts.reset();  
+  leda_list<leda_edge> ml=MAX_CARD_BIPARTITE_MATCHING(lg);
+  std::cout << "LEDA max matching algorithm." << std::endl 
+	    << "Size of matching: " 
+	    << ml.size() << std::endl;
+  std::cout << "elapsed time: " << ts << std::endl << std::endl;
+
+//   ts.reset();
+//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) flow.set(e, 0);
+//   typedef ListGraph MutableGraph;
+//   while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { }
+//   std::cout << "HUGO max matching algorithm based on blocking flow augmentation." 
+// 	    << std::endl << "Matching size: " 
+// 	    << max_flow_test.flowValue() << std::endl;
+//   std::cout << "elapsed time: " << ts << std::endl << std::endl;
+
+  {
+  ListGraph hg;
+  ListGraph::Node s=hg.addNode();  
+  ListGraph::Node t=hg.addNode();
+  BGW::NodeMap<ListGraph::Node> b_s_nodes(bgw);  
+  BGW::NodeMap<ListGraph::Node> b_t_nodes(bgw);
+  
+  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::S_CLASS) {
+    b_s_nodes.set(n, hg.addNode());
+    hg.addEdge(s, b_s_nodes[n]);
+  }
+  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, BGW::T_CLASS) {
+    b_t_nodes.set(n, hg.addNode());
+    hg.addEdge(b_t_nodes[n], t);
+  }
+
+  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) 
+    hg.addEdge(b_s_nodes[bgw.tail(e)], b_t_nodes[bgw.head(e)]);
+
+  ConstMap<ListGraph::Edge, int> cm(1);
+  ListGraph::EdgeMap<int> flow(hg); //0
+  
+  Timer ts;
+
+  ts.reset();
+  MaxFlow<ListGraph, int, ConstMap<ListGraph::Edge, int>, 
+    ListGraph::EdgeMap<int> > 
+    max_flow_test(hg, s, t, cm, flow);
+  max_flow_test.run();
+  std::cout << "HUGO max matching algorithm on ListGraph by copying the graph, based on preflow." 
+	    << std::endl 
+	    << "Size of matching: " 
+	    << max_flow_test.flowValue() << std::endl;
+  std::cout << "elapsed time: " << ts << std::endl << std::endl;
+  }
+
+  return 0;
+}
diff -r 31879aac4dc3 -r dc17013b0e52 src/work/marci/leda/leda_graph_wrapper.h
--- a/src/work/marci/leda/leda_graph_wrapper.h	Tue May 11 20:20:41 2004 +0000
+++ b/src/work/marci/leda/leda_graph_wrapper.h	Tue May 11 21:26:29 2004 +0000
@@ -16,42 +16,27 @@
 
 #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;
     template <typename T> class EdgeMap;
@@ -72,19 +57,19 @@
       friend class OutEdgeIt;
     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
       /// to an undefined value.
       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; }
     };
     
     /// This iterator goes through each node.
@@ -96,7 +81,7 @@
       /// Initialize the iterator to be invalid
       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
     };
     
@@ -105,19 +90,19 @@
       friend class LedaGraphWrapper;
     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
       /// to an undefined value.
       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; }
     };
     
     /// This iterator goes trought the outgoing edges of a certain graph.
@@ -135,7 +120,7 @@
       /// node
       ///@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)) { }
     };
 
     class InEdgeIt : public Edge {
@@ -145,7 +130,7 @@
       InEdgeIt() {}
       /// 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)) { }
     };
 
     //  class SymEdgeIt : public Edge {};
@@ -156,7 +141,7 @@
       EdgeIt() {}
       /// 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()) { }
     };
 
     /// First node of the graph.
@@ -189,23 +174,23 @@
 
     /// 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;
     }
     //SymEdgeIt &next(SymEdgeIt &) const {}
     /// 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; 
     }
 
@@ -225,11 +210,11 @@
 
     ///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)); 
     }
   
     Node aNode(InEdgeIt e) const { return head(e); }
@@ -241,30 +226,30 @@
     //   Node bNode(SymEdgeIt) const {}
 
     /// 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));
+      return Edge(l_graph->new_edge(tail.l_n, head.l_n));
     }
     
-    void erase(Node n) const { _graph->del_node(n._n); }
-    void erase(Edge e) const { _graph->del_edge(e._e); }
+    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 { _graph->clear(); }
+    void clear() const { l_graph->clear(); }
 
-    int nodeNum() const { return _graph->number_of_nodes(); }
-    int edgeNum() const { return _graph->number_of_edges(); }
+    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.
     template<typename T> class NodeMap
@@ -274,16 +259,16 @@
       typedef T ValueType;
       typedef Node KeyType;
 
-      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
-      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
+      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._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]; }
+      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
     };
 
     ///Read/write map from the edges to type \c T.
@@ -294,20 +279,25 @@
       typedef T ValueType;
       typedef Edge KeyType;
 
-      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
-      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
+      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._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]; }
+      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> {
     typedef LedaGraphWrapper<Graph> Parent;
@@ -319,26 +309,6 @@
     }
   };
 
-  // @}
-
 } //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
diff -r 31879aac4dc3 -r dc17013b0e52 src/work/marci/leda/makefile
--- a/src/work/marci/leda/makefile	Tue May 11 20:20:41 2004 +0000
+++ b/src/work/marci/leda/makefile	Tue May 11 21:26:29 2004 +0000
@@ -4,7 +4,7 @@
 INCLUDEDIRS ?= -I. -I../.. -I../../{marci,jacint,alpar,klao,akos,athos} -I$(LEDAROOT)/incl -I../../..
 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