1 | #include <cstdlib> |
---|

2 | #include <iostream> |
---|

3 | #include <sstream> |
---|

4 | |
---|

5 | #include <lemon/smart_graph.h> |
---|

6 | |
---|

7 | #include <lemon/bpugraph_adaptor.h> |
---|

8 | #include <lemon/bipartite_matching.h> |
---|

9 | |
---|

10 | #include <lemon/graph_utils.h> |
---|

11 | #include <lemon/xy.h> |
---|

12 | #include <lemon/graph_to_eps.h> |
---|

13 | |
---|

14 | #include <lemon/time_measure.h> |
---|

15 | |
---|

16 | using namespace std; |
---|

17 | using namespace lemon; |
---|

18 | |
---|

19 | typedef SmartBpUGraph Graph; |
---|

20 | BPUGRAPH_TYPEDEFS(Graph); |
---|

21 | |
---|

22 | int _urandom_init() { |
---|

23 | int seed = time(0); |
---|

24 | srand(seed); |
---|

25 | return seed; |
---|

26 | } |
---|

27 | |
---|

28 | int urandom(int n) { |
---|

29 | static int seed = _urandom_init(); |
---|

30 | ignore_unused_variable_warning(seed); |
---|

31 | return (int)(rand() / (1.0 + RAND_MAX) * n); |
---|

32 | } |
---|

33 | |
---|

34 | int main() { |
---|

35 | |
---|

36 | for (int k = 1; k < 100; ++k) { |
---|

37 | |
---|

38 | int n = k * 100; |
---|

39 | int m = (100 - k) * 100; |
---|

40 | int e = 20000; |
---|

41 | int s = 100; |
---|

42 | |
---|

43 | Timer nt(false), st(false); |
---|

44 | |
---|

45 | for (int i = 0; i < s; ++i) { |
---|

46 | Graph graph; |
---|

47 | vector<Node> aNodes; |
---|

48 | vector<Node> bNodes; |
---|

49 | |
---|

50 | for (int i = 0; i < n; ++i) { |
---|

51 | Node node = graph.addANode(); |
---|

52 | aNodes.push_back(node); |
---|

53 | } |
---|

54 | for (int i = 0; i < m; ++i) { |
---|

55 | Node node = graph.addBNode(); |
---|

56 | bNodes.push_back(node); |
---|

57 | } |
---|

58 | for (int i = 0; i < e; ++i) { |
---|

59 | Node aNode = aNodes[urandom(n)]; |
---|

60 | Node bNode = bNodes[urandom(m)]; |
---|

61 | graph.addEdge(aNode, bNode); |
---|

62 | } |
---|

63 | |
---|

64 | { |
---|

65 | MaxBipartiteMatching<Graph> bpmatch(graph); |
---|

66 | |
---|

67 | nt.start(); |
---|

68 | bpmatch.init(); |
---|

69 | bpmatch.start(); |
---|

70 | nt.stop(); |
---|

71 | |
---|

72 | } |
---|

73 | |
---|

74 | { |
---|

75 | typedef SwapBpUGraphAdaptor<Graph> SGraph; |
---|

76 | SGraph sgraph(graph); |
---|

77 | MaxBipartiteMatching<SGraph> bpmatch(sgraph); |
---|

78 | |
---|

79 | st.start(); |
---|

80 | bpmatch.init(); |
---|

81 | bpmatch.start(); |
---|

82 | st.stop(); |
---|

83 | |
---|

84 | } |
---|

85 | |
---|

86 | } |
---|

87 | |
---|

88 | cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl; |
---|

89 | |
---|

90 | } |
---|

91 | |
---|

92 | return 0; |
---|

93 | } |
---|