Skip to main content

module analysis::graphs::Graph

rascal-Not specified

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"

function transitiveEdges​

Select the short-cut edges, the ones that transitively close at least two other edges.

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