Graph Algorithms¶

Grafeo includes a library of built-in graph algorithms for common analysis tasks, accessible via the db.algorithms property.

Algorithm Categories¶

Quick Reference¶

Using Algorithms¶

From Python¶

Algorithms are accessed through the db.algorithms property:

import grafeo

db = grafeo.GrafeoDB()

# Get the algorithms interface
algs = db.algorithms

# Run PageRank
scores = algs.pagerank()
for node_id, score in scores.items():
    print(f"Node {node_id}: {score:.4f}")

# Find a shortest path: (distance, path), or None when 100 is unreachable.
# Without a weight, the distance is the number of hops.
found = algs.dijkstra(1, target=100)
if found is not None:
    distance, path = found
    print(f"Distance {distance}: {path}")

# Connected components
print(f"Found {algs.connected_component_count()} components")

Available Methods¶

The db.algorithms object provides these methods:

Traversal:

• bfs(start) - Breadth-first search
• dfs(start) - Depth-first search

Shortest Paths:

• dijkstra(source) - Dijkstra's algorithm: the distance to every reachable node
• dijkstra(source, target=...) - One shortest path: (distance, path), or None when the target is unreachable
• sssp(source, weight_attr) - Single-source shortest paths (weighted)
• floyd_warshall() - All-pairs shortest distances (distances, not paths): O(n^3) time, O(n^2) memory

Centrality:

• pagerank() - PageRank algorithm
• betweenness_centrality() - Betweenness centrality
• closeness_centrality() - Closeness centrality
• eigenvector_centrality() - Eigenvector centrality
• degree_centrality() - Degree centrality

Community Detection:

• connected_components() - Find connected components
• strongly_connected_components() - Find SCCs
• louvain() - Louvain community detection
• label_propagation() - Label propagation

Structure:

• total_triangles() - Triangle counting: each triangle once
• triangle_count() - The triangles each node is in
• transitivity() - Global clustering coefficient
• ktruss(k=None) - K-truss decomposition (dense subgraph discovery)
• subgraph_isomorphism_count(pattern_edges, pattern_nodes) - Count non-induced subgraph isomorphisms of a pattern
• kruskal() and prim() - Minimum spanning tree (forest) construction
• max_flow(source, sink) - Maximum flow

From Query Languages (GQL, Cypher, SQL/PGQ)¶

All algorithms are available via CALL statements in any supported query language:

-- Run PageRank with default parameters
CALL grafeo.pagerank()

-- Run PageRank with custom parameters
CALL grafeo.pagerank({damping: 0.85, max_iterations: 20})

-- Select specific columns with YIELD
CALL grafeo.pagerank() YIELD node_id, score

-- Alias output columns
CALL grafeo.pagerank() YIELD node_id AS id, score AS rank

-- Ignore edge direction: each pair of connected nodes counts once
CALL grafeo.pagerank({directed: false})

-- Run on a projection only (CREATE PROJECTION or create_projection())
CALL grafeo.pagerank({projection: 'people'})

-- List all available procedures
CALL grafeo.procedures()

grafeo.procedures() lists each procedure's name, description, parameters and output_columns, whether it writes the graph (writes, a BOOLEAN, refused on a read-only session) and what it reaches outside the database (external_access: 'none', 'reads' or 'writes', refused on a session without external access).

A CALL reads the graph the session selects (USE GRAPH, or set_graph() in Python), unless its projection argument names a projection.

Works the same way across all three languages:

result = db.execute("CALL grafeo.pagerank()")

result = db.execute_cypher("CALL grafeo.pagerank()")

result = db.execute_sql("CALL grafeo.pagerank()")

Available Procedures¶

grafeo.bfs reports each reached node's distance from the start as depth. grafeo.dfs reports its depth in the DFS tree (0 for the start, which can be more than the distance), and its positions in the order DFS reaches the nodes (discovery, pre-order) and finishes them (finish, post-order).

Arguments are constants: literals, parameters (CALL grafeo.bfs($start)) and expressions of them. An argument that reads a row variable, or a value of the wrong type for its parameter, is an error, and so is a map key that names no parameter ({dampingg: 0.5}; projection is taken by every procedure) or a positional argument past the last parameter. The columns follow the arguments: dijkstra with a target gives the one path, kcore with a k the members of that core.

Determinism¶

The same graph, loaded in the same order, gives bit-identical results with the same Grafeo version, in any process, on any platform and with any number of threads:

• Results come in node-id order: CALL rows (edge results by source, then target), the dicts and lists of db.algorithms (the nodes of each component too), and the lists the Rust functions return (flow edges by source, then target). Results whose order is the answer (paths, BFS and DFS order, topological order, spanning tree edges) keep their own order.
• The flow procedures give one row per edge that carries flow: two parallel edges are two rows, each with its own capacity and cost.
• grafeo.topological_sort gives the smallest order by node id: of the nodes whose predecessors are all placed, the one with the smallest id comes next.
• Ties are broken by node id. Louvain and label propagation visit nodes in node-id order, a node that gains equally from several communities joins the one with the smallest index, and communities are numbered 0, 1, 2, ... in order of their smallest node id.
• Floating-point sums run in a fixed order, and averages over many nodes (the clustering coefficient) use compensated summation, so the parallel and the sequential paths agree.

Loaded in a different order, the results that do not depend on node ids stay identical: core numbers, degrees, triangle counts, and connected components and articulation points as sets. PageRank agrees up to rounding, and Louvain and label propagation can find a different partition, since they visit nodes in node-id order.

Results independent of the load order: key=¶

In Python, the methods of db.algorithms that return a value per node, and articulation_points() and kcore(), take key=: a node property every node in scope holds, each with its own value (an id from outside the database). The result is then keyed by that value instead of the node id, in key order:

scores = db.algorithms.pagerank(directed=False, key="id")  # {"src/main.py": 0.12, ...}
communities = db.algorithms.louvain(key="id")["communities"]

PageRank, Louvain and label propagation also run in key order: every sum, visit, tie and community number follows the keys instead of the node ids. Their results are then bit-identical for the same graph whatever order its nodes and edges were loaded in. With keys that sort like the node ids, the results equal those without a key. The other methods (degree, betweenness and closeness centrality, connected components, triangle counts, the clustering coefficients, k-core, articulation points) only change their keys: betweenness and closeness still sum in node-id order.

Every node in scope needs a non-null value of the key, and no two nodes can share one: a node without it, or two nodes whose values are equal (1 and 1.0 too), raise GrafeoError before the algorithm runs. Keys of different types are allowed; they order as ORDER BY orders them. The values must also work as Python dict keys: strings, numbers, booleans, bytes, dates, times and datetimes do. A list, a map, a vector or a duration raises GrafeoError, and so do two values Python treats as the same key, such as True and 1, or two times within the same microsecond (Python times hold microseconds). Ordering the nodes costs one read of the key per node and a sort, about 1.5 ms for 9,000 nodes.

When a release changes an algorithm's results, its CHANGELOG lists the change under "Result changes".

NetworkX Integration¶

For additional algorithms, use the NetworkX adapter:

# Convert to NetworkX graph
nx_adapter = db.as_networkx(directed=True)
nx_graph = nx_adapter.to_networkx()

# Use any NetworkX algorithm
import networkx as nx
centrality = nx.eigenvector_centrality(nx_graph)

Performance Considerations¶

• Graph Size - Large graphs may require more memory
• Iterations - More iterations = better accuracy, longer runtime
• Parallelism - Many algorithms support parallel execution
• Caching - Results can be cached for repeated queries