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:

1. neighbor
2. inneighbor
3. outneighbor

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.
• Find all neighbors of a node.
• Find common neighbors of two nodes.

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 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 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.

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.