⚠

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

rel:graphlib[G]

This section of the graph library supports the following algorithms:

Measure	Description
`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

Parameter	Type	Description
`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_ids 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

Parameter	Type	Description
`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[11]
//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

Parameter	Type	Description
`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[11]
//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

Parameter	Type	Description
`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

Parameter	Type	Description
`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[22]
//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

Parameter	Type	Description
`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[2]
//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);

Was this doc helpful?

Graph Library (graphlib) — Components Algorithms Extension

Graph Library (`graphlib`) — Components Algorithms Extension