src/gr_node.c

   1 /*=========================================================================*\
   2  * LuaGRAPH toolkit
   3  * Graph support for Lua.
   4  * Herbert Leuwer
   5  * 30-7-2006, 01/2017
   6  *
   7  * Node related functionality.
   8  *
   9 \*=========================================================================*/
  10
  11 /*=========================================================================*\
  12  * Includes
  13 \*=========================================================================*/
  14 #include <string.h>
  15 #include <stdlib.h>
  16
  17 #include "lua.h"
  18 #include "lauxlib.h"
  19
  20 #include "gr_graph.h"
  21
  22 /*=========================================================================* \
  23  * Defines
  24 \*=========================================================================*/
  25
  26 /*=========================================================================*\
  27  * Prototypes
  28 \*=========================================================================*/
  29 static int gr_nameof(lua_State *L);
  30 static int gr_id(lua_State *L);
  31 static int gr_equal(lua_State *L);
  32 static int gr_delete(lua_State *L);
  33 static int gr_degree(lua_State *L);
  34 static int gr_graphof(lua_State *L);
  35 static int gr_edge(lua_State *L);
  36 static int gr_nextedge(lua_State *L);
  37 static int gr_walkedges(lua_State *L);
  38 static int gr_nextinput(lua_State *L);
  39 static int gr_walkinputs(lua_State *L);
  40 static int gr_nextoutput(lua_State *L);
  41 static int gr_walkoutputs(lua_State *L);
  42 static int gr_info(lua_State *L);
  43 static int gr_tostring(lua_State *L);
  44
  45 /*=========================================================================*\
  46  * Data
  47 \*=========================================================================*/
  48 static const luaL_Reg reg_methods[] = {
  49   {"delete", gr_delete},
  50   {"degree", gr_degree},
  51   {"edge", gr_edge},
  52   {"nextedge", gr_nextedge},
  53   {"walkedges", gr_walkedges},
  54   {"nextinput", gr_nextinput},
  55   {"walkinputs", gr_walkinputs},
  56   {"nextoutput", gr_nextoutput},
  57   {"walkoutputs", gr_walkoutputs},
  58   {"type", get_object_type},
  59   {"rawget", getval},
  60   {"info", gr_info},
  61   {NULL, NULL}
  62 };
  63
  64 static const luaL_Reg reg_rmembers[] = {
  65   {"id", gr_id},
  66   {"name", gr_nameof},
  67   {"status", gr_status},
  68   {"graph", gr_graphof},
  69   {NULL, NULL}
  70 };
  71
  72 static const luaL_Reg reg_metamethods[] = {
  73   {"__gc", gr_collect},
  74   {"__eq", gr_equal},
  75   {"__newindex", object_newindex_handler},
  76   {"__concat", gr_edge},
  77   {"__add", gr_edge},
  78   {"__tostring", gr_tostring},
  79   {NULL, NULL}
  80 };
  81 /*=========================================================================*\
  82  * Functions
  83 \*=========================================================================*/
  84 /*-------------------------------------------------------------------------*\
  85  * Utility Functions
  86 \*-------------------------------------------------------------------------*/
  87
  88 /*
  89  * Create a new Lua userdata object and configure metatable.
  90  */
  91 int new_node(lua_State *L){
  92   return new_object(L, "node", reg_rmembers, reg_methods, reg_metamethods,
  93                     object_index_handler);
  94 }
  95
  96 /*-------------------------------------------------------------------------*\
  97  * Metamethod: __eq [boolean]
  98  * Compare two nodes.
  99  * Example:
 100  * n1 == n2 or n1 ~= n2 with metamethods
 101 \*-------------------------------------------------------------------------*/
 102 static int gr_equal(lua_State *L)
 103 {
 104   gr_node_t *ud1 = tonode(L, 1, STRICT);
 105   gr_node_t *ud2 = tonode(L, 2, STRICT);
 106   lua_pushboolean(L, (AGID(ud1->n) == AGID(ud2->n)));
 107   return 1;
 108 }
 109
 110 /*-------------------------------------------------------------------------*\
 111  * Property: name [string]
 112  * Provides the name of a node.
 113  * Example:
 114  * name = g.name
 115 \*-------------------------------------------------------------------------*/
 116 static int gr_nameof(lua_State *L)
 117 {
 118   gr_node_t *ud = tonode(L, 1, STRICT);
 119   if (ud->status != ALIVE){
 120     luaL_error(L, "deleted");
 121     return 0;
 122   }
 123   lua_pushstring(L, agnameof(ud->n));
 124   return 1;
 125 }
 126
 127 /*-------------------------------------------------------------------------*\
 128  * Property: id [number]
 129  * Get a node's id.
 130  * Example:
 131  * n = n.id
 132 \*-------------------------------------------------------------------------*/
 133 static int gr_id(lua_State *L)
 134 {
 135   gr_node_t *ud = tonode(L, 1, STRICT);
 136   lua_pushnumber(L, AGID(ud->n));
 137   return 1;
 138 }
 139
 140 /*-------------------------------------------------------------------------*\
 141  * Write info about a node to stdout.
 142  * Example:
 143  * n:info()
 144 \*-------------------------------------------------------------------------*/
 145 static int gr_info(lua_State *L)
 146 {
 147   Agraph_t  *g;
 148   gr_node_t *ud = tonode(L, 1, STRICT);
 149   Agedge_t *se;
 150   Agsym_t *sym;
 151
 152   g = agraphof(ud->n);
 153   printf("INFO NODE '%s' '%s' id=%lu seq=%d\n", agnameof(ud->n), ud->name, (unsigned long) AGID(ud->n), AGSEQ(ud->n));
 154   printf("  ptr: %p\n", ud->n);
 155   printf("  Symbols:\n");
 156   se = agfstout(g, ud->n);
 157   sym=0;
 158   while ((sym = agnxtattr(g,AGNODE,sym))!=NULL)
 159          printf("    %s = '%s'\n",sym->name,sym->defval);
 160 #if 0
 161   printf("  Out edges: d-out=%d u-out=%d\n", agdegree(g, ud->n, 0, 1), agcountuniqedges(g, ud->n, 0, 1));
 162 #endif
 163   while (se) {
 164     printf("    name: '%s', head: '%s', tail: '%s' id=%lud, seq=%d %p\n",
 165            agnameof(se), agnameof(aghead(se)), agnameof(agtail(se)), (unsigned long) AGID(se), AGSEQ(se), (void*)se);
 166     se = agnxtout(g, se);
 167   }
 168 #if 0
 169   printf("  In edges: d-in=%d u-in=%d\n", agdegree(g, ud->n, 1, 0), agcountuniqedges(g, ud->n, 1, 0));
 170 #endif
 171   se = agfstin(g, ud->n);
 172   while (se) {
 173     printf("    name: '%s', head: '%s', tail: '%s' îd=%lu seq=%d %p\n",
 174            agnameof(se), agnameof(aghead(se)), agnameof(agtail(se)), (unsigned long) AGID(se), AGSEQ(se), (void*)se);
 175     se = agnxtin(g, se);
 176   }
 177 #if 0
 178   printf("  Edges: d-io=%d u-io=%d\n", agdegree(g, ud->n, 1, 1), agcountuniqedges(g, ud->n, 1, 1));
 179 #endif
 180   se = agfstedge(g, ud->n);
 181   while (se) {
 182     printf("    name: '%s', head: '%s', tail: '%s' id=%lud seq=%d %p\n",
 183            agnameof(se), agnameof(aghead(se)), agnameof(agtail(se)), (unsigned long) AGID(se), AGSEQ(se), (void*)se);
 184     se = agnxtedge(g, se, ud->n);
 185   }
 186   return 0;
 187 }
 188
 189 /*-------------------------------------------------------------------------* \
 190  * Method: n.delete(self)
 191  * Delete a node. All associated edges are deleted as well.
 192  * Returns non-nil on success.
 193  * Example:
 194  * rv, err = n:delete(h)
 195 \*-------------------------------------------------------------------------*/
 196 static int gr_delete(lua_State *L)
 197 {
 198   Agraph_t *g;
 199   gr_node_t *ud = tonode(L, 1, NONSTRICT);
 200
 201   if (ud->n != NULL){
 202     /* Delete all associated edges with tail on this node */
 203     g = agraphof(ud->n);
 204     if (ud->status == ALIVE){
 205       TRACE("   n.delete(): deleting node '%s' ud=%p id=0x%0lx (%s %d) \n",
 206             agnameof(ud->n), (void *) ud, (unsigned long) AGID(ud->n), __FILE__, __LINE__);
 207       agdelnode(g, ud->n);
 208     }
 209   } else {
 210     TRACE("   n:delete(): ud=%p already closed (%s %d)\n", (void *)ud, __FILE__, __LINE__);
 211   }
 212   lua_pushnumber(L, 0);
 213   return 1;
 214 }
 215
 216 /*
 217  * Provided for external access to gr_delete function.
 218  */
 219 int gr_delete_node(lua_State *L)
 220 {
 221   return gr_delete(L);
 222 }
 223
 224 /*-------------------------------------------------------------------------*\
 225  * Method: n.degree(self, what)
 226  * Determines degree of a node.
 227  * Returns number of in-edges (what='*i'), out-edges (what='*o') or the sum
 228  * of all edges (what='*a') to/from/of a node.
 229  * Example:
 230  * rv, err = n:degree("*i")
 231 \*-------------------------------------------------------------------------*/
 232 int gr_degree(lua_State *L)
 233 {
 234   int count = 0;
 235   Agedge_t *e;
 236   Agraph_t *g;
 237   Agnode_t *n;
 238   gr_node_t *ud = tonode(L, 1, STRICT);
 239   char *flag = (char *) luaL_optstring(L, 2, "*a");
 240   int indeg = TRUE;
 241   int outdeg = TRUE;
 242   n = ud->n;
 243   g = agroot(ud->n);
 244   if (*flag != '*'){
 245     luaL_error(L, "invalid format specifier");
 246     return 0;
 247   }
 248   switch(*(flag+1)){
 249   case 'i': outdeg = FALSE; break;
 250   case 'o': indeg = FALSE; break;
 251   }
 252   if (indeg){
 253     for (e = agfstin(g, n); e; e = agnxtin(g, e)){
 254       count++;
 255     }
 256   }
 257   if (outdeg){
 258     for (e = agfstout(g, n); e; e = agnxtout(g, e)){
 259       count++;
 260     }
 261   }
 262   lua_pushnumber(L, count);
 263   return 1;
 264 }
 265
 266 /*-------------------------------------------------------------------------*\
 267  * Property: n.graph
 268  * Determines the graph to which of a node belongs.
 269  * Returns graph userdata.
 270  * Example:
 271  * rv = n.graph
 272 \*-------------------------------------------------------------------------*/
 273 int gr_graphof(lua_State *L)
 274 {
 275   gr_node_t *ud = tonode(L, 1, STRICT);
 276   Agraph_t *g = agraphof(ud->n);
 277   if (g == NULL){
 278     lua_pushnil(L);
 279     lua_pushstring(L, "no graph");
 280     return 2;
 281   }
 282   return get_object(L, g);
 283 }
 284
 285 /*-------------------------------------------------------------------------*\
 286  * Method: e, tail, head = n.edge(self, node, label, flag)
 287  * Finds or creates an edge. The given node is the tail of the edge.
 288  * The created node is the the edge.
 289  * Label is optional.
 290  * The optional flag nocreate=true inhibits auto-creation of the edge.
 291  * Any node given by name is implicitly created and it's userdata returned
 292  * as additional results - even if nocreate is not set.
 293  * Example:
 294  * e, tail, head = n.edge(head, "edge-1", true | false)
 295  * e, tail, head = e:node("headname", "edge-1", true | false)
 296 \*-------------------------------------------------------------------------*/
 297 static int gr_edge(lua_State *L)
 298 {
 299   Agedge_t *e;
 300   gr_edge_t *edge;
 301   int rv;
 302   char *label;
 303   char ename[32];
 304   Agraph_t *g;
 305   gr_node_t *head;
 306   gr_node_t *tail = tonode(L, 1, STRICT);
 307
 308   g = agroot(tail->n);
 309
 310   if (lua_isuserdata(L, 2))
 311     head = tonode(L, 2, STRICT);
 312   else {
 313     lua_pushcfunction(L, gr_create_node);             /* tail, nhead, (label), (nocreate), func */
 314     get_object(L, agroot(tail->n));                   /* tail, nhead, (label), (nocreate), func, graph */
 315     lua_pushvalue(L, 2);                              /* ... func, graph, nhead */
 316     if (lua_isboolean(L, 4))
 317       lua_pushvalue(L, 4);                            /* ... func, graph, nhead, (nocreate) */
 318     else
 319       lua_pushboolean(L, 0);                          /* ... func, graph, nhead, false */
 320     lua_call(L, 3,  1);                              /* tail, nhead, (label), head */
 321     if (lua_isnil(L, -1))
 322       return  2;
 323     head = tonode(L, -1, STRICT);
 324     lua_pop(L,1);                                    /* tail, nhead, (label) */
 325   }
 326
 327   g = agroot(tail->n);
 328   if (g != agroot(head->n)){
 329     luaL_error(L, "head/tail not in same graph");
 330   }
 331   label = (char *) luaL_optstring(L, 3, NULL);         /* ud, peer, name, (flag) */
 332   if ((e = agedge(g, tail->n, head->n, label, 0)) != NULL){
 333     rv = get_object(L, e);                           /* ud, peer, name, (flag), edge */
 334     if (lua_isnil(L, -rv)){
 335       /* not yet registered */
 336       lua_pop(L, rv);                                /* ud, peer, name, (flag) */
 337       edge = lua_newuserdata(L, sizeof(gr_edge_t));  /* ud, peer, name, (flag), edge */
 338       edge->e = e;
 339       if (label)
 340         agset(e, "label", label);
 341       edge->name = strdup(agnameof(e));
 342       edge->type = AGEDGE;
 343       edge->status = ALIVE;
 344       new_edge(L);
 345       lua_pushlightuserdata(L, tail);
 346       lua_pushlightuserdata(L, head);     /* ud, peer, name, (flag), edge, tail, head */
 347       return 3;
 348     } else {
 349       /* Edge already registered */
 350       lua_pushlightuserdata(L, tail);
 351       lua_pushlightuserdata(L, head);
 352       return rv + 2;                 /* ud, peer, name, (flag), edge, tail, head */
 353     }
 354   } else {
 355     /* Edge does not exist */
 356     if (lua_toboolean(L, 4)){
 357       lua_pushnil(L);
 358       lua_pushstring(L, "edge not found");
 359       return 2;
 360     }
 361     edge = lua_newuserdata(L, sizeof(gr_edge_t));
 362     sprintf(ename, "edge@%u", newid());
 363     if ((edge->e = agedge(g, tail->n, head->n, ename, 1)) == NULL){
 364       luaL_error(L, "agedge failed");
 365       return 0;
 366     }
 367     if (label)
 368       agset(edge->e, "label", label);
 369     edge->name = strdup(agnameof(edge->e));
 370     edge->type = AGEDGE;
 371     edge->status = ALIVE;
 372     new_edge(L);
 373     lua_pushlightuserdata(L, tail);
 374     lua_pushlightuserdata(L, head);
 375     return 3;
 376   }
 377 }
 378
 379 /*-------------------------------------------------------------------------*\
 380  * Method: e = nextedge(self, prev)
 381  * Retrieves next edge of a node.
 382  * Returns the next edge of the given node. With nil as prev the first
 383  * edge is returned.
 384  * Example:
 385  * first = n:nextedge(nil)
 386  * second = n:nextedge(first)
 387  * third = n:nextedge(second)
 388 \*-------------------------------------------------------------------------*/
 389 static int gr_nextedge(lua_State *L)
 390 {
 391   int rv;
 392   char sbuf[32];
 393   Agraph_t *g;
 394   Agedge_t *e;
 395   gr_edge_t *ud_e;
 396   gr_node_t *ud_n = tonode(L, 1, STRICT);
 397   g = agroot(ud_n->n);
 398
 399   if (lua_isnil(L, 2)){
 400     e = agfstedge(g, ud_n->n);
 401   } else {
 402     ud_e = toedge(L, 2, STRICT);
 403     e = agnxtedge(g, ud_e->e, ud_n->n);
 404   }
 405   if (!e){
 406     /* no more edges */
 407     lua_pushnil(L);
 408     return 1;
 409   } else {
 410     /* Check whether userdata exists .. */
 411     rv = get_object(L, e);
 412     if (rv == 1){
 413       /* .. yes: return it */
 414       return rv;
 415     } else {
 416       /* .. no: create it */
 417       lua_pop(L, rv);
 418       ud_e = lua_newuserdata(L, sizeof(gr_edge_t));
 419       ud_e->e = e;
 420       sprintf(sbuf, "edge@%lu", (unsigned long) AGID(e));
 421       ud_e->name = strdup(sbuf);
 422       ud_e->type = AGEDGE;
 423       ud_e->status = ALIVE;
 424       set_object(L, e);
 425       return new_edge(L);
 426     }
 427   }
 428 }
 429
 430 /*-------------------------------------------------------------------------*\
 431  * Iterator: walkedges()
 432  * Iterator over all edges of a given node.
 433  * Example:
 434  * for n in g:walkedges() do ... end
 435 \*-------------------------------------------------------------------------*/
 436 static int gr_walkedges(lua_State *L)
 437 {
 438   lua_pushcfunction(L, gr_nextedge);     /* ud, nextedge */
 439   lua_pushvalue(L, -2);                  /* ud, nextedge, n */
 440   lua_pushnil(L);                        /* ud, nextedge, n, nil */
 441   return 3;
 442 }
 443
 444 /*-------------------------------------------------------------------------*\
 445  * Method: e = nextinput(self, prev)
 446  *         e = nextoutput(self, prev)
 447  * Same behaviour as nextedge, but only input or output edges are returned.
 448  * Example:
 449  * first = n:nextinput(nil)
 450  * second = n:nextinput(first)
 451  * third = n:nextinput(second)
 452 \*-------------------------------------------------------------------------*/
 453 typedef Agedge_t* (edge_first_iter_t)(Agraph_t *g, Agnode_t *n);
 454 typedef Agedge_t* (edge_next_iter_t)(Agraph_t *g, Agedge_t *e);
 455
 456 static int gr_nextinout(lua_State *L, edge_first_iter_t *fst, edge_next_iter_t *nxt)
 457 {
 458   int rv;
 459   Agedge_t *e;
 460   char sbuf[32];
 461   gr_edge_t *ud_e;
 462   gr_node_t *ud_n = tonode(L, 1, STRICT);
 463   Agraph_t *g = agroot(ud_n->n);
 464
 465   if (lua_isnil(L, 2))
 466     e = fst(g, ud_n->n);
 467   else {
 468     ud_e = toedge(L, 2, STRICT);
 469     e = nxt(g, ud_e->e);
 470   }
 471   if (!e){
 472     /* no more nodes */
 473     lua_pushnil(L);
 474     return 1;
 475   } else {
 476     /* Check whether userdata exists .. */
 477     rv = get_object(L, e);
 478     if (rv == 1)
 479       /* .. yes: return it */
 480       return rv;
 481     else {
 482       /* .. no: create it */
 483       lua_pop(L, rv);
 484       ud_e = lua_newuserdata(L, sizeof(gr_edge_t));
 485       ud_e->e = e;
 486       sprintf(sbuf, "edge@%lu", (unsigned long) AGID(e));
 487       ud_e->name = strdup(sbuf);
 488       ud_e->type = AGEDGE;
 489       set_object(L, e);
 490       return new_edge(L);
 491     }
 492   }
 493 }
 494
 495 static int gr_nextinput(lua_State *L)
 496 {
 497   return gr_nextinout(L, agfstin, agnxtin);
 498 }
 499
 500 static int gr_nextoutput(lua_State *L)
 501 {
 502   return gr_nextinout(L, agfstout, agnxtout);
 503 }
 504 /*-------------------------------------------------------------------------*\
 505  * Iterator: e = n.walkinputs(self)
 506  * Iterator over all input edges of a given node.
 507  * Example:
 508  * for e in n:walkinputs() do ... end
 509 \*-------------------------------------------------------------------------*/
 510 static int gr_walkinputs(lua_State *L)
 511 {
 512   lua_pushcfunction(L, gr_nextinput);    /* ud, nextedge */
 513   lua_pushvalue(L, -2);                  /* ud, nextedge, n */
 514   lua_pushnil(L);                        /* ud, nextedge, n, nil */
 515   return 3;
 516 }
 517
 518 /*-------------------------------------------------------------------------*\
 519  * Iterator: e = walkoutputs(self)
 520  * Iterator over all input edges of a given node.
 521  * Example:
 522  * for e in n:walkoutputs() do ... end
 523 \*-------------------------------------------------------------------------*/
 524 static int gr_walkoutputs(lua_State *L)
 525 {
 526   lua_pushcfunction(L, gr_nextoutput);    /* ud, nextedge */
 527   lua_pushvalue(L, -2);                  /* ud, nextedge, n */
 528   lua_pushnil(L);                        /* ud, nextedge, n, nil */
 529   return 3;
 530 }
 531
 532 /*-------------------------------------------------------------------------*\
 533  * Metamethod: __tostring [boolean]
 534  * Return a string presentation of a graph object.
 535  * Example:
 536  * g == h or g != h with metamethods
 537 \*-------------------------------------------------------------------------*/
 538 static int gr_tostring(lua_State *L)
 539 {
 540   gr_object_t *ud = toobject(L, 1, NULL, NONSTRICT);
 541   lua_pushfstring(L, "node: %p (%s)", ud, ud->p.status == ALIVE ? "alive" : "dead");
 542   return 1;
 543 }