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: 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:

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 !