From 84adefa331c4159d432d22840663c38f155cd4c1 Mon Sep 17 00:00:00 2001 From: Erlang/OTP Date: Fri, 20 Nov 2009 14:54:40 +0000 Subject: The R13B03 release. --- lib/stdlib/test/digraph_utils_SUITE.erl | 316 ++++++++++++++++++++++++++++++++ 1 file changed, 316 insertions(+) create mode 100644 lib/stdlib/test/digraph_utils_SUITE.erl (limited to 'lib/stdlib/test/digraph_utils_SUITE.erl') 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. -- cgit v1.2.3