Packages

bitgraph

0.1.2
0.4.8 0.4.7 0.4.6 0.4.5 0.4.4 0.4.3 0.4.2 0.4.1 0.3.4 0.3.3 0.3.2 0.3.1 0.2.9 0.2.8 0.2.7 0.2.6 0.2.5 0.2.4 0.2.3 0.2.2 0.2.1 0.1.23 0.1.22 0.1.21 0.1.20 0.1.19 0.1.18 0.1.17 0.1.16 0.1.15 0.1.14 0.1.13 0.1.12 0.1.11 0.1.10 0.1.9 0.1.8 0.1.7 0.1.6 0.1.5 0.1.4 0.1.3 0.1.2 0.1.1 0.1.0

Mutable directed graph

HexDocs

Current section

45 Versions

Jump to
Readme
45 Versions
2 Dependencies
Dependants
Files
Activity
Hide whitespace

Compare versions

9 files changed
+180 additions
-81 deletions
  @@ -1,6 +1,6 @@
1 1 {<<"links">>,[{<<"GitHub">>,<<"https://github.com/bokner/bitgraph">>}]}.
2 2 {<<"name">>,<<"bitgraph">>}.
3 - {<<"version">>,<<"0.1.1">>}.
3 + {<<"version">>,<<"0.1.2">>}.
4 4 {<<"description">>,<<"Mutable directed graph">>}.
5 5 {<<"elixir">>,<<"~> 1.17">>}.
6 6 {<<"app">>,<<"bitgraph">>}.
  @@ -11,9 +11,9 @@
11 11 <<"lib/bitgraph.ex">>,<<"lib/adjacency.ex">>,<<"src">>,
12 12 <<"src/bit_vector.erl">>,<<"test">>,<<"test/adjacency_test.exs">>,
13 13 <<"test/traversal">>,<<"test/traversal/algorithms_test.exs">>,
14 - <<"test/test_helper.exs">>,<<"test/bitgraph_test.exs">>,
15 - <<"test/common_test.exs">>,<<".formatter.exs">>,<<"mix.exs">>,
16 - <<"README.md">>,<<"LICENSE">>]}.
14 + <<"test/traversal/dfs_test.exs">>,<<"test/test_helper.exs">>,
15 + <<"test/bitgraph_test.exs">>,<<"test/common_test.exs">>,
16 + <<".formatter.exs">>,<<"mix.exs">>,<<"README.md">>,<<"LICENSE">>]}.
17 17 {<<"licenses">>,[<<"MIT">>]}.
18 18 {<<"requirements">>,
19 19 [[{<<"name">>,<<"arrays">>},
  @@ -18,10 +18,6 @@ defmodule BitGraph.Adjacency do
18 18 elem(bit_vector, 2)
19 19 end
20 20
21 - def size(adjacency_table) do
22 - :bit_vector.size(adjacency_table)
23 - end
24 -
25 21 def get(
26 22 %{
27 23 bit_vector: bit_vector,
  @@ -97,8 +93,8 @@ defmodule BitGraph.Adjacency do
97 93 MapSet.new()
98 94 end
99 95
100 - def copy(%{bit_vector: {:bit_vector, _, source_ref} = _bit_vector, table_dimension: dimension} = adjacency, edges \\ nil) do
101 - vector_copy = {:bit_vector, _size, target_ref} = allocate(dimension)
96 + def copy(%{bit_vector: {:bit_vector, source_ref} = _bit_vector, table_dimension: dimension} = adjacency, edges \\ nil) do
97 + vector_copy = {:bit_vector, target_ref} = allocate(dimension)
102 98 Map.put(adjacency, :bit_vector, vector_copy)
103 99 |> tap(fn adjacency ->
104 100 if edges do
  @@ -25,21 +25,26 @@ defmodule BitGraph.Algorithms do
25 25 end
26 26
27 27 def components(graph) do
28 - Dfs.run(graph, :all, direction: :both, reduce_fun:
29 - fn %{root: root, acc: acc} = _state, v, _loop? ->
28 + Dfs.run(graph, :all, direction: :both, process_vertex_fun:
29 + fn %{component_top: root, acc: acc} = _state, v ->
30 30 case acc do
31 - nil -> %{root => MapSet.new([v])}
31 + nil -> %{root => MapSet.new([root, v])}
32 32 existing ->
33 - Map.update(existing, root, MapSet.new([v]),
33 + Map.update(existing, root, MapSet.new([root]),
34 34 fn component -> MapSet.put(component, v) end)
35 35 end
36 - end)
36 + end
37 + )
37 38 |> Map.get(:acc)
38 39 |> Map.values()
39 40 end
40 41
41 - ## Kozaraju's
42 - def strong_components(graph, component_handler \\ &Function.identity/1) do
42 + def strong_components(graph, component_handler \\ fn component, _state -> component end) do
43 + kozaraju(graph, component_handler)
44 + end
45 +
46 + ## Kozaraju's SCC algorithm
47 + def kozaraju(graph, component_handler \\ fn component, _state -> component end) do
43 48 graph
44 49 |> Dfs.run()
45 50 |> Dfs.order(:out, :desc)
  @@ -47,29 +52,27 @@ defmodule BitGraph.Algorithms do
47 52 state = Dfs.run(graph, v,
48 53 direction: :reverse,
49 54 state: state_acc,
50 - reduce_fun: fn %{acc: acc} = _state, vertex ->
55 + process_vertex_fun: fn %{acc: acc} = _state, vertex ->
51 56 MapSet.put(acc || MapSet.new(), vertex)
52 57 end
53 58 )
54 59 component = state[:acc]
55 60
56 61 {Map.put(state, :acc, nil),
57 - component && [component_handler.(component) | components_acc] || components_acc}
62 + component && [component_handler.(component, state) | components_acc] || components_acc}
58 63 end)
59 64 |> elem(1)
60 65 end
61 66
62 67 def get_cycle(graph, vertex) when is_integer(vertex) do
63 68 if E.in_degree(graph, vertex) > 0 && E.out_degree(graph, vertex) > 0 do
64 - Dfs.run(graph, vertex, reduce_fun:
65 - fn %{acc: acc} = state, v, loop? ->
66 - if loop? && (v == vertex) do
69 + Dfs.run(graph, vertex, process_edge_fun:
70 + fn state, vertex, _neighbor, {:edge, :back} ->
67 71 {:stop,
68 72 build_cycle(graph, vertex, state[:parent])
69 73 }
70 - else
74 + %{acc: acc} = _state, _vertex, _neighbor, _event ->
71 75 {:next, acc}
72 - end
73 76 end
74 77 )
75 78 |> Map.get(:acc)
  @@ -25,9 +25,9 @@ defmodule BitGraph.Dfs do
25 25 def run(graph, vertices, opts) when is_list(vertices) do
26 26 initial_state = Keyword.get(opts, :state) || init_dfs(graph, hd(vertices), opts)
27 27 Enum.reduce(vertices, initial_state, fn vertex, state_acc ->
28 - state_acc = Map.put(state_acc, :root, vertex)
29 28 if vertex_color(state_acc, vertex) == @white_vertex do
30 - dfs_impl(graph, vertex, state_acc)
29 + ## New component discovered
30 + dfs_impl(graph, vertex, Map.put(state_acc, :component_top, vertex))
31 31 else
32 32 state_acc
33 33 end
  @@ -37,10 +37,13 @@ defmodule BitGraph.Dfs do
37 37 defp init_dfs(graph, root, opts) do
38 38 num_vertices = BitGraph.num_vertices(graph)
39 39 %{
40 - root: root,
40 + component_top: root,
41 41 direction: Keyword.get(opts, :direction, :forward),
42 - reduce_fun: Keyword.get(opts, :reduce_fun, default_reduce_fun())
43 - |> normalize_reduce_fun(),
42 + process_edge_fun: Keyword.get(opts, :process_edge_fun, default_process_edge_fun())
43 + |> normalize_process_edge_fun(),
44 + process_vertex_fun: Keyword.get(opts, :process_vertex_fun, default_process_vertex_fun())
45 + |> normalize_process_vertex_fun(),
46 +
44 47 dag: true,
45 48 timer: :counters.new(1, [:atomics]),
46 49 ## Color (white, black or gray)
  @@ -63,18 +66,10 @@ defmodule BitGraph.Dfs do
63 66 time = inc_timer(state)
64 67 Array.put(state[:time_in], vertex, time)
65 68 Array.put(state[:color], vertex, @gray_vertex)
66 - {_action, initial_state} = apply_reduce(state, vertex)
69 + initial_state = process_vertex(state, vertex)
67 70 Enum.reduce_while(vertex_neighbors(graph, vertex, direction), initial_state, fn
68 71 neighbor, state_acc ->
69 - Array.put(state[:parent], neighbor, vertex)
70 - case vertex_color(state, neighbor) do
71 - @black_vertex -> state_acc
72 - @gray_vertex ->
73 - on_loop(neighbor, state_acc)
74 - @white_vertex ->
75 - dfs_impl(graph, neighbor, state_acc)
76 - end
77 - |> to_reduce_while_result()
72 + process_edge(graph, state_acc, vertex, neighbor)
78 73 end)
79 74 |> tap(fn _ ->
80 75 time = inc_timer(state)
  @@ -92,35 +87,88 @@ defmodule BitGraph.Dfs do
92 87 Array.get(state[:color], vertex)
93 88 end
94 89
95 - defp default_reduce_fun() do
96 - fn %{acc: _acc} = _state, _vertex, _loop? ->
97 - nil
90 + defp default_process_vertex_fun() do
91 + fn %{acc: acc} = _state, _vertex, _edge_type ->
92 + acc
98 93 end
99 94 end
100 95
101 - defp normalize_reduce_fun(reduce_fun) when is_function(reduce_fun, 2) do
102 - fn state, vertex, _loop? -> reduce_fun.(state, vertex) end
96 + defp default_process_edge_fun() do
97 + fn %{acc: acc} = _state, _vertex, _neighbor, _event? ->
98 + acc
99 + end
103 100 end
104 101
105 - defp normalize_reduce_fun(reduce_fun) when is_function(reduce_fun, 3) do
106 - reduce_fun
102 + defp process_vertex(%{process_vertex_fun: process_vertex_fun} = state, vertex, opts \\ []) when is_function(process_vertex_fun, 3) do
103 + acc = process_vertex_fun.(state, vertex, opts)
104 + Map.put(state, :acc, acc)
107 105 end
108 106
109 - defp apply_reduce(%{reduce_fun: reduce_fun} = state, vertex, opts \\ []) when is_function(reduce_fun, 3) do
110 - {next_action, acc} = case reduce_fun.(state, vertex, Keyword.get(opts, :loop, false)) do
107 + defp process_edge(graph, state, vertex, neighbor) do
108 + case vertex_color(state, neighbor) do
109 + @black_vertex ->
110 + ## (vertex, neighbor) is either a cross edge or forward edge
111 + process_edge_impl(state, vertex, neighbor,
112 + time_in(state, vertex) > time_in(state, neighbor) && :cross || :forward)
113 + @gray_vertex ->
114 + ## (vertex, neighbor) is a back edge
115 + process_edge_impl(Map.put(state, :dag, false), vertex, neighbor, :back)
116 + @white_vertex ->
117 + ## (vertex, neighbor) is a (dfs) tree edge)
118 + update_parent(state, neighbor, vertex)
119 + {next_action, state} = process_edge_impl(state, vertex, neighbor, :tree)
120 + {next_action, dfs_impl(graph, neighbor, state)}
121 + end
122 +
123 + end
124 +
125 + defp update_parent(%{parent: parent_ref} = _state, child, parent) do
126 + Array.put(parent_ref, child, parent)
127 + end
128 +
129 +
130 + ## Function for processing a vertex could be 2-arity (no options) or 3-arity
131 + defp normalize_process_vertex_fun(process_vertex_fun) when is_function(process_vertex_fun, 2) do
132 + fn state, vertex, _opts -> process_vertex_fun.(state, vertex) end
133 + end
134 +
135 + defp normalize_process_vertex_fun(process_vertex_fun) when is_function(process_vertex_fun, 3) do
136 + process_vertex_fun
137 + end
138 +
139 + defp normalize_process_vertex_fun(nil), do: nil
140 +
141 + ## Function for processing an edge could be 3-arity (ignoring edge type) or 4-arity
142 +
143 + defp normalize_process_edge_fun(process_edge_fun) when is_function(process_edge_fun, 3) do
144 + fn state, prev_vertex, current_vertex, _edge_type -> process_edge_fun.(state, prev_vertex, current_vertex) end
145 + end
146 +
147 + defp normalize_process_edge_fun(process_edge_fun) when is_function(process_edge_fun, 4) do
148 + process_edge_fun
149 + end
150 +
151 + defp normalize_process_edge_fun(nil), do: nil
152 +
153 + defp process_edge_impl(%{process_edge_fun: process_edge_fun} = state, start_vertex, end_vertex, edge_type) when is_function(process_edge_fun, 4) do
154 + {next_action, acc} = case process_edge_fun.(state, start_vertex, end_vertex, {:edge, edge_type}) do
111 155 {:next, acc} -> {:next, acc}
112 156 {:stop, acc} -> {:stop, acc}
113 157 acc -> {:next, acc}
114 158 end
115 - {next_action, Map.put(state, :acc, acc)}
159 + {to_reduce_while_result(next_action), Map.put(state, :acc, acc)}
116 160 end
117 161
118 - defp to_reduce_while_result(result) do
119 - case result do
120 - {:next, acc} -> {:cont, acc}
121 - {:stop, acc} -> {:halt, acc}
122 - acc -> {:cont, acc}
123 - end
162 + defp to_reduce_while_result(:next) do
163 + :cont
164 + end
165 +
166 + defp to_reduce_while_result(:stop) do
167 + :halt
168 + end
169 +
170 + defp to_reduce_while_result(_) do
171 + :cont
124 172 end
125 173
126 174 defp vertex_neighbors(graph, vertex, :forward) do
  @@ -140,12 +188,6 @@ defmodule BitGraph.Dfs do
140 188 state.dag
141 189 end
142 190
143 - ## The vertex has closed the loop
144 - defp on_loop(vertex, state) do
145 - Map.put(state, :dag, false)
146 - |> apply_reduce(vertex, loop: true)
147 - end
148 -
149 191 def order(state, :in, order) when order in [:desc, :asc] do
150 192 order_impl(state[:time_in], order)
151 193 end
  @@ -161,4 +203,25 @@ defmodule BitGraph.Dfs do
161 203 |> Enum.sort(order)
162 204 |> Enum.map(fn {_time_out, vertex_idx} -> vertex_idx end)
163 205 end
206 +
207 + def parents(%{parent: parents_ref} = _dfs_state) do
208 + Array.to_list(parents_ref)
209 + end
210 +
211 + def time_ins(%{time_in: ref} = _dfs_state) do
212 + Array.to_list(ref)
213 + end
214 +
215 + def time_in(%{time_in: ref} = _dfs_state, vertex) do
216 + Array.get(ref, vertex)
217 + end
218 +
219 + def time_outs(%{time_out: ref} = _dfs_state) do
220 + Array.to_list(ref)
221 + end
222 +
223 + def time_out(%{time_out: ref} = _dfs_state, vertex) do
224 + Array.get(ref, vertex)
225 + end
226 +
164 227 end
  @@ -4,7 +4,7 @@ defmodule Bitgraph.MixProject do
4 4 def project do
5 5 [
6 6 app: :bitgraph,
7 - version: "0.1.1",
7 + version: "0.1.2",
8 8 elixir: "~> 1.17",
9 9 start_permanent: Mix.env() == :prod,
10 10 deps: deps(),
Loading more files…