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
 401     print("SYSTEM:", self._SYSTEM)
 402     if graph._SYSTEM == "Win32" then
 403       fn = "tmpfile.dot"
 404     else
 405       fn = os.tmpname()..".dot"
 406     end
 407     local rv = self:write(fn)
 408     print("result: "..rv)
 409     if graph._SYSTEM == "Win32" then
 410           rv = os.execute("gvedit "..fn)
 411         else
 412       rv = os.execute("dotty "..fn)
 413     end
 414     os.remove(fn)
 415     return rv
 416   end
 417 end
 418
 419 --------------------------------------------------------------------------------
 420 -- Show graph with dotty
 421 --------------------------------------------------------------------------------
 422 local function show(self, printdot)
 423    local printdot = printdot or false
 424    self:showdotty(doit)
 425    if printdot == true then
 426       self.render(nil, "dot", "out.dot")
 427    end
 428    return true
 429 end
 430
 431 function gvversion()
 432    return io.popen('dot -V 2>&1 | cut -d " " -f 5'):read()
 433 end
 434 --------------------------------------------------------------------------------
 435 -- Partially overload C-defined metamethods
 436 -- Note: keep this function behind the overloading ones
 437 --------------------------------------------------------------------------------
 438 local function overload(g)
 439   local mt = getmetatable(g)
 440   if mt.overloaded == true then return end
 441   mt.__edge = mt.edge
 442   mt.__node = mt.node
 443   mt.__subgraph = mt.subgraph
 444   mt.edge = _edge
 445   mt.node = _node
 446   mt.subgraph = _subgraph
 447   mt.cluster = _cluster
 448   mt.record = _record
 449   mt._findedge = mt.findedge
 450   mt.findedge = findedge
 451   mt.findnode = findnode
 452   mt.findsubgraph = findsubgraph
 453   mt.showdotty = showdotty
 454   mt.show = show
 455   mt.overloaded = true
 456 end
 457
 458 -- resolve forward declaration
 459 _overload = overload
 460
 461 --------------------------------------------------------------------------------
 462 -- Advanced implementation of graph.open() - Main entry
 463 --------------------------------------------------------------------------------
 464 function open(...)
 465   local arg = {...}
 466   local name
 467   local attr = {}
 468   local g
 469   if type(arg[1]) == "string" then
 470     -- Syntax 1: graph.open("NAME","directed", {graph={ATTR,..}, edge={ATTR,..}, node={ATTR,..}})
 471     name = arg[1]
 472     kind = arg[2]
 473     attr = arg[3] or {}
 474
 475   elseif type(arg[1]) == "table" then
 476     -- Syntax 2: graph.open{"NAME", "kind", ATTR, ATTR}
 477     name = arg[1][1]
 478     kind = arg[1][2]
 479     for k,v in npairs(arg[1]) do
 480       if type(v) == "table" then
 481         attr[k] = v
 482       else
 483         attr.graph[k] = v
 484       end
 485     end
 486   end
 487
 488   -- Create the graph and declare attributes
 489   g = _open(name, kind)
 490   g:declare(defattr)
 491   g:declare(attr)
 492
 493   -- adjust methods
 494   overload(g)
 495
 496   return g
 497 end
 498
 499 --------------------------------------------------------------------------------
 500 -- Advanced implementation of graph.read(file, doscan) - Main entry
 501 --------------------------------------------------------------------------------
 502 local function getedge(n, elist)
 503   for e in n:walkedges() do
 504     if not elist[e] then
 505       table.insert(elist, e)
 506     end
 507   end
 508 end
 509
 510 local function getnode(g, nlist, elist)
 511   for n in g:walknodes() do
 512     if elist then
 513       getedge(n, elist)
 514     end
 515     table.insert(nlist, n)
 516   end
 517 end
 518
 519 local function getsubg(g, glist)
 520   for sg in g:walk() do
 521     local t = {sg, graph = {}, node = {}, edge = {}}
 522     table.insert(glist, t)
 523     getsubg(sg, t.graph)
 524     getnode(sg, t.node, t.edge)
 525   end
 526 end
 527
 528 function read(fname, doscan)
 529   local g, err = _read(fname)
 530   if not g then return g, err end
 531   overload(g)
 532   if doscan == true then
 533     local t = {
 534       g,
 535       graph={},
 536       node={},
 537       edge={}
 538     }
 539     getsubg(g, t.graph)
 540     getnode(g, t.node, t.edge)
 541     return g, t
 542   else
 543     return g
 544   end
 545 end
 546
 547 --==============================================================================
 548 -- Utilities to create a graph as Lua table.
 549 -- Each of the following functions returns a constructor function for
 550 -- the corresponding object.
 551 --==============================================================================
 552
 553 --------------------------------------------------------------------------------
 554 -- Create a directed graph.
 555 --------------------------------------------------------------------------------
 556 local function _graph(t, typ)
 557   local name = t.name or t[1]
 558   if type(t[1]) == "string" then
 559     table.remove(t, 1)
 560   end
 561   assert(name, "missing name")
 562   local g = open(name, typ)
 563   for k, v in npairs(t) do
 564     if type(v) == "table" then
 565       g:declare{[k] = v}
 566     elseif type(v) == "string" then
 567       g[k] = v
 568     else
 569       error("invalid attribute type")
 570     end
 571   end
 572   for k,v in ipairs(t) do
 573     if type(v) == "function" then
 574       v(g)
 575     else
 576       error("invalid graph attribute")
 577     end
 578   end
 579   return g
 580 end
 581
 582 function digraph(t)
 583   return _graph(t, "directed")
 584 end
 585
 586 function strictdigraph(t)
 587   return _graph(t, "strictdirected")
 588 end
 589
 590 function graph.graph(t)
 591   return _graph(t, "undirected")
 592 end
 593
 594 function strictgraph(t)
 595   return _graph(t, "strict")
 596 end
 597
 598 --------------------------------------------------------------------------------
 599 -- Create subgraph
 600 --------------------------------------------------------------------------------
 601 function subgraph(t)
 602   return function(g)
 603            assert(type(t[1]) == "string", "missing subgraph name")
 604            local sg = g:subgraph(t[1])
 605            table.remove(t, 1)
 606            for k, v in npairs(t) do
 607              if type(v) == "string" then
 608                sg[k] = v
 609              else
 610                error("invalid attribute type")
 611              end
 612            end
 613            for k,v in ipairs(t) do
 614              if type(v) == "function" then
 615                v(sg)
 616              else
 617                error("invalid attribute type")
 618              end
 619            end
 620            return sg
 621          end
 622 end
 623
 624 --------------------------------------------------------------------------------
 625 -- Create cluster
 626 --------------------------------------------------------------------------------
 627 function cluster(t)
 628   assert(type(t[1]) == "string", "missing cluster name")
 629   t[1] = "cluster_"..t[1]
 630   return subgraph(t)
 631 end
 632
 633 --------------------------------------------------------------------------------
 634 -- Create node
 635 --------------------------------------------------------------------------------
 636 function node(t)
 637   return function(g)
 638            return g:node(t)
 639          end
 640 end
 641
 642 --------------------------------------------------------------------------------
 643 -- Create record
 644 --------------------------------------------------------------------------------
 645 function record(t)
 646   return function(g)
 647            return g:record(t)
 648          end
 649 end
 650 --------------------------------------------------------------------------------
 651 -- Create edge
 652 --------------------------------------------------------------------------------
 653 function edge(t)
 654   return function(g)
 655            local p = {}
 656            for k,v in pairs(t) do
 657              if type(v) == "function" then
 658                table.insert(p, v(g))
 659              elseif type(v) == "string" or type(v) == "userdata" then
 660                p[k] = v
 661              else
 662                error("invalid parameter")
 663              end
 664            end
 665            return g:edge(p)
 666          end
 667 end
 668
 669 return graph