1.1 --- a/src/work/jacint/graph_gen.h	Thu May 06 17:01:31 2004 +0000
     1.2 +++ b/src/work/jacint/graph_gen.h	Thu May 06 17:22:11 2004 +0000
     1.3 @@ -1,16 +1,7 @@
     1.4  // -*- c++ -*-
     1.5 -//randomGraph(i,j) gives a random graph on i nodes and j edges.
     1.6  #include <vector>
     1.7  #include <cstdlib>
     1.8  
     1.9 -//#include <list_graph.h>
    1.10 -//#include <time_measure.h>
    1.11 -//#include <for_each_macros.h>
    1.12 -//#include <bfs_iterator.h>
    1.13 -//#include <bipartite_graph_wrapper.h>
    1.14 -//#include <maps.h>
    1.15 -//#include <max_flow.h>
    1.16 -
    1.17  namespace hugo {
    1.18  
    1.19  
    1.20 @@ -38,15 +29,36 @@
    1.21    }
    1.22  
    1.23  
    1.24 +  /// Generates a random graph with n nodes and m edges.
    1.25 +  /// Before generating the random graph, \c g.clear() is called.
    1.26    template<typename Graph>
    1.27 -  void randomGraph (Graph& g, int n, int m) {
    1.28 -    typedef typename Graph::Node Node;
    1.29 +  void randomGraph(Graph& g, int n, int m) {
    1.30      g.clear();
    1.31 -    std::vector<Node> nodes;
    1.32 +    std::vector<typename Graph::Node> nodes;
    1.33      for (int i=0; i<n; ++i)
    1.34        nodes.push_back(g.addNode());
    1.35      for (int i=0; i<m; ++i) 
    1.36        g.addEdge(nodes[random(n)], nodes[random(n)]);
    1.37    }
    1.38  
    1.39 -}
    1.40 +  /// Generates a random bipartite graph with a and b nodes 
    1.41 +  /// in the color classes and m edges.
    1.42 +  /// According to the bipartite graph concept, the resulting 
    1.43 +  /// graph is directed from the first class to the second one.
    1.44 +  /// Before generating the random graph, \c g.clear() is called.
    1.45 +  template<typename Graph>
    1.46 +  void randomBipartiteGraph(Graph& g, int a, int b, int m) {
    1.47 +    g.clear();
    1.48 +    std::vector<typename Graph::Node> s_nodes;
    1.49 +    std::vector<typename Graph::Node> t_nodes;
    1.50 +    for (int i=0; i<a; ++i)
    1.51 +      ///\bug g.addNode(g.S_CLASS) would be better.
    1.52 +      s_nodes.push_back(g.addNode(false));
    1.53 +    for (int i=0; i<b; ++i)
    1.54 +      ///\bug g.addNode(g.T_CLASS) would be better.
    1.55 +      t_nodes.push_back(g.addNode(true));
    1.56 +    for (int i=0; i<m; ++i) 
    1.57 +      g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    1.58 +  }
    1.59 +
    1.60 +} //namespace hugo

     2.1 --- a/src/work/marci/bipartite_graph_wrapper.h	Thu May 06 17:01:31 2004 +0000
     2.2 +++ b/src/work/marci/bipartite_graph_wrapper.h	Thu May 06 17:22:11 2004 +0000
     2.3 @@ -247,8 +247,8 @@
     2.4      }
     2.5      
     2.6      void clear() {
     2.7 -      FOR_EACH_LOC(typename Parent::EdgeIt, e, G) erase(e);
     2.8 -      FOR_EACH_LOC(typename Parent::NodeIt, n, G) erase(n);
     2.9 +      FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);
    2.10 +      FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);
    2.11      }
    2.12    };
    2.13  

     3.1 --- a/src/work/marci/bipartite_matching_try_3.cc	Thu May 06 17:01:31 2004 +0000
     3.2 +++ b/src/work/marci/bipartite_matching_try_3.cc	Thu May 06 17:22:11 2004 +0000
     3.3 @@ -2,7 +2,6 @@
     3.4  #include <iostream>
     3.5  #include <fstream>
     3.6  #include <vector>
     3.7 -#include <cstdlib>
     3.8  
     3.9  #include <list_graph.h>
    3.10  //#include <smart_graph.h>
    3.11 @@ -13,6 +12,7 @@
    3.12  #include <bipartite_graph_wrapper.h>
    3.13  #include <hugo/maps.h>
    3.14  #include <max_flow.h>
    3.15 +#include <graph_gen.h>
    3.16  
    3.17  using namespace hugo;
    3.18  
    3.19 @@ -79,27 +79,6 @@
    3.20    int matchingValue() { return mf.flowValue(); }
    3.21  };
    3.22  
    3.23 -/**
    3.24 - * Inicializalja a veletlenszamgeneratort.
    3.25 - * Figyelem, ez nem jo igazi random szamokhoz,
    3.26 - * erre ne bizzad a titkaidat!
    3.27 - */
    3.28 -void random_init()
    3.29 -{
    3.30 -	unsigned int seed = getpid();
    3.31 -	seed |= seed << 15;
    3.32 -	seed ^= time(0);
    3.33 -
    3.34 -	srand(seed);
    3.35 -}
    3.36 -
    3.37 -/**
    3.38 - * Egy veletlen int-et ad vissza 0 es m-1 kozott.
    3.39 - */
    3.40 -int random(int m)
    3.41 -{
    3.42 -  return int( double(m) * rand() / (RAND_MAX + 1.0) );
    3.43 -}
    3.44  
    3.45  int main() {
    3.46    //typedef UndirListGraph Graph; 
    3.47 @@ -113,9 +92,6 @@
    3.48  
    3.49    Graph g;
    3.50  
    3.51 -  std::vector<Graph::Node> s_nodes;
    3.52 -  std::vector<Graph::Node> t_nodes;
    3.53 -
    3.54    int a;
    3.55    std::cout << "number of nodes in the first color class=";
    3.56    std::cin >> a; 
    3.57 @@ -127,13 +103,8 @@
    3.58    std::cin >> m; 
    3.59    
    3.60    std::cout << "Generatig a random bipartite graph..." << std::endl;
    3.61 -  for (int i=0; i<a; ++i) s_nodes.push_back(g.addNode(false));
    3.62 -  for (int i=0; i<b; ++i) t_nodes.push_back(g.addNode(true));
    3.63 -
    3.64    random_init();
    3.65 -  for(int i=0; i<m; ++i) {
    3.66 -    g.addEdge(s_nodes[random(a)], t_nodes[random(b)]);
    3.67 -  }
    3.68 +  randomBipartiteGraph(g, a, b, m);
    3.69  
    3.70  //   std::cout << "Edges of the bipartite graph:" << std::endl;
    3.71  //   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";