Aleph::Warshall_Compute_Transitive_Clausure< GT, SA > Class Template Reference

Computes the transitive closure of a graph using Warshall's algorithm. More...

#include <warshall.H>

Inheritance diagram for Aleph::Warshall_Compute_Transitive_Clausure< GT, SA >:

Public Member Functions
void	operator() (GT &g, Bit_Mat_Graph< GT > &mat) const
	Invokes the computation of the transitive closure of a graph.

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Warshall_Compute_Transitive_Clausure< GT, SA >

Computes the transitive closure of a graph using Warshall's algorithm.

This functor class computes the transitive closure of a graph using Warshall's algorithm. The result is stored in a bit matrix.

Each entry (i,j) in the matrix indicates whether there exists a path from the source node with index i to the destination node with index j.

See also

List_Graph Bit_Mat_Graph

Definition at line 113 of file warshall.H.

Member Function Documentation

operator()()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Warshall_Compute_Transitive_Clausure< GT, SA >::operator() ( GT &  g, Bit_Mat_Graph< GT > &  mat  ) const

inline

Invokes the computation of the transitive closure of a graph.

The procedure uses two bit matrices: an internal temporary one (freed when the procedure ends) and the output matrix mat.

Parameters

[in]	g	The graph represented by a List_Graph variant.
[out]	mat	Bit matrix where the result is stored.

Exceptions

std::bad_alloc

if there is not enough memory.

Definition at line 127 of file warshall.H.

References Aleph::maps().

---

The documentation for this class was generated from the following file:

• warshall.H