Zog.Property (Zog v0.4.0)

View Source

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

Summary

Functions

all_maximal_cliques(builder)

Finds all maximal cliques using native Bron-Kerbosch.

all_maximal_cliques(arg1, arg2, arg3, arg4)
arborescence?(builder)

Checks if the graph is an arborescence (directed tree with a single root).

arborescence_root(builder)

Finds the root label of an arborescence, or nil if none exists.

branching?(builder)

Checks if a directed graph is a branching (directed forest).

coloring_dsatur(builder)

Computes graph coloring using the DSatur heuristic natively. Returns {chromatic_number, %{node_label => color}}.

coloring_exact(builder, timeout_ms \\ 5000)

Computes exact graph coloring natively using backtracking with pruning.

complete?(builder)

Checks if the graph is a complete graph (K_n).

eulerian_circuit(graph, opts \\ [])

Finds an Eulerian circuit in the graph using Hierholzer's algorithm.

eulerian_path(graph, opts \\ [])

Finds an Eulerian path in the graph using Hierholzer's algorithm.

find_isomorphism(g1, g2)

Finds node mapping dict %{g1_label => g2_label} if isomorphic, or nil.

forest?(builder)

Checks if the graph is a forest.

has_eulerian_circuit?(builder)

Checks if the graph contains an Eulerian circuit.

has_eulerian_path?(builder)

Checks if the graph contains an Eulerian path.

hash(graph, opts \\ [])

Calculates the Weisfeiler-Lehman (WL) structural graph hash.

is_arborescence?(graph)
is_branching?(graph)
is_complete?(graph)
is_forest?(graph)
is_isomorphic?(g1, g2)
is_regular?(graph, k)
is_tree?(graph)
isomorphic?(g1, g2)

Checks if two graphs are isomorphic using exact VF2 matching.

max_clique(builder)

Finds the maximum clique using native Bron-Kerbosch.

nif_arborescence_root(arg1, arg2, arg3, arg4)
nif_dsatur(arg1, arg2, arg3, arg4)
nif_eulerian_path(arg1, arg2, arg3, arg4, arg5, arg6)
nif_exact_coloring(arg1, arg2, arg3, arg4, arg5)
nif_find_isomorphism(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8, arg9)
nif_has_eulerian_circuit(arg1, arg2, arg3, arg4, arg5)
nif_has_eulerian_path(arg1, arg2, arg3, arg4, arg5)
nif_is_arborescence(arg1, arg2, arg3, arg4)
nif_is_branching(arg1, arg2, arg3, arg4)
nif_is_complete(arg1, arg2, arg3, arg4, arg5)
nif_is_forest(arg1, arg2, arg3, arg4, arg5)
nif_is_regular(arg1, arg2, arg3, arg4, arg5, arg6)
nif_is_tree(arg1, arg2, arg3, arg4, arg5)
nif_isomorphic(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8, arg9)
nif_weisfeiler_lehman_hash(arg1, arg2, arg3, arg4, arg5)
nif_weisfeiler_lehman_hash_custom(arg1, arg2, arg3, arg4, arg5, arg6)
regular?(builder, k)

Checks if the graph is k-regular.

tree?(builder)

Checks if the graph is a tree.

Functions

all_maximal_cliques(builder)

@spec all_maximal_cliques(Zog.SoA.t()) :: [MapSet.t(Zog.SoA.label())]

Finds all maximal cliques using native Bron-Kerbosch.

all_maximal_cliques(arg1, arg2, arg3, arg4)

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

arborescence?(builder)

Checks if the graph is an arborescence (directed tree with a single root).

arborescence_root(builder)

Finds the root label of an arborescence, or nil if none exists.

branching?(builder)

Checks if a directed graph is a branching (directed forest).

coloring_dsatur(builder)

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

Computes graph coloring using the DSatur heuristic natively. Returns {chromatic_number, %{node_label => color}}.

coloring_exact(builder, timeout_ms \\ 5000)

@spec coloring_exact(Zog.SoA.t(), non_neg_integer()) ::
  {:ok, non_neg_integer(), %{required(Zog.SoA.label()) => non_neg_integer()}}
  | {:timeout,
     {non_neg_integer(), %{required(Zog.SoA.label()) => non_neg_integer()}}}

Computes exact graph coloring natively using backtracking with pruning.

complete?(builder)

Checks if the graph is a complete graph (K_n).

eulerian_circuit(graph, opts \\ [])

@spec eulerian_circuit(
  Zog.SoA.t() | struct(),
  keyword()
) :: {:ok, [Zog.SoA.label()]} | {:error, :no_eulerian_circuit}

Finds an Eulerian circuit in the graph using Hierholzer's algorithm.

eulerian_path(graph, opts \\ [])

@spec eulerian_path(
  Zog.SoA.t() | struct(),
  keyword()
) :: {:ok, [Zog.SoA.label()]} | {:error, :no_eulerian_path}

Finds an Eulerian path in the graph using Hierholzer's algorithm.

find_isomorphism(g1, g2)

Finds node mapping dict %{g1_label => g2_label} if isomorphic, or nil.

forest?(builder)

Checks if the graph is a forest.

has_eulerian_circuit?(builder)

@spec has_eulerian_circuit?(Zog.SoA.t() | struct()) :: boolean()

Checks if the graph contains an Eulerian circuit.

has_eulerian_path?(builder)

@spec has_eulerian_path?(Zog.SoA.t() | struct()) :: boolean()

Checks if the graph contains an Eulerian path.

hash(graph, opts \\ [])

@spec hash(
  Zog.SoA.t() | struct(),
  keyword()
) :: String.t()

Calculates the Weisfeiler-Lehman (WL) structural graph hash.

Provides a structural graph hash that iteratively gathers and sorts neighbor labels to construct a deterministic characteristic signature evaluating isomorphism.

Options

  • :iterations - The number of message-passing iterations (default: 3).
  • :node_label_fn - Custom function (graph, node -> String.t()) mapping nodes to initial labels.

Examples

iex> g1 = Zog.undirected() |> Zog.add_edge("a", "b", 1.0) |> Zog.add_edge("b", "c", 1.0)
iex> g2 = Zog.undirected() |> Zog.add_edge(1, 2, 1.0) |> Zog.add_edge(2, 3, 1.0)
iex> Zog.Property.hash(g1) == Zog.Property.hash(g2)
true

is_arborescence?(graph)

is_branching?(graph)

is_complete?(graph)

is_forest?(graph)

is_isomorphic?(g1, g2)

is_regular?(graph, k)

is_tree?(graph)

isomorphic?(g1, g2)

Checks if two graphs are isomorphic using exact VF2 matching.

max_clique(builder)

@spec max_clique(Zog.SoA.t()) :: MapSet.t(Zog.SoA.label())

Finds the maximum clique using native Bron-Kerbosch.

nif_arborescence_root(arg1, arg2, arg3, arg4)

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

nif_dsatur(arg1, arg2, arg3, arg4)

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

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

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

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

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

nif_find_isomorphism(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8, arg9)

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

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

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

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

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

nif_is_arborescence(arg1, arg2, arg3, arg4)

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

nif_is_branching(arg1, arg2, arg3, arg4)

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

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

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

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

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

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

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

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

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

nif_isomorphic(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8, arg9)

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

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

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

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

@spec nif_weisfeiler_lehman_hash_custom(
  0..18_446_744_073_709_551_615,
  [0..4_294_967_295] | <<_::_*32>>,
  [0..4_294_967_295] | <<_::_*32>>,
  [float()] | <<_::_*64>>,
  0..18_446_744_073_709_551_615,
  [[byte()] | binary()]
) :: binary()

regular?(builder, k)

Checks if the graph is k-regular.

tree?(builder)

Checks if the graph is a tree.