Describe a graph structure in Lua

Question

I need to build a user-friendly way to declare graphs in Lua. Users that will create the graphs are computer scientists that usually do not really know the Lua language.

Currently, the graphs are just plain tables. An example (not working) :

local x = "some text"
local a_graph = {
  a = 1,
  b = {
    c = x
  },
  c = {
    k = b
  }
}

A working version of the above graph description should be enough to build the graph where "k=b" is replaced by "k = reference to b" (yes, the "b" contained in "a_graph"). I can easily code the function to do the lookup (recursively visit parents and look at their direct children), but my problem is to detect and store that "b" is a reference. I also need to allow the "c = x" where x is an existing variable.

I have come to two solutions:

1. Use a function around the reference, itself written as text, for instance 'k = ref("b")'. I do not like this solution, because it is error-prone for my users (they may forget the "ref" or the quotes).

2. Moodify the __index of _G or _ENV to return something when a global lookup fails. I tested it and it works, but seems weird.

Is there another solution?

Answer 1

I think the most straightforward solution is to encode the graph structure in some dumb tables and use a constructor function to convert those tables into your preferred internal graph data structure. The constructor can also do error handling in a straightforward manner, since it can look at all the input (as opposed to something localized like your ref function).

Separating the input representation from the final result also lets you have more then one kind of representation. For example:

local graph_1 = adjacency_list {
  a = {'b'},
  b = {'a', 'c'},
  c = {'a'},
}

local graph_2 = list_of_edges {
  {'a', 'b'},
  {'b', 'a'},
  {'b', 'c'},
  {'c', 'a'},
}

local graph_2 = adjacency_matrix {
  {0, 1, 0},
  {1, 0, 1},
  {1, 0, 0},
}