Dungeon_Generator/Graph/MST.lua

-- ================
-- Private helpers
-- ================
local setmetatable = setmetatable
local Graph = require("Graph/Graph")
local Node = require("Graph/Node")
require("func")

local MST = {
_VERSION = "0"
}

function xor(a, b)
  return (a and not b) or (b and not a)
end

-- cost = function taking an edge as argument and returning its cost
function MST.search(g, cost)
  local res = Graph({g.vertices[1]}, {})
  for k,v in pairs(g.vertices) do

  end

  local nb_vertices = 1
  while nb_vertices < #(g.vertices) do
    local edges_not_in_res = filter(function(e)
      if res:contains_edge(e) then
        return false
      end
      return true
      end, g.edges)
    

    for _,e in pairs(edges_not_in_res) do

    end

    local edges_exiting_res = filter(function (e)
      local in_graph = 0
      for _,v in pairs(res.vertices) do
        if v.id == e.p1.id then
          in_graph = in_graph + 1
        end
        if v.id == e.p2.id then
          in_graph = in_graph + 1
        end
      end
      if in_graph == 1 then return true end
      return false
      end, edges_not_in_res)


    local min = nil
    local selected_edge = nil
    for _,e in pairs(edges_exiting_res) do
      c = cost(e)
      if min == nil or min > c then
        min = c
        selected_edge = e
      end
    end


    if not res:contains_vertex(selected_edge.p1) then
      res:append_vertex(selected_edge.p1)
      nb_vertices = nb_vertices + 1 
    end
    if not res:contains_vertex(selected_edge.p2) then
      res:append_vertex(selected_edge.p2)
      nb_vertices = nb_vertices + 1 
    end
    if not res:contains_edge(selected_edge) then
      res:append_edge(selected_edge)
    end

  end


  for k,v in pairs(res.vertices) do

  end
  return res
end

return MST