Graph Algorithms

PageRank, connected components, weighted shortest path, and community detection — executed as native C kernels on CSR indexes, exposed via GRAPH_TABLE COLUMNS functions.

Overview

TeideDB ships four graph algorithms as built-in C engine kernels. Key properties:

• All algorithms operate directly on CSR (Compressed Sparse Row) indexes — the same indexes used for MATCH traversals.
• No data copying — algorithms read CSR pointers in-place, avoiding materialization overhead.
• Results compose with full SQL: GROUP BY, ORDER BY, JOIN, subqueries, and window functions all work on algorithm output columns.

PageRank

PAGERANK(graph_name, node_var)

Iterative rank computation using the power-iteration method. Runs 20 iterations with a damping factor of 0.85. Returns an F64 rank per node that sums to approximately 1.0.

SELECT name, rank
FROM GRAPH_TABLE (social
  MATCH (p:Person)
  COLUMNS (p.name AS name, PAGERANK(social, p) AS rank)
)
ORDER BY rank DESC
LIMIT 10;

Connected Components

COMPONENT(graph_name, node_var)
CONNECTED_COMPONENT(graph_name, node_var)

Label-propagation algorithm that runs until convergence. Treats the graph as undirected regardless of edge direction. Returns an I64 component ID per node — nodes in the same connected subgraph share the same ID.

-- Find disconnected subgraphs and their sizes
SELECT component_id, COUNT(*) AS size
FROM GRAPH_TABLE (network
  MATCH (n:Node)
  COLUMNS (COMPONENT(network, n) AS component_id)
)
GROUP BY component_id
ORDER BY size DESC;

Weighted Shortest Path (Dijkstra)

SHORTEST_DISTANCE(graph_name, src_id, dst_id, 'weight_col')

Dijkstra’s algorithm with edge weights read from a property table column. Returns an F64 distance value. The weight column name is passed as a string literal. Used within GRAPH_TABLE COLUMNS:

-- Distance between two cities via weighted road edges
SELECT distance
FROM GRAPH_TABLE (roads
  MATCH (s:City)-[r:Road]->(d:City)
  COLUMNS (SHORTEST_DISTANCE(roads, 1, 42, 'km') AS distance)
)
LIMIT 1;

Alternatively, use CHEAPEST path patterns with a COST expression for shortest-path queries:

-- Cheapest path with edge weight
SELECT src, dst, total_cost
FROM GRAPH_TABLE (roads
  MATCH CHEAPEST (s:City WHERE s.id = 1)-[r:Road]->{1,5}(d:City WHERE d.id = 42)
  COST r.km
  COLUMNS (s.name AS src, d.name AS dst, COST() AS total_cost)
);

Community Detection (Louvain)

COMMUNITY(graph_name, node_var)
LOUVAIN(graph_name, node_var)

Modularity-optimization algorithm (Louvain Phase 1). Treats the graph as undirected. Returns an I64 community ID per node.

-- Find communities in a social network
SELECT community, COUNT(*) AS members
FROM GRAPH_TABLE (social
  MATCH (p:Person)
  COLUMNS (
    p.name AS name,
    COMMUNITY(social, p) AS community
  )
)
GROUP BY community
ORDER BY members DESC;

Local Clustering Coefficient

CLUSTERING_COEFFICIENT(graph_name, node_var)
CLUSTERING_COEFF(graph_name, node_var)

Computes the local clustering coefficient for each node — the fraction of a node’s neighbors that are also connected to each other. Returns an F64 value between 0.0 and 1.0 (1.0 means all neighbors form a clique). Treats the graph as undirected.

-- Find highly clustered nodes (nodes in tight communities)
SELECT name, lcc
FROM GRAPH_TABLE (social
  MATCH (p:Person)
  COLUMNS (p.name AS name, CLUSTERING_COEFFICIENT(social, p) AS lcc)
)
WHERE lcc > 0.5
ORDER BY lcc DESC;

Performance

All algorithms run as C kernels with direct CSR pointer access — no FFI boundary per edge.