[lua]分布式计算中任务拓扑调度-尊龙凯时

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