⚠

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

Graph Library: Nodes and Edges

Goal

This guide discusses graph nodes and edges in detail. It also demonstrates how to count nodes and edges, test for node and edge membership, and add and remove nodes and edges from a graph.

Introduction

Graphs are comprised of individual elements, called nodes and contained within the graph’s node relation, and edges, which describe relationships between nodes and are contained in the graph’s edge relation. See Graphs: Schema for details.

Nodes

When you create a graph by applying one of the graph constructors to an edge set, the node relation is automatically populated with nodes contained in the edges:

// read query
 
// Construct a directed graph with two nodes and one edge.
def my_graph = directed_graph[{(1, 2)}]
 
// Display the nodes in my_graph.
def output = my_graph:node

Inferring nodes from an edge relation provides a convenient way to create graphs without having to specify both of the node and edge sets.

Data Types

Nodes may have any data type, and graphs may contain nodes with mixed types:

// read query
 
// Construct an undirected graph with two nodes and one edge.
// The nodes have mixed data types: one is a string and the other is an integer.
def my_graph = undirected_graph[{("a", 1)}]
 
// Display the nodes in my_graph.
// Note that the type in the output column is "Mixed."
def output = my_graph:node

💡

For the best performance, use integer nodes. See Performance Tips for more information.

Isolated Nodes

You can include isolated nodes in a graph by first constructing a graph from a binary edge set and then defining a rule that adds the isolated nodes to the node relation:

// read query
 
// Construct a directed graph with two nodes and one edge.
def my_graph = directed_graph[{(1, 2)}]
 
// Add two isolated nodes to the graph.
def my_graph:node = {3; 4}
 
// Display the nodes in my_graph.
def output = my_graph:node

Apply the constructor to an empty edge set to create an edgeless graph:

// read query
 
// Construct an empty directed graph.
def my_graph = directed_graph[{}]
 
// Add two isolated nodes to my_graph:node.
def my_graph:node = {1; 2}
 
// Display the contents of my_graph.
def output = my_graph

Note that there is no edge relation in the output since my_graph has no edges.

Weighted Nodes

The Graph Library does not directly support creating graphs with weighted nodes. However, you can assign weights to nodes if needed by mapping nodes to their weights in a new relation:

// read query
 
// Construct an undirected graph with two nodes and one edge.
def my_graph = undirected_graph[{(1, 2)}]
 
// Map nodes to weights.
def weight = {(1, 0.25); (2, 0.75)}
 
// You can access node weights by partially applying
// the weight relation to a given node.
def output = weight[1]

Note that currently none of the Graph Library’s algorithms are designed to work with weighted graphs.

Edges

When you create a graph by applying one of the graph constructors to an edge set E, the edge relation is populated with edges in E. However, edge sets created by directed_graph and undirected_graph are different from one another.

Directed Edges

Directed edges are tuples (u, v) of nodes in a graph. The edge is said to point from u to v. When visualized, directed edges are drawn as an arrow with the top of the arrow attached to v and the tail attached to u.

A graph created by applying the directed_graph constructor to an edge set E has an edge set identical to E:

// read query
 
// Declare an edge set.
def E = {(1, 2); (2, 3)}
 
// Construct a directed graph with nodes and edges from E.
def my_graph = directed_graph[E]
 
// Display the edges of my_graph.
def output = my_graph:edge

Undirected Edges

Undirected edges do not point from any node towards another. They are modeled as pairs of tuples (u, v) and (v, u), but you only need to supply one of the tuples in the edge set to which undirected_graph is applied:

// read query
 
// Declare an edge set E.
def E = {(1, 2); (2, 3)}
 
// Construct an undirected graph with nodes and edges from E.
def my_graph = undirected_graph[E]
 
// Display the edges in my_graph.
// For each tuple (u, v) in E, both (u, v) and (v, u) are in my_graph:edge.
def output = my_graph:edge

Each tuple (1, 2) and (2, 3) in E is paired with its reverse tuple (2, 1) and (2, 3) in my_graph:edge. More formally, my_graph:edge is the symmetric closure (opens in a new tab) of E.

⚠

The differences between directed and undirected edges have consequences for how edges are counted. See Count Nodes and Edges for more details.

Loops

Graphs in Rel may have loops — that is, edges that start and end at the same node:

// read query
 
// Construct an undirected graph with two nodes and two edges.
// The edge (2, 2) is a loop.
def my_graph = undirected_graph[{(1, 2); (2, 2)}]
 
// Note that the loop (2, 2) is represented by a
// single tuple in my_graph:edge.
def output = my_graph:edge

When a node is involved in a loop in a directed graph, the node is considered both an inneighbor and outneighbor of itself. Loops in an undirected graph contribute 1 to the overall degree of the node to which they are attached.

Weighted Edges

The Graph Library does not directly support creating graphs with weighted edges. However, you can assign weights to edges if needed by declaring a new relation that maps pairs of nodes to the weight of the edge between them:

// read query
 
// Construct an undirected graph with two nodes and one edge.
def my_graph = undirected_graph[{(1, 2); (2, 3)}]
 
// Map edges to weights.
def weight = {(1, 2, 1.25); (2, 3, 1.75)}
 
// You can access edge weights by partially applying
// the weight relation to the nodes in the edge.
def output = weight[1, 2]

Note that currently none of the Graph Library’s algorithms are designed to work with weighted graphs.

Multiedges

The Graph Library does not directly support creating graphs with multiple instances of the same edge. Multiedges may be simulated, however, using an edge weight relation that weights edges by their multiplicity. See Weighted Edges for more information.

Common Scenarios

The following sections explain how to count nodes and edges, test for node and edge membership, and add and remove nodes and edges from a graph.

Count Nodes and Edges

To count the number of nodes and edges in a graph, use the num_nodes and num_edges relations:

// read query
 
// Construct an undirected graph with three nodes and two edges.
def my_undirected_graph = undirected_graph[{(1, 2); (2, 3)}]
 
// Instantiate rel:graphlib on my_undirected_graph.
@inline
def my_graphlib = rel:graphlib[my_undirected_graph]
 
// Display the number of nodes in my_undirected_graph.
def output:number_of_nodes = my_graphlib:num_nodes
 
// Display the number of edges in my_undirected_graph.
def output:number_of_edges = my_graphlib:num_edges

⚠

Always use num_edges to count edges in a graph. This is especially important for undirected graphs, as count may double count edges. See Undirected Graphs for more information.

Test Node and Edge Membership

You test for node and edge membership in a graph the same way that you test set membership for any relation in Rel, by using a relational application:

// read query
 
// Construct a directed graph with three nodes and two edges.
def my_directed_graph = directed_graph[{(1, 2); (2, 3)}]
 
// Test whether or not nodes 1 and 4 are contained in the graph.
// The output relation has_node only contains nodes from test_node
// that are in my_directed_graph:node.
def test_node = {1; 4}
def output:has_node(u) { test_node(u) and my_directed_graph:node(u) }
 
// Test whether or not edges (1, 2) and (3, 2) are in the graph.
// The output relation has_edge only contains edges from test_edge
// that are in my_directed_graph:edge.
def test_edge = {(1, 2); (3, 2)}
def output:has_edge(u, v) { test_edge(u, v) and my_directed_graph:edge(u, v) }

Add Nodes and Edges

There are three ways to add nodes and edges to a graph:

Construct a new graph from the union of the original graph’s edges and a set of new edges. This may be useful when you need to operate on a graph for the purpose of a one-time query or when implementing a custom algorithm.
Add a rule to the graph’s edge set. This can be used to include edges in a graph that are derived from a logical expression instead of directly mapping to tuples in a base relation.
Extend the underlying data from which the graph’s edge set is derived. This happens, for instance, when new CSV data is loaded into an existing base relation.

Create a New Graph

To add nodes or edges to an existing graph, you can construct a new graph from the union of the original graph’s edge set and the set of new edges to be added:

// read query
 
// Construct a directed graph with three nodes and two edges.
def my_directed_graph = directed_graph[{(1, 2); (2, 3)}]
 
// Add the edge (1, 4) to my_directed_graph by constructing a new graph
// whose edge set is the union of my_directed_graph:edge and (1, 4).
def output = directed_graph[{my_directed_graph:edge; (1, 4)}]

⚠

Always use a graph constructor to expand the graph. Directly modifying the graph’s node and edge relations is not recommended.

You can wrap this into a parameterized declaration for a reusable relation that adds edges to any graph:

// read query
 
// Parameterized declaration for a reusable `add_edge` relation.
@inline
def add_edge[G, E] {
    if G:is_directed then
        directed_graph[G:edge; E]
    else
        undirected_graph[G:edge; E]
    end
}
 
 
// Sample usage:
 
// Create an undirected graph with two nodes and one edge.
def my_graph = undirected_graph[{(1, 2)}]
 
// Display the new graph made by adding the edges (1, 3) and (2, 3) to my_graph.
def output = add_edge[my_graph, {(1, 3); (2, 3)}]

Add Edge Rules

You may add nodes and edges by adding or modifying rules for the graph’s edge relation. For example, the following graph is derived from CSV data. Additional edges not contained in the CSV data are added with a new rule.

The source data for the graph is loaded from a CSV string into a base relation called edge_csv:

// write query
 
def edge_csv_string = """
source,target
1,2
2,3
3,4
"""
 
module config
    def data = edge_csv_string
    def schema = {(:source, "int"); (:target, "int")}
end
 
def insert:edge_csv = load_csv[config]

The edge relation and the graph module are persisted to a model file:

// model
 
// Build edges from the CSV file.
def my_edges(source_node, target_node) {
    exists(row_number:
        edge_csv(:source, row_number, source_node)
        and edge_csv(:target, row_number, target_node)
    )
}
 
// Add an edge not in the CSV file to the graph.
def my_edges = (2, 4)
 
// Declare a directed graph from `my_edges`.
def my_graph = directed_graph[my_edges]

Note that my_graph:edge contains the edge (2, 4) even though it is not contained in the CSV data:

// read query
 
def output = my_graph:edge

Extend Underlying Data

When the edge set of a graph is a derived relation, any insertions into relations from which the edges are derived may result in new nodes and edges in the graph.

For example, consider the following graph derived from a base relation containing CSV data. The source data for the graph is loaded from a CSV string into a base relation called edge_csv:

// write query
 
// Insert a base relation with CSV data.
def edge_csv_string = """
source,target
1,2
2,3
"""
 
module config
    def data = edge_csv_string
    def schema = {(:source, "int"); (:target, "int")}
end
 
def insert:edge_csv = load_csv[config]

The edge relation and the graph module are persisted to a model file:

// model
 
def my_edges(source_node, target_node) {
    exists(row:
        edge_csv(:source, row, source_node)
        and edge_csv(:target, row, target_node)
    )
}
 
def my_graph = directed_graph[my_edges]

Currently, my_graph contains three nodes and two edges:

// read query
 
def output = my_graph

When the tuples (:source, 3, 1) and (:target, 3, 3) are inserted into edge_csv, the edge (1, 3) is added to the graph:

// write query
 
def insert:edge_csv = {(:source, 3, 1); (:target, 3, 3)}

// read query
 
def output = my_graph

Typically, you won’t write queries that insert tuples into a base relation. Inserts into base relations usually occur when the database is synced with external data sources.

Remove Nodes and Edges

There are two ways to remove nodes and edges from a graph:

Create a new graph from the set difference of an existing graph’s edges and the set of edges to be removed. This may be useful when you need to operate on a graph for the purpose of a one-time query or when implementing a custom algorithm.
Remove underlying data from which the graph is derived. This may happen, for instance, when a base relation is synced with data from an external source.

Note that you cannot remove nodes and edges by adding rules to the graph’s edge set. Relations are defined by the union of all of their rules. When a new rule is added, the relation either stays the same or includes new tuples. See the Rel Primer for details.

Create a New Graph

To remove edges from a graph, you can create a new graph from the set difference of the existing graph’s edge set and any edges you want to remove using the Standard Library’s diff relation:

// read query
 
// Construct a directed graph with three nodes and two edges.
def my_graph = directed_graph[{(1, 2); (2, 3)}]
 
// Remove the edge (2, 3) from my_graph by constructing a new graph
// whose edge set is the set difference of my_graph:edge and (2, 3).
def output = directed_graph[diff[{my_graph:edge, (2, 3)}]]

You can wrap this into a parameterized declaration for a reusable relation that removes edges from any graph:

// read query
 
// Parameterized declaration for a reusable `remove_edges` relation.
@inline
def remove_edges[G, E] {
    if G:is_directed then
        directed_graph[diff[G:edge, E]]
    else
        undirected_graph[diff[G:edge, E]]
    end
}
 
 
// Sample usage:
 
// Construct a directed graph with three nodes and two edges.
def my_graph = directed_graph[{(1, 2); (2, 3)}]
 
// Display the new graph made by removing the edge (2, 3) to my_graph.
def output = remove_edges[my_graph, (2, 3)]

When all edges involving a node are removed from a graph, that node is also removed. This is why the node 3 is missing in new_graph:node in the preceding examples.

To remove a node from a graph, query the graph for all edges containing that node and then remove those edges:

// read query
 
// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 2); (2, 3); (3, 1)}]
 
// Find all edges containing the node 1.
def node_1_edges(x, y) { my_graph:edge(x, y) and (x = 1 or y = 1) }
 
// Remove the node 1 from my_graph by constructing a new graph
// whose edge set is the set difference of my_graph:edge and node_1_edges.
def output = directed_graph[diff[{my_graph:edge, node_1_edges}]]

You can wrap this into a reusable relation:

// read query
 
// Helper relation to find all edges in a graph G containing nodes in a set N.
@inline
def node_edges[G, N](x, y) { G:edge(x, y) and (N(x) or N(y)) }
 
// Parameterized declaration for a reusable `remove_node` relation.
@inline
def remove_node[G, N] {
    if G:is_directed then
        directed_graph[diff[G:edge, node_edges[G, N]]]
    else
        undirected_graph[diff[G:edge, node_edges[G, N]]]
    end
}
 
 
// Sample usage:
 
// Construct a directed_graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 2); (2, 3); (3, 1)}]
 
// Display the new graph made by removing the node 1 from my_graph.
def output = remove_node[my_graph, 1]

Remove Underlying Data

When the edge set of a graph is a derived relation, any deletions from relations from which the edges are derived may result in removing nodes and edges from the graph.

For example, consider the following graph derived from a base relation containing CSV-style data:

// write query
 
// Insert CSV-style data into a base relation call edge_csv.
def insert:edge_csv = {
    (:source, 1, 1);
    (:source, 2, 2);
    (:target, 1, 2);
    (:target, 2, 3)
}

The edge relation and the graph module are installed in a model file:

// model
 
// Build an edge set from the CSV data.
def my_edges(source_node, target_node) {
    exists(row:
      edge_csv(:source, row, source_node)
      and edge_csv(:target, row, target_node)
  )
}
 
// Construct a directed graph from my_edges.
def my_graph = directed_graph[my_edges]

Currently, my_graph contains three nodes and two edges:

// read query
 
def output = my_graph

When the tuples (:source, 2, 1) and (:target, 2, 2) are deleted from edge_csv, the node 1 and the edge (1, 2) are removed from the graph:

// write query
 
def delete:edge_csv = {(:source, 1, 1); (:target, 1, 2)}

// read query
 
def output = my_graph

Typically, you won’t write queries that delete tuples from a base relation. Deletes from base relations usually occur when the database is synced with external data sources.

Graph Library: Nodes and Edges

Goal

Introduction

Nodes

Data Types

Isolated Nodes

Weighted Nodes

Edges

Directed Edges

Undirected Edges

Loops

Weighted Edges

Multiedges

Common Scenarios

Count Nodes and Edges

Test Node and Edge Membership

Add Nodes and Edges

Create a New Graph

Add Edge Rules

Extend Underlying Data

Remove Nodes and Edges

Create a New Graph

Remove Underlying Data

See Also