Compute.distance()#

relationalai.std.graphs
#Compute.distance(node1: Producer, node2: Producer) -> Expression

This algorithm computes the shortest path length between two nodes in a graph. Must be called in a rule or query context.

NOTE

Be careful using distance on the entire graph, since for large graphs, this may be infeasible.

Supported Graph Types#

Graph TypeSupportedNotes
UndirectedYes
DirectedYes
WeightedYes
UnweightedYes

Parameters#

NameTypeDescription
node1ProducerA node in the graph.
node2ProducerA node in the graph.

Returns#

Returns an Expression object that produces the shortest path length between node1 and node2 as an integer value.

Example (Unweighted Graphs)#

Use .distance() to compute the shortest path length between two nodes in a graph. You access the .distance() method from a Graph object’s .compute attribute:

#import relationalai as rai
from relationalai.std import alias
from relationalai.std.graphs import Graph

# Create a model named "socialNetwork" with a Person type.
model = rai.Model("socialNetwork")
Person = model.Type("Person")

# Add some people to the model and connect them with a multi-valued `follows` property.
with model.rule():
    alice = Person.add(name="Alice")
    bob = Person.add(name="Bob")
    carol = Person.add(name="Carol")
    daniel = Person.add(name="Daniel")
    alice.follows.add(bob)
    bob.follows.add(carol)
    carol.follows.add(daniel)

# Create a directed graph with Person nodes and edges between followers.
# Note that graphs are directed by default.
# This graph has three edges: one from Alice to Bob, Bob to Carol, and Carol to Daniel.
graph = Graph(model)
graph.Node.extend(Person)
graph.Edge.extend(Person.follows)

# Find the distance between Alice and Daniel.
with model.query() as select:
    dist = graph.compute.distance(Person(name="Alice"), Person(name="Daniel"))
    response = select(alias(dist, "distance"))

print(response.results)
# Output:
#    distance
# 0         3

# Find all nodes at distance at most two from Alice.
with model.query() as select:
    node = Person()
    dist = graph.compute.distance(Person(name="Alice"), node)
    dist <= 2
    response = select(node.name, alias(dist, "distance"))

print(response.results)
# Output:
#     name  distance
# 0  Alice         0
# 1    Bob         1
# 2  Carol         2

Note that the distance between a node and itself is 0.

Example (Weighted Graphs)#

Use .distance() to compute the shortest path length between two nodes in a weighted graph. You access the .distance() method from a Graph object’s .compute attribute:

#import relationalai as rai
from relationalai.std import alias
from relationalai.std.graphs import Graph

# Create a model named "socialNetwork" with Person and Friendship types.
model = rai.Model("socialNetwork")
Person = model.Type("Person")
Friendship = model.Type("Friendship")

# Add some people to the model and connect them with the Friendship type.
with model.rule():
    alice = Person.add(name="Alice")
    bob = Person.add(name="Bob")
    carol = Person.add(name="Carol")
    daniel = Person.add(name="Daniel")
    Friendship.add(person1=alice, person2=bob, strength=1.0)
    Friendship.add(person1=bob, person2=carol, strength=0.5)
    Friendship.add(person1=carol, person2=daniel, strength=0.75)

# Create a directed graph with Person nodes and edges between friends.
# Note that graphs are directed by default.
# This graph has three edges: one from Alice to Bob, Bob to Carol, and Carol to Daniel.
# The edges are weighted by the strength of each friendship.
graph = Graph(model, weighted=True)
graph.Node.extend(Person)
with model.rule():
    friendship = Friendship()
    graph.Edge.add(friendship.person1, friendship.person2, weight=friendship.strength)

# Find the weighted distance between Alice and Daniel.
with model.query() as select:
    dist = graph.compute.distance(Person(name="Alice"), Person(name="Daniel"))
    response = select(alias(dist, "distance"))

print(response.results)
# Output:
#    distance
# 0      2.25

# Find all nodes with weighted distance at most two from Alice.
with model.query() as select:
    node = Person()
    dist = graph.compute.distance(Person(name="Alice"), node)
    dist <= 2.0
    response = select(node.name, alias(dist, "distance"))

print(response.results)
# Output:
#     name  distance
# 0  Alice       0.0
# 1    Bob       1.0
# 2  Carol       1.5

See Also#