Compute.diameter_range() Preview #

relationalai.std.graphs

#Compute.diameter_range() -> tuple[Expression, Expression]

Compute lower and upper bounds for the maximum shortest-path distance between any two path-connected pairs of nodes. Edge weights are ignored in weighted graphs. If the graph is disconnected, the upper and lower bounds of the connected component with the most nodes is returned. Must be called in a rule or query context.

INFO

If the graph is disconnected, the diameter is mathematically defined to be infinity. Nevertheless, this information doesn’t tell you much about the graph other than the fact that it is disconnected. You can find out whether a graph is connected using .is_connected().

DANGER

For directed graphs that are not strongly connected (i.e., some node pairs are not mutually reachable), the classical graph-theoretic definition of diameter is either undefined or infinite. This function computes the maximum shortest path length among all reachable node pairs instead, which may not match other definitions of diameter used in the literature.

Supported Graph Types#

Graph Type	Supported	Notes
Undirected	Yes
Directed	Yes
Weighted	Yes	Weights are ignored.
Unweighted	Yes

Returns#

Returns a tuple of two Expression objects that produce the lower and upper bounds for the diameter of the graph. In the case of directed graphs, these bounds apply only to pairs of nodes where a path exists from one to the other.

The diameter range is computed by selecting a subset of highest degree nodes and, for each node, finding the length of the longest shortest path from that node to the rest of the graph. The minimum and maximum of these lengths are returned as the lower and upper bounds of the diameter, respectively.

Example#

Use .diameter_range() to compute the range of possible diameters in a graph. You access the .diameter_range() 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")
    alice.follows.add(bob)
    bob.follows.add(carol)

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

# Compute the diameter range of the graph.
with model.query() as select:
    diam_min, diam_max = graph.compute.diameter_range()
    response = select(alias(diam_min, "min"), alias(diam_max, "max"))

print(response.results)
# Output:
#    min  max
# 0    2    2

In cases like this where the lower and upper bounds are the same, the diameter of the graph is known exactly. This may not always be the case, especially for larger and more complex graphs.