ExOKF.Graph.Adjacency (ex_okf v0.1.0)

Native adjacency-list graph backend implementing ExOKF.Graph.Backend.

Builds directed edges from internal markdown links between concepts. Suitable for typical knowledge bundles; swap in ExOKF.Graph.GraphBLAS for large-scale sparse algebra in v0.2+.

Fields

Field	Type	Description
`outbound`	`%{optional(String.t()) => MapSet.t(String.t())}`	Concept id → set of linked targets.
`inbound`	`%{optional(String.t()) => MapSet.t(String.t())}`	Concept id → set of backlink sources.
`nodes`	`MapSet.t(String.t())`	All concept ids present when the graph was built.

Example

%ExOKF.Graph.Adjacency{
  outbound: %{"tables/orders" => MapSet.new(["tables/customers", "datasets/sales"])},
  inbound: %{"tables/customers" => MapSet.new(["tables/orders", "datasets/sales"])},
  nodes: MapSet.new(["tables/orders", "tables/customers", "datasets/sales"])
}

Summary

Types

t()

Native adjacency graph.

Functions

build(bundle)

Builds an adjacency graph from the bundle's internal links.

cyclic?(graph)

Returns true when the directed graph contains a cycle.

edge_count(graph)

Returns the number of directed edges.

edges(adjacency)

Returns all directed edges as {from, to} tuples, sorted.

has_edge?(adjacency, from, to)

Returns true when a directed edge from → to exists.

neighbors(adjacency, id)

Returns sorted outbound neighbors of id.

node_count(adjacency)

Returns the number of concept nodes.

reachable(graph, id, opts \\ [])

Returns concept ids reachable from id.

reverse_neighbors(adjacency, id)

Returns sorted inbound neighbors (backlinks) of id.

Types

t()

@type t() :: %ExOKF.Graph.Adjacency{
  inbound: %{optional(String.t()) => MapSet.t(String.t())},
  nodes: MapSet.t(String.t()),
  outbound: %{optional(String.t()) => MapSet.t(String.t())}
}

Native adjacency graph.

See the module documentation for field meanings.

Functions

build(bundle)

@spec build(ExOKF.Bundle.t()) :: t()

Builds an adjacency graph from the bundle's internal links.

Parameters

bundle (ExOKF.Bundle.t()) — loaded OKF bundle

Examples

iex> bundle = ExOKF.TestSupport.sample_bundle()
iex> graph = ExOKF.Graph.Adjacency.build(bundle)
iex> "tables/customers" in ExOKF.Graph.Adjacency.neighbors(graph, "tables/orders")
true

cyclic?(graph)

@spec cyclic?(t()) :: boolean()

Returns true when the directed graph contains a cycle.

Uses DFS with a recursion stack (not plain BFS reachability).

Parameters

graph (t/0) — adjacency graph

Examples

iex> bundle = ExOKF.TestSupport.sample_bundle()
iex> is_boolean(ExOKF.Graph.Adjacency.cyclic?(bundle.graph.data))
true

edge_count(graph)

@spec edge_count(t()) :: non_neg_integer()

Returns the number of directed edges.

Parameters

graph (t/0) — adjacency graph

edges(adjacency)

@spec edges(t()) :: [{String.t(), String.t()}]

Returns all directed edges as {from, to} tuples, sorted.

Parameters

graph (t/0) — adjacency graph

has_edge?(adjacency, from, to)

@spec has_edge?(t(), String.t(), String.t()) :: boolean()

Returns true when a directed edge from → to exists.

Parameters

graph (t/0) — adjacency graph
from (String.t()) — source concept id
to (String.t()) — target concept id

neighbors(adjacency, id)

@spec neighbors(t(), String.t()) :: [String.t()]

Returns sorted outbound neighbors of id.

Parameters

graph (t/0) — adjacency graph
id (String.t()) — concept id

node_count(adjacency)

@spec node_count(t()) :: non_neg_integer()

Returns the number of concept nodes.

Parameters

graph (t/0) — adjacency graph

reachable(graph, id, opts \\ [])

@spec reachable(t(), String.t(), keyword()) :: [String.t()]

Returns concept ids reachable from id.

Parameters

graph (t/0) — adjacency graph
id (String.t()) — start concept id
opts (keyword()) — :max_depth (pos_integer() \| :infinity) and :include_self (boolean())

Examples

iex> bundle = ExOKF.TestSupport.sample_bundle()
iex> g = bundle.graph.data
iex> "tables/customers" in ExOKF.Graph.Adjacency.reachable(g, "tables/orders", max_depth: 1)
true

reverse_neighbors(adjacency, id)

@spec reverse_neighbors(t(), String.t()) :: [String.t()]

Returns sorted inbound neighbors (backlinks) of id.

Parameters

graph (t/0) — adjacency graph
id (String.t()) — concept id