ex0ns

about
A Computer Science Student's blog, about programming, algorithms, hack and a lot more.

[Ruby] Graph drawing and Minimum Spanning Tree

10 Feb 2015

Hi, Here is an other article about graphs, in the first time we'll see how to actually draw a graph, it'll help us to get a visual representation of our work. However, We'll not see how the graphs drawing algorithms work (not yet at least), we'll use GraphViz !

Graph Drawing

GraphViz has a ruby interface available on github, a simple:

gem install ruby-graphviz

should do the work ! From here, our work is really simple, we only need to add a draw function to our Graph class (see last article here, here is the code:

require 'graphviz'
def draw(edge_label = true, filename = "graph.png", format = :png)
  g = GraphViz.new(:G, :type => :graph)
  nodes = vertices.map { |v| [v, g.add_nodes(v.id.to_s)] }.to_h
  edges.each do |edge|
    _edge = g.add_edges(nodes[edge.either], nodes[edge.other(edge.either)])
    _edge[:label] = _edge.weight if(edge_label)
  end
  g.output(format => filename)
end

GraphViz uses its own Edge and Node class, thus, we need to convert our vertices and edges. To do so, we create an hash with the old vertices as keys and the GraphViz's vertices as the values. Here we are, we can now easily draw our graphs !
For the second part of the article, we'll study a Minimum Spanning Tree algorithm called Prim's algorithm !

Minimum spanning tree

Introduction

A spanning tree is a tree that connects all the vertices of a graph together, it may not use all the edges to do so. A minimum spanning tree is a spanning tree which total weight is the lowest. For a given graph, there might exists more than one minimum spanning tree. Minimum spanning tree can be used in many application, such as network design (minimum cost for electrical network) or some NP problems approximation (Traveling Salesman for example). There are many MST (Minimum spanning tree) algorithm, but we'll study Prim's one. With this algorithm we start from any vertex of the graph and we add to the MST the minimum-weighted edge connected to this vertex, we also add the other vertex of the edge to our tree, we then repeat this step without forgetting to check that not both vertices of the minimum-weighted edge already are in the tree, we do that until we reached all the vertices. Here is an illustration of the execution of Prim's algorithm on a graph: prim's algorithm With the work we have done before, it should not be too hard to implement this algoritm, here is the pseudo code, G is the Graph, w is the weight function, where w(u, v) is the weight of the edge from u to v, and r is the root (starting vertex)

Prim(G, w, r)
    Make a priority queue Q containing all the vertices of G
    Set the priority of the root to 0 in Q
    Set the priority to infinity for all other members of Q 
    Set the parent of the root to be null
    while Q is not empty
        Let's U be the minimum of the priority queue
        For each adjacent vertex V of U
            if V is in Q dans w(U,V) < priority of V
                Set the parent of V to U (we are coming from U to V)
                Set the priority of V to w(U,V)

As you can see, the trick here is to use a priority queue, with that we can get the vertex with minimum cost really fast, it's the core of the algorithm (once again, we see that knowing some data structure is really mandatory when it comes to algorithm). Unfortunately ruby does not provide any PriorityQueue implementation, but, as always, there is a gem which will save our lives ! (We'll implement our own priority queue soon, but it would be off topic to explain it here). As always

gem install PriorityQueue

Here is the documentation we are now ready to create our Minimum Spanning Tree class !

Implementation

Our MST class initializer is going to take a Graph (UndirectedGraph) as parameter:

class MST
  require 'priority_queue'

  def initialize(graph)
    @mst = Queue.new # The priority queue containing the vertices of the MST
    @graph = graph 
    @marked = Hash.new # We will add the visited vertices to this hash (Hash#has_key? is on O(1) whereas Array#include? is O(n)) 
    @minPQ = PriorityQueue.new # Our priority queue
    @weight = 0 # The MST weight
    @graph.vertices.each do |vertex|
      prim(vertex) if !marked?(vertex) # We run prim from vertex if not already visited
    end
  end

end

As you can see we need more than only one priority queue, we have to remember the visited vertex and keep track of edges in the MST. Before we actually write the "prim" function, let's code the marked? one:

def marked?(vertex)
  @marked.has_key?(vertex)
end

Pretty simple right, here is the prim's one

def prim(vertex)
  scan(vertex)
  until @minPQ.empty?
    edge = @minPQ.delete_min[0]
    from = edge.either
    to = edge.other(from)
    next if(marked?(from) && marked?(to))
    @mst.push(edge)
    @weight += edge.weight
    scan(from) if !marked?(from)
    scan(to) if !marked?(to)
  end
end

As you can see our implementation is not following the pseudo code, indeed, we use the priority queue to store the edge and not the vertices, and we are using the marked? function instead of setting the cost of the vertex to infinity. This code seems simple, but what is purpose of the scan function ? The scan function only checks if we already visited this node and add it to the @marked array if not, and then, for each connected edge, add it to the priority queue, here is the code

def scan(vertex)
  raise 'Already marked' if marked?(vertex)
  @marked[vertex] = true
  @graph.adj(vertex).each do |edge| # look in the adjacency list of the graph
    @minPQ[edge] = edge.weight if(!marked?(edge.other(vertex)))
  end
end

And we now have a working Prim's algorithm to generate a Minimum Spanning tree of a Graph ! But we are not done yet, it could be useful to get a graph from this MST and not only a Queue with all edges, let's create a fonction which generate an UndirectedGraph from this queue.

def generate_graph
  graph = UndirectedGraph.new(@graph.vertices)
  until @mst.empty?
    edge = @mst.pop
    graph.add_edge(edge)
  end
  graph
end

Now we are done ! Here is the final class, along with an example to test (this is the same graph as in the previous article)

class MST
  require 'priority_queue'

  attr_reader :weight

  def initialize(graph)
    @mst = Queue.new # The priority queue containing the vertices of the MST
    @graph = graph 
    @marked = Hash.new # We will add the visited vertices to this hash (Hash#has_key? is on O(1) whereas Array#include? is O(n)) 
    @minPQ = PriorityQueue.new # Our priority queue
    @weight = 0 # The MST weight
    @graph.vertices.each do |vertex|
      prim(vertex) if !marked?(vertex) # We run prim from vertex if not already visited
    end
  end

  def generate_graph
    graph = UndirectedGraph.new(@graph.vertices)
    until @mst.empty?
      edge = @mst.pop
      graph.add_edge(edge)
    end
    graph
  end

  private

  def prim(vertex)
    scan(vertex)
    until @minPQ.empty?
      edge = @minPQ.delete_min[0]
      from = edge.either
      to = edge.other(from)
      next if(marked?(from) && marked?(to))
      @mst.push(edge)
      @weight += edge.weight
      scan(from) if !marked?(from)
      scan(to) if !marked?(to)
    end
  end

  def scan(vertex)
    raise 'Already marked' if marked?(vertex)
    @marked[vertex] = true
    @graph.adj(vertex).each do |edge| # look in the adjacency list of the graph
      @minPQ[edge] = edge.weight if(!marked?(edge.other(vertex)))
    end
  end

  def marked?(vertex)
    @marked.has_key?(vertex)
  end

end

And the example (graph.txt contains the same values as in the previous article)

require './MST.rb'
require './UndirectedGraph.rb'
require './Edge.rb'
require './Vertex.rb'

response = open('graph.txt').read.split("\n")
graph = UndirectedGraph.new()
response.each do |stredge|
    l = stredge.split(" ")
    e = Edge.new(Vertex.new(l[0]), Vertex.new(l[1]), l[2].to_f)
    graph.add_edge(e)
end

mst = MST.new(graph)
p mst.weight
mst.generate_graph.draw

The resulting graph is: Graph Mst

A nice feature we could add is generate a gif file from this MST class, showing all the steps that leaded to the minimum spanning tree, I may add this in a near future ! Once again, thank you for reading, and don't forget to give me feedback !