Safe Haskell	Safe-Inferred
Language	Haskell2010

Pattern.Graph.GraphQuery

Contents

Traversal types
GraphQuery interface
Combinators

Description

This module provides 'GraphQuery v', a record-of-functions that abstracts over any graph representation. Algorithms in Pattern.Graph.Algorithms accept 'GraphQuery v' and are therefore independent of whether the underlying graph is a GraphLens or a PatternGraph.

Categorical Interpretation

'GraphQuery v' is a coalgebra: given a graph element, it produces the elements reachable from it. queryContainers is the upward dual — given an element, it produces the structures that contain it. Together they form a bidirectional traversal interface.

Design Principles

Record-of-functions (not a typeclass) — consistent with GraphClassifier.
TraversalWeight is a call-site parameter, not part of the interface.
Combinators (frameQuery, memoizeIncidentRels) are plain functions.

Example

import Pattern.Graph (fromGraphLens)
import Pattern.PatternGraph (fromPatternGraph)
import Pattern.Graph.GraphQuery (directed)
import qualified Pattern.Graph.Algorithms as Alg

-- From a PatternGraph (O(log n) lookups):
let gq = fromPatternGraph myPatternGraph
let path = Alg.shortestPath gq directed nodeA nodeB

-- From a GraphLens (O(n) lookups):
let gq2 = fromGraphLens myLens
let comps = Alg.connectedComponents gq2 undirected

Synopsis

data TraversalDirection
- = Forward
- | Backward
type TraversalWeight v = Pattern v -> TraversalDirection -> Double
undirected :: TraversalWeight v
directed :: TraversalWeight v
directedReverse :: TraversalWeight v
data GraphQuery v = GraphQuery {
- queryNodes :: [Pattern v]
- queryRelationships :: [Pattern v]
- queryIncidentRels :: Pattern v -> [Pattern v]
- querySource :: Pattern v -> Maybe (Pattern v)
- queryTarget :: Pattern v -> Maybe (Pattern v)
- queryDegree :: Pattern v -> Int
- queryNodeById :: Id v -> Maybe (Pattern v)
- queryRelationshipById :: Id v -> Maybe (Pattern v)
- queryContainers :: Pattern v -> [Pattern v]
}
frameQuery :: (Pattern v -> Bool) -> GraphQuery v -> GraphQuery v
memoizeIncidentRels :: (GraphValue v, Ord (Id v)) => GraphQuery v -> GraphQuery v

Traversal types

data TraversalDirection Source #

The two orientations along a directed relationship.

Forward follows the relationship from source to target; Backward follows it from target to source.

Constructors

Forward
Backward

Instances

Instances details

Show TraversalDirection Source #
Instance details Defined in Pattern.Graph.GraphQuery Methods showsPrec :: Int -> TraversalDirection -> ShowS # show :: TraversalDirection -> String # showList :: [TraversalDirection] -> ShowS #
Eq TraversalDirection Source #
Instance details Defined in Pattern.Graph.GraphQuery Methods (==) :: TraversalDirection -> TraversalDirection -> Bool # (/=) :: TraversalDirection -> TraversalDirection -> Bool #

type TraversalWeight v = Pattern v -> TraversalDirection -> Double Source #

A function assigning a traversal cost to each (relationship, direction) pair.

Infinity (1/0 :: Double) encodes impassability — traversal is blocked in that direction. Non-negative values encode traversal cost. Negative weights are not supported by the standard Dijkstra-based algorithms.

Canonical values: undirected, directed, directedReverse.

undirected :: TraversalWeight v Source #

Uniform cost in both directions. Direction is ignored.

directed :: TraversalWeight v Source #

Forward traversal only. Backward traversal is impassable.

directedReverse :: TraversalWeight v Source #

Backward traversal only. Forward traversal is impassable.

GraphQuery interface

data GraphQuery v Source #

A record-of-functions representing a graph query interface.

Construct via fromGraphLens or fromPatternGraph. Compose with frameQuery and memoizeIncidentRels.

Performance note (Haskell-specific)

The hot-path fields (queryIncidentRels, querySource, queryTarget, queryDegree) are function-typed. GHC will inline their applications at call sites when the GraphQuery value is known statically; use {-# INLINE #-} on algorithms that receive GraphQuery as a parameter to encourage this. {-# UNPACK #-} does not apply here because all fields are either function types or boxed list types — neither can be unboxed.

Invariants

querySource r = Just s implies s ∈ queryNodes.
queryTarget r = Just t implies t ∈ queryNodes.
r ∈ queryIncidentRels n implies querySource r = Just n ∨ queryTarget r = Just n.
queryDegree n = length (queryIncidentRels n) (default; implementations may be faster).
queryNodeById (identify (value n)) = Just n for all n ∈ queryNodes.
queryRelationshipById (identify (value r)) = Just r for all r ∈ queryRelationships.
queryContainers returns only direct containers — does not recurse transitively.

Constructors

GraphQuery

Fields

queryNodes :: [Pattern v]
All node-classified elements in the graph. O(n).
queryRelationships :: [Pattern v]
All relationship-classified elements. O(r).
queryIncidentRels :: Pattern v -> [Pattern v]
All relationships where the given node is source or target. O(r).
querySource :: Pattern v -> Maybe (Pattern v)
The source (first endpoint) of a relationship; Nothing if not a relationship. O(1).
queryTarget :: Pattern v -> Maybe (Pattern v)
The target (second endpoint) of a relationship; Nothing if not a relationship. O(1).
queryDegree :: Pattern v -> Int
Count of incident relationships for a node. O(r) default; O(1) if indexed.
queryNodeById :: Id v -> Maybe (Pattern v)
Node lookup by identity. O(log n) from PatternGraph; O(n) from GraphLens.
queryRelationshipById :: Id v -> Maybe (Pattern v)
Relationship lookup by identity. O(log r) from PatternGraph; O(r) from GraphLens.
queryContainers :: Pattern v -> [Pattern v]
All higher-order structures (relationships, walks, annotations) that directly contain the given element. O(r + w + a).

Combinators

frameQuery :: (Pattern v -> Bool) -> GraphQuery v -> GraphQuery v Source #

Produce a GraphQuery restricted to elements satisfying a predicate.

queryIncidentRels on the framed query excludes relationships whose endpoints fall outside the frame. All GraphQuery invariants are preserved.

Example

let subgraph = frameQuery (\(Pattern v _) -> v == "Person") gq

memoizeIncidentRels :: (GraphValue v, Ord (Id v)) => GraphQuery v -> GraphQuery v Source #

Wrap queryIncidentRels with a pure memoization layer.

Builds a complete cache from queryNodes eagerly, then serves all subsequent queryIncidentRels calls from the cache. All other fields are passed through unchanged.

Useful for algorithms (e.g. betweenness centrality) that call queryIncidentRels repeatedly on the same node.

Note: The cache is per-GraphQuery value, not global.