Skip to main content

module analysis::graphs::Graph

rascal-0.34.0

A Graph alias for reflective relations with associated graph analysis functions.

Usage

import analysis::graphs::Graph;

Dependencies

import Set;
import List;
import Relation;
import util::Math;

Description

The Graph data type is an alias for binary type-reflective relations. So all operators and functions defined on reflective relations are also defined on Graphs.

The Graph library provides the following additional functions:

alias Graph

rel[&T from, &T to]

function order

Compute topological order of the nodes in a graph.

list[&T] order(Graph[&T] g)

Examples

rascal>import  analysis::graphs::Graph;
ok
rascal>order({<3,4>, <1,2>, <2,4>, <1,3>});
list[int]: [1,2,3,4]

function stronglyConnectedComponents

Compute strongly connected components in a graph.

set[set[&T]] stronglyConnectedComponents(Graph[&T] g)

Examples

rascal>import  analysis::graphs::Graph;
ok
rascal>stronglyConnectedComponents({<1, 2>, <2, 3>, <3, 2>, <2, 4>, <4, 2>, <3, 5>, <5, 3>, <4, 5>, <5, 3>});
set[set[int]]: {
{1},
{5,3,2,4}
}

function stronglyConnectedComponentsAndTopSort

Compute the strongly connected components in a graph and return also the topologically sorted elements

tuple[set[set[&T]], list[&T]]  stronglyConnectedComponentsAndTopSort(Graph[&T] g)

Tarjan's algorithm for computing strongly connected components in a graph Returns :

function bottom

Determine the bottom nodes (leaves) of a graph.

set[&T] bottom(Graph[&T] G)

Returns the bottom nodes of Graph G, i.e., the leaf nodes that don't have any descendants.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>bottom({<1,2>, <1,3>, <2,4>, <3,4>});
set[int]: {4}

function predecessors

Determine the direct predecessors of a graph node.

set[&T] predecessors(Graph[&T] G, &T From)

Returns the direct predecessors of node From in Graph G.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>predecessors({<1,2>, <1,3>, <2,4>, <3,4>}, 4);
set[int]: {3,2}

function reach

Determine the graph nodes reachable from a set of nodes.

set[&T] reach(Graph[&T] G, set[&T] Start)

Returns the set of nodes in Graph G that are reachable from any of the nodes in the set Start.

function reachR

Determine the graph nodes reachable from a set of nodes using a restricted set of intermediate nodes.

set[&T] reachR(Graph[&T] G, set[&T] Start, set[&T] Restr)

Returns the set of nodes in Graph G that are reachable from any of the nodes in set Start using path that only use nodes in the set Restr.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>reachR({<1,2>, <1,3>, <2,4>, <3,4>}, {1}, {1, 2, 3});
set[int]: {3,2}

function reachX

Determine the graph nodes reachable from a set of nodes excluding certain intermediate nodes.

set[&T] reachX(Graph[&T] G, set[&T] Start, set[&T] Excl)

Returns set of nodes in Graph G that are reachable from any of the nodes in Start via path that exclude nodes in Excl.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>reachX({<1,2>, <1,3>, <2,4>, <3,4>}, {1}, {2});
set[int]: {3,4}

function shortestPathPair

Determine the shortest path between two graph nodes.

list[&T] shortestPathPair(Graph[&T] G, &T From, &T To)

Returns the shortest path between nodes From and To in Graph G.

function successors

Determine the direct successors of a graph node.

set[&T] successors(Graph[&T] G, &T From)

Returns the direct successors of node From in Graph G.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>successors({<1,2>, <1,3>, <2,4>, <3,4>}, 1);
set[int]: {3,2}

function top

Determine the set of top nodes (roots) of a graph.

set[&T] top(Graph[&T] G)

Returns the top nodes of Graph G, i.e., the root nodes that do not have any predecessors.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>top({<1,2>, <1,3>, <2,4>, <3,4>});
set[int]: {1}

function connectedComponents

Determine the connected components of a graph.

set[set[&T]] connectedComponents(Graph[&T] G)

Returns the [connected components](http://en.wikipedia.org/wiki/Connected_component_(graph_theory) of Graph G, as sets of nodes. All nodes within one component are all reachable from one another, there are no paths between two nodes from different components. The graph is assumed to be undirected.

Examples

rascal>import analysis::graphs::Graph;
ok
rascal>connectedComponents({<1,2>, <1,3>, <4,5>, <5,6>});
set[set[int]]: {
{5,4,6},
{1,3,2}
}

function transitiveReduction

Transitive reduction of a directed graph

Graph[&T] transitiveReduction(Graph[&T] g)

The transitive reduction removes all "superfluous" edges in the sense that all nodes remain reachable but all "shortcuts" have been removed.

The algorithm is inspired by the following paper, and uses the builtin (fast) transitive closure algorithm from Rascal, and the composition operator o as an oracle to find out which edges span more than one level in the graph. Note that the transitive reduction's worst case complexity is in the same order as transitive closure itself anyway.

Aho, A. V.; Garey, M. R.; Ullman, J. D. (1972), "The transitive reduction of a directed graph", SIAM Journal on Computing, 1 (2): 131–137, doi:10.1137/0201008

Benefits

  • directed acyclic graphs are simplified (easier to draw clearly) without breaking node reachability

Pitfalls

  • reduces cyclic sub-graphs to "empty"