Deep Blog

Algorithmics with Rust: Graph


Hello, today we are going to talk about graphs, what are they and how do we make them in Rust.

Before that, I was planning of speaking about merge sort. But, Vaidehi Joshi has already covered the subject in her article Making sense of merge sort. You should really read it for it is well written and really easy to understand.

Back to subject: GRAPHS!

"OK, what is a graph?"

To keep it simple, a graph is a collection of points, called nodes, and a collection of edges linking nodes. Graph can be directed, where edges will be like arrows, or undirected.

[caption id="" align="alignleft" width="231"]File:Directed graph no background.svg Directed graph[/caption]

[caption id="" align="aligncenter" width="333"]File:6n-graf.svg Undirected graph[/caption]

Graph can be divided in class, buuuuuut I let you seek it out on Wikipedia, the article is well documented.

"OK, what does it use for?"

Good question, our reader is a good one for sure!

What I will say will stun you: you see them every day! In telecommunication, social media, etc. Even in programming, for example in object oriented language, you can see and use graph.

"OK, it's useful. How do we make them?"

I'll show you ONE method to make them in Rust.

First, we can define a graph by a collection of nodes, a collection of edges and by being directed or not.

struct Graph<'a> {
  nodes: Vec<&'a Node>,
  edges: Vec<Edge<'a>>,
  directed: bool,
}

Then, we define node and edge.

struct Node {}

struct Edge<'a> {
  source_node: &'a Node,
  target_node: &'a Node,
}

Now we have all needed structures to make graphs.

You can see an example here: link.

We will stop here for today, I don't want to bore you. See you next time to play around graph.

-- Mathieu