Graph Algorithms¶

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

Algorithm Categories¶

Path Finding

Shortest paths, all paths and path analysis.

Path Algorithms
Centrality

PageRank, betweenness, closeness and degree centrality.

Centrality
Community Detection

Louvain, label propagation and connected components.

Community Detection
Link Prediction

Predict missing or future relationships.

Link Prediction
Similarity

Node similarity and graph matching.

Similarity
Graph Metrics

Density, diameter, clustering coefficient.

Graph Metrics

Quick Reference¶

Algorithm	Category	Complexity	Use Case
Shortest Path	Path	O(V + E)	Navigation, routing
PageRank	Centrality	O(V + E)	Ranking, importance
Louvain	Community	O(V log V)	Clustering
Connected Components	Community	O(V + E)	Graph structure
Triangle Count	Metrics	O(E^1.5)	Clustering analysis

Using Algorithms¶

From Python¶

Algorithms are accessed through the db.algorithms() method:

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 shortest path
path = algs.shortest_path(source=1, target=100)
print(f"Path length: {len(path)}")

# Connected components
components = algs.connected_components()
print(f"Found {len(components)} components")

Available Methods¶

The algorithms() object provides these methods:

Traversal:

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

Shortest Paths:

dijkstra(source, target) - Dijkstra's algorithm
shortest_path(source, target) - Generic shortest path
sssp(source, weight_attr) - Single-source shortest paths (weighted)
all_pairs_shortest_path() - All-to-all shortest paths

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:

triangles() - Triangle counting
transitivity() - Global clustering coefficient
minimum_spanning_tree() - MST construction
max_flow(source, sink) - Maximum flow

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

All 22 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

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

Works the same way across all three languages:

GQLCypherSQL/PGQ

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

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

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

Available Procedures¶

Procedure	Category	Output Columns
`grafeo.pagerank()`	Centrality	node_id, score
`grafeo.betweenness_centrality()`	Centrality	node_id, centrality
`grafeo.closeness_centrality()`	Centrality	node_id, centrality
`grafeo.degree_centrality()`	Centrality	node_id, in_degree, out_degree, total_degree
`grafeo.bfs(start)`	Traversal	node_id, depth
`grafeo.dfs(start)`	Traversal	node_id, depth
`grafeo.dijkstra(source)`	Shortest Path	node_id, distance
`grafeo.bellman_ford(source)`	Shortest Path	node_id, distance, has_negative_cycle
`grafeo.sssp(source, weight)`	Shortest Path	node_id, distance
`grafeo.floyd_warshall()`	Shortest Path	source, target, distance
`grafeo.connected_components()`	Components	node_id, component_id
`grafeo.strongly_connected_components()`	Components	node_id, component_id
`grafeo.topological_sort()`	Components	node_id, order
`grafeo.louvain()`	Community	node_id, community_id, modularity
`grafeo.label_propagation()`	Community	node_id, community_id
`grafeo.clustering_coefficient()`	Clustering	node_id, coefficient, triangle_count
`grafeo.kruskal()`	MST	source, target, weight
`grafeo.prim()`	MST	source, target, weight
`grafeo.max_flow(source, sink)`	Flow	source, target, flow, max_flow
`grafeo.min_cost_max_flow(source, sink)`	Flow	source, target, flow, cost, max_flow
`grafeo.articulation_points()`	Structure	node_id
`grafeo.bridges()`	Structure	source, target
`grafeo.k_core()`	Structure	node_id, core_number, max_core

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