Zog.ResourceGraph (Zog v0.1.0)

View Source

Native graph resource backed by Zog (Zig) via Zigler.

Unlike the Copy-In/Copy-Out pattern, ResourceGraph keeps the Zig ArrayGraph or GraphMap alive as a NIF resource between calls. Build once, run many algorithms, destroy when done.

Backends

Zog supports two native graph backends, selectable via the :backend option:

  • :soa (default) - Structure of Arrays (ArrayGraph).
    • Structure: Stores nodes and edges in flat, contiguous memory slices.
    • Performance: Provides maximum execution speed and optimal cache locality.
    • Use Case: Recommended for read-heavy, build-once-run-many query workloads where the topology does not change between NIF calls.
  • :hash_graph - Hash Map Graph (GraphMap).
    • Structure: Stores nodes and edges using standard hash tables with buckets and dynamic resizing.
    • Performance: Incurs significant overhead due to pointer-heavy hashing, collision resolution, and lack of cache locality.
    • Use Case: Use only if your workload relies on dynamic graph mutation (adding or deleting nodes/edges natively) between algorithm executions.

Examples

Create a resource graph using the high-performance :soa backend:

graph = Zog.directed() |> Zog.add_edge("A", "B", 1.0)
res = Zog.ResourceGraph.new(graph, backend: :soa)
# compute centralities...
Zog.ResourceGraph.destroy(res)

Create a resource graph using the :hash_graph backend:

res = Zog.ResourceGraph.read_edgelist("edges.txt", backend: :hash_graph)
# compute centralities...
Zog.ResourceGraph.destroy(res)

Summary

Types

t()

A native graph resource together with its label mapping.

Functions

alpha_centrality(map, opts \\ [])

Alpha centrality.

alpha_centrality(arg1, arg2, arg3, arg4, arg5)
analyze(map, opts \\ [])

Analyzes an undirected ResourceGraph natively to find all bridges and articulation points.

assortativity(map)

Degree assortativity.

astar(map, start_label, goal_label, x_coords, y_coords, heuristic \\ :euclidean, opts \\ [])

Computes the shortest path and its weight between two nodes using A* algorithm directly on the native graph resource.

average_clustering_coefficient(map)

Average clustering coefficient.

bellman_ford(map, start_label, goal_label, opts \\ [])

Computes the shortest path and its weight between two nodes using Bellman-Ford algorithm directly on the native graph resource.

betweenness_f64(map, opts \\ [])

Weighted betweenness centrality.

betweenness_unweighted(map, opts \\ [])

Unweighted betweenness centrality.

closeness_f64(map, opts \\ [])

Closeness centrality.

core_numbers(map, opts \\ [])

Calculates all core numbers for all nodes in the ResourceGraph.

density(map)

Graph density.

destroy(map)

Explicitly destroys a native graph resource, freeing its memory.

dijkstra(map, start_label, goal_label, opts \\ [])

Computes the shortest path and its weight between two nodes using Dijkstra's algorithm directly on the native graph resource.

eigenvector(map, opts \\ [])

Eigenvector centrality.

eigenvector(arg1, arg2, arg3)
floyd_warshall(map)

Floyd-Warshall all-pairs shortest paths.

from_libgraph(libgraph, opts \\ [])

Builds a native graph resource directly from a Graph (from libgraph).

from_yog(yog_graph, opts \\ [])

Builds a native graph resource directly from a Yog.Graph.

global_min_cut(map, opts \\ [])

Computes the global minimum cut of the undirected network using the Stoer-Wagner algorithm.

harmonic_centrality_f64(map, opts \\ [])

Harmonic centrality.

is_reachable(map, start_label, goal_label, opts \\ [])

Checks if a target node is reachable from a start node using BFS traversal directly on the native graph resource.

johnsons(map)

Johnson's Algorithm for all-pairs shortest paths.

katz(map, opts \\ [])

Katz centrality.

katz(arg1, arg2, arg3, arg4, arg5)
kruskal(graph, opts \\ [])
label_propagation(map, opts \\ [])

Label Propagation community detection.

label_propagation(arg1, arg2, arg3)
leiden(map, opts \\ [])

Leiden community detection.

leiden(arg1, arg2, arg3, arg4, arg5)
leiden_hierarchical(map, opts \\ [])

Leiden hierarchical community detection.

leiden_hierarchical(arg1, arg2, arg3, arg4, arg5)
local_clustering_coefficient(map, opts \\ [])

Local clustering coefficient for each node.

louvain(map, opts \\ [])

Louvain community detection.

louvain(arg1, arg2, arg3, arg4)
max_flow(graph, source, sink, algorithm_or_opts \\ :edmonds_karp, opts \\ [])

Computes the maximum flow and minimum cut natively on a ResourceGraph.

modularity(map, community_map)

Computes modularity for a given community partition.

modularity_f64(arg1, arg2)
new(builder, opts \\ [])

Builds a native graph resource from a SoA.

new(arg1, arg2, arg3, arg4, arg5)
nif_analyze_connectivity(arg1)
nif_assortativity(arg1)
nif_astar(arg1, arg2, arg3, arg4, arg5, arg6)
nif_average_clustering_coefficient(arg1)
nif_bellman_ford(arg1, arg2, arg3)
nif_betweenness_f64(arg1)
nif_betweenness_unweighted(arg1)
nif_closeness_f64(arg1)
nif_core_numbers(arg1)
nif_density(arg1)
nif_destroy(arg1)
nif_dijkstra(arg1, arg2, arg3)
nif_floyd_warshall(arg1)
nif_global_min_cut(arg1)
nif_harmonic_centrality_f64(arg1)
nif_is_reachable(arg1, arg2, arg3)
nif_johnsons(arg1)
nif_kruskal(arg1)
nif_local_clustering_coefficient(arg1)
nif_max_flow(arg1, arg2, arg3)
nif_push_relabel(arg1, arg2, arg3)
nif_read_adjlist(arg1, arg2, arg3, arg4)
nif_read_edgelist(arg1, arg2, arg3, arg4)
nif_read_tgf(arg1, arg2, arg3, arg4)
nif_strongly_connected_components(arg1)
nif_triangle_count(arg1)
pagerank(map, opts \\ [])

PageRank centrality.

pagerank(arg1, arg2, arg3, arg4)
read_adjlist(path, opts \\ [])

Reads a graph from an adjacency list file directly in native memory.

read_edgelist(path, opts \\ [])

Reads a graph from an edge list file directly in native memory.

read_tgf(path, opts \\ [])

Reads a graph from a Trivial Graph Format (TGF) file directly in native memory.

strongly_connected_components(map, opts \\ [])

Finds strongly connected components in the ResourceGraph natively. Returns a list of lists of node labels.

to_libgraph(map)

Converts a native graph resource back to a Graph (from libgraph).

to_yog(map)

Converts a native graph resource back to a Yog.Graph.

triangle_count(map)

Triangle count.

Types

t()

@type t() :: %{resource: reference(), builder: Zog.SoA.t()}

A native graph resource together with its label mapping.

Functions

alpha_centrality(map, opts \\ [])

@spec alpha_centrality(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Alpha centrality.

Options

  • :alpha - Attenuation factor (defaults to 0.5).
  • :initial - Initial values (defaults to 1.0).
  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :tolerance - Convergence tolerance (defaults to 0.0001).
  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

alpha_centrality(arg1, arg2, arg3, arg4, arg5)

@spec alpha_centrality(
  reference(),
  float(),
  float(),
  0..18_446_744_073_709_551_615,
  float()
) :: [
  float()
]

analyze(map, opts \\ [])

@spec analyze(
  t(),
  keyword()
) :: %{
  bridges: [{Zog.SoA.label(), Zog.SoA.label()}],
  articulation_points: [Zog.SoA.label()]
}

Analyzes an undirected ResourceGraph natively to find all bridges and articulation points.

assortativity(map)

@spec assortativity(t()) :: float()

Degree assortativity.

astar(map, start_label, goal_label, x_coords, y_coords, heuristic \\ :euclidean, opts \\ [])

@spec astar(
  t(),
  Zog.SoA.label(),
  Zog.SoA.label(),
  map() | list(),
  map() | list(),
  atom(),
  keyword()
) ::
  {:ok, {[Zog.SoA.label()], float()}} | {:error, :no_path}

Computes the shortest path and its weight between two nodes using A* algorithm directly on the native graph resource.

average_clustering_coefficient(map)

@spec average_clustering_coefficient(t()) :: float()

Average clustering coefficient.

bellman_ford(map, start_label, goal_label, opts \\ [])

@spec bellman_ford(t(), Zog.SoA.label(), Zog.SoA.label(), keyword()) ::
  {:ok, {[Zog.SoA.label()], float()}}
  | {:error, :no_path}
  | {:error, :negative_cycle}

Computes the shortest path and its weight between two nodes using Bellman-Ford algorithm directly on the native graph resource.

betweenness_f64(map, opts \\ [])

@spec betweenness_f64(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Weighted betweenness centrality.

Options

  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

betweenness_unweighted(map, opts \\ [])

@spec betweenness_unweighted(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Unweighted betweenness centrality.

Options

  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

closeness_f64(map, opts \\ [])

@spec closeness_f64(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Closeness centrality.

Options

  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

core_numbers(map, opts \\ [])

@spec core_numbers(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => integer()} | [integer()]

Calculates all core numbers for all nodes in the ResourceGraph.

Options

  • :raw - If true, returns a list of core numbers directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

density(map)

@spec density(t()) :: float()

Graph density.

destroy(map)

@spec destroy(t()) :: :ok

Explicitly destroys a native graph resource, freeing its memory.

dijkstra(map, start_label, goal_label, opts \\ [])

@spec dijkstra(t(), Zog.SoA.label(), Zog.SoA.label(), keyword()) ::
  {:ok, {[Zog.SoA.label()], float()}} | {:error, :no_path}

Computes the shortest path and its weight between two nodes using Dijkstra's algorithm directly on the native graph resource.

eigenvector(map, opts \\ [])

@spec eigenvector(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Eigenvector centrality.

Options

  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :tolerance - Convergence tolerance (defaults to 0.0001).
  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

eigenvector(arg1, arg2, arg3)

@spec eigenvector(reference(), 0..18_446_744_073_709_551_615, float()) :: [float()]

floyd_warshall(map)

@spec floyd_warshall(t()) :: {:ok, [[float()]]} | {:error, :negative_cycle}

Floyd-Warshall all-pairs shortest paths.

from_libgraph(libgraph, opts \\ [])

@spec from_libgraph(
  Graph.t(),
  keyword()
) :: t()

Builds a native graph resource directly from a Graph (from libgraph).

from_yog(yog_graph, opts \\ [])

@spec from_yog(
  Yog.graph(),
  keyword()
) :: t()

Builds a native graph resource directly from a Yog.Graph.

global_min_cut(map, opts \\ [])

@spec global_min_cut(
  t(),
  keyword()
) :: %{
  cut_value: float(),
  source_side: [Zog.SoA.label()],
  sink_side: [Zog.SoA.label()]
}

Computes the global minimum cut of the undirected network using the Stoer-Wagner algorithm.

harmonic_centrality_f64(map, opts \\ [])

@spec harmonic_centrality_f64(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Harmonic centrality.

Options

  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

is_reachable(map, start_label, goal_label, opts \\ [])

@spec is_reachable(t(), Zog.SoA.label(), Zog.SoA.label(), keyword()) :: boolean()

Checks if a target node is reachable from a start node using BFS traversal directly on the native graph resource.

johnsons(map)

@spec johnsons(t()) :: {:ok, [[float()]]} | {:error, :negative_cycle}

Johnson's Algorithm for all-pairs shortest paths.

katz(map, opts \\ [])

@spec katz(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Katz centrality.

Options

  • :alpha - Attenuation factor (defaults to 0.1).
  • :beta - Weight parameter (defaults to 1.0).
  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :tolerance - Convergence tolerance (defaults to 0.0001).
  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

katz(arg1, arg2, arg3, arg4, arg5)

@spec katz(reference(), float(), float(), 0..18_446_744_073_709_551_615, float()) :: [
  float()
]

kruskal(graph, opts \\ [])

@spec kruskal(
  t(),
  keyword()
) :: {:ok, [Yog.MST.edge()]}

label_propagation(map, opts \\ [])

@spec label_propagation(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => non_neg_integer()} | [non_neg_integer()]

Label Propagation community detection.

Options

  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :seed - Random seed (defaults to 0).
  • :raw - If true, returns a list of community IDs directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

label_propagation(arg1, arg2, arg3)

@spec label_propagation(
  reference(),
  0..18_446_744_073_709_551_615,
  0..18_446_744_073_709_551_615
) :: [
  0..18_446_744_073_709_551_615
]

leiden(map, opts \\ [])

@spec leiden(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => non_neg_integer()} | [non_neg_integer()]

Leiden community detection.

Options

  • :min_modularity_gain - Minimum modularity gain to stop iterations (defaults to 0.000001).
  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :seed - Random seed for execution (defaults to 42).
  • :theta - Resolution parameter theta (defaults to 1.0).
  • :raw - If true, returns a list of community IDs directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

leiden(arg1, arg2, arg3, arg4, arg5)

@spec leiden(
  reference(),
  float(),
  0..18_446_744_073_709_551_615,
  0..18_446_744_073_709_551_615,
  float()
) :: [0..18_446_744_073_709_551_615]

leiden_hierarchical(map, opts \\ [])

@spec leiden_hierarchical(
  t(),
  keyword()
) :: Zog.Community.Dendrogram.t() | [[non_neg_integer()]]

Leiden hierarchical community detection.

Options

  • :min_modularity_gain - Minimum modularity gain to stop iterations (defaults to 0.000001).
  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :seed - Random seed for execution (defaults to 42).
  • :theta - Resolution parameter theta (defaults to 1.0).
  • :raw - If true, returns a raw list of lists of community assignments for each level instead of a Dendrogram struct.

leiden_hierarchical(arg1, arg2, arg3, arg4, arg5)

@spec leiden_hierarchical(
  reference(),
  float(),
  0..18_446_744_073_709_551_615,
  0..18_446_744_073_709_551_615,
  float()
) :: [[0..18_446_744_073_709_551_615]]

local_clustering_coefficient(map, opts \\ [])

@spec local_clustering_coefficient(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

Local clustering coefficient for each node.

Options

  • :raw - If true, returns a list of coefficients directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

louvain(map, opts \\ [])

@spec louvain(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => non_neg_integer()} | [non_neg_integer()]

Louvain community detection.

Options

  • :min_modularity_gain - Minimum modularity gain to stop iterations (defaults to 0.000001).
  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :seed - Random seed for execution (defaults to 42).
  • :raw - If true, returns a list of community IDs directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

louvain(arg1, arg2, arg3, arg4)

@spec louvain(
  reference(),
  float(),
  0..18_446_744_073_709_551_615,
  0..18_446_744_073_709_551_615
) :: [
  0..18_446_744_073_709_551_615
]

max_flow(graph, source, sink, algorithm_or_opts \\ :edmonds_karp, opts \\ [])

@spec max_flow(t(), Zog.SoA.label(), Zog.SoA.label(), atom() | keyword(), keyword()) ::
  %{
    max_flow: float(),
    residual_graph: Zog.SoA.t(),
    source_side: [Zog.SoA.label()],
    sink_side: [Zog.SoA.label()]
  }

Computes the maximum flow and minimum cut natively on a ResourceGraph.

modularity(map, community_map)

@spec modularity(t(), %{required(Zog.SoA.label()) => non_neg_integer()}) :: float()

Computes modularity for a given community partition.

modularity_f64(arg1, arg2)

@spec modularity_f64(reference(), [0..18_446_744_073_709_551_615] | <<_::_*64>>) ::
  float()

new(builder, opts \\ [])

@spec new(
  Zog.SoA.t(),
  keyword()
) :: t()

Builds a native graph resource from a SoA.

Options

  • :backend - Choose the native graph backend, either :soa or :hash_graph (defaults to :soa).

new(arg1, arg2, arg3, arg4, arg5)

@spec new(
  0..18_446_744_073_709_551_615,
  [0..4_294_967_295] | <<_::_*32>>,
  [0..4_294_967_295] | <<_::_*32>>,
  [float()] | <<_::_*64>>,
  term()
) :: reference()

nif_analyze_connectivity(arg1)

@spec nif_analyze_connectivity(reference()) :: term()

nif_assortativity(arg1)

@spec nif_assortativity(reference()) :: float()

nif_astar(arg1, arg2, arg3, arg4, arg5, arg6)

@spec nif_astar(
  reference(),
  0..4_294_967_295,
  0..4_294_967_295,
  [float()] | <<_::_*64>>,
  [float()] | <<_::_*64>>,
  term()
) :: term()

nif_average_clustering_coefficient(arg1)

@spec nif_average_clustering_coefficient(reference()) :: float()

nif_bellman_ford(arg1, arg2, arg3)

@spec nif_bellman_ford(reference(), 0..4_294_967_295, 0..4_294_967_295) :: term()

nif_betweenness_f64(arg1)

@spec nif_betweenness_f64(reference()) :: [float()]

nif_betweenness_unweighted(arg1)

@spec nif_betweenness_unweighted(reference()) :: [float()]

nif_closeness_f64(arg1)

@spec nif_closeness_f64(reference()) :: [float()]

nif_core_numbers(arg1)

@spec nif_core_numbers(reference()) :: [0..4_294_967_295]

nif_density(arg1)

@spec nif_density(reference()) :: float()

nif_destroy(arg1)

@spec nif_destroy(reference()) :: :ok

nif_dijkstra(arg1, arg2, arg3)

@spec nif_dijkstra(reference(), 0..4_294_967_295, 0..4_294_967_295) :: term()

nif_floyd_warshall(arg1)

@spec nif_floyd_warshall(reference()) :: term()

nif_global_min_cut(arg1)

@spec nif_global_min_cut(reference()) :: term()

nif_harmonic_centrality_f64(arg1)

@spec nif_harmonic_centrality_f64(reference()) :: [float()]

nif_is_reachable(arg1, arg2, arg3)

@spec nif_is_reachable(reference(), 0..4_294_967_295, 0..4_294_967_295) :: term()

nif_johnsons(arg1)

@spec nif_johnsons(reference()) :: term()

nif_kruskal(arg1)

@spec nif_kruskal(reference()) :: term()

nif_local_clustering_coefficient(arg1)

@spec nif_local_clustering_coefficient(reference()) :: [float()]

nif_max_flow(arg1, arg2, arg3)

@spec nif_max_flow(reference(), 0..4_294_967_295, 0..4_294_967_295) :: term()

nif_push_relabel(arg1, arg2, arg3)

@spec nif_push_relabel(reference(), 0..4_294_967_295, 0..4_294_967_295) :: term()

nif_read_adjlist(arg1, arg2, arg3, arg4)

@spec nif_read_adjlist([byte()] | binary(), boolean(), term(), boolean()) :: term()

nif_read_edgelist(arg1, arg2, arg3, arg4)

@spec nif_read_edgelist([byte()] | binary(), boolean(), term(), boolean()) :: term()

nif_read_tgf(arg1, arg2, arg3, arg4)

@spec nif_read_tgf([byte()] | binary(), boolean(), term(), boolean()) :: term()

nif_strongly_connected_components(arg1)

@spec nif_strongly_connected_components(reference()) :: [0..4_294_967_295]

nif_triangle_count(arg1)

@spec nif_triangle_count(reference()) :: 0..18_446_744_073_709_551_615

pagerank(map, opts \\ [])

@spec pagerank(
  t(),
  keyword()
) :: %{required(Zog.SoA.label()) => float()} | [float()]

PageRank centrality.

Options

  • :damping - PageRank damping factor (defaults to 0.85).
  • :max_iterations - Maximum iteration steps (defaults to 100).
  • :tolerance - Convergence tolerance (defaults to 0.0001).
  • :raw - If true, returns a list of scores directly corresponding to internal u32 node IDs instead of mapping to Elixir labels.

pagerank(arg1, arg2, arg3, arg4)

@spec pagerank(reference(), float(), 0..18_446_744_073_709_551_615, float()) :: [
  float()
]

read_adjlist(path, opts \\ [])

@spec read_adjlist(
  Path.t(),
  keyword()
) :: t()

Reads a graph from an adjacency list file directly in native memory.

Options

  • :directed - Boolean flag representing if the graph is directed (defaults to true).
  • :backend - Choose the native graph backend, either :soa or :hash_graph (defaults to :soa).
  • :integer_labels - If true, parses labels as integers directly in Zig, bypassing string hash-map lookups (defaults to false).

read_edgelist(path, opts \\ [])

@spec read_edgelist(
  Path.t(),
  keyword()
) :: t()

Reads a graph from an edge list file directly in native memory.

Options

  • :directed - Boolean flag representing if the graph is directed (defaults to true).
  • :backend - Choose the native graph backend, either :soa or :hash_graph (defaults to :soa).
  • :integer_labels - If true, parses labels as integers directly in Zig, bypassing string hash-map lookups (defaults to false).

read_tgf(path, opts \\ [])

@spec read_tgf(
  Path.t(),
  keyword()
) :: t()

Reads a graph from a Trivial Graph Format (TGF) file directly in native memory.

Options

  • :directed - Boolean flag representing if the graph is directed (defaults to true).
  • :backend - Choose the native graph backend, either :soa or :hash_graph (defaults to :soa).
  • :integer_labels - If true, parses labels as integers directly in Zig, bypassing string hash-map lookups (defaults to false).

strongly_connected_components(map, opts \\ [])

@spec strongly_connected_components(
  t(),
  keyword()
) :: [[Zog.SoA.label()]] | [non_neg_integer()]

Finds strongly connected components in the ResourceGraph natively. Returns a list of lists of node labels.

Options

  • :raw - If true, returns a list of component IDs directly corresponding to internal u32 node IDs instead of grouping and mapping to Elixir labels.

to_libgraph(map)

@spec to_libgraph(t()) :: Graph.t()

Converts a native graph resource back to a Graph (from libgraph).

to_yog(map)

@spec to_yog(t()) :: Yog.graph()

Converts a native graph resource back to a Yog.Graph.

triangle_count(map)

@spec triangle_count(t()) :: non_neg_integer()

Triangle count.