[LUA]分布式计算中任务拓扑调度

2015/12/14 40961

清华大佬耗费三个月吐血整理的几百G的资源，免费分享！....>>>

?
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
local DAG = {
    vset = {}
}
 
function DAG.addVertex(G, v)
    assert(v ~= nil, "cannot add nil as vertex")
    assert(G.vset[v] == nil, "vertex already in graph")
    G.vset[v] = {};
    return G;
end
 
function DAG.addDirectedEdge(G, from, to)
    assert(from ~= nil and to ~= nil, "cannot add nil vertex to edge")
    assert(G.vset[from] ~= nil and G.vset[to] ~= nil, "vertex is not in graph.")
    G.vset[from][to] = 1;
    return G;
end
 
local function _topology(G, order)
    assert(order ~= nil and type(order) == "table", "the parameter order is either nil or not a table");
    if next(G.vset) == nil then return order end
    local removed = {};
    for column, _ in pairs(G.vset) do
        local remove = true;
        repeat
            for _, row in pairs(G.vset) do
                if row[column] == 1 then
                    remove = false;
                    break;
                end
            end
        until true
        if remove then
            table.insert(removed, column);
        end
    end
    assert(next(removed) ~= nil, "cycle found in DAG")
    table.insert(order, removed);
    for _,v in pairs(removed) do
        for column, _ in pairs(G.vset) do
            if v == column then G.vset[column] = nil end
        end
    end
    return _topology(G, order);
end
 
function DAG.topology(G)
    assert(next(G.vset) ~= nil, "cannot topology against a nil DAG")
    return _topology(G, {})
end
 
return DAG