graph50.lua

localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph
localgraph=require"graph.core"
localstring=require"string"
localtable=require"table"
localbase=_G
localtype, getmetatable, pairs, ipairs, assert=
_G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert

module("graph")

localggraph=graph
--
-- Overloaded graph.open(), graph.read()
--
local_open=open
local_read=read

--==============================================================================
-- Constants
--==============================================================================
--
-- Default attributes
--
localdefattr= {
graph={
 },
node={
 },
edge={
 }
}

OUTPUTFORMATS= {
dot="DOT",
xdot="extended DOT",
cmap="Client-side imagemap (deprecated)",
dia="Dia format",
fig="FIG",
gd="Graphics Draw format",
gd2="Graphics Draw 2 format",
gif="Graphics Interchage Format",
gtk="Antialiased image using a GTK 2.0 canvas",
hpgl="Hewlett Packard Graphics Language HP-GL/2",
imap="Server-side and client-side imagemaps",
cmapx="Server-side and client-side imagemaps",
ismap="Server-side imagemap (deprecated)",
jpg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
jpeg="JPEG (deprecated - 8 May 2006 - will no longer be supported)",
mif="FrameMaker MIF format",
mp="MetaPost",
pcl="Hewlett Packard Printer Control",
pic="Autodesk PIC",
plain="Simple text format",
 ["plain-ext"] ="Extended text format",
png="Portable Network Graphics format",
ps="PostScript",
ps2="PostScript for PDF",
svg="Scalable Vector Graphics",
svgz="Scalable Vector Graphics",
vrml="VRML",
vtx="Visual Thought format",
wbmp="Wireless BitMap format"
}
--==============================================================================
-- Utilities
--==============================================================================
--------------------------------------------------------------------------------
-- Get graphviz version as major, minor
--------------------------------------------------------------------------------
string.gsub(_GVVERSION,"(%d+).(%d+)", 
function(u,v)
_GVMAJOR=base.tonumber(u)
_GVMINOR=base.tonumber(v)
end)

--------------------------------------------------------------------------------
-- Iterator over non-numeric indices of a table
--------------------------------------------------------------------------------
localfunctionnpairs(t)
returnfunction(t, prev)
k,v=base.next(t, prev)
whiletype(k) =="number" do
k,v=base.next(t, prev)
prev=k
end
returnk,v
end, t, nil
end

--------------------------------------------------------------------------------
-- Copy attributes from parameter table
--------------------------------------------------------------------------------
localfunctionattribs(params)
localt= {}
fork,vinnpairs(params) do
t[k] =v
end
returnt
end

--------------------------------------------------------------------------------
-- Get default attributes for the given object (type)
--------------------------------------------------------------------------------
localfunctiongetattrib(self)
localt= {}
localdefined=self.graph:defaults()[self:type()]
fork,vinpairs(defined) do
t[k] =self:rawget(k)
end
returnt
end

--------------------------------------------------------------------------------
-- Add a method to an object (node, graph, edge)
--------------------------------------------------------------------------------
localfunctionaddmethod(self, name, func)
localmt=getmetatable(self)
ifnotmtormt[name] thenreturnend
mt[name] =func
end

-- A forward declaration
local_overload

--==============================================================================
-- Advanced implementations
--==============================================================================
--------------------------------------------------------------------------------
-- Subgraph creation
-- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
-- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
--------------------------------------------------------------------------------
localfunction_subgraph(self, ...)
localname
localattr= {graph={}}
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing subgraph name")
end
localg, err=self:__subgraph(name)
_overload(g)
g:declare(defattr)
g:declare(attr)
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng, err
end

--------------------------------------------------------------------------------
-- Cluster creation
-- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
-- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
--------------------------------------------------------------------------------
localfunction_cluster(self, ...)
iftype(arg[1]) =="table" then
arg[1][1] ="cluster_"..arg[1][1]
elseiftype(arg[1]) =="string" then
arg[1] ="cluster_"..arg[1]
else
error("missing cluster name")
end
return_subgraph(self, base.unpack(arg))
end

--------------------------------------------------------------------------------
-- Edge creation
-- e = g:edge{node, .., "node", ATTR, ..., ATTR}
-- with ATTR: key = value
-- node: object or node name
-- e = g:edge(tail, head, "label", nocreate)
-- e = g:edge("tail", "head", "label", nocreate)
--------------------------------------------------------------------------------
localfunction_edge(self, ...)
localnodes, edges= {}, {}
localattr
localnode= {}
locallast
iftype(arg[1]) =="table" then
attr=attribs(arg[1])
-- create the edges
fori, vinipairs(arg[1]) do
-- we must care about ports here:
node= {}
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node.name=u
node.port=v
node.compass=w
end)
node.node=self:__node(node.name)
elseiftype(v) =="userdata" then
node.node=v
else
error("wrong node type")
end
table.insert(nodes, node.node)
ifi>1then
-- Create edges and set attributes to each edge
locale=self:__edge(last.node, node.node)
iflast.portthene.tailport=last.portend
ifnode.portthene.headport=node.portend
addmethod(e, "getattrib", getattrib)
fork,vinpairs(attr) do
e[k] =v
end
table.insert(edges, e)
end
last=node
end
returnedges, nodes
elseiftype(arg[1]) =="string" ortype(arg[1]) =="userdata" then
localnode= {[1]={},[2]={}}
fori=1,2do
localv=arg[i]
-- we must care about ports here:
iftype(v) =="string" then
string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
node[i].name=u
node[i].port=v
node[i].compass=w
end)
arg[i] =self:__node(node[i].name)
end
end
locale=self:__edge(base.unpack(arg))
ifnode[1].portthene.tailport=node[1].portend
ifnode[2].portthene.headport=node[2].portend
addmethod(e, "getattrib", getattrib)
returne, tail, head
else
error("invalid edge declaration")
end
end

--------------------------------------------------------------------------------
-- Node creation.
-- n = g:node{"name", ATTR, ..., ATTR, nocreate}
-- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
-- with ATTR: key = value
--------------------------------------------------------------------------------
localfunction_node(self, ...)
localname, attr
iftype(arg[1]) =="table" then
name=arg[1][1]
nocreate=arg[1][2]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
attr=arg[2] or {}
nocreate=arg[3]
else
error("missing node name")
end
localn=self:__node(name, nocreate)
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--------------------------------------------------------------------------------
-- Returns a function that creates horizontal oriented fields
-- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
--------------------------------------------------------------------------------
functionhbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("h") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="h" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Returns a function that creates vertical oriented fields
-- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
--------------------------------------------------------------------------------
functionvbox(t)
returnfunction(dir)
localss=""
fork, vinipairs(t) do
iftype(v) =="function" then
ss=ss..v("v") .."|"
elseiftype(v) =="string" then
ss=ss..v.."|"
end
end
ss=string.sub(ss, 1, -2)
ifdir~="v" thenss="{" ..ss.."}" end
returnss
end
end

--------------------------------------------------------------------------------
-- Record
-- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
-- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate) 
--------------------------------------------------------------------------------
localfunction_record(self, ...)
localname, attr, labelfunc
iftype(arg[1]) =="table" then
name=arg[1][1]
lfunc=arg[1][2]
nocreate=arg[1][3]
attr=attribs(arg[1])
elseiftype(arg[1]) =="string" then
name=arg[1]
lfunc=arg[2]
attr=arg[3] or {}
nocreate=arg[4]
else
error("missing record name")
end
assert(type(lfunc) =="function", "missing record struct")
locallabel=lfunc("h")
localn=self:__node(name, nocreate)
n.shape="record"
n.label=label
fork,vinpairs(attr) do
n[k] =v
end
addmethod(n, "getattrib", getattrib)
returnn
end

--==============================================================================
-- Additional graph methods
--==============================================================================
--------------------------------------------------------------------------------
-- Find a node
--------------------------------------------------------------------------------
localfunctionfindnode(self, name)
ifnotnamethen
returnnil, "not found" 
end
returnself:__node(name, true)
end

--------------------------------------------------------------------------------
-- Find an edge
--------------------------------------------------------------------------------
localfunctionfindedge(self, tail, head, label)
returnself:_findedge(tail, head, label)
end

--------------------------------------------------------------------------------
-- Find a subgraph
--------------------------------------------------------------------------------
localfunctionfindsubgraph(self, tail, head)
returnself:_subgraph(tail, head, false)
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshowdotty(self, doit)
doit=doitortrue
ifdoit==truethen
localfn=os.tmpname()..".dot"
self:write(fn)
rv=os.execute("dotty "..fn)
os.remove(fn)
returnrv
end
end

--------------------------------------------------------------------------------
-- Show graph with dotty
--------------------------------------------------------------------------------
localfunctionshow(self, doit)
doit=doitortrue
ifdoit==truethen
if_GVMINOR>8then
self:layout()
returnself:render("gtk")
else
returnself:showdotty(doit)
end
end
end

--------------------------------------------------------------------------------
-- Partially overload C-defined metamethods
-- Note: keep this function behind the overloading ones
--------------------------------------------------------------------------------
localfunctionoverload(g)
localmt=getmetatable(g)
ifmt.overloaded==truethenreturnend
mt.__edge=mt.edge
mt.__node=mt.node
mt.__subgraph=mt.subgraph
mt.edge=_edge
mt.node=_node
mt.subgraph=_subgraph
mt.cluster=_cluster
mt.record=_record
mt._findedge=mt.findedge
mt.findedge=findedge
mt.findnode=findnode
mt.findsubgraph=findsubgraph
mt.showdotty=showdotty
mt.show=show
mt.overloaded=true
end

-- resolve forward declaration
_overload=overload

--------------------------------------------------------------------------------
-- Advanced implementation of graph.open() - Main entry
--------------------------------------------------------------------------------
functionopen(...)
localname
localattr= {graph={}}
localg

iftype(arg[1]) =="string" then
-- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
name=arg[1]
kind=arg[2]
attr=arg[3] or {}

elseiftype(arg[1]) =="table" then
-- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
name=arg[1][1]
kind=arg[1][2]
fork,vinnpairs(arg[1]) do
iftype(v) =="table" then
attr[k] =v
else
attr.graph[k] =v
end
end
end
-- Create the graph and declare attributes
g=_open(name, kind)
g:declare(defattr)
g:declare(attr)

-- adjust methods
overload(g)

-- set attributes
fork,vinpairs(attr) do
iftype(v) =="table" then
g:declare(v)
else
g:declare{graph={k=v}}
end
end
returng
end

--------------------------------------------------------------------------------
-- Advanced implementation of graph.read(file, doscan) - Main entry
--------------------------------------------------------------------------------
localfunctiongetedge(n, elist)
foreinn:walkedges() do
ifnotelist[e] then
table.insert(elist, e)
end
end
end

localfunctiongetnode(g, nlist, elist)
forning:walknodes() do
ifelistthen
getedge(n, elist)
end
table.insert(nlist, n)
end
end

localfunctiongetsubg(g, glist)
forsging:walk() do
localt= {sg, graph= {}, node= {}, edge= {}}
table.insert(glist, t)
getsubg(sg, t.graph)
getnode(sg, t.node, t.edge)
end
end

functionread(fname, doscan)
localg, err=_read(fname)
ifnotgthenreturng, errend
overload(g)
ifdoscan==truethen
localt= {
g,
graph={},
node={},
edge={}
 }
getsubg(g, t.graph)
getnode(g, t.node, t.edge)
returng, t
else
returng
end
end

--==============================================================================
-- Utilities to create a graph as Lua table.
-- Each of the following functions returns a constructor function for
-- the corresponding object. 
--==============================================================================

--------------------------------------------------------------------------------
-- Create a directed graph.
--------------------------------------------------------------------------------
localfunction_graph(t, typ)
localname=t.nameort[1]
iftype(t[1]) =="string" then
table.remove(t, 1)
end
assert(name, "missing name")
localg=open(name, typ)
fork, vinnpairs(t) do
iftype(v) =="table" then
g:declare{[k] =v} 
elseiftype(v) =="string" then
g[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(g)
else
error("invalid graph attribute")
end
end
returng
end

functiondigraph(t)
return_graph(t, "directed")
end

functionstrictdigraph(t)
return_graph(t, "strictdirected")
end

functiongraph.graph(t)
return_graph(t, "undirected")
end

functionstrictgraph(t)
return_graph(t, "strict")
end

--------------------------------------------------------------------------------
-- Create subgraph
--------------------------------------------------------------------------------
functionsubgraph(t)
returnfunction(g) 
assert(type(t[1]) =="string", "missing subgraph name")
localsg=g:subgraph(t[1])
table.remove(t, 1)
fork, vinnpairs(t) do
iftype(v) =="string" then
sg[k] =v
else
error("invalid attribute type")
end
end
fork,vinipairs(t) do
iftype(v) =="function" then
v(sg)
else
error("invalid attribute type")
end
end
returnsg
end
end

--------------------------------------------------------------------------------
-- Create cluster
--------------------------------------------------------------------------------
functioncluster(t)
assert(type(t[1]) =="string", "missing cluster name")
t[1] ="cluster_"..t[1]
returnsubgraph(t)
end

--------------------------------------------------------------------------------
-- Create node
--------------------------------------------------------------------------------
functionnode(t)
returnfunction(g) 
returng:node(t) 
end
end

--------------------------------------------------------------------------------
-- Create record
--------------------------------------------------------------------------------
functionrecord(t)
returnfunction(g) 
returng:record(t) 
end
end
--------------------------------------------------------------------------------
-- Create edge
--------------------------------------------------------------------------------
functionedge(t)
returnfunction(g) 
localp= {}
fork,vinpairs(t) do
iftype(v) =="function" then
table.insert(p, v(g))
elseiftype(v) =="string" ortype(v) =="userdata" then
p[k] =v
else
error("invalid parameter")
end
end
returng:edge(p) 
end
end

returngraph