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

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

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

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!