aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/test/digraph_utils_SUITE.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/stdlib/test/digraph_utils_SUITE.erl')
-rw-r--r--lib/stdlib/test/digraph_utils_SUITE.erl316
1 files changed, 316 insertions, 0 deletions
diff --git a/lib/stdlib/test/digraph_utils_SUITE.erl b/lib/stdlib/test/digraph_utils_SUITE.erl
new file mode 100644
index 0000000000..d6d477b388
--- /dev/null
+++ b/lib/stdlib/test/digraph_utils_SUITE.erl
@@ -0,0 +1,316 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2000-2009. All Rights Reserved.
+%%
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%%
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%%
+%% %CopyrightEnd%
+%%
+-module(digraph_utils_SUITE).
+
+%-define(debug, true).
+-ifdef(debug).
+-define(line, put(line, ?LINE), ).
+-else.
+-include("test_server.hrl").
+-endif.
+
+-export([all/1]).
+
+-export([simple/1, loop/1, isolated/1, topsort/1, subgraph/1,
+ condensation/1, tree/1]).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+all(suite) -> {req, [stdlib], [simple, loop, isolated, topsort,
+ subgraph, condensation, tree]}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+simple(doc) -> [];
+simple(suite) -> [];
+simple(Config) when is_list(Config) ->
+ ?line G = digraph:new(),
+ ?line add_vertices(G, [a]),
+ ?line add_edges(G, [{b,c},{b,d},{e,f},{f,g},{g,e},{h,h},{i,i},{i,j}]),
+ ?line 10 = length(digraph_utils:postorder(G)),
+ ?line 10 = length(digraph_utils:preorder(G)),
+ ?line ok = evall(digraph_utils:components(G),
+ [[a],[b,c,d],[e,f,g],[h],[i,j]]),
+ ?line ok = evall(digraph_utils:strong_components(G),
+ [[a],[b],[c],[d],[e,f,g],[h],[i],[j]]),
+ ?line ok = evall(digraph_utils:cyclic_strong_components(G),
+ [[e,f,g],[h],[i]]),
+ ?line true = path(G, e, e),
+ ?line false = path(G, e, j),
+ ?line false = path(G, a, a),
+ ?line false = digraph_utils:topsort(G),
+ ?line false = digraph_utils:is_acyclic(G),
+ ?line ok = eval(digraph_utils:loop_vertices(G), [h,i]),
+ ?line ok = eval(digraph_utils:reaching([e], G), [e,f,g]),
+ ?line ok = eval(digraph_utils:reaching_neighbours([e], G), [e,f,g]),
+ ?line ok = eval(digraph_utils:reachable([e], G), [e,f,g]),
+ ?line ok = eval(digraph_utils:reachable_neighbours([e], G), [e,f,g]),
+ ?line ok = eval(digraph_utils:reaching([b], G), [b]),
+ ?line ok = eval(digraph_utils:reaching_neighbours([b], G), []),
+ ?line ok = eval(digraph_utils:reachable([b], G), [b,c,d]),
+ ?line ok = eval(digraph_utils:reachable_neighbours([b], G), [c,d]),
+ ?line ok = eval(digraph_utils:reaching([h], G), [h]),
+ ?line ok = eval(digraph_utils:reaching_neighbours([h], G), [h]),
+ ?line ok = eval(digraph_utils:reachable([h], G), [h]),
+ ?line ok = eval(digraph_utils:reachable_neighbours([h], G), [h]),
+ ?line ok = eval(digraph_utils:reachable([e,f], G), [e,f,g]),
+ ?line ok = eval(digraph_utils:reachable_neighbours([e,f], G), [e,f,g]),
+ ?line ok = eval(digraph_utils:reachable([h,h,h], G), [h]),
+ ?line true = digraph:delete(G),
+ ok.
+
+loop(doc) -> [];
+loop(suite) -> [];
+loop(Config) when is_list(Config) ->
+ ?line G = digraph:new(),
+ ?line add_vertices(G, [a,b]),
+ ?line add_edges(G, [{a,a},{b,b}]),
+ ?line ok = evall(digraph_utils:components(G), [[a],[b]]),
+ ?line ok = evall(digraph_utils:strong_components(G), [[a],[b]]),
+ ?line ok = evall(digraph_utils:cyclic_strong_components(G), [[a],[b]]),
+ ?line [_,_] = digraph_utils:topsort(G),
+ ?line false = digraph_utils:is_acyclic(G),
+ ?line ok = eval(digraph_utils:loop_vertices(G), [a,b]),
+ ?line [_,_] = digraph_utils:preorder(G),
+ ?line [_,_] = digraph_utils:postorder(G),
+ ?line ok = eval(digraph_utils:reaching([b], G), [b]),
+ ?line ok = eval(digraph_utils:reaching_neighbours([b], G), [b]),
+ ?line ok = eval(digraph_utils:reachable([b], G), [b]),
+ ?line ok = eval(digraph_utils:reachable_neighbours([b], G), [b]),
+ ?line true = path(G, a, a),
+ ?line true = digraph:delete(G),
+ ok.
+
+isolated(doc) -> [];
+isolated(suite) -> [];
+isolated(Config) when is_list(Config) ->
+ ?line G = digraph:new(),
+ ?line add_vertices(G, [a,b]),
+ ?line ok = evall(digraph_utils:components(G), [[a],[b]]),
+ ?line ok = evall(digraph_utils:strong_components(G), [[a],[b]]),
+ ?line ok = evall(digraph_utils:cyclic_strong_components(G), []),
+ ?line [_,_] = digraph_utils:topsort(G),
+ ?line true = digraph_utils:is_acyclic(G),
+ ?line ok = eval(digraph_utils:loop_vertices(G), []),
+ ?line [_,_] = digraph_utils:preorder(G),
+ ?line [_,_] = digraph_utils:postorder(G),
+ ?line ok = eval(digraph_utils:reaching([b], G), [b]),
+ ?line ok = eval(digraph_utils:reaching_neighbours([b], G), []),
+ ?line ok = eval(digraph_utils:reachable([b], G), [b]),
+ ?line ok = eval(digraph_utils:reachable_neighbours([b], G), []),
+ ?line false = path(G, a, a),
+ ?line true = digraph:delete(G),
+ ok.
+
+topsort(doc) -> [];
+topsort(suite) -> [];
+topsort(Config) when is_list(Config) ->
+ ?line G = digraph:new(),
+ ?line add_edges(G, [{a,b},{b,c},{c,d},{d,e},{e,f}]),
+ ?line ok = eval(digraph_utils:topsort(G), [a,b,c,d,e,f]),
+ ?line true = digraph:delete(G),
+ ok.
+
+subgraph(doc) -> [];
+subgraph(suite) -> [];
+subgraph(Config) when is_list(Config) ->
+ ?line G = digraph:new([acyclic]),
+ ?line add_edges(G, [{b,c},{b,d},{e,f},{f,fg,fgl,g},{f,fg2,fgl2,g},{g,e},
+ {h,h},{i,i},{i,j}]),
+ ?line add_vertices(G, [{b,bl},{f,fl}]),
+ ?line SG = digraph_utils:subgraph(G, [u1,b,c,u2,f,g,i,u3]),
+ ?line [b,c,f,g,i] = lists:sort(digraph:vertices(SG)),
+ ?line {b,bl} = digraph:vertex(SG, b),
+ ?line {c,[]} = digraph:vertex(SG, c),
+ ?line {fg,f,g,fgl} = digraph:edge(SG, fg),
+ ?line {fg2,f,g,fgl2} = digraph:edge(SG, fg2),
+ ?line {_, {_, acyclic}} = lists:keysearch(cyclicity, 1, digraph:info(SG)),
+ ?line true = digraph:delete(SG),
+
+ ?line SG1 = digraph_utils:subgraph(G, [f, g, h],
+ [{type, []}, {keep_labels, false}]),
+ ?line [f,g,h] = lists:sort(digraph:vertices(SG1)),
+ ?line {f,[]} = digraph:vertex(SG1, f),
+ ?line {fg,f,g,[]} = digraph:edge(SG1, fg),
+ ?line {_, {_, cyclic}} = lists:keysearch(cyclicity, 1, digraph:info(SG1)),
+ ?line true = digraph:delete(SG1),
+
+ ?line SG2 = digraph_utils:subgraph(G, [f, g, h],
+ [{type, [acyclic]},
+ {keep_labels, true}]),
+ ?line [f,g,h] = lists:sort(digraph:vertices(SG2)),
+ ?line {f,fl} = digraph:vertex(SG2, f),
+ ?line {fg,f,g,fgl} = digraph:edge(SG2, fg),
+ ?line {_, {_, acyclic}} = lists:keysearch(cyclicity, 1, digraph:info(SG2)),
+ ?line true = digraph:delete(SG2),
+
+ ?line {'EXIT',{badarg,_}} =
+ (catch digraph_utils:subgraph(G, [f], [{invalid, opt}])),
+ ?line {'EXIT',{badarg,_}} =
+ (catch digraph_utils:subgraph(G, [f], [{keep_labels, not_Bool}])),
+ ?line {'EXIT',{badarg,_}} =
+ (catch digraph_utils:subgraph(G, [f], [{type, not_type}])),
+ ?line {'EXIT',{badarg,_}} =
+ (catch digraph_utils:subgraph(G, [f], [{type, [not_type]}])),
+ ?line {'EXIT',{badarg,_}} =
+ (catch digraph_utils:subgraph(G, [f], not_a_list)),
+
+ ?line true = digraph:delete(G),
+
+ ok.
+
+condensation(doc) -> [];
+condensation(suite) -> [];
+condensation(Config) when is_list(Config) ->
+ ?line G = digraph:new([]),
+ ?line add_edges(G, [{b,c},{b,d},{e,f},{f,fg,fgl,g},{f,fg2,fgl2,g},{g,e},
+ {h,h},{j,i},{i,j}]),
+ ?line add_vertices(G, [q]),
+ ?line CG = digraph_utils:condensation(G),
+ ?line Vs = sort_2(digraph:vertices(CG)),
+ ?line [[b],[c],[d],[e,f,g],[h],[i,j],[q]] = Vs,
+ ?line Fun = fun(E) ->
+ {_E, V1, V2, _L} = digraph:edge(CG, E),
+ {lists:sort(V1), lists:sort(V2)}
+ end,
+ ?line Es = lists:map(Fun, digraph:edges(CG)),
+ ?line [{[b],[c]},{[b],[d]},{[e,f,g],[e,f,g]},{[h],[h]},{[i,j],[i,j]}] =
+ lists:sort(Es),
+ ?line true = digraph:delete(CG),
+ ?line true = digraph:delete(G),
+ ok.
+
+tree(doc) -> ["OTP-7081"];
+tree(suite) -> [];
+tree(Config) when is_list(Config) ->
+ ?line false = is_tree([], []),
+ ?line true = is_tree([a], []),
+ ?line false = is_tree([a,b], []),
+ ?line true = is_tree([{a,b}]),
+ ?line false = is_tree([{a,b},{b,a}]),
+ ?line true = is_tree([{a,b},{a,c},{b,d},{b,e}]),
+ ?line false = is_tree([{a,b},{a,c},{b,d},{b,e}, {d,e}]),
+ ?line false = is_tree([{a,b},{a,c},{b,d},{b,e}, {b,e}]),
+ ?line true = is_tree([{a,c},{c,b}]),
+ ?line true = is_tree([{b,a},{c,a}]),
+ %% Parallel edges. Acyclic and with one componets
+ %% (according to the digraph module).
+ ?line false = is_tree([{a,b},{a,b}]),
+
+ ?line no = arborescence_root([], []),
+ ?line {yes, a} = arborescence_root([a], []),
+ ?line no = arborescence_root([a,b], []),
+ ?line {yes, a} = arborescence_root([{a,b}]),
+ ?line no = arborescence_root([{a,b},{b,a}]),
+ ?line {yes, a} = arborescence_root([{a,b},{a,c},{b,d},{b,e}]),
+ ?line no = arborescence_root([{a,b},{a,c},{b,d},{b,e}, {d,e}]),
+ ?line no = arborescence_root([{a,b},{a,c},{b,d},{b,e}, {b,e}]),
+ ?line {yes, a} = arborescence_root([{a,c},{c,b}]),
+ ?line no = arborescence_root([{b,a},{c,a}]),
+
+ ?line false = is_arborescence([], []),
+ ?line true = is_arborescence([a], []),
+ ?line false = is_arborescence([a,b], []),
+ ?line true = is_arborescence([{a,b}]),
+ ?line false = is_arborescence([{a,b},{b,a}]),
+ ?line true = is_arborescence([{a,b},{a,c},{b,d},{b,e}]),
+ ?line false = is_arborescence([{a,b},{a,c},{b,d},{b,e}, {d,e}]),
+ ?line false = is_arborescence([{a,b},{a,c},{b,d},{b,e}, {b,e}]),
+ ?line true = is_arborescence([{a,c},{c,b}]),
+ ?line false = is_arborescence([{b,a},{c,a}]),
+
+ %% Parallel edges.
+ ?line false = is_arborescence([{a,b},{a,b}]),
+
+ ok.
+
+is_tree(Es) ->
+ is_tree([], Es).
+
+is_tree(Vs, Es) ->
+ gu(Vs, Es, is_tree).
+
+is_arborescence(Es) ->
+ is_arborescence([], Es).
+
+is_arborescence(Vs, Es) ->
+ gu(Vs, Es, is_arborescence).
+
+arborescence_root(Es) ->
+ arborescence_root([], Es).
+
+arborescence_root(Vs, Es) ->
+ gu(Vs, Es, arborescence_root).
+
+gu(Vs, Es, F) ->
+ G = digraph:new(),
+ add_vertices(G, Vs),
+ add_edges(G, Es),
+ Reply = digraph_utils:F(G),
+ true = digraph:delete(G),
+ Reply.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+sort_2(L) ->
+ lists:sort(lists:map(fun(V) -> lists:sort(V) end, L)).
+
+path(G, V1, V2) ->
+ digraph:get_path(G, V1, V2) /= false.
+
+add_vertices(G, Vs) ->
+ lists:foreach(fun({V, Label}) -> digraph:add_vertex(G, V, Label);
+ (V) -> digraph:add_vertex(G, V)
+ end, Vs).
+
+add_edges(G, L) ->
+ Fun = fun({From, To}) ->
+ digraph:add_vertex(G, From),
+ digraph:add_vertex(G, To),
+ digraph:add_edge(G, From, To);
+ ({From, Edge, Label, To}) ->
+ digraph:add_vertex(G, From),
+ digraph:add_vertex(G, To),
+ digraph:add_edge(G, Edge, From, To, Label)
+ end,
+ lists:foreach(Fun, L).
+
+eval(L, E) ->
+ Expected = lists:sort(E),
+ Got = lists:sort(L),
+ if
+ Expected == Got ->
+ ok;
+ true ->
+ not_ok
+ end.
+
+evall(L, E) ->
+ F = fun(L1) -> lists:sort(L1) end,
+ Fun = fun(LL) -> F(lists:map(F, LL)) end,
+
+ Expected = Fun(E),
+ Got = Fun(L),
+ if
+ Expected == Got ->
+ ok;
+ true ->
+ not_ok
+ end.
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 20:52:17 +0000