| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Pattern.Graph.Algorithms
Description
Graph algorithms operating on 'GraphQuery v'.
All traversal algorithms accept a 'TraversalWeight v' at the call site,
enabling the same GraphQuery to be used with directed, undirected, or
custom-weighted traversal without any conversion.
Categorical Interpretation
Algorithms are natural transformations over the GraphQuery coalgebra.
They unfold the coalgebra according to a traversal policy (TraversalWeight)
and accumulate results.
Complexity Note
betweennessCentrality uses the Brandes algorithm: O(n·(n+r)·log n).
It calls queryIncidentRels in the inner loop. For large graphs, wrap
the GraphQuery with memoizeIncidentRels before calling this function.
TODO: bulk adjacency — see open question §1 in the feature proposal.
Synopsis
- bfs :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> [Pattern v]
- dfs :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> [Pattern v]
- shortestPath :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> Maybe [Pattern v]
- hasPath :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> Bool
- allPaths :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> [[Pattern v]]
- isNeighbor :: (GraphValue v, Eq (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> Bool
- isConnected :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Bool
- connectedComponents :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> [[Pattern v]]
- topologicalSort :: (GraphValue v, Ord (Id v)) => GraphQuery v -> Maybe [Pattern v]
- hasCycle :: (GraphValue v, Ord (Id v)) => GraphQuery v -> Bool
- minimumSpanningTree :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> [Pattern v]
- degreeCentrality :: (GraphValue v, Ord (Id v)) => GraphQuery v -> Map (Id v) Double
- betweennessCentrality :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Map (Id v) Double
- queryAnnotationsOf :: GraphClassifier extra v -> GraphQuery v -> Pattern v -> [Pattern v]
- queryWalksContaining :: GraphClassifier extra v -> GraphQuery v -> Pattern v -> [Pattern v]
- queryCoMembers :: (GraphValue v, Eq (Id v)) => GraphQuery v -> Pattern v -> Pattern v -> [Pattern v]
Traversal
bfs :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> [Pattern v] Source #
Breadth-first search from a starting node.
Returns all nodes reachable from start in BFS order, including start.
Traversal direction and cost are governed by weight.
dfs :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> [Pattern v] Source #
Depth-first search from a starting node.
Returns all nodes reachable from start in DFS order, including start.
Traversal direction and cost are governed by weight.
Paths
shortestPath :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> Maybe [Pattern v] Source #
hasPath :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> Bool Source #
Return True if a path exists between src and tgt.
allPaths :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> [[Pattern v]] Source #
All simple paths between two nodes (DFS-based, no repeated nodes).
Returns [] if no path exists or the graph is empty.
Warning: exponential in the worst case for dense graphs.
Boolean queries
isNeighbor :: (GraphValue v, Eq (Id v)) => GraphQuery v -> TraversalWeight v -> Pattern v -> Pattern v -> Bool Source #
Return True if a and b are directly connected by a relationship
with finite traversal cost.
isConnected :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Bool Source #
Return True if the graph is connected under the given traversal weight.
An empty graph is considered connected (vacuously true).
Structural
connectedComponents :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> [[Pattern v]] Source #
Find all connected components under the given traversal weight.
Returns a list of node lists, each representing one component.
topologicalSort :: (GraphValue v, Ord (Id v)) => GraphQuery v -> Maybe [Pattern v] Source #
Topological sort using DFS (Kahn-style post-order).
Returns Nothing if the graph contains a cycle.
Operates on the directed structure implied by relationship endpoint order
(source → target), ignoring TraversalWeight.
hasCycle :: (GraphValue v, Ord (Id v)) => GraphQuery v -> Bool Source #
Return True if the graph contains a directed cycle.
Spanning
minimumSpanningTree :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> [Pattern v] Source #
Minimum spanning tree using Kruskal's algorithm.
Returns the list of nodes in the MST (not edges). For a forest (disconnected graph), returns nodes reachable in the minimum spanning forest. Edge weight is the average of forward and backward traversal costs.
Centrality
degreeCentrality :: (GraphValue v, Ord (Id v)) => GraphQuery v -> Map (Id v) Double Source #
Degree centrality: normalized count of incident relationships per node.
Returns a map from node identity to normalized degree in [0, 1]. Normalization factor is (n - 1) where n is the number of nodes.
betweennessCentrality :: (GraphValue v, Ord (Id v)) => GraphQuery v -> TraversalWeight v -> Map (Id v) Double Source #
Betweenness centrality using the Brandes algorithm.
Returns a map from node identity to betweenness score (unnormalized).
Complexity: O(n·(n+r)·log n). For large graphs, wrap the GraphQuery
with memoizeIncidentRels before calling this function.
TODO: bulk adjacency — see open question §1 in the feature proposal.
This implementation calls queryIncidentRels in the inner loop, which
is O(r) per call. A bulk adjacency representation would reduce this to O(1).
Context query helpers
queryAnnotationsOf :: GraphClassifier extra v -> GraphQuery v -> Pattern v -> [Pattern v] Source #
Return all annotations that directly contain the given element.
Filters the result of queryContainers to elements classified as GAnnotation.
queryWalksContaining :: GraphClassifier extra v -> GraphQuery v -> Pattern v -> [Pattern v] Source #
Return all walks that directly contain the given element.
Filters the result of queryContainers to elements classified as GWalk.
queryCoMembers :: (GraphValue v, Eq (Id v)) => GraphQuery v -> Pattern v -> Pattern v -> [Pattern v] Source #
Return all co-members of element within container.
Co-members are the other elements that are contained by container (i.e. all
elements that share this container with element), excluding element itself.
E.g. for two nodes that share a common walk, calling queryCoMembers with
one node and the walk as container returns the other node(s) in that walk.