# Module:Graph

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

```local WBHack = require( 'Module:WBHacks' )

local p = {}

local Graph = {

}

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
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}
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

-- 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
```