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