The R13B03 release.OTP_R13B03

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.