warshall.H File Reference

Warshall's algorithm for transitive closure. More...

#include <tpl_graph.H>
#include <tpl_matgraph.H>

Include dependency graph for warshall.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Warshall_Compute_Transitive_Clausure< GT, SA >
	Computes the transitive closure of a graph using Warshall's algorithm. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::warshall_compute_transitive_clausure (GT &g, Bit_Mat_Graph< GT, SA > &mat)
	Computes the transitive closure of a graph using Warshall's algorithm.

Detailed Description

Warshall's algorithm for transitive closure.

Computes the transitive closure of a directed graph: determines reachability between all pairs of vertices.

Features

• Boolean reachability matrix
• Works on adjacency matrix representation

Complexity: O(V³)

See also

Floyd_Warshall.H All-pairs shortest paths (weighted)

Author

Leandro Rabindranath León

Definition in file warshall.H.