Current section
45 Versions
Jump to
Current section
45 Versions
Compare versions
11
files changed
+360
additions
-135
deletions
| @@ -1,6 +1,6 @@ | |
| 1 1 | {<<"links">>,[{<<"GitHub">>,<<"https://github.com/bokner/bitgraph">>}]}. |
| 2 2 | {<<"name">>,<<"bitgraph">>}. |
| 3 | - {<<"version">>,<<"0.3.3">>}. |
| 3 | + {<<"version">>,<<"0.3.4">>}. |
| 4 4 | {<<"description">>,<<"Mutable directed graph">>}. |
| 5 5 | {<<"elixir">>,<<"~> 1.18">>}. |
| 6 6 | {<<"app">>,<<"bitgraph">>}. |
| @@ -10,22 +10,27 @@ | |
| 10 10 | <<"lib/algorithms/algorithms.ex">>,<<"lib/algorithms/scc">>, |
| 11 11 | <<"lib/algorithms/scc/kozaraju.ex">>,<<"lib/algorithms/scc/tarjan.ex">>, |
| 12 12 | <<"lib/algorithms/scc/utils.ex">>,<<"lib/edge.ex">>,<<"lib/utils">>, |
| 13 | - <<"lib/utils/array.ex">>,<<"lib/utils/common.ex">>,<<"lib/utils/stack.ex">>, |
| 14 | - <<"lib/traversal">>,<<"lib/traversal/dfs.ex">>,<<"lib/traversal/utils.ex">>, |
| 15 | - <<"lib/bitgraph.ex">>,<<"lib/adjacency.ex">>,<<"src">>, |
| 16 | - <<"src/bit_vector.erl">>,<<"test">>,<<"test/neighbor_finder_test.exs">>, |
| 17 | - <<"test/algorithms">>,<<"test/algorithms/strong_components_test.exs">>, |
| 13 | + <<"lib/utils/common.ex">>,<<"lib/traversal">>, |
| 14 | + <<"lib/traversal/bfs.ex.wip">>,<<"lib/traversal/dfs.ex">>, |
| 15 | + <<"lib/traversal/utils.ex">>,<<"lib/bitgraph.ex">>,<<"lib/adjacency.ex">>, |
| 16 | + <<"src">>,<<"src/bit_vector.erl">>,<<"test">>, |
| 17 | + <<"test/neighbor_finder_test.exs">>,<<"test/algorithms">>, |
| 18 | + <<"test/algorithms/strong_components_test.exs">>, |
| 18 19 | <<"test/algorithms/algorithms_test.exs">>, |
| 19 20 | <<"test/algorithms/bipartite_matching">>, |
| 20 21 | <<"test/algorithms/bipartite_matching/kuhn_test.exs">>,<<"test/utils">>, |
| 21 | - <<"test/utils/stack_test.exs">>,<<"test/adjacency_test.exs">>, |
| 22 | - <<"test/traversal">>,<<"test/traversal/dfs_test.exs">>, |
| 23 | - <<"test/test_helper.exs">>,<<"test/bitgraph_test.exs">>, |
| 24 | - <<"test/common_test.exs">>,<<".formatter.exs">>,<<"mix.exs">>, |
| 25 | - <<"README.md">>,<<"LICENSE">>]}. |
| 22 | + <<"test/adjacency_test.exs">>,<<"test/traversal">>, |
| 23 | + <<"test/traversal/dfs_test.exs">>,<<"test/test_helper.exs">>, |
| 24 | + <<"test/bitgraph_test.exs">>,<<"test/common_test.exs">>, |
| 25 | + <<".formatter.exs">>,<<"mix.exs">>,<<"README.md">>,<<"LICENSE">>]}. |
| 26 26 | {<<"licenses">>,[<<"MIT">>]}. |
| 27 27 | {<<"requirements">>, |
| 28 | - [[{<<"name">>,<<"arrays">>}, |
| 28 | + [[{<<"name">>,<<"inplace">>}, |
| 29 | + {<<"app">>,<<"inplace">>}, |
| 30 | + {<<"optional">>,false}, |
| 31 | + {<<"requirement">>,<<"~> 0.1">>}, |
| 32 | + {<<"repository">>,<<"hexpm">>}], |
| 33 | + [{<<"name">>,<<"arrays">>}, |
| 29 34 | {<<"app">>,<<"arrays">>}, |
| 30 35 | {<<"optional">>,false}, |
| 31 36 | {<<"requirement">>,<<"~> 2.1">>}, |
| @@ -1,6 +1,7 @@ | |
| 1 1 | defmodule BitGraph.Algorithm do |
| 2 | - alias BitGraph.{Dfs, Array, E, V} |
| 2 | + alias BitGraph.{Dfs, E, V} |
| 3 3 | alias BitGraph.Algorithm.{SCC, Matching.Kuhn} |
| 4 | + alias InPlace.Array |
| 4 5 | |
| 5 6 | @callback preprocess(BitGraph.t(), Keyword.t()) :: Keyword.t() |
| 6 7 | @callback run(BitGraph.t(), Keyword.t()) :: any() |
| @@ -7,7 +7,7 @@ defmodule BitGraph.Algorithm.Matching.Kuhn do | |
| 7 7 | """ |
| 8 8 | |
| 9 9 | alias BitGraph.V |
| 10 | - alias BitGraph.Array |
| 10 | + alias InPlace.Array |
| 11 11 | alias Iter.Iterable |
| 12 12 | import BitGraph.Common |
| 13 13 | |
| @@ -198,8 +198,8 @@ defmodule BitGraph.Algorithm.Matching.Kuhn do | |
| 198 198 | |
| 199 199 | %{ |
| 200 200 | left_partition: left_partition, |
| 201 | - used: Array.new(allocated), |
| 202 | - match: Array.new(allocated), |
| 201 | + used: Array.new(allocated, 0), |
| 202 | + match: Array.new(allocated, 0), |
| 203 203 | match_count: :counters.new(1, [:atomics]), |
| 204 204 | max_matching_size: MapSet.size(left_partition), |
| 205 205 | required_size: Keyword.get(opts, :required_size) |
| @@ -235,7 +235,7 @@ defmodule BitGraph.Algorithm.Matching.Kuhn do | |
| 235 235 | {:cont, acc} |
| 236 236 | else |
| 237 237 | case get_match(state, candidate_vertex_idx) do |
| 238 | - value when value == 0 -> |
| 238 | + 0 -> |
| 239 239 | {:cont, |
| 240 240 | {c, |
| 241 241 | (!adjacent_to_left_partition?(graph, candidate_vertex_idx, left_partition_indices) && |
| @@ -1,8 +1,10 @@ | |
| 1 1 | defmodule BitGraph.Algorithm.SCC.Tarjan do |
| 2 | - alias BitGraph.{Dfs, Array, Stack, Algorithm} |
| 2 | + alias BitGraph.{Dfs, Algorithm} |
| 3 3 | |
| 4 4 | import BitGraph.Algorithm.SCC.Utils |
| 5 5 | |
| 6 | + alias InPlace.{Array, Stack} |
| 7 | + |
| 6 8 | import BitGraph.Algorithm |
| 7 9 | |
| 8 10 | @behaviour Algorithm |
| @@ -89,8 +91,8 @@ defmodule BitGraph.Algorithm.SCC.Tarjan do | |
| 89 91 | |
| 90 92 | %{ |
| 91 93 | stack: Stack.new(num_vertices), |
| 92 | - on_stack: Array.new(num_vertices), |
| 93 | - lowest: Array.new(num_vertices), |
| 94 | + on_stack: Array.new(num_vertices, 0), |
| 95 | + lowest: Array.new(num_vertices, 0), |
| 94 96 | sccs: nil |
| 95 97 | } |
| 96 98 | end |
| @@ -0,0 +1,322 @@ | |
| 1 | + defmodule BitGraph.Bfs do |
| 2 | + alias BitGraph.{V, Algorithm} |
| 3 | + alias BitGraph.Neighbor, as: N |
| 4 | + alias InPlace.Array |
| 5 | + import BitGraph.Common |
| 6 | + |
| 7 | + @moduledoc """ |
| 8 | + Breadth-first search. |
| 9 | + The implementation roughly follows |
| 10 | + https://cp-algorithms.com/graph/breadth-first-search.html |
| 11 | + """ |
| 12 | + |
| 13 | + @behaviour Algorithm |
| 14 | + |
| 15 | + @white_vertex 0 |
| 16 | + @gray_vertex 1 |
| 17 | + @black_vertex 2 |
| 18 | + |
| 19 | + @doc """ |
| 20 | + Options: |
| 21 | + - `vertices` - list of vertex indices (not vertex ids!) or :all (default) |
| 22 | + - `state` - initial state |
| 23 | + - `direction` - direction of edges connected to current vertex |
| 24 | + - :forward - out-edges |
| 25 | + - :reverse - in-edges |
| 26 | + - :both - all edges |
| 27 | + - `process_vertex_fun` callback for processing vertices |
| 28 | + - `process_edge_fun` - callback for processing edges |
| 29 | + - `edge_process_order` - whether the (bfs tree) edge processing will be made |
| 30 | + - before (:preorder, default) |
| 31 | + - after (:postorder) |
| 32 | + - before and after (:both) |
| 33 | + """ |
| 34 | + |
| 35 | + @impl true |
| 36 | + def run(graph, opts \\ []) do |
| 37 | + graph = update_graph_opts(graph, opts) |
| 38 | + vertices = Keyword.get(opts, :vertices, []) |
| 39 | + initial_state = Keyword.get(opts, :state) || ( |
| 40 | + case vertices do |
| 41 | + [] -> nil |
| 42 | + list when is_struct(vertices, MapSet) or is_list(vertices) -> |
| 43 | + Enum.empty?(list) && nil || init_dfs(graph, opts) |
| 44 | + other -> |
| 45 | + throw({:error, {:invalid_vertex_list, other}}) |
| 46 | + end |
| 47 | + ) |
| 48 | + |
| 49 | + Enum.reduce(vertices, initial_state, fn vertex, state_acc -> |
| 50 | + if vertex_color(state_acc, vertex) == @white_vertex do |
| 51 | + ## New component discovered |
| 52 | + dfs_impl(graph, vertex, Map.put(state_acc, :component_top, vertex)) |
| 53 | + else |
| 54 | + state_acc |
| 55 | + end |
| 56 | + end) |
| 57 | + end |
| 58 | + |
| 59 | + defp update_graph_opts(graph, opts) do |
| 60 | + BitGraph.update_opts(graph, opts) |
| 61 | + |> then(fn g -> |
| 62 | + BitGraph.get_opts(g)[:neighbor_finder] && g |
| 63 | + || BitGraph.set_neighbor_finder(g, N.default_neighbor_iterator()) |
| 64 | + end) |
| 65 | + end |
| 66 | + |
| 67 | + @impl true |
| 68 | + def preprocess(graph, opts) do |
| 69 | + vertex_indices = build_vertices(graph, Keyword.get(opts, :vertices, :all)) |
| 70 | + Keyword.put(opts, :vertices, vertex_indices) |
| 71 | + end |
| 72 | + |
| 73 | + defp build_vertices(graph, :all) do |
| 74 | + BitGraph.vertex_indices(graph) |
| 75 | + end |
| 76 | + |
| 77 | + defp build_vertices(_graph, vertex) when is_integer(vertex) do |
| 78 | + [vertex] |
| 79 | + end |
| 80 | + |
| 81 | + defp build_vertices(_graph, vertices) when is_list(vertices) or is_struct(vertices, MapSet) do |
| 82 | + vertices |
| 83 | + end |
| 84 | + |
| 85 | + @impl true |
| 86 | + def postprocess(_graph, result) do |
| 87 | + result |
| 88 | + end |
| 89 | + |
| 90 | + defp init_bfs(graph, opts) do |
| 91 | + max_index = BitGraph.max_index(graph) |
| 92 | + |
| 93 | + %{ |
| 94 | + component_top: nil, |
| 95 | + direction: Keyword.get(opts, :direction, :forward), |
| 96 | + process_edge_fun: |
| 97 | + Keyword.get(opts, :process_edge_fun, default_process_edge_fun()) |
| 98 | + |> normalize_process_edge_fun(), |
| 99 | + process_vertex_fun: |
| 100 | + Keyword.get(opts, :process_vertex_fun, default_process_vertex_fun()) |
| 101 | + |> normalize_process_vertex_fun(), |
| 102 | + ## Order of processing for 'tree' edge: |
| 103 | + ## :preorder - before DFS call |
| 104 | + ## :postorder - after DFS call |
| 105 | + ## :both - before and after DFS call |
| 106 | + edge_process_order: Keyword.get(opts, :edge_process_order, :preorder), |
| 107 | + ## to track traversal of nodes |
| 108 | + discovered: Array.new(max_index), |
| 109 | + ## to track processing of nodes |
| 110 | + processed: Array.new(max_index), |
| 111 | + parent: Array.new(max_index), |
| 112 | + acc: nil |
| 113 | + } |
| 114 | + end |
| 115 | + |
| 116 | + defp bfs_impl(graph, vertex, %{direction: direction} = state) |
| 117 | + when is_integer(vertex) do |
| 118 | + |
| 119 | + initial_state = init_vertex_processing(state, vertex) |
| 120 | + neighbor_iterator = vertex_neighbors(graph, vertex, direction) |
| 121 | + |
| 122 | + iterate(neighbor_iterator, initial_state, |
| 123 | + fn neighbor, acc -> |
| 124 | + process_edge(graph, acc, vertex, neighbor) |
| 125 | + end) |
| 126 | + |> finalize_vertex_processing(vertex) |
| 127 | + end |
| 128 | + |
| 129 | + defp init_vertex_processing(state, vertex) do |
| 130 | + time = inc_timer(state) |
| 131 | + Array.put(state[:visited], vertex, time) |
| 132 | + process_vertex(state, vertex, :discovered) |
| 133 | + end |
| 134 | + |
| 135 | + defp finalize_vertex_processing(state, vertex) do |
| 136 | + process_vertex(state, vertex, :processed) |
| 137 | + end |
| 138 | + |
| 139 | + defp default_process_vertex_fun() do |
| 140 | + fn %{acc: acc} = _state, _vertex, _edge_type -> |
| 141 | + acc |
| 142 | + end |
| 143 | + end |
| 144 | + |
| 145 | + defp default_process_edge_fun() do |
| 146 | + fn %{acc: acc} = _state, _vertex, _neighbor, _event? -> |
| 147 | + acc |
| 148 | + end |
| 149 | + end |
| 150 | + |
| 151 | + defp process_vertex(%{process_vertex_fun: process_vertex_fun} = state, vertex, event) |
| 152 | + when is_function(process_vertex_fun, 3) do |
| 153 | + Map.put(state, :acc, process_vertex_fun.(state, vertex, event)) |
| 154 | + end |
| 155 | + |
| 156 | + defp process_edge(graph, %{edge_process_order: process_order} = state, vertex, neighbor) do |
| 157 | + case vertex_color(state, neighbor) do |
| 158 | + @black_vertex -> |
| 159 | + ## (vertex, neighbor) is either a cross edge or forward edge |
| 160 | + process_edge_impl( |
| 161 | + state, |
| 162 | + vertex, |
| 163 | + neighbor, |
| 164 | + (time_in(state, vertex) > time_in(state, neighbor) && :cross) || :forward |
| 165 | + ) |
| 166 | + |
| 167 | + @gray_vertex -> |
| 168 | + ## (vertex, neighbor) is a back edge |
| 169 | + process_edge_impl(Map.put(state, :dag, false), vertex, neighbor, :back) |
| 170 | + |
| 171 | + @white_vertex -> |
| 172 | + ## (vertex, neighbor) is a (dfs) tree edge) |
| 173 | + update_parent(state, neighbor, vertex) |
| 174 | + process_tree_edge(graph, state, vertex, neighbor, process_order) |
| 175 | + end |
| 176 | + end |
| 177 | + |
| 178 | + defp update_parent(%{parent: parent_ref} = _state, child, parent) do |
| 179 | + Array.put(parent_ref, child, parent) |
| 180 | + end |
| 181 | + |
| 182 | + ## Function for processing a vertex could be 2-arity (no options) or 3-arity |
| 183 | + defp normalize_process_vertex_fun(process_vertex_fun) when is_function(process_vertex_fun, 2) do |
| 184 | + fn state, vertex, _opts -> process_vertex_fun.(state, vertex) end |
| 185 | + end |
| 186 | + |
| 187 | + defp normalize_process_vertex_fun(process_vertex_fun) when is_function(process_vertex_fun, 3) do |
| 188 | + process_vertex_fun |
| 189 | + end |
| 190 | + |
| 191 | + defp normalize_process_vertex_fun(nil), do: nil |
| 192 | + |
| 193 | + ## Function for processing an edge could be 3-arity (ignoring edge type) or 4-arity |
| 194 | + |
| 195 | + defp normalize_process_edge_fun(process_edge_fun) when is_function(process_edge_fun, 3) do |
| 196 | + fn state, prev_vertex, current_vertex, _edge_type -> |
| 197 | + process_edge_fun.(state, prev_vertex, current_vertex) |
| 198 | + end |
| 199 | + end |
| 200 | + |
| 201 | + defp normalize_process_edge_fun(process_edge_fun) when is_function(process_edge_fun, 4) do |
| 202 | + process_edge_fun |
| 203 | + end |
| 204 | + |
| 205 | + defp normalize_process_edge_fun(nil), do: nil |
| 206 | + |
| 207 | + defp process_edge_impl( |
| 208 | + %{process_edge_fun: process_edge_fun} = state, |
| 209 | + start_vertex, |
| 210 | + end_vertex, |
| 211 | + edge_type |
| 212 | + ) |
| 213 | + when is_function(process_edge_fun, 4) do |
| 214 | + {next_action, acc} = |
| 215 | + case process_edge_fun.(state, start_vertex, end_vertex, edge_type) do |
| 216 | + {:next, acc} -> {:next, acc} |
| 217 | + {:stop, acc} -> {:stop, acc} |
| 218 | + acc -> {:next, acc} |
| 219 | + end |
| 220 | + |
| 221 | + {to_reduce_while_result(next_action), Map.put(state, :acc, acc)} |
| 222 | + end |
| 223 | + |
| 224 | + defp process_tree_edge(graph, state, start_vertex, end_vertex, :preorder) do |
| 225 | + process_edge_impl(state, start_vertex, end_vertex, :tree) |
| 226 | + |> then(fn |
| 227 | + {:halt, state} -> |
| 228 | + {:halt, state} |
| 229 | + |
| 230 | + {:cont, state} -> |
| 231 | + {:cont, dfs_impl(graph, end_vertex, state)} |
| 232 | + end) |
| 233 | + end |
| 234 | + |
| 235 | + defp process_tree_edge(graph, state, start_vertex, end_vertex, :both) do |
| 236 | + process_edge_impl(state, start_vertex, end_vertex, :tree) |
| 237 | + |> then(fn |
| 238 | + {:halt, state} -> |
| 239 | + {:halt, state} |
| 240 | + |
| 241 | + {:cont, state} -> |
| 242 | + dfs_impl(graph, end_vertex, state) |
| 243 | + |> process_edge_impl(start_vertex, end_vertex, :tree) |
| 244 | + end) |
| 245 | + end |
| 246 | + |
| 247 | + defp process_tree_edge(graph, state, start_vertex, end_vertex, :postorder) do |
| 248 | + dfs_impl(graph, end_vertex, state) |
| 249 | + |> process_edge_impl(start_vertex, end_vertex, :tree) |
| 250 | + end |
| 251 | + |
| 252 | + defp to_reduce_while_result(:next) do |
| 253 | + :cont |
| 254 | + end |
| 255 | + |
| 256 | + defp to_reduce_while_result(:stop) do |
| 257 | + :halt |
| 258 | + end |
| 259 | + |
| 260 | + defp to_reduce_while_result(_) do |
| 261 | + :cont |
| 262 | + end |
| 263 | + |
| 264 | + defp vertex_neighbors(graph, vertex, :forward) do |
| 265 | + V.out_neighbors(graph, vertex) |
| 266 | + end |
| 267 | + |
| 268 | + defp vertex_neighbors(graph, vertex, :reverse) do |
| 269 | + V.in_neighbors(graph, vertex) |
| 270 | + end |
| 271 | + |
| 272 | + defp vertex_neighbors(graph, vertex, :both) do |
| 273 | + V.neighbors(graph, vertex) |
| 274 | + end |
| 275 | + |
| 276 | + def acyclic?(state) do |
| 277 | + state.dag |
| 278 | + end |
| 279 | + |
| 280 | + def order(state, :in, order) when order in [:desc, :asc] do |
| 281 | + order_impl(state[:time_in], order) |
| 282 | + end |
| 283 | + |
| 284 | + def order(state, :out, order) when order in [:desc, :asc] do |
| 285 | + order_impl(state[:time_out], order) |
| 286 | + end |
| 287 | + |
| 288 | + defp order_impl(arr_ref, order) do |
| 289 | + arr_ref |
| 290 | + ## Skip vertices with unassigned orders |
| 291 | + |> Array.reduce({[], 1}, fn 0, {list, idx} -> {list, idx + 1} |
| 292 | + el, {list, idx} -> {[{el, idx} | list], idx + 1} |
| 293 | + end) |
| 294 | + |> elem(0) |
| 295 | + |> Enum.sort(order) |
| 296 | + |> Enum.map(fn {_time_out, vertex_idx} -> vertex_idx end) |
| 297 | + end |
| 298 | + |
| 299 | + def parents(%{parent: parents_ref} = _dfs_state) do |
| 300 | + Array.to_list(parents_ref) |
| 301 | + end |
| 302 | + |
| 303 | + def parent(%{parent: parents_ref} = _dfs_state, vertex) do |
| 304 | + Array.get(parents_ref, vertex) |
| 305 | + end |
| 306 | + |
| 307 | + def time_ins(%{time_in: ref} = _dfs_state) do |
| 308 | + Array.to_list(ref) |
| 309 | + end |
| 310 | + |
| 311 | + def time_in(%{time_in: ref} = _dfs_state, vertex) do |
| 312 | + Array.get(ref, vertex) |
| 313 | + end |
| 314 | + |
| 315 | + def time_outs(%{time_out: ref} = _dfs_state) do |
| 316 | + Array.to_list(ref) |
| 317 | + end |
| 318 | + |
| 319 | + def time_out(%{time_out: ref} = _dfs_state, vertex) do |
| 320 | + Array.get(ref, vertex) |
| 321 | + end |
| 322 | + end |
Loading more files…