Packages

bitgraph

0.4.8
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

Files

Jump to
Readme
45 Versions
2 Dependencies
Dependants
Files
Activity
bitgraph test traversal dfs_test.exs
Raw

test/traversal/dfs_test.exs 

defmodule BitGraphTest.Dfs do

  use ExUnit.Case



  import BitGraph.Algorithm



  test "edge classification" do

    tree_edges = [{1, 2}, {2, 4}, {4, 6}, {1, 3}, {3, 5}, {5, 7}, {5, 8}]

    forward_edges = [{1, 8}]

    back_edges = [{6, 2}]

    cross_edges = [{5, 4}]



    all_edges = tree_edges ++ forward_edges ++ back_edges ++ cross_edges

    graph = BitGraph.new() |> BitGraph.add_vertices(1..8) |> BitGraph.add_edges(all_edges)



    type_map =

      dfs(graph,

        process_edge_fun: fn %{acc: acc} = _state, from, to, edge_type ->

          [{edge_type, {from, to}} | acc || []]

        end

      )

      |> Map.get(:acc)

      |> Enum.group_by(fn {type, _edge} -> type end, fn {_type, edge} -> edge end)



    assert_equal_edges(type_map, :tree, tree_edges)

    assert_equal_edges(type_map, :back, back_edges)

    assert_equal_edges(type_map, :forward, forward_edges)

    assert_equal_edges(type_map, :cross, cross_edges)

  end



  test "Dfs on empty graph" do

    graph = BitGraph.new()

    assert dfs(graph) == nil

  end



  defp assert_equal_edges(type_map, type, edges) do

    assert Map.get(type_map, type) |> Enum.sort() == Enum.sort(edges)

  end

end