| Example Program Kruskals Algorithm Kruskal's algorithm for computing a minimum spanning tree. A tutorial about kruskal's algorithm
| 1 | #include <iostream>
| | 2 | #include <seqan/graph_algorithms.h>
| | 3 |
| | 4 | using namespace seqan;
| | 5 |
| | 6 |
| | 7 | int main() {
| | 8 | typedef Graph<Undirected<> > TGraph;
| | 9 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
| | 10 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
| | 11 | typedef Size<TGraph>::Type TSize;
|
| 12 | TSize numEdges = 14;
| | 13 | TVertexDescriptor edges[] = {0,1, 0,6, 1,2, 1,6, 2,3, 2,4, 2,8, 3,5, 3,8, 4,6, 4,7, 5,8, 6,7, 7,8};
| | 14 | TGraph g;
| | 15 | addEdges(g,edges, numEdges);
| | 16 | ::std::cout << g << std::endl;
|
| 17 | unsigned int weights[] = {4, 8, 8, 11, 7, 2, 4, 9, 14, 7, 6, 10, 1, 2 };
| | 18 | char names[] = {'a', 'b', 'c', 'd', 'i', 'e', 'h', 'g', 'f'};
| | 19 | String<int> weightMap;
| | 20 | resizeEdgeMap(g, weightMap, weights);
| | 21 | String<char> nameMap;
| | 22 | resizeVertexMap(g,nameMap, names);
|
| 23 | String<TVertexDescriptor> treeEdges;
|
| 24 | kruskals_algorithm(g, 0, weightMap, treeEdges);
|
| 25 | ::std::cout << "Minimum Spanning Tree (Kruskal's algorithm): " << ::std::endl;
| | 26 | ::std::cout << "Tree Edges: ";
| | 27 | typedef Iterator<String<TVertexDescriptor> >::Type TStrIterator;
| | 28 | TStrIterator it = begin(treeEdges);
| | 29 | TStrIterator itEnd = end(treeEdges);
| | 30 | while(it!=itEnd) {
| | 31 | ::std::cout << "(" << getProperty(nameMap,getValue(it)) << ",";
| | 32 | goNext(it);
| | 33 | ::std::cout << getProperty(nameMap,getValue(it)) << "), ";
| | 34 | goNext(it);
| | 35 | }
| | 36 | ::std::cout << ::std::endl;
| | 37 | return 0;
| | 38 | }
|
|