Module:Graph

Documentation for this module may be created at Module:Graph/doc

local WBHack = require( 'Module:WBHacks' )
 
local p = {}

local Graph = {
	
}

function Graph:addNode(n)
	self.node[n] = true
	local get_children = get_children_function
end

function Graph:new(o)
    o = o or {}   			-- create object if user does not provide one
    
    o.node = {}				-- attributes
    
    setmetatable(o, self)
    self.__index = self
    
    return o
end

function Graph:setNodeData(n, key, val)
	if self.node[n] == nil or self.node[n] == true then
		self.node[n] = {}
	end
	self.node[n][key] = val
end

function Graph:getNodeData(n, key, defval)
	if  self.node[n] == nil or self.node[n][key] == nil then
		return defval
	else
		return self.node[n][key] 
	end
end

function Graph:getChildren(n)
	if self.node[n]["children"] == nil then
		self.node[n]["children"] = self.get_children_function(n)
	end
	return self.node[n]
end

function Graph:getRoot()
	return self.node[1]
end

function Graph:hasData(n, key)
	return self.node[n][key] ~= nil
end

-- graph builder
function Graph.rootedGraphFromChildrenFunction(initialNode, func)
	local graph = Graph:new{get_children_function = func}
	graph:addNode(initialNode)
	return graph
end



function createCoveringTree(o, computeChildrenFunction, initialNode)
end	
-- Performs a Depth First Search to compute a covering tree from a graph
--- Returns an annotated list of nodes.
---- Annotation includes:
----* a topological ordering of the node of the graph 
-----   (when the graph in not a DAG, the arcs that leads to loops in the order of the DFS exploration are ignored to compute the ordering)
----* a 'state' of the node datas[node]["status"] : 
----- "complete", if the algorithm entered all the immidiate children of this node
----- "incomplete", if his depth on the computed covering tree is the maxdepth
 
function p.treeFromGraph(firstItemId, get_children_function, maxdepth )
	-- firstItemId : the id of the starting point of the graph exploration
	-- get_children_function : a function that takes an item and returns the set of children of this item in 
 
 
	--while there are unmarked nodes do
	--    select an unmarked node n
	--    visit(n) 
	--function visit(node n)
	--    if n has a temporary mark then stop (not a DAG)
	--    if n is not marked (i.e. has not been visited yet) then
	--        mark n temporarily
	--        for each node m with an edge from n to m do
	--            visit(m)
	--        mark n permanently
	--        add n to head of L
 
	-- local firstItem = WBHack.get( firstItemId )
 
	local opened = 1
	local closed = 2
	local incomplete = 3
 
	local tree = Graph.rootedGraphFromChildrenFunction(firstItemId, get_children_function)
	local marks = {}
 	
	-- this function 
	-- * visits and builds the tree, DAG or graph,
	-- * in the same pass, computes a topological ordering for the DAG
	-- * annotates the nodes with informations
    function visit(n, depth, rank)
 
		mw.log(n .. " " .. tostring(marks[n]))
		if marks[n] == opened then 
			tree:setNodeData(n, "status", "loop")
			tree:setNodeData(n, "rank", rank)
			return rank
		elseif marks[n] ~= closed then
			marks[n] = opened
 
			childrens = tree:getChildren(n)
 
			for _, node in ipairs(childrens) do
				tree.setNodeData(node, "nparents", 
					tree:getNodeData(node, "nparents", 0) + 1
				) 
				if depth <= maxdepth then
					rank = visit(node, depth + 1, rank + 1)
				end
			end
 
			if depth <= maxdepth then
				if tree:getNodeData(n, "status", "complete") ~= "loop" then
					tree:setNodeData(n, "status", "complete")
				end
				marks[n] = closed
			else
				tree:setNodeData(n, "status", "incomplete")
				marks[n] = incomplete
			end
 
			tree:setNodeData(n, "rank", rank)
		end
		return rank + 1
	end
	tree:setNodeData(firstItemId, "nparents", 0)
	visit(firstItemId, 1, 0)
 
	return tree
end

return p