Force-directed graphs?

[clofresh]

Has anyone implemented something to lay out graphs in a nice way, like with a force-directed drawing algorithm? Something like this:

http://bl.ocks.org/mbostock/4062045

[Inny]

I played with the idea once. I'll post the code to facilitate discussion, but it needs a lot of work to be useful. It uses Middleclass, and I'm sure the other missing pieces like color definitions you can hack together yourself.

Code: Select all

Node = class('Node')

function Node:initialize(x, y, r)
  self.x = x
  self.y = y
  self.radius = r or 5
  self.color = color.GREEN
end

Network = class('Network')

function Network:initialize(level)
  self.level = level
  self.center_x = self.level.width / 2
  self.center_y = self.level.height / 2
  self:generateNodes()
end

function Network:generateNodes()
  self.edges = {}
  self.nodes = {}
  local partition = math.ceil(math.sqrt(self.level.nodes))
  local block_width = (self.level.width / partition)
  local block_height = (self.level.height / partition)

  for i = 1, self.level.nodes do
    self.edges[i] = {}
    for j = 1, self.level.nodes do
      self.edges[i][j] = false
    end
  end
  for i = 1, self.level.nodes do
    self.nodes[i] = Node(love.math.random(block_width*0.9) + (((i-1) % partition) * block_width),
      love.math.random(block_height*0.9) + (math.floor(((i-1) / partition)) * block_height))
  end

  for i = 1, self.level.nodes do
    local connects = {}
    local x = ((i-1) % partition)
    local y = math.floor(((i-1) / partition))

    for yy = y-1, y+1 do
      for xx = x-1, x+1 do
        if (xx ~= x or yy ~= y) and ((xx>=0) and (xx<partition) and (yy>=0) and (yy < partition)) then
          local id = 1 + yy*partition+xx
          if self.nodes[id] then
            connects[#connects+1] = id
          end
        end
      end
    end

    for a = 1, #connects - 1 do
      local b = love.math.random(a+1, #connects)
      connects[a], connects[b] = connects[b], connects[a]
    end

    local max_connects = love.math.random(1, 3)
    for k = 1, math.min(max_connects, #connects) do
      self.edges[i][connects[k]] = true
      self.edges[connects[k]][i] = true
    end

  end
end

local bearing = function(x1, y1, x2, y2)
  return math.atan2(y2 - y1, x2 - x1)
end

local distance = function(x1, y1, x2, y2)
  return math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))
end

-- coulombs law
local repulsion = function(x1, y1, x2, y2, dt)
  local proximity = math.max(0.01, distance(x1, y1, x2, y2))
  local magnitude = -10000 / math.pow(proximity, 2) * dt
  local theta = bearing(x1, y1, x2, y2)
  return magnitude * math.cos(theta), magnitude * math.sin(theta)
end

-- hooke's law
local attraction = function(x1, y1, x2, y2, dt, spring)
  local proximity = math.max(1, distance(x1, y1, x2, y2))
  local magnitude = 0.1 * math.max(0, proximity - spring) * dt
  local theta = bearing(x1, y1, x2, y2)
  return magnitude * math.cos(theta), magnitude * math.sin(theta)
end

local revolve = function(x1, y1, x2, y2, theta, dt)
  theta = theta * dt
  local px, py = x1 - x2, y1 - y2
  local c, s = math.cos(theta), math.sin(theta)
  return (c * px - s * py) - px, (s * px + c * py) - py
end

function Network:arrangeNodes(dt)
  local forces_x = {}
  local forces_y = {}
  for i = 1, #self.nodes do
    local node = self.nodes[i]
    -- all nodes are attracted to and orbitting the center
    -- local rx, ry = revolve(node.x, node.y, self.center_x, self.center_y, math.pi / 2, dt)
    -- local ax, ay = attraction(node.x, node.y, self.center_x, self.center_y, dt, 1000)
    -- local bx, by = repulsion(node.x, node.y, self.center_x, self.center_y, dt)
    forces_x[i] = 0 --ax-- + bx
    forces_y[i] = 0 --ay-- + by
  end

  for i = 1, #self.nodes do
    local node = self.nodes[i]

    for j = i, #self.nodes do
      if i ~= j then
        local other = self.nodes[j]
        if self.edges[i][j] then
          local fx, fy = repulsion(node.x, node.y, other.x, other.y, dt)
          forces_x[i] = forces_x[i] + fx
          forces_y[i] = forces_y[i] + fy
          forces_x[j] = forces_x[j] - fx
          forces_y[j] = forces_y[j] - fy
        end
        if self.edges[i][j] then
          local fx, fy = attraction(node.x, node.y, other.x, other.y, dt, self.level.width / 3)
          forces_x[i] = forces_x[i] + fx
          forces_y[i] = forces_y[i] + fy
          forces_x[j] = forces_x[j] - fx
          forces_y[j] = forces_y[j] - fy
        end
      end
    end
  end

  for i = 1, #self.nodes do
    local node = self.nodes[i]
    node.x = math.max(0, math.min(self.level.width, node.x + forces_x[i]))
    node.y = math.max(0, math.min(self.level.height, node.y + forces_y[i]))
  end
end


function Network:drawNodes()
  love.graphics.setColor(color.BLUE)
  love.graphics.circle("fill", self.center_x, self.center_y, 48, 16)
  love.graphics.setColor(color.PUREWHITE)
  for i = 1, #self.edges do
    for j = 1, #self.edges[i] do
      if self.edges[i][j] then
        love.graphics.line(self.nodes[i].x, self.nodes[i].y, self.nodes[j].x, self.nodes[j].y)
      end
    end
  end

  for i = 1, #self.nodes do
    love.graphics.setColor(self.nodes[i].color)
    love.graphics.circle("fill", self.nodes[i].x, self.nodes[i].y, self.nodes[i].radius, 16)
  end
end

-- level structure just to get the code working:
levels = {}
levels.example = {
  name = "example",
  nodes = 16,
  width = 1600,
  height = 900,
}

[rmcode]

I know this topic is quite old, but I'm currently working on getting a force directed layout working:

forceDirected.png (106.88 KiB) Viewed 1897 times

The dots represent folders, the circles represent files located in those folders. Files are attracted to the position of their parent folder and repulse each other. Connected folders attract and repulse each other. The mass of each folder is calculated from its file count and number of connected edges, so folder nodes with lots of content should be pushed further out.

It already works quite well for some structures, but I'm still lacking a force between all (and not just connected) nodes which should improve the layout. I am also struggling with how to structure the graph itself (using nested tables, or keep all nodes on the same level). I will make the repo public later today and post a link, but I still want to add a few things beforehand.

[rmcode]

Posted it in the projects section.