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 sourcerel:graphlib[G]In this section of the graph library supports the following similarity algorithms:
| Algorithm | Description |
|---|---|
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 nodesG.
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
| Parameter | Type | Description |
|---|---|---|
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[12]
//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> 1Check 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> () // trueCompute 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 sourcetransitive_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
| Parameter | Type | Description |
|---|---|---|
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[2]
//output> 3
// 4Check 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> () // trueCompute 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