fn() transitiveClosure
Determines whether there is a path between any two given vertices or not.

Defined in <seqan/graph_algorithms.h>
Signature void transitiveClosure(closure, g);

Parameters

closure A matrix which indicates the closure. Entry (i,j) in this matrix indicates whether there is a path from i to j in the graph or not. Types: Matrix
g A directed graph. Types: Directed Graph

Detailed Description

Example

#include <iostream>
#include <seqan/graph_algorithms.h>

using namespace seqan2;

int main()
{
    typedef Graph<Directed<> > TGraph;
    typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
    typedef Size<TGraph>::Type TSize;

    // Create graph with 5 directed edges (3,0), (1,2), ...
    TSize numEdges = 5;
    TVertexDescriptor edges[] = {3, 0, 1, 2, 2, 1, 1, 3, 3, 2};
    TGraph g;
    addEdges(g, edges, numEdges);
    // Print graph to stdout.
    std::cout << g << "\n";

    // Compute transitive closure.
    String<bool> closure;
    transitiveClosure(closure, g);

    // Print result to stdout.
    TSize len = static_cast<TSize>(std::sqrt((double) length(closure)));
    for (TSize row = 0; row < len; ++row)
    {
        for (TSize col = 0; col < len; ++col)
            std::cout << getValue(closure, row * len + col) << ",";
        std::cout << std::endl;
    }

    return 0;
}
Adjacency list:
0 -> 
1 -> 3,2,
2 -> 1,
3 -> 2,0,
Edge list:
Source: 1,Target: 3 (Id: 3)
Source: 1,Target: 2 (Id: 1)
Source: 2,Target: 1 (Id: 2)
Source: 3,Target: 2 (Id: 4)
Source: 3,Target: 0 (Id: 0)

1,0,0,0,
1,1,1,1,
1,1,1,1,
1,1,1,1,

Data Races

If not stated otherwise, concurrent invocation is not guaranteed to be thread-safe.