fn() topologicalSortPerforms a topological sort on a directed acyclic graph (DAG).
Performs a topological sort on a directed acyclic graph (DAG).
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
void topologicalSort(g, topSort);
|
Parameters
g
|
A directed acyclic graph. Types: Directed Graph |
---|---|
topSort
|
A topological ordering of the vertices. Types: String. |
Detailed Description
A topological sort is a linear ordering of all its vertices such that if the graph contains an edge (u,v) then u appears before v in the ordering.
Example
#include <iostream> #include <seqan/graph_algorithms.h> using namespace seqan; int main() { typedef Graph<Directed<> > TGraph; typedef VertexDescriptor<TGraph>::Type TVertexDescriptor; typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor; typedef Size<TGraph>::Type TSize; // Create graph with 9 directed edges (0,3), (0,1), ... TSize numEdges = 9; TVertexDescriptor edges[] = {0,3, 0,1, 1,2, 3,2, 5,7, 5,6, 6,7, 6,3, 8,7}; TGraph g; addEdges(g, edges, numEdges); // Print graph. std::cout << g << "\n"; // Create external property map with vertex labels. String<std::string> nameMap; std::string names[] = {"shirt", "tie", "jacket", "belt", "watch", "undershorts", "pants", "shoes", "socks"}; assignVertexMap(g, nameMap, names); // Get vertex descriptor in topological sort order. String<TVertexDescriptor> order; topologicalSort(g, order); // Write the result to stdout. std::cout << "Topological sort: \n"; typedef Iterator<String<TVertexDescriptor> >::Type TStringIterator; TStringIterator it = begin(order); TStringIterator itEnd = end(order); while (it != itEnd) { std::cout << getProperty(nameMap, getValue(it)) << ","; goNext(it); } std::cout << "\n"; return 0; }
Adjacency list: 0 -> 1,3, 1 -> 2, 2 -> 3 -> 2, 4 -> 5 -> 6,7, 6 -> 3,7, 7 -> 8 -> 7, Edge list: Source: 0,Target: 1 (Id: 1) Source: 0,Target: 3 (Id: 0) Source: 1,Target: 2 (Id: 2) Source: 3,Target: 2 (Id: 3) Source: 5,Target: 6 (Id: 5) Source: 5,Target: 7 (Id: 4) Source: 6,Target: 3 (Id: 7) Source: 6,Target: 7 (Id: 6) Source: 8,Target: 7 (Id: 8) Topological sort: socks,undershorts,pants,shoes,watch,shirt,belt,tie,jacket,