1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
-module(rebar_digraph).
-export([check_graph/2
,restore_graph/1
,store_graph/3
,solve/2
,subgraph/2]).
-include("rebar.hrl").
check_graph(_File, #graph{vsn=?GRAPH_VSN}) ->
ok;
check_graph(File, #graph{vsn=Vsn}) ->
?ABORT("~s file version is incompatible. expected: ~b got: ~b",
[File, ?GRAPH_VSN, Vsn]);
check_graph(File, _) ->
?ABORT("~s file is invalid. Please delete before next run.",
[File]).
restore_graph({Vs, Es}) ->
G = digraph:new(),
lists:foreach(fun({V, LastUpdated}) ->
digraph:add_vertex(G, V, LastUpdated)
end, Vs),
lists:foreach(fun({V1, V2}) ->
digraph:add_edge(G, V1, V2)
end, Es),
G;
restore_graph(File) ->
G = digraph:new(),
case file:read_file(File) of
{ok, Data} ->
try binary_to_term(Data) of
G ->
%% ok = check_erlcinfo(Config, Graph),
#graph{info=Graph} = G,
{Vs, Es} = Graph,
lists:foreach(
fun({V, LastUpdated}) ->
digraph:add_vertex(G, V, LastUpdated)
end, Vs),
lists:foreach(
fun({V1, V2}) ->
digraph:add_edge(G, V1, V2)
end, Es)
catch
error:badarg ->
?ERROR(
"Failed (binary_to_term) to restore rebar info file."
" Discard file.", []),
ok
end;
_Err ->
ok
end,
G.
store_graph(_G, _File, _Modified = false) ->
ok;
store_graph(G, File, _Modified) ->
Vs = lists:map(
fun(V) ->
digraph:vertex(G, V)
end, digraph:vertices(G)),
Es = lists:flatmap(
fun({V, _}) ->
lists:map(
fun(E) ->
{_, V1, V2, _} = digraph:edge(G, E),
{V1, V2}
end, digraph:out_edges(G, V))
end, Vs),
ok = filelib:ensure_dir(File),
Data = term_to_binary(#graph{info={Vs, Es}}, [{compressed, 9}]),
file:write_file(File, Data).
solve(Graph, Vertices) ->
solve(Graph, Vertices, dict:new()).
solve(_Graph, [], Solution) ->
{_, Vertices} = lists:unzip(dict:to_list(Solution)),
Vertices;
solve(Graph, Vertices, Solution) ->
{NV, NS} =
lists:foldl(fun(V, {NewVertices, SolutionAcc}) ->
OutNeighbors = digraph:out_neighbours(Graph, V),
lists:foldl(fun({Key, _}=N, {NewVertices1, SolutionAcc1}) ->
case dict:is_key(Key, SolutionAcc1) orelse
lists:keymember(Key, 1, Vertices) of
true ->
{NewVertices1, SolutionAcc1};
false ->
{[N | NewVertices1], dict:store(Key, N, SolutionAcc1)}
end
end, {NewVertices, SolutionAcc}, OutNeighbors)
end, {[], Solution}, Vertices),
solve(Graph, NV, NS).
subgraph(Graph, Vertices) ->
digraph_utils:subgraph(Graph, Vertices).
|
