Hi, It's been a while since the last time I wrote something, I was quite busy, and I'm currently working on an C++ Game Engine, which takes almost all my spare time. Today we are talking about graphs, graphs are powerful and can be used to solve many problems, it's a pretty big topic so I'm going to split it in severals articles, this one is about graph representation because when it comes to graphs the main question is : "How do I represent a graph in a program ?", hence we will not see any algorithm on graph today, but we'll create the data structure we'll need later ! I'll use ruby for this article, as it's quite versatile, and will save us time.

### Vertices

The vertices are the component of the graph we want to connect, they have a name (or any kind of identifier), may have a weight, and... and it's all, vertices are really simple objects, here is the class for vertex:

```
class Vertex
include Comparable
attr_accessor :weight
attr_reader :id
def initialize(id, weight = 0)
@id = id
@weight = weight
end
def <=>(other)
@id<=>other.id
end
def hash
@id.hash
end
def eql?(other)
hash == other.hash
end
end
```

The code is pretty self explanatory, but We need to include Comparable in our class so that we can compare and distinguish vertices, we also need to add the *hash* and *eql?* methods as we'll use vertices as key in a Hash!
The identifier can be anything (Fixnum, String, ...) but mush also be a Comparable.
Not that we have our vertices, let's see how to connect them !

### Edges

An edge is a connection between two vertices, it can be directed or undirected, and have a weight, the power of the graph theory is that this 'weight' can represent almost anything, from a distance to a flux or even a price, here is the code

```
class Edge
include Comparable
attr_reader :weight, :from, :to
def initialize(from, to, weight)
@from = from
@to = to
@weight = weight
end
def either
@from
end
def other(vertex)
(vertex == @from) ? @to : @from
end
def <=>(edge)
@weight<=>edge.weight
end
end
```

Once again, the implementation is pretty clear, we need to include Comparable to compare edge (only the weight comparison is interesting here), the methods either and other are a nice way to find the two vertices of an undirected edge !

As you can see, the two previous class were pretty simple, and we'll now need a graph class to connect both of them !

### Weighted Graph

In a graph we need to keep track of the edge between to vertices, there is two way of doing that, either the adjency list or adjacency matrix both have their pros and cons, but we'll use ans adjacency list for our implementation, first we'll need a constructor which can take an array of vertices (or nil):

```
def initialize(vertices = nil)
@adj = Hash.new
if(!vertices.nil?)
vertices.each { |vertex| @adj[vertex] = Array.new }
end
@edge_number = 0
end
```

We use a Hash to keep a track of the vertices, each of the vertices is associated with an empty array, this array will store the edges connected to it, let's code a method to add an edge to the graph, if one of the vertices of the edge is not in the graph, we'll add it.

```
def add_edge(edge)
v1 = get_or_create(edge.either)
v2 = get_or_create(edge.other(v1))
@adj[v1].push(edge)
if(v1 != v2) then @adj[v2].push(edge) end # If start == from we don't want to add the edge twice
@edge_number += 1
end
```

As our vertices are objects, we need to be sure that we use the same reference for all the edge, this is why we need to create a helper method "get*or*create" which will search in @adj.keys if there already exists such a vertex, and create it if not found, here is this helper

```
def get_or_create(vertex)
array_id = vertices.find_index(vertex)
return vertices[array_id] if array_id
@adj[vertex] = Array.new
vertex
end
```

We now have an almost fully functional graph, but we need to add some getter methods to retrieve the edges, the vertices, and the adjacendy vertices.

```
def edges # returns an Array containing all the graph vertices
edges = Array.new
@adj.each do |vertex, _edges|
_edges.each do |edge|
if(edge.other(vertex) > vertex) # as we are currently using un undirected graph, we don't want to add the same edge twice
edges.push(edge)
end
end
end
end
def vertices_number
@adj.size
end
def vertices
@adj.keys
end
def adj(vertex)
validate_vertex(vertex)
@adj[vertex].dup
end
def degree(vertex)
validate_vertex(vertex)
@adj[vertex].size
end
```

We don't need to do an edge_number method as edge_number property is a attr_reader (getter created by ruby), the edges method loop through the hash and add the edges if not already added, it's one of the only method you would have to change to go from an undirected graph to a directed one (along with add_edge). In the previous method, there is a method validate_vertex, which throw an exception if the vertex is not in the graph, here is the method:

```
private
def validate_vertex(vertex)
raise 'Vertex is not part of the graph' if !@adj.has_key?(vertex)
end
```

The UndirectedGraph class is ready to be used, here is the complete class:

```
class UndirectedGraph
require './Edge.rb'
require './Vertex.rb'
attr_reader :edge_number
def initialize(vertices = nil)
@adj = Hash.new
if(!vertices.nil?)
vertices.each { |vertex| @adj[vertex] = Array.new }
end
@edge_number = 0
end
def add_edge(edge)
v1 = get_or_create(edge.either)
v2 = get_or_create(edge.other(edge.either))
edge = Edge.new(v1, v2, edge.weight)
@adj[v1].push(edge)
if(v1 != v2) then @adj[v2].push(edge) end # If start == from we don't want to add the edge twice
@edge_number += 1
end
def edges # returns an Array containing all the graph vertices
edges = Array.new
@adj.each do |vertex, _edges|
_edges.each do |edge|
if(edge.other(vertex) > vertex) # as we are currently using un undirected graph, we don't want to add the same edge twice
edges.push(edge)
end
end
end
edges
end
def vertices_number
@adj.size
end
def vertices
@adj.keys
end
def adj(vertex)
validate_vertex(vertex)
@adj[vertex].dup
end
def degree(vertex)
validate_vertex(vertex)
@adj[vertex].size
end
private
def validate_vertex(vertex)
raise 'Vertex is not part of the graph' if !@adj.has_key?(vertex)
end
def get_or_create(vertex)
array_id = vertices.find_index(vertex)
return vertices[array_id] if !array_id.nil?
@adj[vertex] = Array.new
vertex
end
end
```

Let's see how we can use it to represent an actual graph, we will read the following graph: For testing purposes, I recommend you to create an text file with the following structure:

```
from to weight
```

Here is the one for the previous graph:

```
a b 4
a h 8
b h 11
b c 8
c i 2
c d 7
c f 4
d f 14
d e 9
e f 10
f g 2
g i 6
g h 1
h i 7
```

Here is a ruby code to read it and create the graph:

```
require './UndirectedGraph.rb'
require './Vertex.rb'
require './Edge.rb'
data = open('graph.txt').read.split("\n")
graph = UndirectedGraph.new
data.each do |strdata|
strdata = strdata.split(" ")
v1 = Vertex.new(strdata[0], 0) # We don't want our vertex to have a weight
v2 = Vertex.new(strdata[1], 0) # Same here
edge = Edge.new(v1, v2, strdata[2].to_f)
graph.add_edge(edge)
end
graph.edges.each do |edge|
p edge
end
```

Here is the ouput:

```
#<Edge:0x00000001e57558 @from=#<Vertex:0x00000001e57698 @id="a", @weight=0>, @to=#<Vertex:0x00000001e57670 @id="b", @weight=0>, @weight=4.0>
#<Edge:0x00000001e57328 @from=#<Vertex:0x00000001e57698 @id="a", @weight=0>, @to=#<Vertex:0x00000001e57418 @id="h", @weight=0>, @weight=8.0>
#<Edge:0x00000001e57120 @from=#<Vertex:0x00000001e57670 @id="b", @weight=0>, @to=#<Vertex:0x00000001e57418 @id="h", @weight=0>, @weight=11.0>
#<Edge:0x00000001e56f18 @from=#<Vertex:0x00000001e57670 @id="b", @weight=0>, @to=#<Vertex:0x00000001e57008 @id="c", @weight=0>, @weight=8.0>
#<Edge:0x00000001e55ac8 @from=#<Vertex:0x00000001e57418 @id="h", @weight=0>, @to=#<Vertex:0x00000001e56e00 @id="i", @weight=0>, @weight=7.0>
#<Edge:0x00000001e56d10 @from=#<Vertex:0x00000001e57008 @id="c", @weight=0>, @to=#<Vertex:0x00000001e56e00 @id="i", @weight=0>, @weight=2.0>
#<Edge:0x00000001e56b08 @from=#<Vertex:0x00000001e57008 @id="c", @weight=0>, @to=#<Vertex:0x00000001e56bf8 @id="d", @weight=0>, @weight=7.0>
#<Edge:0x00000001e56900 @from=#<Vertex:0x00000001e57008 @id="c", @weight=0>, @to=#<Vertex:0x00000001e569f0 @id="f", @weight=0>, @weight=4.0>
#<Edge:0x00000001e566f8 @from=#<Vertex:0x00000001e56bf8 @id="d", @weight=0>, @to=#<Vertex:0x00000001e569f0 @id="f", @weight=0>, @weight=14.0>
#<Edge:0x00000001e564f0 @from=#<Vertex:0x00000001e56bf8 @id="d", @weight=0>, @to=#<Vertex:0x00000001e565e0 @id="e", @weight=0>, @weight=9.0>
#<Edge:0x00000001e560e0 @from=#<Vertex:0x00000001e569f0 @id="f", @weight=0>, @to=#<Vertex:0x00000001e561d0 @id="g", @weight=0>, @weight=2.0>
#<Edge:0x00000001e562e8 @from=#<Vertex:0x00000001e565e0 @id="e", @weight=0>, @to=#<Vertex:0x00000001e569f0 @id="f", @weight=0>, @weight=10.0>
#<Edge:0x00000001e55ed8 @from=#<Vertex:0x00000001e561d0 @id="g", @weight=0>, @to=#<Vertex:0x00000001e56e00 @id="i", @weight=0>, @weight=6.0>
#<Edge:0x00000001e55cd0 @from=#<Vertex:0x00000001e561d0 @id="g", @weight=0>, @to=#<Vertex:0x00000001e57418 @id="h", @weight=0>, @weight=1.0>
```

Ok, I admit it does not seems really powerful here, but from this, we can really do a lot of things quite easily, the next time we'll see how to find the Minimum Spanning Tree of a graph.

Thank you for reading, and don't forget to give me feedback !