Library: graphlib (components)

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

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

A library extension to `graphlib` containing various connectivity algorithms.

## Module: rel:graphlib

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

This section of the graph library supports the following algorithms:

MeasureDescription
`weakly_connected_component`A mapping from nodes to their components.
`is_connected`Whether the graph is connected or disconnected.
`triangle`List all tuples that form a triangle.
`unique_triangle`The set of all tuples that form a unique triangle.
`num_triangles`The number of unique triangles.
`triangle_count`The number of unique triangles a node belongs to.
`triangle_distribution`The distribution of unique triangles.
`diameter_range`The range of possible diameter values.

### weakly_connected_component

View source
``````weakly_connected_component
weakly_connected_component[u]
weakly_connected_component(u, c)``````

`weakly_connected_component` computes the weakly connected components of `G`. `weakly_connected_component[u]` computes the weakly connected component to which `u` belongs in `G`. `weakly_connected_component(u, c)` checks if `u` belongs to the weakly connected component `c` in `G`.

Parameters

ParameterTypeDescription
`u``G:node`A node in `G`.
`c``G:node`A unique identifier of a component.

Explanation

Weakly connected components (opens in a new tab) maps nodes to their components via tuples of the form `(node_id, component_id)`. The `component_id` is a unique value that is taken to be the minimum of the `node_id`s in a given component. `weakly_connected_component` is supported for directed and undirected graphs. For undirected graphs, weakly connected compoments are the same as connected components.

Examples

Compute the weakly connected component on a directed graph.

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

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

Compute weakly_connected_component on an undirected graph.

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

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

### is_connected

View source
``is_connected``

`is_connected` checks whether `G` is connected.

Explanation

`is_connected` is used to determine whether or not the graph is connected. A graph is considered connected if any node is reachable from any other node in the graph in the undirected case, and any node is reachable from any other node in the graph in the directed case when we discard directions.

Examples

`is_connected` is empty (false) when the graph is disconnected:

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

def output = my_graphlib:is_connected
//output>     // false``````

`is_connected` is true when the graph is connected:

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

def output = my_graphlib:is_connected
//output> ()  // true``````

### triangle

View source
``````triangle
triangle[a]
triangle[a, b]
triangle(a, b, c)``````

`triangle` computes triangles in graph `G`. `triangle[a]` computes nodes forming a triangle starting at node `a`. `triangle[a, b]` computes nodes forming a triangle starting at node `a` and then `b`. `triangle(a, b, c)` is true if nodes `a`, `b`, and `c` form a triangle.

Parameters

ParameterTypeDescription
`a``G:node`A node in `G`.
`b``G:node`A node in `G`.
`c``G:node`A node in `G`.

Examples

Compute triangles in a directed graph:

``````def my_edges = {(11, 22); (22, 33); (33, 11)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle
//output> (11, 22, 33)
//        (22, 33, 11)
//        (33, 11, 22)
``````

Compute triangles in an undirected graph:

``````def my_edges = {(11, 22); (22, 33); (33, 11)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle
//output> (11, 22, 33)
//        (22, 11, 33)
//        (22, 33, 11)
//        (33, 11, 22)
//        (33, 22, 11)``````

Compute the nodes forming triangles starting at a given node:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle
//output> (22, 33)``````

Given a set of nodes, compute the nodes forming a triangle starting at each nodes in the set:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle[{11; 22}]
//output> (22, 33)
//        (33, 11)``````

Compute the last node forming a triangle with a given set of two nodes:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle[11, 22]
//output> 33``````

Given a set of three nodes, check if they form a triangle:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle(11, 22, 33)
//output> ()  // true``````

### unique_triangle

View source
``````unique_triangle
unique_triangle[a]
unique_triangle[a, b]
unique_triangle(a, b, c)``````

`unique_triangle` computes unique triangles in graph `G`. `unique_triangle[a]` computes nodes forming a unique triangle starting at node `a`. `unique_triangle[a, b]` computes nodes forming a unique triangle starting at node `a` and then `b`. `unique_ triangle(a, b, c)` is true if nodes `a`, `b`, and `c` form a unique triangle.

Parameters

ParameterTypeDescription
`a``G:node`A node in `G`.
`b``G:node`A node in `G`.
`c``G:node`A node in `G`.

Explanation

`unique_triangle` contains triples of nodes `(a, b, c)` representing unique triangles in a graph. In undirected graphs, uniqueness of each triangle is guaranteed because `unique_triangle` only contains triples with `a < b < c`.

For directed graphs, the triple `(a, b, c)` represents a triangle with directed edges `(a, b)`, `(b, c)`, and `(c, a)`, and is unique up to ordering of the nodes and direction of the edges. `unique_triangle` only contains triples such that `a < b`, `a < c`, and `b != c`. For example, the triples `(1, 2, 3)` and `(1, 3, 2)` represent two unique directed triangles.

Examples

Compute unique triangles in a directed graph:

``````def my_edges = {(11, 33); (22, 11); (33, 22); (33, 44); (22, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:unique_triangle
//output> (11, 33, 22)``````

Compute unique triangles in an undirected graph:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (22, 44)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:unique_triangle
//output> (11, 22, 33)
//        (22, 33, 44)``````

Compute the nodes forming unique triangles starting at a given node:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:unique_triangle
//output> (22, 33)``````

Given a set of nodes, compute the nodes forming a triangle starting at each nodes in the set:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:unique_triangle[{11; 22}]
//output> (22, 33)``````

Given two nodes, compute the nodes forming unique triangles with the given nodes:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:unique_triangle[11, 22]
//output> 33``````

Given a set of three nodes, check if they form a unique triangle:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:unique_triangle(11, 22, 33)
//output> ()  // true``````

### num_triangles

View source
``````num_triangles
num_triangles(n)``````

`num_triangles` computes the number of unique triangles in graph `G`. `num_triangles(n)` is `true` if there are `n` unique triangles in graph `G`.

Parameters

ParameterTypeDescription
`n``Int`An integer value.

Examples

Compute the number of unique triangles:

``````def my_edges = {(11, 33); (22, 11); (33, 22); (33, 44); (11, 44)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:num_triangles
//output> 1``````

If a graph has no triangles, the result of `num_triangles` is 0:

``````def my_edges = {(11, 22); (22, 33)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:num_triangles
//output> 0``````

Check if the graph has `n` unique triangles:

``````def my_edges = {(11, 33); (22, 11); (33, 22); (33, 44); (11, 44)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:num_triangles(2)
//output> ()  // true``````

### triangle_count

View source
``````triangle_count
triangle_count[w]
triangle_count(w, n)``````

`triangle_count` computes the number of unique triangles to which each node in graph `G` belongs. `triangle_count[w]` computes the number of unique triangles to which node `w` belongs. `triangle_count(w, n)` is true if node `w` belongs to `n` unique triangles.

Parameters

ParameterTypeDescription
`w``G:node`A `G:node` relation.
`n``Int`An integer value.

Examples

Compute the number of unique triangles to which each node belong:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle_count
//output> (11, 1)
//        (22, 1)
//        (33, 1)
//        (44, 0)
//        (55, 0)``````

Compute the number of unique triangles to which a given node belongs:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle_count
//output> 1``````

Compute the number of unique triangles to which the nodes in given a node relation belong:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle_count[22; 44]
//output> 0
//        1``````

Check if a node belongs to a unique triangle:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:num_triangles(22, 1)
//output> ()  // true``````

### triangle_distribution

View source
``````triangle_distribution
triangle_distribution[n]
triangle_distribution(n, c)``````

`triangle_distribution` computes the distribution of unique triangles in graph `G`. `triangle_distribution[n]` computes the number of nodes that belong to `n` unique triangles. `triangle_distribution(n, c)` is true if `c` nodes belong to `n` unique triangles.

Parameters

ParameterTypeDescription
`n``Int`An integer relation corresponding to the number of triangles.
`c``Int`An integer relation corresponding to node counts.

Examples

Compute the distribution of triangles:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = directed_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle_distribution
//output> (0, 2)
//        (1, 3)``````

Compute the number of nodes that belong to two unique triangles:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:triangle_distribution
//output> 2``````

Check whether `c` nodes belong to `n` unique triangles:

``````def my_edges = {(11, 22); (22, 33); (22, 44); (33, 11); (33, 44); (55, 11)}
def my_graph = undirected_graph[my_edges]
def my_graphlib = rel:graphlib[my_graph]

def output = my_graphlib:num_triangles(2, 2)
//output> ()  // true - two nodes belong to two unique triangles``````

### diameter_range

View source
``diameter_range``

`diameter_range` estimates the diameter of a graph by giving a minimum bound and a maximum bound.

Explanation

`diameter_range` is used to determine the range of possible diameter values. This is done by selecting a number of random nodes in the graph and taking the maximum of all shortest paths lengths to the rest of the graph. This gives a range per node. Then, the intersection of these ranges is taken and the final range is returned.

Examples

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

def output = my_graphlib:diameter_range
//output> ("max", 2);
//        ("min", 2);``````