Several changes in Kruskal alg.
- Input object interface was changed to an STL compatible one.
- template parameters of class KruskalPairVec has been simplified.
- (the most of) the names meet the naming conventions.
- a lot of (but still not enough) documentation has been added.
- class KruskalMapVec has been commented out.
5 #include <sage_graph.h>
6 //#include <smart_graph.h>
7 #include <hugo/dimacs.h>
8 #include <hugo/time_measure.h>
9 #include <hugo/for_each_macros.h>
15 typedef SageGraph Graph;
16 typedef Graph::Node Node;
17 typedef Graph::NodeIt NodeIt;
18 typedef Graph::Edge Edge;
19 typedef Graph::EdgeIt EdgeIt;
20 typedef Graph::OutEdgeIt OutEdgeIt;
24 Graph::EdgeMap<int> cap(g);
25 //readDimacsMaxFlow(std::cin, g, s, t, cap);
26 readDimacs(std::cin, g);
28 Graph::NodeMap<OutEdgeIt> pred(g);
34 Graph::NodeMap<bool> reached(g);
37 std::queue<Node> bfs_queue;
39 while (!bfs_queue.empty()) {
40 Node v=bfs_queue.front();
43 for(g.first(e,v); g.valid(e); g.next(e)) {
53 std::cout << ts << std::endl;
59 Graph::NodeMap<bool> bfs_reached(g);
60 Graph::NodeMap<Edge> bfs_pred(g);
61 Graph::NodeMap<int> bfs_dist(g);
63 Bfs< Graph, Graph::NodeMap<bool>,
64 Graph::NodeMap<Edge>, Graph::NodeMap<int> >
65 bfs(g,bfs_reached, bfs_pred, bfs_dist );
69 while (!bfs.finished()) {
71 if (g.valid(bfs) && bfs.isBNodeNewlyReached())
72 pred.set(bfs.bNode(), bfs);
75 std::cout << ts << std::endl;