@spec acyclic?(graph()) :: boolean()

Determines if a graph is acyclic (contains no cycles).

This is the logical opposite of cyclic?. For directed graphs, returning true means the graph is a Directed Acyclic Graph (DAG).

Time Complexity: O(V + E)

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}])
iex> Yog.acyclic?(graph)
true

@spec add_edge(
  graph(),
  keyword()
) :: {:ok, graph()} | {:error, String.t()}

Adds an edge to the graph.

For directed graphs, adds a single edge from from to to. For undirected graphs, adds edges in both directions.

Returns {:ok, graph} or {:error, reason}.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(from: 1, to: 2, with: 10)
iex> Yog.successors(graph, 1)
[{2, 10}]

With pattern matching for chaining

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> {:ok, graph} = Yog.add_edge(graph, from: 1, to: 2, with: 10)
iex> {:ok, graph} = Yog.add_edge(graph, from: 2, to: 1, with: 5)
iex> Yog.successors(graph, 2)
[{1, 5}]

@spec add_edge(graph(), node_id(), node_id(), any()) ::
  {:ok, graph()} | {:error, String.t()}

Raw binding for add_edge with positional arguments.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> {:ok, graph} = Yog.add_edge(graph, 1, 2, 10)
iex> Yog.successors(graph, 1)
[{2, 10}]

@spec add_edge!(
  graph(),
  keyword()
) :: graph()

Adds an edge to the graph, raising on error.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> graph = Yog.add_edge!(graph, from: 1, to: 2, with: 10)
iex> Yog.successors(graph, 1)
[{2, 10}]

Adds an edge to the graph with positional arguments, raising on error.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> graph = Yog.add_edge!(graph, 1, 2, 10)
iex> Yog.successors(graph, 1)
[{2, 10}]

@spec add_edge_ensure(
  graph(),
  keyword()
) :: graph()

Ensures both endpoint nodes exist, then adds an edge.

If from or to is not already in the graph, it is created with the supplied default node data. Existing nodes are left unchanged.

Always succeeds and returns a Graph (never fails). Use this when you want to build graphs quickly without pre-creating nodes.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10, default: "anon")
iex> # Nodes 1 and 2 are auto-created with data "anon"
iex> Yog.successors(graph, 1)
[{2, 10}]

Ensures both endpoint nodes exist with positional arguments, then adds an edge.

Example

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10, "anon")
iex> Yog.successors(graph, 1)
[{2, 10}]

@spec add_edge_with(graph(), node_id(), node_id(), any(), (node_id() -> any())) ::
  graph()

Adds an edge with a function to create default node data if nodes don't exist.

If from or to is not already in the graph, it is created by calling the default_fn function with the node ID to generate the node data. Existing nodes are left unchanged.

Always succeeds and returns a Graph (never fails).

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_edge_with(1, 2, 10, fn id -> "Node#{id}" end)
iex> # Nodes 1 and 2 are auto-created with "Node1" and "Node2"
iex> Yog.successors(graph, 1)
[{2, 10}]

@spec add_edges(graph(), [edge_tuple()]) :: {:ok, graph()} | {:error, String.t()}

Adds multiple edges to the graph.

Fails fast on the first edge that references non-existent nodes. Returns {:error, reason} if any endpoint node doesn't exist.

This is more ergonomic than chaining multiple add_edge calls as it only requires unwrapping a single result.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}, {1, 3, 15}])
iex> length(Yog.successors(graph, 1))
2

Adds multiple edges to the graph, raising on error.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges!([{1, 2, 10}, {2, 3, 5}])
iex> length(Yog.successors(graph, 1))
1

@spec add_node(graph(), node_id(), any()) :: graph()

Adds a node to the graph with the given ID and label. If a node with this ID already exists, its data will be replaced.

Example

iex> graph = Yog.directed()
iex> graph = Yog.add_node(graph, 1, "Node A")
iex> graph = Yog.add_node(graph, 2, "Node B")
iex> Yog.all_nodes(graph) |> Enum.sort()
[1, 2]

@spec add_nodes_from(graph(), Enumerable.t()) :: graph()

Adds multiple nodes to the graph from an iterable.

See Yog.Model.add_nodes_from/2 for details.

@spec add_simple_edge(
  graph(),
  keyword()
) :: {:ok, graph()} | {:error, String.t()}

Adds a simple edge with weight 1.

This is a convenience function for graphs with integer weights where a default weight of 1 is appropriate (e.g., unweighted graphs, hop counts).

Returns {:ok, graph} or {:error, reason} if either endpoint node doesn't exist.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_simple_edge(from: 1, to: 2)
iex> Yog.successors(graph, 1)
[{2, 1}]

@spec add_simple_edge(graph(), node_id(), node_id()) ::
  {:ok, graph()} | {:error, String.t()}

Adds a simple edge with positional arguments (weight = 1).

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_simple_edge(1, 2)
iex> Yog.successors(graph, 1)
[{2, 1}]

Adds a simple edge with weight 1, raising on error.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_simple_edge!(from: 1, to: 2)
iex> Yog.successors(graph, 1)
[{2, 1}]

@spec add_simple_edges(graph(), [{node_id(), node_id()}]) ::
  {:ok, graph()} | {:error, String.t()}

Adds multiple simple edges (weight = 1).

Fails fast on the first edge that references non-existent nodes. Convenient for unweighted graphs where all edges have weight 1.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_simple_edges([{1, 2}, {2, 3}, {1, 3}])
iex> length(Yog.successors(graph, 1))
2

@spec add_unweighted_edge(
  graph(),
  keyword()
) :: {:ok, graph()} | {:error, String.t()}

Adds an unweighted edge to the graph.

This is a convenience function for graphs where edges have no meaningful weight. Uses nil as the edge data type.

Returns {:ok, graph} or {:error, reason} if either endpoint node doesn't exist.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_unweighted_edge(from: 1, to: 2)
iex> Yog.successors(graph, 1)
[{2, nil}]

@spec add_unweighted_edge(graph(), node_id(), node_id()) ::
  {:ok, graph()} | {:error, String.t()}

Adds an unweighted edge with positional arguments.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_unweighted_edge(1, 2)
iex> Yog.successors(graph, 1)
[{2, nil}]

Adds an unweighted edge to the graph, raising on error.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_unweighted_edge!(from: 1, to: 2)
iex> Yog.successors(graph, 1)
[{2, nil}]

@spec add_unweighted_edges(graph(), [{node_id(), node_id()}]) ::
  {:ok, graph()} | {:error, String.t()}

Adds multiple unweighted edges (weight = nil).

Fails fast on the first edge that references non-existent nodes. Convenient for graphs where edges carry no weight information.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_unweighted_edges([{1, 2}, {2, 3}, {1, 3}])
iex> length(Yog.successors(graph, 1))
2

@spec all_edges(graph()) :: [{node_id(), node_id(), any()}]

Returns all edges in the graph as triplets {from, to, weight}.

Example

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10)
iex> Yog.all_edges(graph)
[{1, 2, 10}]

@spec all_nodes(graph()) :: [node_id()]

Returns all unique node IDs that have edges in the graph.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> Yog.all_nodes(graph) |> Enum.sort()
[1, 2]

@spec arborescence?(graph()) :: boolean()

Returns true if the graph is an arborescence (directed tree with a unique root).

@spec arborescence_root(graph()) :: node_id() | nil

Returns the root of an arborescence, or nil if it's not an arborescence.

@spec complement(graph(), any()) :: graph()

Returns the complement of the graph (edges that don't exist in the original).

The complement has edges between all pairs of nodes that are NOT connected in the original graph.

Parameters

• graph - The input graph
• default_weight - Weight to assign to new edges in the complement

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> complement = Yog.complement(graph, 1)
iex> # The complement has an edge from 2 to 1 (which didn't exist)
iex> Yog.successors(complement, 2)
[{1, 1}]

@spec complete?(graph()) :: boolean()

Returns true if the graph is complete (every pair of distinct nodes is connected).

@spec contract(graph(), node_id(), node_id(), (any(), any() -> any())) :: graph()

Contracts (merges) two nodes into a single node.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 3, 10}, {2, 3, 20}])
iex> contracted = Yog.contract(graph, 1, 2, fn a, b -> a + b end)
iex> length(Yog.all_nodes(contracted))
2

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

Determines if a graph contains any cycles.

For directed graphs, a cycle exists if there is a path from a node back to itself. For undirected graphs, a cycle exists if there is a path of length >= 3 from a node back to itself, or a self-loop.

Time Complexity: O(V + E)

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {3, 1, 1}])
iex> Yog.cyclic?(graph)
true

@spec degree(graph(), node_id()) :: non_neg_integer()

Returns the total degree of a node.

@spec directed() :: graph()

Creates a new empty directed graph.

This is a convenience function that's equivalent to Yog.new(:directed), but requires only a single import.

Example

iex> graph = Yog.directed()
iex> Yog.graph?(graph)
true

@spec edge_count(graph()) :: integer()

Returns the number of edges in the graph.

Example

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10) |> Yog.add_edge_ensure(2, 3, 5)
iex> Yog.edge_count(graph)
2

@spec ego_graph(graph(), node_id(), non_neg_integer(), keyword()) :: graph()

Returns the ego graph of a node — the subgraph induced by the node and all nodes within radius hops.

For directed graphs, the :mode option controls traversal:

• :successors (default) - follows outgoing edges only
• :neighbors - follows both outgoing and incoming edges

Example

iex> graph =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
iex> ego = Yog.ego_graph(graph, 1)
iex> Enum.sort(Yog.all_nodes(ego))
[1, 2]

@spec filter_edges(graph(), (node_id(), node_id(), any() -> boolean())) :: graph()

Filter edges by a predicate. Removes edges that don't match the predicate.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges!([{1, 2, 10}, {1, 3, 20}])
iex> filtered = Yog.filter_edges(graph, fn _src, _dst, w -> w > 15 end)
iex> Yog.successors(filtered, 1)
[{3, 20}]

@spec filter_nodes(graph(), (any() -> boolean())) :: graph()

Filter nodes by a predicate. Removes nodes that don't match the predicate and all edges connected to them.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "keep")
...>   |> Yog.add_node(2, "remove")
...>   |> Yog.add_edge(1, 2, 10)
iex> filtered = Yog.filter_nodes(graph, fn label -> label == "keep" end)
iex> Yog.all_nodes(filtered)
[1]

Creates a graph from an adjacency list.

Delegates to Yog.IO.List.from_list/2.

Example

iex> entries = [{1, [{2, 1}, {3, 1}]}, {2, [{3, 1}]}, {3, []}]
iex> graph = Yog.from_adjacency_list(:undirected, entries)
iex> Yog.Model.order(graph)
3

Creates a graph from an adjacency list string.

Delegates to Yog.IO.List.from_string/3.

Example

iex> text = "1: 2 3\n2: 3\n3:"
iex> graph = Yog.from_adjacency_list_string(:undirected, text)
iex> Yog.Model.order(graph)
3

Creates a graph from an adjacency matrix.

Delegates to Yog.IO.Matrix.from_matrix/2.

Example

iex> matrix = [[0, 1, 1], [1, 0, 0], [1, 0, 0]]
iex> graph = Yog.from_adjacency_matrix(:undirected, matrix)
iex> Yog.Model.order(graph)
3

@spec from_edges(:directed | :undirected, [{node_id(), node_id(), any()}]) :: graph()

Creates a graph from a list of edges.

Auto-creates nodes with nil data as needed.

Example

iex> edges = [{1, 2, 10}, {2, 3, 20}]
iex> graph = Yog.from_edges(:directed, edges)
iex> length(Yog.successors(graph, 1))
1

@spec from_nodes(:directed | :undirected, Enumerable.t()) :: graph()

Creates a graph from a list of nodes.

Accepts:

• A list of node IDs: [1, 2, 3]
• A list of {id, data} tuples: [{1, "A"}, {2, "B"}]
• A map: %{1 => "A", 2 => "B"}

Example

iex> graph = Yog.from_nodes(:directed, [1, {2, "B"}])
iex> Yog.Model.order(graph)
2
iex> Yog.Model.node(graph, 2)
"B"

@spec from_unweighted_edges(:directed | :undirected, [{node_id(), node_id()}]) ::
  graph()

Creates a graph from a list of unweighted edges (weight will be nil).

Example

iex> edges = [{1, 2}, {2, 3}]
iex> graph = Yog.from_unweighted_edges(:directed, edges)
iex> Yog.successors(graph, 1)
[{2, nil}]

@spec graph?(any()) :: boolean()

Returns true if the given value is a Yog graph.

Example

iex> graph = Yog.directed()
iex> Yog.graph?(graph)
true
iex> Yog.graph?("not a graph")
false

@spec has_edge?(graph(), node_id(), node_id()) :: boolean()

Checks if the graph contains an edge between src and dst.

Example

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10)
iex> Yog.has_edge?(graph, 1, 2)
true
iex> Yog.has_edge?(graph, 2, 1)
false

@spec has_node?(graph(), node_id()) :: boolean()

Checks if the graph contains a node with the given ID.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A")
iex> Yog.has_node?(graph, 1)
true
iex> Yog.has_node?(graph, 2)
false

@spec hopcroft_karp(graph()) :: %{required(node_id()) => node_id()}

Finds a maximum cardinality matching in a bipartite graph using the Hopcroft-Karp algorithm.

Returns a bidirectional map of matched pairs. Raises ArgumentError if the graph is not bipartite.

Example

iex> graph = Yog.from_edges(:undirected, [{:a1, :b1, 1}, {:a1, :b2, 1}, {:a2, :b2, 1}])
iex> matching = Yog.hopcroft_karp(graph)
iex> map_size(matching)
4

@spec in_degree(graph(), node_id()) :: non_neg_integer()

Returns the in-degree of a node (number of incoming edges).

@spec k_core(graph(), integer()) :: graph()

Extracts the k-core of a graph (maximal subgraph with minimum degree k).

@spec map_edges(graph(), (term() -> term())) :: graph()

Creates a new graph where edge weights are transformed.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> doubled = Yog.map_edges(graph, fn w -> w * 2 end)
iex> Yog.successors(doubled, 1)
[{2, 20}]

@spec map_nodes(graph(), (any() -> any())) :: graph()

Creates a new graph where node labels are transformed.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "a")
...>   |> Yog.add_node(2, "b")
...>   |> Yog.add_edge(1, 2, 10)
iex> mapped = Yog.map_nodes(graph, &String.upcase/1)
iex> mapped.nodes[1]
"A"

@spec merge(graph(), graph()) :: graph()

Merges two graphs. Combines nodes and edges from both graphs.

Example

iex> {:ok, g1} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> {:ok, g2} =
...>   Yog.directed()
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge(2, 3, 20)
iex> merged = Yog.merge(g1, g2)
iex> length(Yog.all_nodes(merged))
3

@spec neighbor_ids(graph(), node_id()) :: [node_id()]

Returns all neighbor node IDs (without weights).

Example

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10) |> Yog.add_edge_ensure(1, 3, 20)
iex> Yog.neighbor_ids(graph, 1) |> Enum.sort()
[2, 3]

@spec neighbors(graph(), node_id()) :: [{node_id(), term()}]

Gets all nodes connected to the given node, regardless of direction. For undirected graphs, this is equivalent to successors. For directed graphs, this combines successors and predecessors.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(1, 2, 10)
...>   |> Yog.add_edge_ensure(3, 1, 20)
iex> length(Yog.neighbors(graph, 1))
2

@spec new(:directed | :undirected) :: graph()

Creates a new empty graph of the specified type.

Example

iex> graph = Yog.new(:directed)
iex> Yog.graph?(graph)
true

iex> graph = Yog.new(:undirected)
iex> Yog.graph?(graph)
true

@spec node(graph(), node_id()) :: term() | nil

Gets the data associated with a node.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A")
iex> Yog.node(graph, 1)
"A"

@spec node_count(graph()) :: integer()

Returns the number of nodes in the graph.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> Yog.node_count(graph)
2

@spec node_ids(graph()) :: [node_id()]

Returns all unique node IDs in the graph.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> Yog.node_ids(graph) |> Enum.sort()
[1, 2]

@spec order(graph()) :: integer()

Returns the number of nodes in the graph (graph order).

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
iex> Yog.order(graph)
2

@spec out_degree(graph(), node_id()) :: non_neg_integer()

Returns the out-degree of a node (number of outgoing edges).

@spec predecessors(graph(), node_id()) :: [{node_id(), term()}]

Gets nodes you came FROM to reach the given node (predecessors). Returns a list of tuples containing the source node ID and edge data.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> Yog.predecessors(graph, 2)
[{1, 10}]

@spec regular?(graph(), integer()) :: boolean()

Returns true if the graph is k-regular (every node has degree exactly k).

@spec remove_edge(graph(), node_id(), node_id()) :: graph()

Removes an edge from the graph.

Example

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10) |> Yog.remove_edge(1, 2)
iex> Yog.has_edge?(graph, 1, 2)
false

@spec remove_node(graph(), node_id()) :: graph()

Removes a node and all its connected edges.

Example

iex> graph = Yog.directed() |> Yog.add_node(1, "A") |> Yog.remove_node(1)
iex> Yog.has_node?(graph, 1)
false

@spec subgraph(graph(), [node_id()]) :: graph()

Extracts a subgraph keeping only the specified nodes.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 20}])
iex> subgraph = Yog.subgraph(graph, [1, 2])
iex> Yog.all_nodes(subgraph)
[1, 2]

@spec successor_ids(graph(), node_id()) :: [node_id()]

Gets node IDs you can travel TO from the given node. Convenient for traversal algorithms that only need the IDs.

Example

iex> graph =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edge_ensure(1, 2, 10)
...>   |> Yog.add_edge_ensure(1, 3, 20)
iex> Yog.successor_ids(graph, 1) |> Enum.sort()
[2, 3]

@spec successors(graph(), node_id()) :: [{node_id(), term()}]

Gets nodes you can travel TO from the given node (successors). Returns a list of tuples containing the destination node ID and edge data.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> Yog.successors(graph, 1)
[{2, 10}]

Exports a graph to an adjacency list.

Delegates to Yog.IO.List.to_list/1.

Example

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
iex> Yog.to_adjacency_list(graph)
[{1, [{2, 5}]}, {2, [{1, 5}]}]

Exports a graph to an adjacency list string.

Delegates to Yog.IO.List.to_string/2.

Example

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
iex> Yog.to_adjacency_list_string(graph)
"1: 2\n2: 1"

Exports a graph to an adjacency matrix representation.

Delegates to Yog.IO.Matrix.to_matrix/1.

Example

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
iex> {_nodes, matrix} = Yog.to_adjacency_matrix(graph)
iex> matrix
[[0, 5], [5, 0]]

@spec to_directed(graph()) :: graph()

Converts an undirected graph to directed.

Example

iex> {:ok, graph} =
...>   Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> directed = Yog.to_directed(graph)
iex> Yog.successors(directed, 1)
[{2, 10}]

@spec to_undirected(graph(), (any(), any() -> any())) :: graph()

Converts a directed graph to undirected.

When there are edges in both directions, the resolve_fn is called to combine the weights.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 1, 20}])
iex> undirected = Yog.to_undirected(graph, fn a, b -> min(a, b) end)
iex> length(Yog.successors(undirected, 1))
1

@spec transpose(graph()) :: graph()

Returns a graph where all edges have been reversed.

Example

iex> {:ok, graph} =
...>   Yog.directed()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_edge(1, 2, 10)
iex> transposed = Yog.transpose(graph)
iex> Yog.successors(transposed, 2)
[{1, 10}]

@spec tree?(graph()) :: boolean()

Returns true if the graph is a tree (undirected, connected, and acyclic).

@spec type(graph()) :: graph_type()

Gets the type of the graph (:directed or :undirected).

Example

iex> graph = Yog.directed()
iex> Yog.type(graph)
:directed

@spec undirected() :: graph()

Creates a new empty undirected graph.

This is a convenience function that's equivalent to Yog.new(:undirected), but requires only a single import.

Example

iex> graph = Yog.undirected()
iex> Yog.graph?(graph)
true

@spec update_edge(graph(), node_id(), node_id(), term(), (term() -> term())) ::
  graph()

Updates a specific edge's weight/metadata.

@spec update_node(graph(), node_id(), term(), (term() -> term())) :: graph()

Updates a specific node's data using an updater function.