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[1]
```

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[1]
// Display the set of outneighbors of node 1.
def output:outneighbor_of_1 = my_graphlib:outneighbor[1]
```

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`

.

## See Also

See Degrees to learn about working with degree relations. See the Overview of Graph Algorithms to explore all of the algorithms implemented in Rel’s Graph Library.