[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