Yog.Flow.MinCutResult (YogEx v0.70.0)

Copy Markdown View Source

Result of minimum cut computation.

A cut partitions the nodes into two sets: the source side (reachable from source) and the sink side (the rest). The cut value equals the total capacity of edges crossing from source side to sink side.

Fields

  • source_side - Set of nodes reachable from source in residual graph
  • sink_side - Set of nodes on the sink side of the cut
  • cut_value - Total capacity of the cut (optional, can be computed from max flow)
  • cut_edges - List of edges in the cut (optional)
  • algorithm - Name of the algorithm used (optional)
  • metadata - Optional metadata

Examples

iex> result = %Yog.Flow.MinCutResult{
...>   source_side: MapSet.new([1, 2]),
...>   sink_side: MapSet.new([3, 4]),
...>   cut_value: 15
...> }
iex> MapSet.size(result.source_side)
2

Summary

Types

t()

Functions

compute_cut_value(min_cut_result, graph)

Compute the cut value from a graph and the partition.

extract_cut_edges(min_cut_result, graph)

Extract the edges that cross the cut.

from_map(map)

Backward compatibility: convert from legacy map format.

in_sink?(min_cut_result, node)

Check if a node is in the sink partition.

in_source?(min_cut_result, node)

Check if a node is in the source partition.

new(source_side, sink_side)

Creates a new min cut result.

new(source_side, sink_side, cut_value)

Creates a new min cut result with cut value.

to_map(min_cut_result)

Convert to legacy map format.

Types

t()

@type t() :: %Yog.Flow.MinCutResult{
  algorithm: atom(),
  cut_edges: [{Yog.Model.node_id(), Yog.Model.node_id()}],
  cut_value: number() | nil,
  metadata: map(),
  sink_side: MapSet.t(Yog.Model.node_id()),
  source_side: MapSet.t(Yog.Model.node_id())
}

Functions

compute_cut_value(min_cut_result, graph)

@spec compute_cut_value(t(), Yog.graph()) :: number()

Compute the cut value from a graph and the partition.

Sums the capacities of edges going from source side to sink side.

extract_cut_edges(min_cut_result, graph)

@spec extract_cut_edges(t(), Yog.graph()) :: [
  {Yog.Model.node_id(), Yog.Model.node_id()}
]

Extract the edges that cross the cut.

Returns list of {source_node, sink_node} pairs.

from_map(map)

@spec from_map(map()) :: t()

Backward compatibility: convert from legacy map format.

in_sink?(min_cut_result, node)

@spec in_sink?(t(), Yog.Model.node_id()) :: boolean()

Check if a node is in the sink partition.

in_source?(min_cut_result, node)

@spec in_source?(t(), Yog.Model.node_id()) :: boolean()

Check if a node is in the source partition.

new(source_side, sink_side)

@spec new(MapSet.t(Yog.Model.node_id()), MapSet.t(Yog.Model.node_id())) :: t()

Creates a new min cut result.

new(source_side, sink_side, cut_value)

@spec new(MapSet.t(Yog.Model.node_id()), MapSet.t(Yog.Model.node_id()), number()) ::
  t()

Creates a new min cut result with cut value.

to_map(min_cut_result)

@spec to_map(t()) :: map()

Convert to legacy map format.