graphs_transclos.h File Reference

Computation of transitive closures in graphs. More...

#include <stdbool.h>
#include "graphs.h"
#include "graphs_tarjan.h"
#include "type_binheap.h"

Go to the source code of this file.

Functions
graph *	compute_dag_of_sccs (graph *, parti *)
	Given as input an arbitrary graph and its partition into SCCs, computes the associated DAG of SCCs (each class of the partition is a vertex).
dequeue *	topo_sort_dag (graph *)
	Given a DAG as input, computes a topological ordering on its vertices.
dequeue *	topo_sort_dag_start (graph *, uint)
	Given a DAG as input and a vertex of this graph, computes a topological ordering on the vertices that are reachable from the input vertex.
graph *	compute_tclos_dag (graph *, dequeue *)
	Computes the transitive closure of a DAG.

Detailed Description

Computation of transitive closures in graphs.

Function Documentation

compute_dag_of_sccs()

graph * compute_dag_of_sccs	(	graph *	G,
		parti *	clist )

Given as input an arbitrary graph and its partition into SCCs, computes the associated DAG of SCCs (each class of the partition is a vertex).

Returns

The DAG of SCCs.

Parameters

G	An arbitray graph.
clist	The partition into SCCs.

compute_tclos_dag()

graph * compute_tclos_dag	(	graph *	G,
		dequeue *	topo_sort )

Computes the transitive closure of a DAG.

Attention

A list of all vertices sorted in topological order must be given as input.

Returns

The transitive closure.

Parameters

G	A directed acyclic graph.
topo_sort	A list of all vertices sorted according to a topological ordering.

topo_sort_dag()

dequeue * topo_sort_dag

(

graph *

G

)

Given a DAG as input, computes a topological ordering on its vertices.

Attention

The input graph must be a DAG (the algorithm does not terminate otherwise).

Returns

A list of all vertices in the graph sorted according to a topological ordering.

Parameters

G	A directed acyclic graph.

topo_sort_dag_start()

dequeue * topo_sort_dag_start	(	graph *	G,
		uint	start )

Given a DAG as input and a vertex of this graph, computes a topological ordering on the vertices that are reachable from the input vertex.

Attention

The input graph must be a DAG (the algorithm does not terminate otherwise).

Returns

A list of all reachable vertices sorted according to a topological ordering.

Parameters

G	A directed acyclic graph.
start	A vertex.