The R13B03 release.OTP_R13B03

1 files changed, 520 insertions, 0 deletions

diff --git a/lib/stdlib/test/digraph_SUITE.erl b/lib/stdlib/test/digraph_SUITE.erl
new file mode 100644
index 0000000000..6ef5b1ddef
--- /dev/null
+++ b/lib/stdlib/test/digraph_SUITE.erl
@@ -0,0 +1,520 @@
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 1996-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_SUITE).
+
+%-define(STANDALONE,1).
+
+-ifdef(STANDALONE).
+-define(line, put(line, ?LINE), ).
+-else.
+-include("test_server.hrl").
+-endif.
+
+-export([all/1]).
+
+-export([opts/1, degree/1, path/1, cycle/1, misc/1, vertices/1,
+	 edges/1, data/1, tickets/1, otp_3522/1, otp_3630/1, otp_8066/1]).
+
+-export([spawn_graph/2]).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+all(suite) -> {req, [stdlib], [opts, degree, path, cycle, misc, tickets]}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+opts(doc) -> [];
+opts(suite) -> [];
+opts(Config) when is_list(Config) ->
+    %% OTP-5985: the 'public' option has been removed
+    ?line {'EXIT',{badarg,_}} = (catch digraph:new([public])),
+    ?line {P2,G2} = spawn_graph([private]),
+    ?line {'EXIT',{badarg,_}} = (catch digraph:add_vertex(G2, x)),
+    ?line kill_graph(P2),
+    ?line {P3,G3} = spawn_graph([protected]),
+    ?line {'EXIT',{badarg,_}} = (catch digraph:add_vertex(G3, x)),
+    ?line kill_graph(P3),
+    ?line Template = [{v1,[v2]}, {v2,[v3]}, {v3,[v4]}, {v4,[]}],
+    ?line G4 = build_graph([], Template),
+    ?line e = digraph:add_edge(G4, e, v4, v1, []),
+    ?line digraph:delete(G4),
+    ?line G5 = build_graph([cyclic], Template),
+    ?line e = digraph:add_edge(G5, e, v4, v1, []),
+    ?line digraph:delete(G5),
+    ?line G6 = build_graph([acyclic], Template),
+    ?line acyclic = info(G6, cyclicity),
+    ?line {error, {bad_edge,_}} = digraph:add_edge(G6, v4, v1),
+    ?line digraph:delete(G6),
+    ok.
+    
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+degree(doc) -> [];
+degree(suite) -> [];
+degree(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x1,[]}, {x2,[x1]}, {x3,[x1,x2]},
+			       {x4,[x1,x2,x3]}, {x5,[x1,x2,x3,x4]}]),
+    %% out degree
+    ?line 0 = digraph:out_degree(G, x1),
+    ?line 1 = digraph:out_degree(G, x2),
+    ?line 2 = digraph:out_degree(G, x3),
+    ?line 3 = digraph:out_degree(G, x4),
+    ?line 4 = digraph:out_degree(G, x5),
+    %% out neighbours
+    ?line [] = check(digraph:out_neighbours(G, x1), []),
+    ?line [] = check(digraph:out_neighbours(G, x2), [x1]),
+    ?line [] = check(digraph:out_neighbours(G, x3), [x1,x2]),
+    ?line [] = check(digraph:out_neighbours(G, x4), [x1,x2,x3]),
+    ?line [] = check(digraph:out_neighbours(G, x5), [x1,x2,x3,x4]),
+
+    %% in degree
+    ?line 4 = digraph:in_degree(G, x1),
+    ?line 3 = digraph:in_degree(G, x2),
+    ?line 2 = digraph:in_degree(G, x3),
+    ?line 1 = digraph:in_degree(G, x4),
+    ?line 0 = digraph:in_degree(G, x5),
+    %% in neighbours
+    ?line [] = check(digraph:in_neighbours(G, x1), [x2,x3,x4,x5]),
+    ?line [] = check(digraph:in_neighbours(G, x2), [x3,x4,x5]),
+    ?line [] = check(digraph:in_neighbours(G, x3), [x4,x5]),
+    ?line [] = check(digraph:in_neighbours(G, x4), [x5]),
+    ?line [] = check(digraph:in_neighbours(G, x5), []),
+    digraph:delete(G),
+    ok.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+path(doc) -> [];
+path(suite) -> [];
+path(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x1,[x2,x3]}, {x2,[x4]}, {x3,[x4]},
+			       {x4,[x5,x6]}, {x5,[x7]}, {x6,[x7]}]),
+    ?line Vi = case digraph:get_path(G, x1, x7) of
+		   [x1,x2,x4,x5,x7] -> digraph:del_vertex(G, x5), x6;
+		   [x1,x2,x4,x6,x7] -> digraph:del_vertex(G, x6), x5;
+		   [x1,x3,x4,x5,x7] -> digraph:del_vertex(G, x5), x6;
+		   [x1,x3,x4,x6,x7] -> digraph:del_vertex(G, x6), x5
+	       end,
+    ?line Vj = case digraph:get_path(G, x1, x7) of
+		   [x1,x2,x4,Vi,x7] -> digraph:del_vertex(G,x2), x3;
+		   [x1,x3,x4,Vi,x7] -> digraph:del_vertex(G,x3), x2
+	       end,
+    ?line [x1,Vj,x4,Vi,x7] = digraph:get_path(G, x1, x7),
+    ?line digraph:del_vertex(G, Vj),
+    ?line false = digraph:get_path(G, x1, x7),
+    ?line [] = check(digraph:vertices(G), [x1,x4,Vi,x7]),
+    digraph:delete(G),
+    ok.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+cycle(doc) -> [];
+cycle(suite) -> [];
+cycle(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x1,[x2,x3]}, {x2,[x4]}, {x3,[x4]},
+			       {x4,[x5,x6]}, {x5,[x7]}, {x6,[x7,x8]},
+			       {x8,[x3,x8]}]), 
+    ?line false = digraph:get_cycle(G, x1),
+    ?line false = digraph:get_cycle(G, x2),
+    ?line false = digraph:get_cycle(G, x5),
+    ?line false = digraph:get_cycle(G, x7),
+    ?line [x3,x4,x6,x8,x3] = digraph:get_cycle(G, x3),
+    ?line [x4,x6,x8,x3,x4] = digraph:get_cycle(G, x4),
+    ?line [x6,x8,x3,x4,x6] = digraph:get_cycle(G, x6),
+    ?line [x8,x3,x4,x6,x8] = digraph:get_cycle(G, x8),
+    ?line digraph:del_vertex(G, x4),
+    ?line [x8] = digraph:get_cycle(G, x8),
+    digraph:delete(G),
+    ok.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+misc(suite) -> [vertices, edges, data].
+
+vertices(doc) -> [];
+vertices(suite) -> [];
+vertices(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x,[]}, {y,[]}]),
+    ?line [] = check(digraph:vertices(G), [x,y]),
+    ?line digraph:del_vertices(G, [x,y]),
+    ?line [] = digraph:vertices(G),
+    ?line digraph:delete(G),
+    ok.
+
+edges(doc) -> [];
+edges(suite) -> [];
+edges(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x, [{exy,y},{exx,x}]},
+			       {y, [{eyx,x}]}
+			      ]),
+    ?line [] = check(digraph:edges(G), [exy, eyx, exx]),
+    ?line [] = check(digraph:out_edges(G, x), [exy,exx]),
+    ?line [] = check(digraph:in_edges(G, x), [eyx,exx]),
+    ?line [] = check(digraph:out_edges(G, y), [eyx]),
+    ?line [] = check(digraph:in_edges(G, y), [exy]),
+    ?line true = digraph:del_edges(G, [exy, eyx, does_not_exist]),
+    ?line [exx] = digraph:edges(G),
+    ?line [] = check(digraph:out_edges(G, x), [exx]),
+    ?line [] = check(digraph:in_edges(G, x), [exx]),
+    ?line [] = check(digraph:out_edges(G, y), []),
+    ?line [] = check(digraph:in_edges(G, y), []),
+    ?line digraph:del_vertices(G, [x,y]),
+    ?line [] = digraph:edges(G),
+    ?line [] = digraph:vertices(G),
+    ?line digraph:delete(G),
+    ok.
+
+data(doc) -> [];
+data(suite) -> [];
+data(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x, [{exy, y}]}, {y, []}]),
+    
+    ?line {x,[]} = digraph:vertex(G, x),
+    ?line {y,[]} = digraph:vertex(G, y),
+    ?line {exy,x,y,[]} = digraph:edge(G, exy),
+
+    ?line digraph:add_edge(G, exy, x, y, {data,x,y}),
+    ?line E = digraph:add_edge(G, x, y, {data,y,x}),
+    ?line digraph:add_vertex(G, x, {any}),
+    ?line digraph:add_vertex(G, y, '_'),
+
+    ?line {x,{any}} = digraph:vertex(G, x),
+    ?line {y,'_'} = digraph:vertex(G, y),
+    ?line {exy,x,y,{data,x,y}} = digraph:edge(G, exy),
+    ?line {E,x,y,{data,y,x}} = digraph:edge(G, E),
+    ?line true = digraph:del_edge(G, E),
+    ?line false = digraph:edge(G, E),
+    ?line true = sane(G),
+    ?line digraph:delete(G),
+    ok.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+tickets(suite) -> [otp_3522, otp_3630, otp_8066].
+
+otp_3522(doc) -> [];
+otp_3522(suite) -> [];
+otp_3522(Config) when is_list(Config) ->
+    ?line G1 = build_graph([acyclic], [{x, []}]),
+    ?line {error, {bad_edge,_}} = digraph:add_edge(G1, x, x),
+    ?line true = digraph:delete(G1),
+
+    ?line G = digraph:new(),
+    ?line 0 = digraph:no_vertices(G),
+    ?line 0 = digraph:no_edges(G),
+    ?line V1 = digraph:add_vertex(G),
+    ?line '$vid' = digraph:add_vertex(G, '$vid'),
+    ?line V2 = digraph:add_vertex(G),
+    ?line '$eid' = digraph:add_edge(G, '$eid', V1, V2, []),
+    ?line E = digraph:add_edge(G, V1, V2),
+    ?line 3 = digraph:no_vertices(G),
+    ?line 2 = digraph:no_edges(G),
+    ?line cyclic = info(G, cyclicity),
+    ?line protected = info(G, protection),
+
+    ?line [] = check(digraph:in_edges(G, V2), ['$eid', E]),
+    ?line [] = check(digraph:out_edges(G, V1), ['$eid', E]),
+    ?line [] = check(digraph:vertices(G), [V1,V2,'$vid']),
+    ?line [] = check(digraph:edges(G), [E, '$eid']),
+    ?line true = sane(G),
+    ?line true = digraph:delete(G),
+    ok.
+
+otp_3630(doc) -> [];
+otp_3630(suite) -> [];
+otp_3630(Config) when is_list(Config) ->
+    ?line G = build_graph([], [{x, [{exy,y},{exx,x}]},
+			       {y, [{eyy,y},{eyx,x}]}
+			      ]),
+    ?line [x,y] = digraph:get_path(G, x, y),
+    ?line [y,x] = digraph:get_path(G, y, x),
+
+    ?line [x,x] = digraph:get_short_path(G, x, x),
+    ?line [y,y] = digraph:get_short_path(G, y, y),
+    ?line true = digraph:delete(G),
+
+    ?line G1 = build_graph([], [{1, [{12,2},{13,3},{11,1}]},
+				{2, [{23,3}]},
+				{3, [{34,4},{35,5}]},
+				{4, [{45,5}]},
+				{5, [{56,6},{57,7}]},
+				{6, [{67,7}]},
+				{7, [{71,1}]}
+			       ]),
+    
+    ?line [1,3,5,7] = digraph:get_short_path(G1, 1, 7),
+    ?line [3,5,7,1,3] = digraph:get_short_cycle(G1, 3),
+    ?line [1,1] = digraph:get_short_cycle(G1, 1),
+    ?line true = digraph:delete(G1),
+
+    F = 0.0, I = round(F),
+    ?line G2 = digraph:new([acyclic]),
+    ?line digraph:add_vertex(G2, F),
+    ?line digraph:add_vertex(G2, I),
+    ?line E = digraph:add_edge(G2, F, I),
+    ?line true = not is_tuple(E),
+    ?line true = sane(G2),
+    ?line true = digraph:delete(G2),
+
+    ok.
+
+otp_8066(doc) -> [];
+otp_8066(suite) -> [];
+otp_8066(Config) when is_list(Config) ->
+    fun() ->
+            D = digraph:new(),
+            V1 = digraph:add_vertex(D),
+            V2 = digraph:add_vertex(D),
+            _ = digraph:add_edge(D, V1, V2),
+            ?line [V1, V2] = digraph:get_path(D, V1, V2),
+            ?line true = sane(D),
+            ?line true = digraph:del_path(D, V1, V2),
+            ?line true = sane(D),
+            ?line false = digraph:get_path(D, V1, V2),
+            ?line true = digraph:del_path(D, V1, V2),
+            ?line true = digraph:delete(D)
+    end(),
+
+    fun() ->
+            D = digraph:new(),
+            V1 = digraph:add_vertex(D),
+            V2 = digraph:add_vertex(D),
+            _ = digraph:add_edge(D, V1, V2),
+            _ = digraph:add_edge(D, V1, V2),
+            _ = digraph:add_edge(D, V1, V1),
+            _ = digraph:add_edge(D, V2, V2),
+            ?line [V1, V2] = digraph:get_path(D, V1, V2),
+            ?line true = sane(D),
+            ?line true = digraph:del_path(D, V1, V2),
+            ?line false = digraph:get_short_path(D, V2, V1),
+
+            ?line true = sane(D),
+            ?line false = digraph:get_path(D, V1, V2),
+            ?line true = digraph:del_path(D, V1, V2),
+            ?line true = digraph:delete(D)
+    end(),
+
+    fun() ->
+            G = digraph:new(),
+            W1 = digraph:add_vertex(G),
+            W2 = digraph:add_vertex(G),
+            W3 = digraph:add_vertex(G),
+            W4 = digraph:add_vertex(G),
+            _ = digraph:add_edge(G,['$e'|0], W1, W2, {}),
+            ?line {error,{bad_vertex, bv}} =
+                digraph:add_edge(G, edge, bv, W1, {}),
+            ?line {error,{bad_vertex, bv}} =
+                digraph:add_edge(G, edge, W1, bv, {}),
+            ?line false = digraph:get_short_cycle(G, W1),
+            ?line {error, {bad_edge,_}} =
+                digraph:add_edge(G,['$e'|0], W3, W4, {}),
+            ?line true = sane(G),
+            ?line true = digraph:delete(G)
+    end(),
+    ok.
+    
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+sane(G) ->
+    sane1(G),
+    erase(sane) =:= undefined.
+
+sane1(G) ->
+    %% etab: {E, V1, V2, Label}
+    %% ntab: {{out,V},E} eller {{in,V},E}
+    %% vtab: {V,Label}
+
+    Es = digraph:edges(G),
+    Vs = digraph:vertices(G),
+    VEs = lists:flatmap(fun(V) -> digraph:edges(G, V) end, Vs),
+    case lists:sort(Es++Es) =:= lists:sort(VEs) of
+        true -> ok;
+        false ->
+            io:format("Bad edges~n", []), put(sane, no)
+    end,
+
+    lists:foreach(
+      fun(E) ->
+              Edge = {E, V1, V2, _L} = digraph:edge(G, E),
+              case {digraph:vertex(G, V1), digraph:vertex(G, V2)} of
+                  {{V1, _}, {V2, _}} -> ok;
+                  _ -> io:format("Missing vertex ~p~n", [Edge]), put(sane, no)
+              end,
+              In = digraph:in_edges(G, V2),
+              case lists:member(E, In) of 
+                  true -> ok;
+                  false ->
+                      io:format("Missing in-neighbour ~p~n", [Edge]),
+                      put(sane, no)
+              end,
+              Out = digraph:out_edges(G, V1),
+              case lists:member(E, Out) of 
+                  true -> ok;
+                  false ->
+                      io:format("Missing out-neighbour ~p~n", [Edge]),
+                      put(sane, no)
+              end
+      end, Es),
+
+    lists:foreach(
+      fun(V) ->
+              InEs = digraph:in_edges(G, V),
+              %% Nu har man *alla* inkanter f�r V
+              lists:foreach(
+                fun(E) ->
+                        case digraph:edge(G, E) of
+                            {E, _, V, _} -> ok;
+                            _ -> 
+                                io:format("Bad in-edge ~p: ~p~n", [V, E]),
+                                put(sane, no)
+                        end
+                end, InEs),
+              OutEs = digraph:out_edges(G, V),
+              lists:foreach(
+                fun(E) ->
+                        case digraph:edge(G, E) of
+                            {E, V, _, _} -> ok;
+                            _ -> 
+                                io:format("Bad out-edge ~p: ~p~n", [V, E]),
+                                put(sane, no)
+                        end
+                end, OutEs)
+      end, Vs),
+    
+    InEs = lists:flatmap(fun(V) -> digraph:in_edges(G, V) end, Vs),
+    OutEs = lists:flatmap(fun(V) -> digraph:out_edges(G, V) end, Vs),
+    lists:foreach(
+      fun(E) ->
+              case digraph:edge(G, E) of
+                  {E, _, _, _} -> ok;
+                  _ -> 
+                      io:format("Unknown edge (neighbour) ~p~n", [E]),
+                      put(sane, no)
+              end
+      end, InEs++OutEs),
+
+    N_in = length(InEs),
+    N_out = length(OutEs),
+    N_edges = digraph:no_edges(G),
+    if 
+        N_in =/= N_out ->
+            io:format("Number of in- and out-edges differs~n", []),
+            put(sane, no);
+        N_in+N_out =/= N_edges+N_edges  ->
+            io:format("Invalid number of edges (~p+~p =/= 2*~p)~n",
+                      [N_in, N_out, N_edges]),
+            put(sane, no);
+        true -> ok
+    end,
+    Edges = [digraph:edge(G, E) || E <- Es],
+    EVs = lists:usort([V || {_, V, _, _} <- Edges] ++
+                      [V || {_, _, V, _} <- Edges]),
+    lists:foreach(
+      fun(V) ->
+              case digraph:vertex(G, V) of
+                  {_, _} -> ok;
+                  false ->
+                      io:format("Unknown vertex in edge: ~p~n", [V]),
+                      put(sane, no)
+              end
+      end, EVs),
+
+    %% sink_vertices and source_vertices were introduced in 2001. They
+    %% are not documented.
+
+    %% sink: a vertex with no outgoing edges
+    SinkVs = [V || V <- Vs, digraph:out_edges(G, V) =:= [] ],
+    case lists:sort(SinkVs) =:=  lists:sort(digraph:sink_vertices(G)) of
+        true -> ok;
+        false -> 
+            io:format("Bad sinks~n"), put(sane, no)
+    end,
+    %% sink: a vertex with no incoming edges
+    SourceVs = [V || V <- Vs, digraph:in_edges(G, V) =:= [] ],
+    case lists:sort(SourceVs) =:=  lists:sort(digraph:source_vertices(G)) of
+        true -> ok;
+        false -> 
+            io:format("Bad sources~n"), put(sane, no)
+    end,
+
+    true.
+
+build_graph(Opts, Gs) ->
+    G = digraph:new(Opts),
+    build_g(G, Gs).
+
+build_g(G, [{V,Ns} | Gs]) ->
+    digraph:add_vertex(G, V),
+    build_ns(G, V, Ns),
+    build_g(G, Gs);
+build_g(G, []) -> 
+    true = sane(G),
+    G.
+
+build_ns(G, V, [{E,W} | Ns]) ->
+    digraph:add_vertex(G, W),
+    digraph:add_edge(G, E, V, W, []),
+    build_ns(G, V, Ns);
+build_ns(G, V, [W | Ns]) ->
+    digraph:add_vertex(G, W),
+    digraph:add_edge(G, V, W),
+    build_ns(G, V, Ns);
+build_ns(_G, _V, []) ->
+    true.
+
+%% Spawn a process that create a graph return {Pid, Graph}
+
+spawn_graph(Opts) ->
+    Pid = spawn(?MODULE, spawn_graph, [self(),Opts]),
+    receive
+	{Pid, G} -> {Pid,G}
+    end.
+
+%% Create a graph and wait for die message
+spawn_graph(Starter, Opts) ->
+    G = digraph:new(Opts),
+    Starter ! {self(), G},
+    receive
+	die -> true
+    end.
+
+info(G, What) ->
+    case lists:keysearch(What, 1, digraph:info(G)) of
+	{value, {What, Value}} -> Value;
+	false -> []
+    end.
+
+%% Kill process created by spawn_graph
+kill_graph(Pid) ->
+    Pid ! die.
+
+check(R0, E0) ->
+    R = lists:sort(R0),
+    E = lists:sort(E0),
+    case R of
+	E ->
+	    [];
+	_ ->
+	    (R -- E) ++ (E -- R)
+    end.