Library: graphlib (basics)

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

# Graph Library (`graphlib`) — Basics

A collection of relations to enable graph workloads in Rel.

## Module: undirected_graph

View source
``undirected_graph[E]``

`undirected_graph[E]` creates an undirected graph from the binary edge relation `E`.

Parameters

ParameterTypeDescription
`E`RelationA binary edge relation. Must be grounded.

Explanation

`undirected_graph[E]` creates an undirected graph using unique node IDs and edges from a given binary edge relation `E` where there is an edge between `u` and `v` if `(u, v)` is in `E`. Loops are allowed and expressed by the tuple `(u, u)`.

The resulting graph is a module with two relations: a unary relation `node` and a binary relation `edge`. The relation `node` contains all the node IDs and the relation `edge` contains the edge pairs similar to `E`. Since the resulting graph is undirected, both node pair combinations, `(u, v)` and `(v, u)`, are stored in `edge`.

Examples

Consider the following graph:

``````11 --- 12 --- 14
|
13__
|__|``````

This can be epxressed in Rel as follows:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
def output = my_graph:node
//output> 11
//        12
//        13
//        14

def output = my_graph:node
//output> ()  // true

def output = my_graph:node(11; 12; 13; 14)
//output> ()  // true``````

## Module: directed_graph

View source
``directed_graph[E]``

`directed_graph[E]` creates a directed graph from the binary edge relation `E`.

Parameters

ParameterTypeDescription
`E`RelationA binary edge relation. Must be grounded.

Explanation

`directed_graph[E]` creates an undirected graph using unique node ids and edges from a given binary edge relation `E` where there is an edge from `u` to `v` if `(u, v)` is in `E` and `(u, u)` is a self loop.

The resulting graph is a module with two relations: a unary relation `node` and a binary relation `edge`. The relation `node` contains all the node IDs and the relation `edge` contains the edge pairs as they occur in `E`.

Examples

Consider the following graph:

``````11 → 12 → 14
↓
13
↺``````

This can be epxressed in Rel as follows:

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
def output = my_graph:node
//output> 11
//        12
//        13
//        14

def output = my_graph:node
//output> ()  // true

def output = my_graph:node(11; 12; 13; 14)
//output> ()  // true``````

## Module: rel:graphlib

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

The library `graphlib` provides a wide range of graph algorithms for a given graph `G`.

Parameters

ParameterTypeDescription
`G`GraphA valid graph. Must be grounded.

Explanation

The module `rel:graphlib` is the heart of the graph library. It provides a wide range of graph operations and algorithms that can be performed over a relational graph `G`.

The graph `G`, over which the graph algorithm should be performed, needs to be stated as an argument for the graph library, `rel:graphlib[G]`.

The graph library assumes that the relational graph `G` follows a specific schema where the nodes and edges are defined in relations `node` and `edge`, respectively.

More information about the structure can be found in the docstrings of `undirected_graph` and `directed_graph`.

To perform a graph algorithm (like `neighbor`) over a graph `G`, one can state the graph and the algorithm together

``````def my_graph = undirected_graph[{(1,2); (2,3); (2,4)}]
def output = rel:graphlib[my_graph, :neighbor]``````

or for convenience, first bind the graph library to your graph of interest, and then in a second step pick the algorithm of choice.

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

def output:in = my_graphlib[:inneighbor]
def output:out = my_graphlib[:outneighbor]``````

Alternatively, you can do

``````def my_graph = undirected_graph[{(1,2); (2,3); (2,4)}]

with rel:graphlib[my_graph] use inneighbor, outneighbor

def output:in = inneighbor
def output:out = outneighbor``````

Note that `my_graphlib[:neighbor]` can be equally well written without the square brackets, `my_graphlib:neighbor`.

The graph library comes with the following algorithms:

AlgorithmDescription
`num_nodes`The number of nodes.
`num_edges`The number of edges.
`neighbor`The set of neighboring nodes.
`inneighbor`The set of neighboring nodes that are connected with the target node by an incoming edge.
`outneighbor`The set of neighboring nodes that are connected with the target node by an outgoing edge.

Examples

Define an undirected graph G and use the graph library to calculate the number of edges in the graph.

``````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:num_edges
//output> 4``````

### num_nodes

View source
``````num_nodes
num_nodes(n)``````

`num_nodes` computes the number of nodes in `G`. `num_nodes(n)` checks if `G` has `n` nodes.

Parameters

ParameterTypeDescription
`n``Int`The node count of the graph.

Examples

``````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:num_nodes
//output> 4

def output = my_graphlib:num_nodes(4)
//output> ()  // true``````

### num_edges

View source
``````num_edges
num_edges(n)``````

`num_edges` computes the number of edges in `G`. `num_edges(n)` checks if `G` has `n` edges.

Parameters

ParameterTypeDescription
`n``Int`A number.

Examples

``````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:num_edges
//output> 4

def output = my_graphlib:num_edges(4)
//output> ()  // true``````

### neighbor

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

`neighbor` computes the neighbors of every node in `G`. `neighbor[u]` computes the neighbors of `u` in `G`. `neighbor(u, v)` checks if `v` is a neighbor of `u` in `G`.

Parameters

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

Explanation

`neighbor` can be used to get the set of neighbors for each node in `G`. If `G` is directed, both inneighbors and outneighbors are considered as neighbors.

Examples

``````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:neighbor
//output> (11, 12)
//        (12, 11)
//        (12, 13)
//        (12, 14)
//        (13, 12)
//        (13, 13)
//        (14, 12)

def output = my_graphlib:neighbor
//output> 11
//        13
//        14

def output = my_graphlib:neighbor(12, 11)
//output> ()  // true``````

### inneighbor

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

`inneighbor` computes the inneighbors of every node in `G`. `inneighbor[u]` computes the inneighbors of `u` in `G`. `inneighbor(u, v)` checks if `v` is an inneighbor of `u` in `G`.

Parameters

ParameterTypeDescription
`u``G:node`A node in `G`.
`v``G:node`An inneighbor of `u` in `G`.

Explanation

`inneighbor` can be used to get the set of inbound neighbors for each node in `G`. If `G` is undirected, `neighbor` and `inneighbor` are identical.

Examples

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:inneighbor
//output> (12, 11)
//        (13, 12)
//        (13, 13)
//        (14, 12)

def output = my_graphlib:inneighbor
//output> 12
//        13

def output = my_graphlib:inneighbor(13, 12)
//output> ()  // true``````

### outneighbor

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

`outneighbor` computes the outneighbors of every node in `G`. `outneighbor` computes the outneighbors of `u` in `G`. `outneighbor(u, v)` checks `v` is an outneighbor of `u` in `G`.

Parameters

ParameterTypeDescription
`u``G:node`A node in `G`.
`v``G:node`An outneighbor of `u` in `G`.

Explanation

`outneighbor` can be used to get the set of outbound neighbors for each node in `G`. If `G` is undirected, `neighbor` and `outneighbor` are identical.

Examples

``````def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:outneighbor
//output> (11, 12)
//        (12, 13)
//        (12, 14)
//        (13, 13)

def output = my_graphlib:outneighbor
//output> 13
//        14

def output = my_graphlib:outneighbor(12, 13)
//output> ()  // true``````