:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.
Python ab-testingai-analyticsanalyticscdpdata-warehouseexperimentsfeature-flagsjavascriptproduct-analyticspythonreactsession-replaysurveystypescriptweb-analytics
"""In-memory DAG graph traversal utilities.
Loads edges once and computes upstream/downstream relationships in Python
instead of running recursive DB queries per node.
"""
from collections import defaultdict
from uuid import UUID
from django.db.models import Q
from products.data_modeling.backend.logic.graph_traversal import reachable
from products.data_modeling.backend.models.edge import Edge
from products.data_modeling.backend.models.node import NodeType
class Graph:
"""In-memory representation of a DAG's edge structure.
Loads all edges for the given scope in a single query, then supports
O(V+E) traversal for upstream/downstream lookups.
"""
def __init__(
self,
team_id: int,
exclude_table_sources: bool = True,
exclude_table_targets: bool = True,
dag_id: UUID | str | None = None,
hidden_types: frozenset[str] = frozenset(),
):
"""Load edges and build adjacency maps.
Args:
team_id: filter edges to this team
dag_id: when set, load only this DAG's edges instead of every edge for the team
exclude_table_sources: skip edges whose source is a TABLE node (for upstream counts)
exclude_table_targets: skip edges whose target is a TABLE node (for downstream counts)
hidden_types: node types the reader may not see, dropped from both sides so a count
never reports a node the same reader's node list omits
"""
qs = Edge.objects.filter(team_id=team_id).exclude(
Q(source__saved_query__deleted=True) | Q(target__saved_query__deleted=True)
)
if dag_id is not None:
qs = qs.filter(dag_id=dag_id)
# Fetch edges with source/target types in a single query
edge_rows = list(
qs.select_related("source", "target").values_list("source_id", "target_id", "source__type", "target__type")
)
# Build separate adjacency maps for upstream (excluding table sources)
# and downstream (excluding table targets) to match the old behavior
self._upstream_adj: dict[str, set[str]] = defaultdict(set) # target -> sources
self._downstream_adj: dict[str, set[str]] = defaultdict(set) # source -> targets
for source_id, target_id, source_type, target_type in edge_rows:
if source_type in hidden_types or target_type in hidden_types:
continue
s = str(source_id)
t = str(target_id)
if not exclude_table_sources or source_type != NodeType.TABLE:
self._upstream_adj[t].add(s)
if not exclude_table_targets or target_type != NodeType.TABLE:
self._downstream_adj[s].add(t)
def get_upstream(self, node_id: str | UUID) -> set[str]:
"""Get all upstream (ancestor) node IDs, excluding TABLE nodes."""
return reachable(str(node_id), self._upstream_adj)
def get_downstream(self, node_id: str | UUID) -> set[str]:
"""Get all downstream (descendant) node IDs, excluding TABLE nodes."""
return reachable(str(node_id), self._downstream_adj)
def get_upstream_count(self, node_id: str | UUID) -> int:
return len(self.get_upstream(node_id))
def get_downstream_count(self, node_id: str | UUID) -> int:
return len(self.get_downstream(node_id))
def batch_counts(self, node_ids: list[str]) -> dict[str, tuple[int, int]]:
"""Compute (upstream_count, downstream_count) for a batch of nodes.
Returns a dict of node_id -> (upstream_count, downstream_count).
"""
result: dict[str, tuple[int, int]] = {}
for nid in node_ids:
key = str(nid)
result[key] = (self.get_upstream_count(key), self.get_downstream_count(key))
return result