flow-101.lua

-- Problem: there is a directed graph and a subset of some A
-- associated with each node. An element of A traverses the graph
-- along the edges from start node S to finish node F, only
-- passing through nodes with sets containing the element.
-- Calculate set of possible visiting elements for each node.

-- Solution: resulting set for a node N is intersection of two sets:
-- set of elements that can reach N from S and set of elements that
-- can reach F from N. They can be calculated for each node separately
-- using forward and backward flow analysis correspondingly, where
-- the lattice is subsets of A ordered by inclusion, transfer function is
-- intersection with associated set, join function is union and initial value
-- is whole A.

local function intersection(set1, set2)
   local res = {}

   for element in pairs(set1) do
      if set2[element] then
         res[element] = true
      end
   end

   return res
end

local function update(set1, set2)
   for element in pairs(set2) do
      set1[element] = true
   end
end

local function is_subset(set1, set2)
   for element in pairs(set1) do
      if not set2[element] then
         return false
      end
   end

   return true
end

local function append(queue, node)
   if not queue[node] then
      queue.last = queue.last + 1
      queue[queue.last] = node
   end
end

local function pop_front(queue)
   if queue.first <= queue.last then
      local node = queue[queue.first]
      queue.first = queue.first + 1
      queue[node] = nil
      return node
   end
end

local function set_reaching_elements(nodes, base_set, forward)
   local index = forward and "forward" or "backward"

   for _, node in ipairs(nodes) do
      node[index] = base_set
   end

   local queue = {first = 1, last = 0}

   if forward then
      for i = #nodes, 1, -1 do
         append(queue, nodes[i])
      end
   else
      for _, node in ipairs(nodes) do
         append(queue, node)
      end
   end

   while true do
      local node = pop_front(queue)

      if not node then
         break
      end

      local input

      if node == nodes[forward and #nodes or 1] then
         input = base_set
      else
         input = {}

         for _, another_node in ipairs(node[not forward]) do
            update(input, another_node[index])
         end
      end

      local new_output = intersection(node.filter, input)


      if not is_subset(node[index], new_output) then
         node[index] = new_output

         for _, yet_another_node in ipairs(node[forward]) do
            append(queue, yet_another_node)
         end
      end
   end
end

local function set_results(nodes, base_set)
   set_reaching_elements(nodes, base_set, true)
   set_reaching_elements(nodes, base_set, false)

   for _, node in ipairs(nodes) do
      node.result = intersection(node.forward, node.backward)
   end
end

local function postorder_visit(node, visited_set, exited_nodes)
   visited_set[node] = true

   for _, successor in ipairs(node[true]) do
      if not visited_set[successor] then
         postorder_visit(successor, visited_set, exited_nodes)
      end
   end

   table.insert(exited_nodes, node)
end

local function add_node(nodes, index)
   if not nodes[index] then
      nodes[index] = {
         index = index,
         [true] = {},
         [false] = {}
      }
   end

   return nodes[index]
end

local function read_graph()
   local nodes = {}
   local base_set = {}
   local i = 1

   while true do
      local line = io.stdin:read("*l")

      if not line then
         break
      end

      local node = add_node(nodes, i)

      for part in line:gmatch("%S+") do
         if node.filter then
            local successor = add_node(nodes, assert(tonumber(part), part.." is not a number"))
            table.insert(node[true], successor)
            table.insert(successor[false], node)
         else
            node.filter = {}

            for char in part:gmatch(".") do
               node.filter[char] = true
               base_set[char] = true
            end
         end
      end

      i = i + 1
   end

   return nodes[1], base_set
end

local function concat_set(set)
   local chars = {}

   for char in pairs(set) do
      table.insert(chars, char)
   end

   table.sort(chars)
   return table.concat(chars)
end

local function write_graph(nodes)
   for _, node in ipairs(nodes) do
      print(("%d: '%s' ('%s' * '%s')"):format(node.index,
         concat_set(node.result), concat_set(node.forward), concat_set(node.backward)))
   end
end

local function main(args)
   if #args > 0 then
      io.stdout:write("No arguments expected.\n")
      io.stderr:write("Enter space separated filter and successors.\n")
      os.exit(0)
   else
      local graph, base_set = read_graph(io.stdin)

      if not graph then
         io.stderr:write("Graph is empty.\n")
         os.exit(1)
      else
         local nodes = {}
         postorder_visit(graph, {}, nodes)
         set_results(nodes, base_set)
         write_graph(nodes)
         os.exit(0)
      end
   end
end

main(arg)