%% %% %CopyrightBegin% %% %% Copyright Ericsson AB 2000-2016. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. %% You may obtain a copy of the License at %% %% http://www.apache.org/licenses/LICENSE-2.0 %% %% Unless required by applicable law or agreed to in writing, software %% distributed under the License is distributed on an "AS IS" BASIS, %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %% See the License for the specific language governing permissions and %% limitations under the License. %% %% %CopyrightEnd% %% -module(digraph_utils_SUITE). %%-define(debug, true). -ifdef(debug). -define(line, put(line, ?LINE), ). -else. -include_lib("common_test/include/ct.hrl"). -endif. -export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1, init_per_group/2,end_per_group/2]). -export([simple/1, loop/1, isolated/1, topsort/1, subgraph/1, condensation/1, tree/1]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% suite() -> [{ct_hooks,[ts_install_cth]}]. all() -> [simple, loop, isolated, topsort, subgraph, condensation, tree]. groups() -> []. init_per_suite(Config) -> Config. end_per_suite(_Config) -> ok. init_per_group(_GroupName, Config) -> Config. end_per_group(_GroupName, Config) -> Config. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% simple(Config) when is_list(Config) -> G = digraph:new(), add_vertices(G, [a]), add_edges(G, [{b,c},{b,d},{e,f},{f,g},{g,e},{h,h},{i,i},{i,j}]), 10 = length(digraph_utils:postorder(G)), 10 = length(digraph_utils:preorder(G)), ok = evall(digraph_utils:components(G), [[a],[b,c,d],[e,f,g],[h],[i,j]]), ok = evall(digraph_utils:strong_components(G), [[a],[b],[c],[d],[e,f,g],[h],[i],[j]]), ok = evall(digraph_utils:cyclic_strong_components(G), [[e,f,g],[h],[i]]), true = path(G, e, e), false = path(G, e, j), false = path(G, a, a), false = digraph_utils:topsort(G), false = digraph_utils:is_acyclic(G), ok = eval(digraph_utils:loop_vertices(G), [h,i]), ok = eval(digraph_utils:reaching([e], G), [e,f,g]), ok = eval(digraph_utils:reaching_neighbours([e], G), [e,f,g]), ok = eval(digraph_utils:reachable([e], G), [e,f,g]), ok = eval(digraph_utils:reachable_neighbours([e], G), [e,f,g]), ok = eval(digraph_utils:reaching([b], G), [b]), ok = eval(digraph_utils:reaching_neighbours([b], G), []), ok = eval(digraph_utils:reachable([b], G), [b,c,d]), ok = eval(digraph_utils:reachable_neighbours([b], G), [c,d]), ok = eval(digraph_utils:reaching([h], G), [h]), ok = eval(digraph_utils:reaching_neighbours([h], G), [h]), ok = eval(digraph_utils:reachable([h], G), [h]), ok = eval(digraph_utils:reachable_neighbours([h], G), [h]), ok = eval(digraph_utils:reachable([e,f], G), [e,f,g]), ok = eval(digraph_utils:reachable_neighbours([e,f], G), [e,f,g]), ok = eval(digraph_utils:reachable([h,h,h], G), [h]), true = digraph:delete(G), ok. loop(Config) when is_list(Config) -> G = digraph:new(), add_vertices(G, [a,b]), add_edges(G, [{a,a},{b,b}]), ok = evall(digraph_utils:components(G), [[a],[b]]), ok = evall(digraph_utils:strong_components(G), [[a],[b]]), ok = evall(digraph_utils:cyclic_strong_components(G), [[a],[b]]), [_,_] = digraph_utils:topsort(G), false = digraph_utils:is_acyclic(G), ok = eval(digraph_utils:loop_vertices(G), [a,b]), [_,_] = digraph_utils:preorder(G), [_,_] = digraph_utils:postorder(G), ok = eval(digraph_utils:reaching([b], G), [b]), ok = eval(digraph_utils:reaching_neighbours([b], G), [b]), ok = eval(digraph_utils:reachable([b], G), [b]), ok = eval(digraph_utils:reachable_neighbours([b], G), [b]), true = path(G, a, a), true = digraph:delete(G), ok. isolated(Config) when is_list(Config) -> G = digraph:new(), add_vertices(G, [a,b]), ok = evall(digraph_utils:components(G), [[a],[b]]), ok = evall(digraph_utils:strong_components(G), [[a],[b]]), ok = evall(digraph_utils:cyclic_strong_components(G), []), [_,_] = digraph_utils:topsort(G), true = digraph_utils:is_acyclic(G), ok = eval(digraph_utils:loop_vertices(G), []), [_,_] = digraph_utils:preorder(G), [_,_] = digraph_utils:postorder(G), ok = eval(digraph_utils:reaching([b], G), [b]), ok = eval(digraph_utils:reaching_neighbours([b], G), []), ok = eval(digraph_utils:reachable([b], G), [b]), ok = eval(digraph_utils:reachable_neighbours([b], G), []), false = path(G, a, a), true = digraph:delete(G), ok. topsort(Config) when is_list(Config) -> G = digraph:new(), add_edges(G, [{a,b},{b,c},{c,d},{d,e},{e,f}]), ok = eval(digraph_utils:topsort(G), [a,b,c,d,e,f]), true = digraph:delete(G), ok. subgraph(Config) when is_list(Config) -> G = digraph:new([acyclic]), 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}]), add_vertices(G, [{b,bl},{f,fl}]), SG = digraph_utils:subgraph(G, [u1,b,c,u2,f,g,i,u3]), [b,c,f,g,i] = lists:sort(digraph:vertices(SG)), {b,bl} = digraph:vertex(SG, b), {c,[]} = digraph:vertex(SG, c), {fg,f,g,fgl} = digraph:edge(SG, fg), {fg2,f,g,fgl2} = digraph:edge(SG, fg2), {_, {_, acyclic}} = lists:keysearch(cyclicity, 1, digraph:info(SG)), true = digraph:delete(SG), SG1 = digraph_utils:subgraph(G, [f, g, h], [{type, []}, {keep_labels, false}]), [f,g,h] = lists:sort(digraph:vertices(SG1)), {f,[]} = digraph:vertex(SG1, f), {fg,f,g,[]} = digraph:edge(SG1, fg), {_, {_, cyclic}} = lists:keysearch(cyclicity, 1, digraph:info(SG1)), true = digraph:delete(SG1), SG2 = digraph_utils:subgraph(G, [f, g, h], [{type, [acyclic]}, {keep_labels, true}]), [f,g,h] = lists:sort(digraph:vertices(SG2)), {f,fl} = digraph:vertex(SG2, f), {fg,f,g,fgl} = digraph:edge(SG2, fg), {_, {_, acyclic}} = lists:keysearch(cyclicity, 1, digraph:info(SG2)), true = digraph:delete(SG2), {'EXIT',{badarg,_}} = (catch digraph_utils:subgraph(G, [f], [{invalid, opt}])), {'EXIT',{badarg,_}} = (catch digraph_utils:subgraph(G, [f], [{keep_labels, not_Bool}])), {'EXIT',{badarg,_}} = (catch digraph_utils:subgraph(G, [f], [{type, not_type}])), {'EXIT',{badarg,_}} = (catch digraph_utils:subgraph(G, [f], [{type, [not_type]}])), {'EXIT',{badarg,_}} = (catch digraph_utils:subgraph(G, [f], not_a_list)), true = digraph:delete(G), ok. condensation(Config) when is_list(Config) -> G = digraph:new([]), 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}]), add_vertices(G, [q]), CG = digraph_utils:condensation(G), Vs = sort_2(digraph:vertices(CG)), [[b],[c],[d],[e,f,g],[h],[i,j],[q]] = Vs, Fun = fun(E) -> {_E, V1, V2, _L} = digraph:edge(CG, E), {lists:sort(V1), lists:sort(V2)} end, Es = lists:map(Fun, digraph:edges(CG)), [{[b],[c]},{[b],[d]}] = lists:sort(Es), true = digraph:delete(CG), true = digraph:delete(G), ok. %% OTP-7081 tree(Config) when is_list(Config) -> false = is_tree([], []), true = is_tree([a], []), false = is_tree([a,b], []), true = is_tree([{a,b}]), false = is_tree([{a,b},{b,a}]), true = is_tree([{a,b},{a,c},{b,d},{b,e}]), false = is_tree([{a,b},{a,c},{b,d},{b,e}, {d,e}]), false = is_tree([{a,b},{a,c},{b,d},{b,e}, {b,e}]), true = is_tree([{a,c},{c,b}]), true = is_tree([{b,a},{c,a}]), %% Parallel edges. Acyclic and with one componets %% (according to the digraph module). false = is_tree([{a,b},{a,b}]), no = arborescence_root([], []), {yes, a} = arborescence_root([a], []), no = arborescence_root([a,b], []), {yes, a} = arborescence_root([{a,b}]), no = arborescence_root([{a,b},{b,a}]), {yes, a} = arborescence_root([{a,b},{a,c},{b,d},{b,e}]), no = arborescence_root([{a,b},{a,c},{b,d},{b,e}, {d,e}]), no = arborescence_root([{a,b},{a,c},{b,d},{b,e}, {b,e}]), {yes, a} = arborescence_root([{a,c},{c,b}]), no = arborescence_root([{b,a},{c,a}]), false = is_arborescence([], []), true = is_arborescence([a], []), false = is_arborescence([a,b], []), true = is_arborescence([{a,b}]), false = is_arborescence([{a,b},{b,a}]), true = is_arborescence([{a,b},{a,c},{b,d},{b,e}]), false = is_arborescence([{a,b},{a,c},{b,d},{b,e}, {d,e}]), false = is_arborescence([{a,b},{a,c},{b,d},{b,e}, {b,e}]), true = is_arborescence([{a,c},{c,b}]), false = is_arborescence([{b,a},{c,a}]), %% Parallel edges. 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.