5062CEM

Programming and Algorithms 2

Graph Theory

 Light  Dark  Auto

Graph Theory

For this activity, you will need to be using an Integrated Development Environment (IDE). The recommended IDE for this module is JetBrains IntelliJ IDEA for Python and JetBrains CLion for C++. You can follow instructions at the following page to set up your development environment:

Setting up your Development Environment

You will also be provided with some partially incomplete code. You are tasked with providing a solution for the missing code/functions by completing the tasks below.

Adjacency Matrix - Python

Using the source-code provided, you are tasked with implementing an unweighted and undirected graph data structure as an adjacency matrix, where the vertices consist of positive integers. Note, that zero is not a positive integer.

The implementation should consist of the following functions:

  • Adding a vertex to the graph
  • Adding an edge to the graph
  • Removing an edge from the graph
  • Printing the graph as a matrix, which should look like:
  |   1   2   3   4   5   6
----------------------------
1 |   0   1   1   0   0   0
2 |   1   0   1   0   0   0
3 |   1   1   0   1   0   0
4 |   0   0   1   0   0   0
5 |   0   0   0   0   0   0
6 |   0   0   0   0   0   0

There should be a check for each of the functions provided above, i.e. determine whether the vertex exists before adding it. To simplify things a little, you may remove edges with no need to worry about vertices.

An issue with the adjacency matrix representation of a graph is that it is difficult to give vertices specific values, i.e. the values above will be based on the list index values. This can be addressed by implementing a graph as an adjacency list.

For this task, implement an unweighted and undirected graph data structure as an adjacency list, where the vertices consist of positive integers (note that zero is not a positive integer).

The implementation should consist of the following methods/functions:

  • Adding a vertex to the graph
  • Adding an edge to the graph
  • Removing an edge from the graph
  • Removing a vertex from the graph
  • Printing the graph as a matrix, which should look like:
vertex | edges
--------------
1      | 2
2      | 3
3      | 4
4      | 1, 5
5      | 2

You will not be supplied any source-code for this task. However, it would make sense to implement the graph as a dictionary. The implementation is not required to follow the Object-Oriented Programming (OOP) principles. However, you can if you would like to.

The graph does not need to be ordered (although they can be); dictionaries are usually not ordered by their key value. Therefore, printing of the graph does not need to be sorted by the key value.

If you are struggling with this lab activity, you may want to get some additional support. You can speak to the module leader/team in the room of when the lab week is active, or you can visit the Additional Support page for more information on how you can get extra support.