| Example Program Dijkstras Algorithm Computing single source shortest paths using Dijkstra algorithm. File "graph_algo_path_dijkstra.cpp" This code example illustrates the dijkstra's algorithm, once using an external map and once using an internal map.
1 | #include <seqan/graph_algorithms.h>
2 | #include <iostream>
3 |
4 | using namespace seqan;
5 |
6 | int main() {
7 | typedef Graph<Directed<> > TGraph;
8 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
9 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
10 | typedef Size<TGraph>::Type TSize;
Graph creation: 10 directed edges (0,1), (0,3), ...
11 | TSize numEdges = 10;
12 | TVertexDescriptor edges[] = {0,1, 0,3, 1,2, 1,3, 2,4, 3,1, 3,2, 3,4, 4,0, 4,2};
13 | TGraph g;
14 | addEdges(g, edges, numEdges);
15 | std::cout << g << ::std::endl;
One external property map: Weight map
16 | unsigned int weights[] = {10, 5, 1, 2, 4, 3, 9, 2, 7, 6};
17 | String<unsigned int> weightMap;
18 | resizeEdgeMap(g,weightMap, weights);
Out-parameters: Predecessor and distance map
19 | String<unsigned int> predMap;
20 | String<unsigned int> distMap;
Dijkstra from vertex 0
21 | dijkstra(g,0,weightMap,predMap,distMap);
Console Output
22 | std::cout << "Single-Source Shortest Paths: " << ::std::endl;
23 | typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
24 | TVertexIterator it(g);
25 | while(!atEnd(it)) {
26 | std::cout << "Path from 0 to " << getValue(it) << ": ";
27 | _print_path(g,predMap,(TVertexDescriptor) 0, getValue(it));
28 | std::cout << " (Distance: " << getProperty(distMap, getValue(it)) << ")" << ::std::endl;
29 | goNext(it);
30 | }
We can achieve the same thing using an internal map that is edge cargos.
31 | typedef unsigned int TEdgeCargo;
32 | typedef Directed<TEdgeCargo> TEdges;
33 | typedef Graph<TEdges> TCargoGraph;
Graph creation
34 | TCargoGraph cargo_g;
35 | addEdges(cargo_g, edges, numEdges);
36 | std::cout << cargo_g << ::std::endl;
One internal property map: Weight map
37 | InternalMap<TEdgeCargo> intMap;
38 | resizeEdgeMap(cargo_g,intMap, weights);
Out parameters of Dijkstra: Predecessor map and distance map
39 | clear(predMap);
40 | clear(distMap);
Dijkstra from vertex 0 using an internal map
41 | dijkstra(cargo_g,0,intMap,predMap,distMap);
Console Output
42 | std::cout << "Single-Source Shortest Paths: " << ::std::endl;
43 | typedef Iterator<TCargoGraph, VertexIterator>::Type TCargoVertexIterator;
44 | TCargoVertexIterator itC(cargo_g);
45 | while(!atEnd(itC)) {
46 | std::cout << "Path from 0 to " << getValue(itC) << ": ";
47 | _print_path(cargo_g,predMap,(TVertexDescriptor) 0, getValue(itC));
48 | std::cout << " (Distance: " << getProperty(distMap, getValue(itC)) << ")" << ::std::endl;
49 | goNext(itC);
50 | }
51 | return 0;
52 | }
See dijkstra, Graph SeqAn - Sequence Analysis Library - www.seqan.de