Library: graphlib (paths)

EXPERIMENTAL: These features are experimental and should not be used in production systems.

# Graph Library (`graphlib`) — Paths Algorithms Extension

A library extension to `graphlib` containing various path-finding algorithms.

## Module: rel:graphlib

View source
``rel:graphlib[G]``

In this section of the graph library supports the following similarity algorithms:

AlgorithmDescription
`shortest_path_length`The length of the shortest path between two nodes.
`transitive_closure`The reachability of nodes.

### shortest_path_length

View source
`````` shortest_path_length
shortest_path_length[u]
shortest_path_length[u, v]
shortest_path_length(u, v, l)``````

`shortest_path_length` computes the length of the shortest path between every pair of nodes`G`. `shortest_path_length[u, v]` computes the length of the shortest path between nodes `u` and `v` in `G`. `shortest_path_length(u, v, l)` checks if `l` is the length of the shortest path between `u` and `v` in `G`.

Parameters

ParameterTypeDescription
`u``G:node`A node in `G`.
`v``G:node`A node in `G`.
`l``Int`The length of the shortest path between nodes `u` and `v`.

Examples

Compute the shortest path length between every pair of nodes:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:shortest_path_length
//output> (11, 11, 0)
//        (11, 12, 1)
//        (11, 13, 2)
//        (11, 14, 2)``````

Careful using `shortest_path_length` on the entire graph, as in the preceding example. For large graphs, this may be infeasible.

Compute the shortest path length between a node and every other node:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:shortest_path_length
//output> (11, 1)
//        (12, 0)
//        (13, 1)
//        (14, 1)``````

Compute the shortest path length between the given two nodes:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:shortest_path_length[12, 14]
//output> 1``````

Check whether `l` is the shortest path length between two nodes:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:shortest_path_length(12, 14, 1)
//output> ()  // true``````

Compute the shortest distance between all pairs of nodes in the relation `my_node`:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14); (14, 13)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def my_node = {11; 12}
def my_shortest_path_length[u in my_node, v in my_node] = my_graphlib:shortest_path_length[u, v]

def output = my_shortest_path_length
//output> (11, 11, 0)
//        (11, 12, 1)
//        (12, 11, 1)
//        (12, 12, 0)``````

### transitive_closure

View source
``````transitive_closure
transitive_closure[u]
transitive_closure(u, v)``````

`transitive_closure` computes the transitive closure of graph `G`. `transitive_closure[u]` computes the set of reachable nodes from node `u`. `transitive_closure(u, v)` is true when node `v` is reachable from node `u`.

Parameters

ParameterTypeDescription
`u``G:node`A node in `G`.
`v``G:node`A node in `G`.

Examples

Compute the transitive closure of graph `G`:

``````def my_edges = {(1, 2); (2, 3); (3, 4)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:transitive_closure
//output> (1, 2)
//        (1, 3)
//        (1, 4)
//        (2, 3)
//        (2, 4)
//        (3, 4)``````

Careful using `transitive_closure` on the entire graph, as in the preceding example. For large graphs, this may be infeasible.

Compute the set of reachable nodes from node `u`:

``````def my_edges = {(1, 2); (2, 3); (3, 4)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:transitive_closure
//output> 3
//        4``````

Check whether node `v` is reachable from node `u`:

``````def my_edges = {(1, 2); (2, 3); (3, 4)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:transitive_closure(2, 4)
//output> ()  // true``````

Compute the transitive closure of a set of nodes `my_nodes`:

``````def my_edges = {(1, 2); (2, 3); (3, 4); (5, 6)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]

def my_nodes = {2; 3; 5}
def output = my_graphlib:transitive_closure[my_nodes]
//output> 3
//        4
//        6``````