| Example Program Heuristic Matching Path-growing code example File "graph_algo_matching_pathgrowing.cpp" This code example illustrates the simple path growing heuristic for matching
1 | #include <seqan/graph.h>
2 | #include <iostream>
3 |
4 | using namespace seqan;
5 |
6 | int main() {
7 | typedef Graph<Undirected<> > TGraph;
8 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
9 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
10 | typedef Iterator<TGraph, EdgeIterator>::Type TEdgeIterator;
11 | typedef Size<TGraph>::Type TSize;
Graph creation: 14 undirected edges {0,7}, {0,5}, ...
12 | TSize numEdges = 14;
13 | TVertexDescriptor edges[] = {0,7, 0,5, 0,8, 1,5, 1,6, 2,6, 2,5, 2,8, 3,8, 3,4, 4,5, 4,6, 4,7, 4,8};
14 | TGraph g;
15 | addEdges(g,edges, numEdges);
16 | std::cout << g << std::endl;
One external property map: Edge weights
17 | unsigned int weights[] = {20, 5, 19, 6, 7, 10, 3, 9, 12, 11, 13, 12, 9, 12};
18 | String<unsigned int> weightMap;
19 | resizeEdgeMap(g, weightMap, weights);
Out-parameters: Selected edges
20 | String<bool> edgeMap;
Path growing algorithm
21 | unsigned int weight = path_growing_algorithm(g, weightMap, edgeMap);
Console output
22 | std::cout << "Found matching of weight: " << weight << std::endl;
23 | std::cout << "Selected edges are: " << std::endl;
24 | TEdgeIterator it(g);
25 | for(;!atEnd(it);++it) {
26 | if (getProperty(edgeMap, *it) == true) {
27 | std::cout << '{' << sourceVertex(it) << ',' << targetVertex(it) << '}' << " - Weight: " << getProperty(weightMap, *it) << std::endl;
28 | }
29 | }
30 | return 0;
31 | }
See Graph SeqAn - Sequence Analysis Library - www.seqan.de