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

# Graph Library: Neighbors

## Goal

This guide demonstrates how to use the Graph Library’s neighbor relations and perform common operations such as finding all the neighbors of a node or finding common neighbors of two nodes.

## Introduction

The Graph Library implements several relations for finding the neighbors of nodes in undirected graphs and the inneighbors and outneighbors of nodes in directed graphs. These relations are described in detail in the Neighbor Relations section.

Examples of using these relations, as well as other common operations involving neighbors of nodes, are described in the Common Scenarios section.

## Neighbor Relations

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

The `neighbor` relation is typically used with undirected graphs, whereas `inneighbor` and `outneighbor` are primarily used with directed graphs. For undirected graphs, both `inneighbor` and `outneighbor` are aliases for `neighbor`.

### `neighbor`

Two nodes `u` and `v` are neighbors if any of the edges `(u, v)` or `(v, u)` exist in the graph. `neighbor` is a binary relation that maps nodes in a graph to their neighbors:

``````// read query

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

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

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

The output contains three tuples. The tuple `(1, 2)` indicates that `2` is a neighbor of `1`. Since `my_graph` is undirected, `1` is also a neighbor of `2`, which is why the tuple `(2, 1)` is included in the output. Node `2` is a neighbor of itself since `my_graph:edge` contains the loop `(2, 2)`.

The relation `neighbor` is primarily used with undirected graphs, but is also compatible with directed graphs. When used on a directed graph, `neighbor` maps nodes to their inneighbors and outneighbors. In essence, `neighbor` treats directed graphs as if they were undirected:

``````// read query

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

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

// Display the contents of my_graphlib:neighbor
def output = my_graphlib:neighbor``````

The output is the same as in the preceding example for an undirected graph constructed from the same edge set.

### `inneighbor`

In a directed graph, a node `v` is said to be an inneighbor of node `u` if the edge `(v, u)` exists in the graph. The edge `(v, u)` is thought of as pointing out of `v` and in to `u`. `inneighbor` is a binary relation that maps nodes in a graph to their inneighbors:

``````// read query

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

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

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

The relation `my_graph` is directed and has the edge `(1, 2)`, so `1` is an inneighbor of `2` and the output contains `(2, 1)`. Node `2` is an inneighbor of itself because `my_graph:edge` contains the loop `(2, 2)`. Note that there are no edges in `my_graph` pointing in to node `1`. This is why the output has no tuples starting with `1`.

### `outneighbor`

In a directed graph, a node `v` is said to be an outneighbor of node `u` if the edge `(u, v)` exists in the graph. The edge `(u, v)` is thought of as pointing out of `u` and in to `v`. `outneighbor` is a binary relation that maps nodes in a graph to their outneighbors:

``````// 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 the contents of my_graphlib:outneighbor.
def output = my_graphlib:outneighbor``````

The relation `my_graph` is directed and has the edge `(1, 2)`, so `2` is an outneighbor of `1` and the output contains the tuple `(1, 2)`. Node `2` is an outneighbor of itself because `my_graph:edge` contains the loop `(2, 2)`. Note that there are no edges in `my_graph` pointing out of node `3`. This is why the output has no tuples starting with `3`.

## Common Scenarios

In this section, you’ll learn how to perform common operations with neighbor relations, including how to:

### Test Whether Nodes Are Neighbors

To test whether two nodes are neighbors, apply the `neighbor` relation to the nodes:

``````// 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]

// Test whether 2 is a neighbor of 1, 3 is a neighbor of 1, and 2 is a
// neighbor of itself. The output relation has_neighbor contains
// pairs (u, v) from test_neighbor if u and v are neighbors in my_graph.
def test_neighbor = {(1, 2); (1, 3); (2, 2)}
def output:has_neighbor(u, v) {
test_neighbor(u, v)
and my_graphlib:neighbor(u, v)
}``````

Node `2` is a neighbor of node `1` so `has_neighbor` contains `(1, 2)`. But there is no edge in the graph between nodes `1` and `3`, so `has_neighbor` does not contain `(1, 3)`. Note that node `2` is a neighbor of itself since `my_graph:edge` contains the loop `(2, 2)`.

🔎

In directed graphs, `neighbor(u, v)` tests whether `v` is any kind of neighbor of `u`: either an inneighbor or an outneighbor. See `neighbor` for details.

In a directed graph, use `inneighbor` or `outneighbor` to test whether a node is an inneighbor or outneighbor of another node.

### Find All Neighbors of a Node

The set of all neighbors of a node is called the node’s neighborhood. To find the neighborhood of a node, partially apply the `neighbor` relation to the node:

``````// read query

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

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

// Display the neighborhood of node 1 by partially applying
// the neighbor relation to the node 1.
def output = my_graphlib:neighbor``````

Node `1` is a neighbor of itself because `my_graph:edge` contains the loop `(1, 1)`, and `2` is a neighbor of `1` because `my_graph:edge` contains the edge `(1, 2)`. But `3` is not a neighbor of `1`, since there is no edge between `1` and `3` in `my_graph:edge`, which is why `3` does not appear in the output.

🔎

In directed graphs, `neighbor[u]` finds the set of nodes that are any kind of neighbor of `u`: either an inneighbor or an outneighbor. See `neighbor` for details.

In a directed graph, partially apply the `inneighbor` or `outneighbor` relations to a node to find the set of all inneighbors and outneighbors 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)}]

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

// Display the set of inneighbors of node 1.
def output:inneighbor_of_1 = my_graphlib:inneighbor

// Display the set of outneighbors of node 1.
def output:outneighbor_of_1 = my_graphlib:outneighbor``````

Node `1` is both an inneighbor and outneighbor of itself since `my_graph:edge` contains the loop `(1, 1)`. Node `2` is an outneighbor of `1` because `my_graph:edge` contains the edge `(1, 2)`, but it is not an inneighbor of `1`, since there is no edge `(2, 1)`. There are no edges between `1` and `3`, so `3` is neither an inneighbor nor an outneighbor of `1`.

### Find Common Neighbors

A node `w` is a common neighbor of nodes `u` and `v` if `w` is a neighbor of both `u` and `v`. Many graph algorithms involve finding the number of or iterating over common neighbors of nodes. To find the set of neighbors common to nodes `u` and `v`, partially apply the `common_neighbor` relation to `u` and `v`:

``````// read query

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

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

// Display the set of neighbors common to nodes 1 and 3.
def output = my_graphlib:common_neighbor[1, 3]``````

You can use `common_neighbor` to test whether a node `w` is a common neighbor of two other nodes `u` and `v` by applying the relation to the triple `(u, v, w)`:

``````// read query

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

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

// Test whether 2 is a common neighbor of 1 and 3 and whether 3 is a common
// neighbor of 1 and 2. The output relation is_common_neighbor contains
// triples (u, v, w) from test_common_neighbor that are also contained
// in common_neighbor.
def test_common_neighbor = {(1, 3, 2); (1, 2, 3)}
def output:is_common_neighbor(u, v, w) {
test_common_neighbor(u, v, w)
and my_graphlib:common_neighbor(u, v, w)
}``````

Note that `is_common_neighbor` does not contain the triple `(1, 2, 3)`, since `3` is not a neighbor of `1`.

🔎

In directed graphs, `common_neighbor` finds nodes that are any kind of neighbor — either an inneighbor or an outneighbor — common to the two nodes to which the relation is applied. See `neighbor` for details.

To find common inneighbors or common outneighbors in a directed graph, you’ll need to write some Rel that directly uses the `inneighbor` or `outneighbor` relations. For instance, the following query finds common inneighbors of two nodes:

``````// read query

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

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

// Compute the common inneighbors of pairs of nodes in my_graph.
// Replace my_graphlib:inneighbor with my_graphlib:outneighbor
// to find common outneighbors instead.
def common_inneighbor(u, v, w) {
my_graphlib:inneighbor(u, w)
and my_graphlib:inneighbor(v, w)
}

// Sample usage:

// Find the common inneighbors of 2 and 3.
def output = common_inneighbor[2, 3]``````

Node `1` is an inneighbor of both node `2` and node `3`, so the output contains `1`.