menu
Subclubs
Artificial Intelligence
Beginners'
All subclubs
Resources
All resources
Options

Implementations of Graph Theory#9

~ / Subclubs / Advanced / Implementations of Graph Theory

Lessons

Previous lesson

Introduction to Graph Theory

Next lesson

Applications of Graph Theory

Setting Things Up

Introduction to C++

Type Modifiers and Pointers

Standard I/O

Introduction to Algorithms

Recursion and Dynamic Programming Draft

Data Structures Draft

Introduction to Graph Theory Draft

Implementations of Graph Theory Draft

Applications of Graph Theory Draft

Minimum Spanning Tree Draft

Shortest Path Draft

Travelling Salesman

Other Algorithms Draft

This lesson is a draft.

We're currently in the process of finishing this lesson. Check back frequently as we continue to add more content and improve our typos.

Now that you what graph theory is and what it entails, perhaps you want to know how to actually code something that represents it.

There are two common methods of doing this.

Adjacency Matrices

An adjacency matrix is exactly what it sounds like (if you know what the words mean): a matrix (two-dimensional array) that stores adjacencies between nodes.

Typically, these are implemented as two-dimensional arrays. Each value in the array is the weight of an edge between two adjacent nodes; if it’s some previously-specified error value (usually 0 or -1), then the two nodes aren’t adjacent.

These are very simple to implement, but have two downsides:

  1. they are memory-intensive and typically waste lots memory, considering that most nodes aren’t adjacent to most other nodes, and

  2. they are useless for edge-optimized algorithms such as Bellman-Ford’s or Kruskal’s algorithm, as edges are stored implicitly.

But if you’re not sure how to implement the more robust method, the adjacency matrix is very useful for getting yourself started.

<span id="L1" class="line"><span class="kt">int</span> <span class="n">weights</span><span class="p">[</span><span class="n">num_nodes</span><span class="p">][</span><span class="n">num_nodes</span><span class="p">];</span></span>

Object-Oriented Approach

I say "object-oriented," but it’s not actually using stuff with objects. We don’t need classes or inheritance or anything stupid like that; rather, we’re just approaching it from that mindset: nodes and edges are both objects.

A node stores a list of edges that it can traverse with, and an edges stores the two nodes it connects and whatever extra properties it may have.

What you get, then, is this:

<span id="L1" class="line"><span class="c1">//prototype</span></span>
<span id="L2" class="line"><span class="k">struct</span> <span class="n">edge</span><span class="p">;</span></span>
<span id="L3" class="line"></span>
<span id="L4" class="line"><span class="k">struct</span> <span class="n">node</span></span>
<span id="L5" class="line"><span class="p">{</span></span>
<span id="L6" class="line">    <span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">edge</span><span class="o">*&gt;</span> <span class="n">connections</span><span class="p">;</span></span>
<span id="L7" class="line"><span class="p">};</span></span>
<span id="L8" class="line"><span class="k">struct</span> <span class="n">edge</span></span>
<span id="L9" class="line"><span class="p">{</span></span>
<span id="L10" class="line">    <span class="n">node</span> <span class="o">*</span><span class="n">from</span><span class="p">,</span> <span class="o">*</span><span class="n">to</span><span class="p">;</span></span>
<span id="L11" class="line">    <span class="kt">int</span> <span class="n">weight</span><span class="p">;</span></span>
<span id="L12" class="line"><span class="p">};</span></span>
<span id="L13" class="line"></span>
<span id="L14" class="line"><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">node</span><span class="o">&gt;</span> <span class="n">all_nodes</span><span class="p">;</span></span>
<span id="L15" class="line"><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">edge</span><span class="o">&gt;</span> <span class="n">all_edges</span><span class="p">;</span></span>

If you’ve been following on how to use pointers, then you’ll see why this makes sense: we have nodes which store pointers to edges and edges which store pointers to nodes. To keep track of everything, we also have two master lists of nodes and edges, from which all of the references are grounded.

We can also include an ID field in the nodes and edges if we wanted to, which would help us find which node and edge are which index in their respective master lists very quickly.

This is harder to code, but in the end it’s more sustainable than an adjacency matrix, and it’ll work for edge-based optimizations.

Using the Standard Library

You can also use stuff from the standard library.

<span id="L1" class="line"><span class="cp">#include &lt;vector&gt;</span></span>
<span id="L2" class="line"><span class="cp">#include &lt;map&gt;</span></span>
<span id="L3" class="line"></span>
<span id="L4" class="line"></span>
<span id="L5" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span></span>
<span id="L6" class="line"><span class="p">{</span></span>
<span id="L7" class="line">    <span class="n">std</span><span class="o">::</span><span class="n">map</span> <span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="n">std</span><span class="o">::</span><span class="n">vector</span> <span class="o">&lt;</span> <span class="n">std</span><span class="o">::</span><span class="n">pair</span> <span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="o">&gt;</span> <span class="o">&gt;</span> <span class="n">adjList</span><span class="p">;</span></span>
<span id="L8" class="line">    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">NO_EDGES</span><span class="p">;</span> <span class="o">++</span><span class="n">a</span><span class="p">){</span></span>
<span id="L9" class="line">        <span class="n">scanf</span> <span class="p">(</span><span class="s">"%d%d%d"</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">from</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">to</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">weight</span><span class="p">);</span></span>
<span id="L10" class="line">        <span class="k">if</span> <span class="p">(</span><span class="n">adjList</span><span class="p">.</span><span class="n">count</span><span class="p">(</span><span class="n">from</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">){</span></span>
<span id="L11" class="line">            <span class="n">std</span><span class="o">::</span><span class="n">vector</span> <span class="o">&lt;</span> <span class="n">std</span><span class="o">::</span><span class="n">pair</span> <span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="o">&gt;</span> <span class="n">v</span><span class="p">;</span></span>
<span id="L12" class="line">            <span class="n">adjList</span><span class="p">[</span><span class="n">from</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span></span>
<span id="L13" class="line">        <span class="p">}</span></span>
<span id="L14" class="line">        <span class="n">adjList</span><span class="p">[</span><span class="n">from</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">std</span><span class="o">::</span><span class="n">make_pair</span><span class="p">(</span><span class="n">to</span><span class="p">,</span> <span class="n">weight</span><span class="p">));</span></span>
<span id="L15" class="line">    <span class="p">}</span></span>
<span id="L16" class="line">    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">a</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">adjList</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">size</span><span class="p">();</span> <span class="o">++</span><span class="n">a</span><span class="p">){</span></span>
<span id="L17" class="line">        <span class="n">printf</span> <span class="p">(</span><span class="s">"to = %d, weight = %d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">adjList</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">a</span><span class="p">].</span><span class="n">first</span><span class="p">,</span> <span class="n">adjList</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">a</span><span class="p">].</span><span class="n">second</span><span class="p">);</span></span>
<span id="L18" class="line">    <span class="p">}</span></span>
<span id="L19" class="line"><span class="p">}</span></span>

I’m not quite sure how this works to be honest, so please ask Victor if you have any questions.

And now that you know how to put this stuff in code, you’re probably wondering about what we’re going to do with all this stuff. That’s for the Applications of Graph Theory section.