ex0ns

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

LXC - Networking

17 Sep 2015

I've heard a lot about virtualization recently with, at the top, docker. I wanted to understand a bit more about those, and I started with LXC which stands for Linux Containers, the goal of the project was (and is) to provide tools for lightweight virtualization.

Contrary to machine virtualization, which create a whole isolated system (VMWare and VirtualBox for example), LXC uses a system of container, those containers share portions of the host kernel and even part of the host operating system, meaning that containers have less overhead than 'heavy' virtualization. On the other hand, those containers do not guarantee as much isolation (hence security) of the system as machine virtualization does, as always, both have pros and cons, but this is not the topic of this article.

When I started this journey in virtualization, I had no background on system administration nor networking, and even if setting up a LXC containers is really easy, I've had a lot of trouble to connect the containers to the internet, and this is the topic of this article.

Requirement

You will obviously need LXC, I let you use your favorite package manager to get the last version. Then we will create a Ubuntu container with the following command (on arch, there was an issue with debootstrap and ubuntu keyrings, I had to do a yaourt -S ubuntu-keyring and create a symlink for 'gpg1v' : sudo ln -s /usr/bin/gpgv /usr/bin/gpg1v in order to solve this):

sudo lxc-create --name natContainer -t ubuntu

This will simply create us a container named natContainer with an ubuntu on it, we do not need to start it or to do anything with it for now, but if you want more details on LXC basis I recommend the DigitalOcean guide.

By default, containers do not have any internet connection, we will need to create a bridge interface between them and the host so they can be reached from the 'out world'. In fact, we aren't going to create a real bridge (which can be viewed as a virtual switch), but we will be doing NAT to the container (ServerFault post about bridge and NAT).

The main interest of using this technique is that the bridge is not linked to any existing interface, and as Wireless interface can't (at least for what I know) be bridged, it will work the same way almost anywhere.

As I said, we need a bridge interface, we'll see two ways of creating a bridge interface:

  • The first one with netctl a profile based network manager
  • And the other one with systemd-networkd which is the networking tool created by Systemd to setup network configuration with container (which is exactly our case).

I'm using my server as an host, the main interface is eth0 and its IP is my public IP, which is 5.196.95.238 at the time I'm writing this article but we don't really need this at all (as we are not doing Bridged Connection). What we want is to create a subnet on 192.169.100.0/24 and connect our container(s) to it (containers will behave like computer in a local network).

Our previously created container will be at 192.168.100.10 (we are only interested in static configuration) and have a SSH server running on port 22 (with the default ubuntu/ubuntu login), the goal of this article is to establish a ssh connection from my laptop. Here is the following network schema (as you can see, NATint makes my host behaves like a router).

If you already have some networking knowledge, you might want to skip the next two sections, they are meant to be a very brief introduction of some network related element we'll need after.

NAT Bridge

A NAT bridge is a virtual interface which isn't connected to any existing interface (sometimes described as 'standalone interface') it basically creates a private subnet to which we can connect our VMs and containers. In fact, NATting is really common in our home private network, this is one of the main purpose of your router. By default, devices on a private network can't be reach (or reach) the ouside world, but they can reach other machines on the same private network.

When setting up a NAT (on the gateway) all outgoing packets are going to be 'parsed' by the NAT and inserted in a lookup table, this table stores the source ip and port and destination ip and port. With that, when the NAT receives the response, it can redirect the packet to the correct device on the private network. NAT itself it not the topic of this article, so as always, if you're interested, there are a lot of great resources out there.

One thing you need to keep in mind is that devices behind a NAT can't reach (or be reach) from the internet (by default), which is the main difference with the 'Host Bridge'.

Host Bridge

Contrary to the NAT Bridge, this type of bridge are actually 'connected' to an existing physical interface (eth0 in my case). Devices connected to this kind of bridge behave as if there were on the same network. Devices can reach other machines in the network, but also the internet. If a public IP is assigned to the devices in the network, they will even be accessible from the internet, without adding any routing ! In this case the bridge behave exactly as a switch does. In this article we will focus on NAT Bridge (there might be another one about host bridges and virtualization soon).

Creating a bridge using netctl

As I said, netctl is a profile based network manager, to create our new bridge interface, we will add a new file named lxcbridge in /etc/netctl/:

## sudo vim /etc/netctl/lxcbridge
Description="LXC Bridge"
Interface=lxcbr0
Connection=bridge
IP=static
Address='192.168.100.1/24'
SkipForwardingDelay=yes

This file will create lxcbr0 bridge interface with a static IP. To start the interface, we still need to load the profile:

sudo netctl start lxcbridge
sudo netctl enable lxcbridge # To start the interface at boot

You can check the interface's parameters with a simple ip addr:

74: lxcbr0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UNKNOWN group default 
    link/ether 3e:11:8b:90:0e:a0 brd ff:ff:ff:ff:ff:ff
    inet 192.168.100.1/24 brd 192.168.100.255 scope global lxcbr0
       valid_lft forever preferred_lft forever
    inet6 fe80::3c11:8bff:fe90:ea0/64 scope link 
       valid_lft forever preferred_lft forever

Creating a bridge using networkd

Creating a new interface with networkd requires to add a file in /etc/systemd/network/, namely lxcbridge.netdev:

[NetDev]
Name=lxcbr0
Kind=bridge

This file only contains the data about the virtual network device, we then need to configure it using a second file: lxcbridge.network in the same directory:

[Match]
Name=lxcbr0

[Network]
Address=192.168.100.1/24
Gateway=192.168.100.1
IPForward=kernel # Very important, otherwise no routing and the network will be isolated

We then need to start this inteface:

sudo ip link del dev lxcbr0 # We make sure to delete the interface if it already exists
sudo systemctl stop systemd-networkd #We could also restart it, but I've had issues with restarting services
sudo systemctl start systemd-networkd

You should now be able to see your new interface:

# ip addr
128: lxcbr0: <NO-CARRIER,BROADCAST,MULTICAST,UP> mtu 1500 qdisc noqueue state DOWN group default 
    link/ether fa:d3:06:37:22:01 brd ff:ff:ff:ff:ff:ff
    inet 192.168.100.1/24 brd 192.168.100.255 scope global lxcbr0
       valid_lft forever preferred_lft forever

LXC Config

To enable the network on our LXC container, we'll have to change add some lines inside our container's configuration. The configuration file for the containers are located in /var/lib/lxc/natContainer/config:

# sudo vim /var/lib/lxc/natContainer/config
lxc.network.type = veth
lxc.network.name = veth0
lxc.network.flags = up
lxc.network.link = lxcbr0
lxc.network.veth.pair = veth0-natContainer
lxc.network.ipv4 = 192.168.100.10/24
lxc.network.ipv4.gateway = 192.168.100.1

The network type specifies that we want to have a Virtual network. The name is the adapter name inside the LXC container.

The link is the related bridge of the host (the one we created earlier) and the pair key will be the name of the LXC interface but from the Host point of view. We then set a static IP to our container (192.168.100.10) as well as the gateway (the host in this case).

Routing

With the previous configurations, if you start the container, it should be inside a private network, meaning that every container can ping the others (and the host).

## On the host
sudo lxc-start --name natContainer
sudo lxc-console --name natContainer
## Login on the container
ping 192.168.100.1

But unfortunately, we still can't reach the internet:

## ping google.fr
ping: unknown host google.fr

We need to add some rules to our host to enable packet routing/forwarding, we will need iptables for that:

sudo iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE # Redirect all incoming traffic on NAT interfaces to eth0
sudo sysctl -w net.ipv4.ip_forward=1 # Enable ipv4 forwarding

You'll also need to setup a dns server on the Gateway (the host in our case), I'll use dnsmasq for this.

sudo pacman -S dnsmasq
sudo dnsmasq

It's as easy ! You should now be able to reach any IP from inside your container, the NAT is working ! Even if our NAT is working, we can't reach the container from the internet, meaning that we still can't establish a SSH connection with them, we need to add a new rules to our iptables to redirect incoming traffic to our container:

sudo iptables -t nat -A PREROUTING -i eth0 -p tcp --dport 31000 -j DNAT --to 192.168.100.10:22

From my laptop I should be able to connect to my server's IP(5.196.95.238) on port 3100 and have a SSH shell on the container !

ssh ubuntu@5.196.95.238 -p 31000
ubuntu@ex0ns.me's password: 
ubuntu@ex0ns:~$ whoami
ubuntu
ubuntu@ex0ns:~$ 

Here is the end of this quick overview of LXC and network.

PS: I finally have a PGP key, see my contact page.

Resources

[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 !

[Ruby] Graph representation

30 Jan 2015

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 "getorcreate" 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: graph_1 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 !