Graph Library (graphlib) — Basics

Module: undirected_graph

undirected_graph[E]

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

Parameters

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[12]
//output> ()  // true
 
def output = my_graph:node(11; 12; 13; 14)
//output> ()  // true

See Also

directed_graph.

Module: directed_graph

directed_graph[E]

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

Parameters

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[12]
//output> ()  // true
 
def output = my_graph:node(11; 12; 13; 14)
//output> ()  // true

See Also

undirected_graph.

Module: rel:graphlib

rel:graphlib[G]

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

Parameters

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:

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
num_nodes(n)

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
num_edges(n)

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
neighbor[u]
neighbor(u, v)

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[12]
//output> 11
//        13
//        14
 
def output = my_graphlib:neighbor(12, 11)
//output> ()  // true

inneighbor
inneighbor[u]
inneighbor(u, v)

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[13]
//output> 12
//        13
 
def output = my_graphlib:inneighbor(13, 12)
//output> ()  // true

outneighbor
outneighbor[u]
outneighbor(u, v)

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[12]
//output> 13
//        14
 
def output = my_graphlib:outneighbor(12, 13)
//output> ()  // true