A push/relabel type max cardinality matching implementation.
(slightly incompatible with bipartite_matching.h)
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 #include<lemon/smart_graph.h>
22 #include"bench_tools.h"
25 using namespace lemon;
27 inline int numOfOnes(int n,int dim)
30 for(int i=0;i<dim;i++) {
37 inline int numOfZeros(int n,int dim)
40 for(int i=0;i<dim;i++) {
48 void bfsStlQueue(Graph &G,typename Graph::Node source)
50 GRAPH_TYPEDEFS(typename Graph);
54 typename Graph::template NodeMap<bool> visited(G,false);
56 queue<typename Graph::Node> Q;
64 for(OutEdgeIt e(G,n);e!=INVALID;++e)
65 if(!visited[m=G.target(e)]) {
73 void bfsOwnQueue(Graph &G,typename Graph::Node source)
75 GRAPH_TYPEDEFS(typename Graph);
79 typename Graph::template NodeMap<bool> visited(G,false);
82 vector<typename Graph::Node> Q(N);
88 visited.set(source,true);
92 for(OutEdgeIt e(G,n);e!=INVALID;++e)
93 if(!visited[m=G.target(e)]) {
100 template<class Graph>
101 void iteratorBench(Graph &G)
103 GRAPH_TYPEDEFS(typename Graph);
107 for(NodeIt n(G);n!=INVALID;++n)
108 for(OutEdgeIt e(G,n);e!=INVALID;++e)
112 int main(int argc, char *argv[])
114 typedef SmartGraph Graph;
116 GRAPH_TYPEDEFS(Graph);
123 cout << "Usage: " << argv[0] << " dim mul\n";
127 int dim=atoi(argv[1]);
128 int mul=atoi(argv[2]);
130 // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
131 // << dim*(1<<dim) << " edges):";
135 addBiDirHyperCube(G,dim,nodes);
137 PrintTime("GENGRAPH",T);
141 for(int i=0;i<mul;i++)
142 bfsStlQueue(G,nodes[0]);
144 PrintTime("BFS-STL",T);
147 for(int i=0;i<mul;i++)
148 bfsOwnQueue(G,nodes[0]);
150 PrintTime("BFS-OWN",T);
153 for(int i=0;i<mul;i++)
156 PrintTime("ITERATE",T);