graph.lua

   1 --=========================================================================*\
   2 -- LuaGRAPH toolkit
   3 -- Graph support for Lua.
   4 -- Herbert Leuwer
   5 -- 30-7-2006, 30-12-2016, 01/2017
   6 --
   7 -- Lua module "graph.lua"
   8 --=========================================================================*\
   9 local graph = require "graph.core"
  10 local string = require "string"
  11 local table = require "table"
  12
  13 local type, getmetatable, pairs, ipairs, assert =
  14   _G.type, _G.getmetatable, _G.pairs, _G.ipairs, _G.assert
  15
  16 module("graph", package.seeall)
  17 --
  18 -- Overloaded graph.open(), graph.read()
  19 --
  20 local _open = open
  21 local _read = read
  22
  23 --==============================================================================
  24 -- Constants
  25 --==============================================================================
  26 --
  27 -- Default attributes
  28 --
  29 local defattr = {
  30   graph={
  31   },
  32   node={
  33   },
  34   edge={
  35   }
  36 }
  37
  38 OUTPUTFORMATS = {
  39    {format = "canon", descr = "DOT pretty"},
  40    {format = "dot",   descr = "DOT"},
  41    {format = "xdot",  descr = "extended DOT"},
  42    {format = "cmap",  descr = "Client-side imagemap (deprecated)"},
  43    {format = "dia",   descr = "Dia format"},
  44    {format = "eps",   descr = "Encapsulated PostScript"},
  45    {format = "fig",   descr = "FIG"},
  46    {format = "gd",    descr = "Graphics Draw format"},
  47    {format = "gd2",   descr = "Graphics Draw 2 format"},
  48    {format = "gif",   descr = "Graphics Interchage Format"},
  49    {format = "gtk",   descr = "Antialiased image using a GTK 2.0 canvas"},
  50    {format = "hpgl",  descr = "Hewlett Packard Graphics Language HP-GL/2"},
  51    {format = "ico",   descr = "Icon Image File Format"},
  52    {format = "imap",  descr = "Server-side and client-side imagemaps"},
  53    {format = "imap_np", descr = "Server-side and client-side imagemaps"},
  54    {format = "cmapx", descr = "Server-side and client-side imagemaps"},
  55    {format = "cmapx_np", descr = "Server-side and client-side imagemaps"},
  56    {format = "ismap", descr = "Server-side imagemap (deprecated)"},
  57    {format = "jpg",   descr = "JPEG (deprecated - 8 May 2006 - will no longer be supported)"},
  58    {format = "jpeg",  descr = "JPEG (deprecated - 8 May 2006 - will no longer be supported)"},
  59    {format = "mif",   descr = "FrameMaker MIF format"},
  60    {format = "mp",    descr = "MetaPost"},
  61    {format = "pcl",   descr = "Hewlett Packard Printer Control"},
  62    {format = "pdf",   descr = "Portable Document Format (PDF)"},
  63    {format = "pic",   descr = "Autodesk PIC"},
  64    {format = "plain", descr = "Simple text format"},
  65    {format = "plain-ext", descr = "Extended text format"},
  66    {format = "png",   descr = "Portable Network Graphics format"},
  67    {format = "ps",    descr = "PostScript"},
  68    {format = "ps2",   descr = "PostScript for PDF"},
  69    {format = "svg",   descr = "Scalable Vector Graphics"},
  70    {format = "svgz",  descr = "Scalable Vector Graphics"},
  71    {format = "vml",   descr = "Vector Markup Language (VML)"},
  72    {format = "vmlz",  descr = "Vector Markup Language (VML) - compressed"},
  73    {format = "vrml",  descr = "VRML"},
  74    {format = "vtx",   descr ="Visual Thought format"},
  75    {format = "wbmp",  descr = "Wireless BitMap format"},
  76    {format = "xlib",  descr = "Xlib canvas"},
  77 }
  78 --==============================================================================
  79 -- Utilities
  80 --==============================================================================
  81
  82 --------------------------------------------------------------------------------
  83 -- Iterator over non-numeric indices of a table
  84 --------------------------------------------------------------------------------
  85 local function npairs(t)
  86   return function(t, prev)
  87            k,v = next(t, prev)
  88            while type(k) == "number" do
  89              k,v = next(t, prev)
  90              prev = k
  91            end
  92            return k,v
  93          end, t, nil
  94 end
  95
  96 --------------------------------------------------------------------------------
  97 -- Copy attributes from parameter table
  98 --------------------------------------------------------------------------------
  99 local function attribs(params)
 100   local t = {}
 101   for k,v in npairs(params) do
 102     t[k] = v
 103   end
 104   return t
 105 end
 106
 107 --------------------------------------------------------------------------------
 108 -- Get default attributes for the given object (type)
 109 --------------------------------------------------------------------------------
 110 local function getattrib(self)
 111   local t = {}
 112   local defined = self.graph:defaults()[self:type()]
 113   for k,v in pairs(defined) do
 114     t[k] = self:rawget(k)
 115   end
 116   return t
 117 end
 118
 119 --------------------------------------------------------------------------------
 120 -- Add a method to an object (node, graph, edge)
 121 --------------------------------------------------------------------------------
 122 local function addmethod(self, name, func)
 123   local mt = getmetatable(self)
 124   if not mt or mt[name] then return end
 125   mt[name] = func
 126 end
 127
 128 -- A forward declaration
 129 local _overload
 130
 131 --==============================================================================
 132 -- Advanced implementations
 133 --==============================================================================
 134 --------------------------------------------------------------------------------
 135 -- Subgraph creation
 136 -- sg = g:subgraph{"name", ATTR, ..., ATTR, nocreate}
 137 -- sg = g:subgraph("name", {ATTR, ..., ATTR}, nocreate)
 138 --------------------------------------------------------------------------------
 139 local function _subgraph(self, ...)
 140   local arg = {...}
 141   local name
 142   local attr = {}
 143   if type(arg[1]) == "table" then
 144     name = arg[1][1]
 145     nocreate = arg[1][2]
 146     for k,v in npairs(arg[1]) do
 147       if type(v) == "table" then
 148         attr[k] = v
 149       else
 150         attr.graph[k] = v
 151       end
 152     end
 153   elseif type(arg[1]) == "string" then
 154     name = arg[1]
 155     attr = arg[2] or {}
 156     nocreate = arg[3]
 157   else
 158     error("missing subgraph name")
 159   end
 160   local g, err = self:__subgraph(name)
 161   _overload(g)
 162   g:declare(defattr)
 163   g:declare(attr)
 164   for k,v in pairs(attr) do
 165     if type(v) == "table" then
 166       g:declare(v)
 167     else
 168       g:declare{k=v}
 169     end
 170   end
 171   return g, err
 172 end
 173
 174 --------------------------------------------------------------------------------
 175 -- Cluster creation
 176 -- c = g:cluster{"name", ATTR, ..., ATTR, nocreate}
 177 -- c = g:cluster("name", {ATTR, ..., ATTR}, nocreate}
 178 --------------------------------------------------------------------------------
 179 local function _cluster(self, ...)
 180   local arg = {...}
 181   if type(arg[1]) == "table" then
 182     arg[1][1] = "cluster_"..arg[1][1]
 183   elseif type(arg[1]) == "string" then
 184     arg[1] = "cluster_"..arg[1]
 185   else
 186     error("missing cluster name")
 187   end
 188   return _subgraph(self, unpack(arg))
 189 end
 190
 191 --------------------------------------------------------------------------------
 192 -- Edge creation
 193 -- e = g:edge{node, .., "node", ATTR, ..., ATTR}
 194 --     with ATTR: key = value
 195 --          node: object or node name
 196 -- e = g:edge(tail, head, "label", nocreate)
 197 -- e = g:edge("tail", "head", "label", nocreate)
 198 --------------------------------------------------------------------------------
 199 local function _edge(self, ...)
 200    local arg = {...}
 201    local nodes, edges = {}, {}
 202    local attr
 203    local node = {}
 204    local last
 205    if type(arg[1]) == "table" then
 206       attr = attribs(arg[1])
 207       -- create the edges
 208       for i, v in ipairs(arg[1]) do
 209          -- we must care about ports here:
 210          node = {}
 211          if type(v) == "string" then
 212             string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
 213                            node.name = u
 214                            node.port = v
 215                            node.compass = w
 216             end)
 217             node.node = self:__node(node.name)
 218          elseif type(v) == "userdata" then
 219             node.node = v
 220          else
 221             error("wrong node type")
 222          end
 223          table.insert(nodes, node.node)
 224          if i > 1 then
 225             -- Create edges and set attributes to each edge
 226             local e, tail_or_err, head = self:__edge(last.node, node.node)
 227             if not e then
 228                return nil, err
 229             end
 230             if last.port then e.tailport = last.port end
 231             if node.port then e.headport = node.port end
 232             addmethod(e, "getattrib", getattrib)
 233             for k,v in pairs(attr) do
 234                e[k] = v
 235             end
 236             table.insert(edges, e)
 237          end
 238          last = node
 239       end
 240       return edges, nodes
 241    elseif type(arg[1]) == "string" or type(arg[1]) == "userdata" then
 242       local node = {[1]={},[2]={}}
 243       for i = 1,2 do
 244          local v = arg[i]
 245          -- we must care about ports here:
 246          if type(v) == "string" then
 247             string.gsub(v, "^(%w+):*(%w*):*(%w*)", function(u, v, w)
 248                            node[i].name = u
 249                            node[i].port = v
 250                            node[i].compass = w
 251             end)
 252             arg[i] = self:__node(node[i].name)
 253          end
 254       end
 255       local e, tail_or_err, head = self:__edge(unpack(arg))
 256       if not e then return e, tail_or_err end
 257       if node[1].port then e.tailport=node[1].port end
 258       if node[2].port then e.headport=node[2].port end
 259       addmethod(e, "getattrib", getattrib)
 260       return e, tail_or_err, head
 261    else
 262       error("invalid edge declaration")
 263    end
 264 end
 265
 266 --------------------------------------------------------------------------------
 267 -- Node creation.
 268 -- n = g:node{"name", ATTR, ..., ATTR, nocreate}
 269 -- n = g:node("name", {ATTR, ..., ATTR}, nocreate)
 270 --     with ATTR: key = value
 271 --------------------------------------------------------------------------------
 272 local function _node(self, ...)
 273   local arg = {...}
 274   local name, attr
 275   if type(arg[1]) == "table" then
 276     name = arg[1][1]
 277     nocreate = arg[1][2]
 278     attr = attribs(arg[1])
 279   elseif type(arg[1]) == "string" then
 280     name = arg[1]
 281     attr = arg[2] or {}
 282     nocreate = arg[3]
 283   else
 284     error("missing node name")
 285   end
 286   local n = self:__node(name, nocreate)
 287   for k,v in pairs(attr) do
 288     n[k] = v
 289   end
 290   addmethod(n, "getattrib", getattrib)
 291   return n
 292 end
 293
 294 --------------------------------------------------------------------------------
 295 -- Returns a function that creates horizontal oriented fields
 296 -- gr.hbox{"field", gr.vbox{...}, "field", gr.vbox{...}}
 297 --------------------------------------------------------------------------------
 298 function hbox(t)
 299   return function(dir)
 300            local ss = ""
 301            for k, v in ipairs(t) do
 302              if type(v) == "function" then
 303                ss = ss .. v("h") .. "|"
 304              elseif type(v) == "string" then
 305                ss = ss .. v .. "|"
 306              end
 307            end
 308            ss = string.sub(ss, 1, -2)
 309            if dir ~= "h" then ss = "{" .. ss .. "}" end
 310            return ss
 311          end
 312 end
 313
 314 --------------------------------------------------------------------------------
 315 -- Returns a function that creates vertical oriented fields
 316 -- gr.vbox{"field", gr.hbox{...}, "field", gr.hbox{...}}
 317 --------------------------------------------------------------------------------
 318 function vbox(t)
 319   return function(dir)
 320            local ss = ""
 321            for k, v in ipairs(t) do
 322              if type(v) == "function" then
 323                ss = ss .. v("v") .. "|"
 324              elseif type(v) == "string" then
 325                ss = ss .. v .. "|"
 326              end
 327            end
 328            ss = string.sub(ss, 1, -2)
 329            if dir ~= "v" then ss = "{" .. ss .. "}" end
 330            return ss
 331          end
 332 end
 333
 334 --------------------------------------------------------------------------------
 335 -- Record
 336 -- n = g:record{"n1", vbox{...}, ATTR, ...,ATTR, nocreate}
 337 -- n = g:record("n1", vbox{"name", hbox{...}, ...}, {ATTR, ..., ATTR}, nocreate)
 338 --------------------------------------------------------------------------------
 339 local function _record(self, ...)
 340   local name, attr, labelfunc
 341   local arg = {...}
 342   if type(arg[1]) == "table" then
 343     name = arg[1][1]
 344     lfunc = arg[1][2]
 345     nocreate = arg[1][3]
 346     attr = attribs(arg[1])
 347   elseif type(arg[1]) == "string" then
 348     name = arg[1]
 349     lfunc = arg[2]
 350     attr = arg[3] or {}
 351     nocreate = arg[4]
 352   else
 353     error("missing record name")
 354   end
 355   assert(type(lfunc) == "function", "missing record struct")
 356   local label = lfunc("h")
 357   local n = self:__node(name, nocreate)
 358   n.shape = "record"
 359   n.label = label
 360   for k,v in pairs(attr) do
 361     n[k] = v
 362   end
 363   addmethod(n, "getattrib", getattrib)
 364   return n
 365 end
 366
 367 --==============================================================================
 368 -- Additional graph methods
 369 --==============================================================================
 370 --------------------------------------------------------------------------------
 371 -- Find a node
 372 --------------------------------------------------------------------------------
 373 local function findnode(self, name)
 374   if not name then
 375     return nil, "not found"
 376   end
 377   return self:__node(name, true)
 378 end
 379
 380 --------------------------------------------------------------------------------
 381 -- Find an edge
 382 --------------------------------------------------------------------------------
 383 local function findedge(self, tail, head, label)
 384   return self:_findedge(tail, head, label)
 385 end
 386
 387 --------------------------------------------------------------------------------
 388 -- Find a subgraph
 389 --------------------------------------------------------------------------------
 390 local function findsubgraph(self, tail, head)
 391   return self:_subgraph(tail, head, false)
 392 end
 393
 394 --------------------------------------------------------------------------------
 395 -- Show graph with dotty
 396 --------------------------------------------------------------------------------
 397 local function showdotty(self, doit)
 398   doit = doit or true
 399   if doit == true then
 400     local fn = os.tmpname()..".dot"
 401     local rv = self:write(fn)
 402     print("result: "..rv)
 403     rv = os.execute("dotty "..fn)
 404     os.remove(fn)
 405     return rv
 406   end
 407 end
 408
 409 --------------------------------------------------------------------------------
 410 -- Show graph with dotty
 411 --------------------------------------------------------------------------------
 412 local function show(self, printdot)
 413    local printdot = printdot or false
 414    self:showdotty(doit)
 415    if printdot == true then
 416       self.render(nil, "dot", "out.dot")
 417    end
 418    return true
 419 end
 420
 421 function gvversion()
 422    return io.popen('dot -V 2>&1 | cut -d " " -f 5'):read()
 423 end
 424 --------------------------------------------------------------------------------
 425 -- Partially overload C-defined metamethods
 426 -- Note: keep this function behind the overloading ones
 427 --------------------------------------------------------------------------------
 428 local function overload(g)
 429   local mt = getmetatable(g)
 430   if mt.overloaded == true then return end
 431   mt.__edge = mt.edge
 432   mt.__node = mt.node
 433   mt.__subgraph = mt.subgraph
 434   mt.edge = _edge
 435   mt.node = _node
 436   mt.subgraph = _subgraph
 437   mt.cluster = _cluster
 438   mt.record = _record
 439   mt._findedge = mt.findedge
 440   mt.findedge = findedge
 441   mt.findnode = findnode
 442   mt.findsubgraph = findsubgraph
 443   mt.showdotty = showdotty
 444   mt.show = show
 445   mt.overloaded = true
 446 end
 447
 448 -- resolve forward declaration
 449 _overload = overload
 450
 451 --------------------------------------------------------------------------------
 452 -- Advanced implementation of graph.open() - Main entry
 453 --------------------------------------------------------------------------------
 454 function open(...)
 455   local arg = {...}
 456   local name
 457   local attr = {}
 458   local g
 459   if type(arg[1]) == "string" then
 460     -- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
 461     name = arg[1]
 462     kind = arg[2]
 463     attr = arg[3] or {}
 464
 465   elseif type(arg[1]) == "table" then
 466     -- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
 467     name = arg[1][1]
 468     kind = arg[1][2]
 469     for k,v in npairs(arg[1]) do
 470       if type(v) == "table" then
 471         attr[k] = v
 472       else
 473         attr.graph[k] = v
 474       end
 475     end
 476   end
 477
 478   -- Create the graph and declare attributes
 479   g = _open(name, kind)
 480   g:declare(defattr)
 481   g:declare(attr)
 482
 483   -- adjust methods
 484   overload(g)
 485
 486   return g
 487 end
 488
 489 --------------------------------------------------------------------------------
 490 -- Advanced implementation of graph.read(file, doscan) - Main entry
 491 --------------------------------------------------------------------------------
 492 local function getedge(n, elist)
 493   for e in n:walkedges() do
 494     if not elist[e] then
 495       table.insert(elist, e)
 496     end
 497   end
 498 end
 499
 500 local function getnode(g, nlist, elist)
 501   for n in g:walknodes() do
 502     if elist then
 503       getedge(n, elist)
 504     end
 505     table.insert(nlist, n)
 506   end
 507 end
 508
 509 local function getsubg(g, glist)
 510   for sg in g:walk() do
 511     local t = {sg, graph = {}, node = {}, edge = {}}
 512     table.insert(glist, t)
 513     getsubg(sg, t.graph)
 514     getnode(sg, t.node, t.edge)
 515   end
 516 end
 517
 518 function read(fname, doscan)
 519   local g, err = _read(fname)
 520   if not g then return g, err end
 521   overload(g)
 522   if doscan == true then
 523     local t = {
 524       g,
 525       graph={},
 526       node={},
 527       edge={}
 528     }
 529     getsubg(g, t.graph)
 530     getnode(g, t.node, t.edge)
 531     return g, t
 532   else
 533     return g
 534   end
 535 end
 536
 537 --==============================================================================
 538 -- Utilities to create a graph as Lua table.
 539 -- Each of the following functions returns a constructor function for
 540 -- the corresponding object.
 541 --==============================================================================
 542
 543 --------------------------------------------------------------------------------
 544 -- Create a directed graph.
 545 --------------------------------------------------------------------------------
 546 local function _graph(t, typ)
 547   local name = t.name or t[1]
 548   if type(t[1]) == "string" then
 549     table.remove(t, 1)
 550   end
 551   assert(name, "missing name")
 552   local g = open(name, typ)
 553   for k, v in npairs(t) do
 554     if type(v) == "table" then
 555       g:declare{[k] = v}
 556     elseif type(v) == "string" then
 557       g[k] = v
 558     else
 559       error("invalid attribute type")
 560     end
 561   end
 562   for k,v in ipairs(t) do
 563     if type(v) == "function" then
 564       v(g)
 565     else
 566       error("invalid graph attribute")
 567     end
 568   end
 569   return g
 570 end
 571
 572 function digraph(t)
 573   return _graph(t, "directed")
 574 end
 575
 576 function strictdigraph(t)
 577   return _graph(t, "strictdirected")
 578 end
 579
 580 function graph.graph(t)
 581   return _graph(t, "undirected")
 582 end
 583
 584 function strictgraph(t)
 585   return _graph(t, "strict")
 586 end
 587
 588 --------------------------------------------------------------------------------
 589 -- Create subgraph
 590 --------------------------------------------------------------------------------
 591 function subgraph(t)
 592   return function(g)
 593            assert(type(t[1]) == "string", "missing subgraph name")
 594            local sg = g:subgraph(t[1])
 595            table.remove(t, 1)
 596            for k, v in npairs(t) do
 597              if type(v) == "string" then
 598                sg[k] = v
 599              else
 600                error("invalid attribute type")
 601              end
 602            end
 603            for k,v in ipairs(t) do
 604              if type(v) == "function" then
 605                v(sg)
 606              else
 607                error("invalid attribute type")
 608              end
 609            end
 610            return sg
 611          end
 612 end
 613
 614 --------------------------------------------------------------------------------
 615 -- Create cluster
 616 --------------------------------------------------------------------------------
 617 function cluster(t)
 618   assert(type(t[1]) == "string", "missing cluster name")
 619   t[1] = "cluster_"..t[1]
 620   return subgraph(t)
 621 end
 622
 623 --------------------------------------------------------------------------------
 624 -- Create node
 625 --------------------------------------------------------------------------------
 626 function node(t)
 627   return function(g)
 628            return g:node(t)
 629          end
 630 end
 631
 632 --------------------------------------------------------------------------------
 633 -- Create record
 634 --------------------------------------------------------------------------------
 635 function record(t)
 636   return function(g)
 637            return g:record(t)
 638          end
 639 end
 640 --------------------------------------------------------------------------------
 641 -- Create edge
 642 --------------------------------------------------------------------------------
 643 function edge(t)
 644   return function(g)
 645            local p = {}
 646            for k,v in pairs(t) do
 647              if type(v) == "function" then
 648                table.insert(p, v(g))
 649              elseif type(v) == "string" or type(v) == "userdata" then
 650                p[k] = v
 651              else
 652                error("invalid parameter")
 653              end
 654            end
 655            return g:edge(p)
 656          end
 657 end
 658
 659 return graph