โ

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

# Graph Library: Degrees

## Goal

This guide demonstrates how to use the Graph Libraryโs degree relations and perform common operations such as computing the degree of a node, computing the degree sequence of a graph, and finding the minimum, maximum, and average degrees of a graph.

## Introduction

Numerous graph algorithms depend on the degrees of nodes in a graph. The Graph Library implements several relations for finding the degrees of nodes in undirected graphs and the indegrees and outdegrees of nodes in directed graphs. These relations are described in detail in the Degree Relations section.

Additionally, the Graph Library provides several relations for computing degree statistics and finding the degree sequence of a graph. Examples of using these relations, as well as other common operations involving degrees, are described in the Common Scenarios section.

## Degree Relations

The Graph Library provides three relations for finding the neighbors of nodes in a graph.:

The `degree` relation is primarily used with undirected graphs, while the `indegree` and `outdegree` relations are typically used with directed graphs. In undirected graphs, `indegree` and `outdegree` are both aliases for `degree`.

### `degree`

The degree of a node is the number of neighbors it has in the graph. `degree` is a binary relation that maps nodes in a graph to their degree:

``````// read query

// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 1); (1, 2); (2, 3)}]

// Add an isolated node to the graph.
def my_graph:node = 4

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the contents of my_graphlib:degree.
def output = my_graphlib:degree``````

Node `1` is a neighbor of itself, since `my_graph:edge` contains the loop `(1, 1)`. Node `1` is also a neighbor of `2`, and therefore has degree two. Note that the degree of an isolated node is zero, since it has no neighbors.

In directed graphs, `degree` computes the total degree of the node, that is, the sum of the `indegree` and `outdegree` of the node:

``````// read query

// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 1); (1, 2); (2, 3)}]

// Add an isolated node to the graph.
def my_graph:node = 4

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the contents of my_graphlib:degree.
def output = my_graphlib:degree``````

Node `1` is an inneighbor and outneighbor of itself, and node `2` is also an outneighbor of `1`. So, `1` has indegree one and outdegree two. The total degree of node `1`, then, is three, which is why `(1, 3)` appears in the output.

### `indegree`

The indegree of a node in a directed graph is the number of inneighbors of the node. `indegree` is a binary relation that maps nodes to their indegree:

``````// read query

// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 1); (1, 2); (3, 2)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the contents of my_graphlib:degree.
def output = my_graphlib:indegree``````

Node `1` has one inneighbor โ itself โ so its indegree is one. Both nodes `1` and `3` are inneighbors of `2`, so node `2` has indegree two. Node `3` has no inneighbors, so its indegree is zero.

### `outdegree`

The outdegree of a node in a directed graph is the number of outneighbors of the node. `outdegree` is a binary relation that maps nodes to their outdegree:

``````// read query

// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 1); (1, 2); (3, 2)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the contents of my_graphlib:degree.
def output = my_graphlib:outdegree``````

Node `1` has two outneighbors โ itself and node `2` โ so its outdegree is two. Node `2` is an outneighbor of node `3`, so the outdegree of `3` is one. But, node `2` has no outneighbors so its outdegree is zero.

## Common Scenarios

In this section, youโll learn how to perform common operations with degree relations, including how to:

### Compute the Degree of a Node

To compute the degree of a node, partially apply the `degree` relation to the node:

``````// read query

// Construct an undirected graph with two nodes and two edges.
def my_graph = undirected_graph[{(1, 1); (1, 2)}]

// Instantiate rel:graphlib on my_undirected_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the degree of node 1.
def output = my_graphlib:degree[1]``````

Node `1` is a neighbor of itself because `my_graph:edge` contains the loop `(1, 1)`. Node `1` also a neighbor of `2` and therefore has degree two.

In directed graphs, `degree` computes the total degree, that is, the sum of the indegree and outdegree of a node:

``````// read query

// Construct a directed graph with two nodes and two edges.
def my_graph = directed_graph[{(1, 1); (1, 2)}]

// Instantiate rel:graphlib on my_undirected_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the degree of node 1.
def output = my_graphlib:degree[1]``````

Node `1` has degree three since it has indegree one and outdegree two. See `degree` for more information.

๐

To compute the indegree or outdegree of a node in a directed graph, use `indegree` or `outdegree`.

### Find All Nodes With a Degree

To find all nodes in a graph with a given degree, you can write some Rel that selects nodes from the first column of `degree` that have the degree you are seeking in the second column:

``````// read query

// Construct an undirected graph with three nodes and two edges.
def my_graph = undirected_graph[{(1, 2); (2, 3)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display all nodes with degree 1.
def output(node) { my_graphlib:degree(node, 1) }``````

Both nodes `1` and `3` have degree one, so they are shown in the output. Node `2` has degree two, so it is not included.

๐

To find all nodes with a given indegree or outdegree in a directed graph, use `indegree` or `outdegree`.

You can wrap this into a reusable relation that can be loaded into a model and used to find nodes of any degree in a graph.

``````// read query

// Find all nodes of degree k in a Degree relation.
// Degree may be one of degree, indegree, or outdegree, for example.
@outline
def degree_k_node(Degree, k in Int, node) { Degree(node, k) }

// Sample usage:

// Construct an undirected graph.
def my_graph = undirected_graph[{(1, 2); (2, 3)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display all nodes in my_graph with degree 2.
def output:degree_two = degree_k_node[my_graphlib:degree, 2]

// Display all nodes with degree 0.
// Note that there are no nodes with degree 0,
// so the degree_zero relation is not displayed in the output.
def output:degree_zero = degree_k_node[my_graphlib:degree, 0]``````

The relation `degree_k_node` uses the `@outline` annotation to support the higher-order `Degree` parameter.

### Compute the Degree Sequence

The degree sequence of a graph lists the degrees of each node in the graph ordered from largest to smallest. In Rel, sequences are modeled as relations containing tuples of the form `(index, value)`, where `index` represents the position of `value` in the sequence.

To compute the degree sequence of a graph, use the `degree_sequence` relation:

``````// read query

// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]

// Add one isolated node to my_graph.
def my_graph:node = 4

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the degree sequence of my_graph.
def output = my_graphlib:degree_sequence``````

The result of `degree_sequence` contains four tuples: one for each node in `my_graph`. The tuple `(1, 3)` indicates that `3` is the largest degree in the graph, since it has index `1`. There are two nodes with degree `1` represented by the tuples `(2, 1)` and `(3, 1)`. The single isolated node in the graph is represented by the tuple `(4, 0)`. Since `4` is the largest index in the sequence, `0` is the smallest degree in the graph.

๐

To find the sequence of indegrees and outdegrees in directed graphs, use `indegree_sequence` or `outdegree_sequence`.

In directed graphs, `degree_sequence` results in the sequence of total degrees of the graph โ that is, the sum of the indegree and outdegree of each node:

``````// read query

// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 2); (2, 2); (2, 3)}]

// Add one isolated node to my_graph.
def my_graph:node = 4

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the degree sequence of my_graph.
def output = my_graphlib:degree_sequence``````

See `degree` for more information on how degrees are computed in directed graphs.

### Find the Min, Max, and Average Degrees

To find the minimum, maximum, and average degrees of a graph, use the `min_degree`, `max_degree`, and `average_degree` relations:

``````// read query

// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the minimum, maximum, and average degree of my_graph.
def output:min = my_graphlib:min_degree
def output:max = my_graphlib:max_degree
def output:avg = my_graphlib:average_degree``````

To find the minimum, maximum, and average indegree or outdegree of the graph, append `_indegree` or `_outdegree` to one of `min`, `max`, or `average`. For instance, `min_indegree` for the minmum indegree.

### View Degree Statistics

You can view a summary of all degree statistics of a graph using the `degree_statistics` relation:

``````// read query

// Construct a directed graph with three nodes and three edges.
def my_graph = directed_graph[{(1, 2); (2, 2); (2, 3)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display a summary of degree statistics.
def output = my_graphlib:degree_statistics``````

The `degree_statistics` relation is compatible with both directed and undirected graphs.

### Plot a Degree Histogram

The `degree_histogram` relation counts the number of nodes with each degree in the graph and contains tuples of the form `(degree, node_count)`:

``````// read query

// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the contents of degree_histogram.
def output = my_graphlib:degree_histogram``````

The tuple `(1, 2)` in the output indicates that there are two nodes with degree `1`. You can see that nodes `1` and `3` both have degree `1`. Node `2` is the only node with degree `3`, which is why `(3, 1)` also appears in the output.

๐

To count the number of nodes with a given indegree or outdegree in directed graphs, use the `indegree_histogram` and `outdegree_histogram` relations.

In the next example, the degree histogram is plotted using the `vegalite:bar` relation. The graph is loaded from a CSV file hosted on Azure. See Create a Graph From a CSV File for details on loading graphs from a CSV file. The CSV data, edge set, and instantiated graph and library modules are loaded into a model:

``````// model

// Declare a configuration module for the load_csv relation
// containing the path to the CSV file on Azure
// and the schema for the columns.
module config
def path = "https://raidocs.blob.core.windows.net/datasets/power-grid/opsahl-powergrid.csv"
def schema = (:node_from, "int"); (:node_to, "int")
end

// Load the CSV data into a relation called my_graph_csv.

// Build an edge set from the CSV data.
def my_edge(node1 in Int, node2 in Int) {
exists(row_num:
my_graph_csv(:node_from, row_num, node1)
and my_graph_csv(:node_to, row_num, node2)
)
}

// Create an unidirected graph with edges from my_edge.
def my_graph = undirected_graph[my_edge]

// Instantiate the graph library on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]``````

The histogram is built by organizing the data in `degree_histogram` into a module that can be provided to the `:data` parameter of the `vegalite:bar` relation:

``````// read query

// Count the number of nodes for each degree in my_graph.
def degree_hist = my_graphlib:degree_histogram

// Preare the data for visualization.
module data
def degree = d for d in first[degree_hist]
def node_count = degree_hist
end

// Create a histogram using vegalite:bar.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values),
// and :node_count is selected as the source for the height of each bar.
def histogram = vegalite:bar[:degree, :node_count, {(:data, data)}]

// Display the histogram.
def output = vegalite:plot[histogram]``````

Note that you may plot the indegree or outdegree histograms of directed graphs by using `indegree` or `outdegree` for the data instead of `degree`.

Alternatively, you may use `my_graphlib:degree` as the data for the chart and use Vega-Lite to do the aggregation:

``````// read query

// Prepare the data for visualization.
def data:degree = my_graphlib:degree

// Build a histogram using vegalite:bar.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values).
// The height of each bar is determined by aggregating all of the
// degree values by count.
def histogram = vegalite:bar[
:degree,
{(:aggregate, "count")},
{(:data, data)}
]

// Display the histogram.
def output = vegalite:plot[histogram]``````

In the preceding version of the plot, the Vega-Lite Library performs the aggregation, not the Graph Library. This has some advantages. For example, you may specify custom bin sizes. The following query displays the same data as the preceding histogram but grouped into bins with step size five. The bars are also displayed on a log scale:

``````// read query

// Prepare the data for visualization.
def data:degree = my_graphlib:degree

// Build a binned histogram using vegalite:bar.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values)
// with bins of step size 5. The height of each bar is determined
// by aggregating all of the degree values by count
// and is computed on a log scale.
def binned_histogram = vegalite:bar[
{:degree; (:bin, {(:step, 5)})},
{(:aggregate, "count"); (:scale, {(:type, "log")})},
{(:data, data)}
]

// Display the binned histogram.
def output = vegalite:plot[binned_histogram]``````

For large graphs, it may be more performant to use `degree_histogram` rather than Vega-Lite to perform the aggregation. See Data Visualization: Vega-Lite for more information on plotting in Rel.

### Plot the Degree Distribution

The `degree_distribution` relation computes the proportion of nodes that have a given degree to the total number of nodes in the graph:

``````// read query

// Construct an undirected graph with three nodes and three edges.
def my_graph = undirected_graph[{(1, 2); (2, 2); (2, 3)}]

// Instantiate rel:graphlib on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Display the contents of degree_distribution.
def output = my_graphlib:degree_distribution``````

The relation `my_graph` has three nodes: nodes `1` and `3` have degree `1`, and node `2` has degree `3`. The output contains two tuples: one for each of the degrees in the graph. The tuple `(1, 0.6666666666666666)` indicates that two-thirds of the nodes have degree `1`, and `(3, 0.3333333333333333)` indicates that one-third of the nodes have degree `3`.

๐

To compute the distribution of indegrees and outdegrees in directed graphs, use the `indegree_distribution` and `outdegree_distribution` relations.

To plot the distribution as a bar chart, use the `vegalite:bar` relation. The following query loads a graph from a CSV file on Azure and displays a bar chart of the degree distribution:

``````// read query

// Declare a configuration module for the load_csv relation
// containing the path to the CSV file on Azure
// and the schema for the columns.
module config
def path = "https://raidocs.blob.core.windows.net/datasets/power-grid/opsahl-powergrid.csv"
def schema = (:node_from, "int"); (:node_to, "int")
end

// Load the CSV data into a relation called my_graph_csv.

// Build an edge set from the CSV data.
def my_edge(node1 in Int, node2 in Int) {
exists(row_num:
my_graph_csv(:node_from, row_num, node1)
and my_graph_csv(:node_to, row_num, node2)
)
}

// Create an unidirected graph with edges from my_edge.
def my_graph = undirected_graph[my_edge]

// Instantiate the graph library on my_graph.
@inline
def my_graphlib = rel:graphlib[my_graph]

// Compute the degree distribution.
def degree_distribution = my_graphlib:degree_distribution

// Prepare the data for visualization.
module data
def degree = d for d in first[degree_distribution]
def proportion = degree_distribution
end

// Build a bar chart of the degree distribution.
// The data module is provided as data to the chart constructor.
// :degree is selected as the source for the bars (x-values).
// :proportion is selected as the source for the height of the bars.
def distribution_plot = vegalite:bar[:degree, :proportion, {(:data, data)}]

// Display the bar chart.
def output = vegalite:plot[distribution_plot]``````

Note that you may plot the indegree of outdegree distrubtions by using `indegree_distribution` or `outdegree_distribution` for the chart data instead of `degree_distribution`. See Create a Graph From a CSV File and Data Visualization: Vega-Lite for more information on loading graphs and plotting in Rel.