# Mark Brown Tuition

Physics, Mathematics and Computer

Science Tuition & Resources

# Basic Implementation of Graphs In Python

Posted on 11-02-19 in Computing

In this article we will look at implementation of graphs in Python. First let's make sure we understand dictionaries!

# Dictionary Review¶

A Dictionary in Python is a data structure which relates unique keys to values. They are defined and indexed as such

```
scores = {'mark' : 20, 'bob' : 15, 'mary' : 25}
scores['frank'] = 20 # new player
for player in scores:
print(f"{player.capitalize():<10} scores {scores[player]:3}")
```

Don't understand line 6? Review https://markbrowntuition.co.uk/computing/2017/11/10/fancy-printing-with-python/

Here we can iterate over dictionaries in the same way with lists. Importantly we need to remember that whilst in later versions of Python that dictionaries are ordered, this is not a guaranteed behaviour!

## Questions¶

```
parcel = {'length' : 0, 'width' : 0, 'height' : 0, 'weight' : 0}
# 1 Iterate Over the parcel object and ask the user for values
# 2 Add new entries to the parcel for volume and density
```

## What is a graph?¶

A graph is points (called nodes) connected by lines (called edges). These edges can be one-way or two-ways. We can also assign weights to these edges. These can correspond to whatever we need - the length of a road or the difficulty in getting from one PC to another.

In this article we will cover how to use Python to define such graphs and how to traverse them in various ways. We will use two possible representations of the graph

- Dictionaries
- Adjacency Matrix

Let's look at the first.

```
simple_path = {'A' : 'B',
'B' : 'C',
'C' : 'D',
'D' : 'E',
'E' : 'F',
'F' : 'A'
}
for node in simple_path:
print(f"{node} is connected to {simple_path[node]}")
```

Here we have used the keys in the dictionary as the list of nodes available. The value in this case holds a single possible destination. I've drawn this graph above for a visual comparison.

This needs to be altered slightly - after all a single node can be connected to multiple places!

```
simple_path = {'A' : ['B',],
'B' : ['C',],
'C' : ['D',],
'D' : ['E',],
'E' : ['F',],
'F' : ['A',]
}
for node in simple_path:
print(f"{node} is connected to {simple_path[node]}")
```

## Questions¶

- Give at least three examples of a graphs.
- The above graph is uni-directional. Alter it so we can go either direction around the loop.
- Create a dictionary for the following images

```
simple_path = {'A' : ['B',],
'B' : ['C',],
'C' : ['D',],
'D' : ['E',],
'E' : ['F',],
'F' : ['A',]
}
to_visit = ['A', ]
visited = []
while to_visit:
current_location = to_visit.pop(0)
print(f"We are currently at {current_location}")
visited.append(current_location)
for node in simple_path[current_location]:
if node not in visited:
to_visit.append(node)
```

## Questions¶

- What is the purpose of the
*visited*list? - Add an end node. If we arrive at this node, end early.
- Visit every node
*n*times, not once. - From a list of nodes, create a dictionary that makes every node connected to every other node.
- Traverse the incomplete graph below. How can we ensure the computer does not crash?
**Aside**When would you want to visit a location several times?

```
simple_path = {'A' : ['B',],
'B' : ['C',],
'C' : ['D',],
'D' : ['E',],
'E' : ['F', 'G'],
}
to_visit = ['A', ]
visited = []
while to_visit:
current_location = to_visit.pop(0)
print(f"We are currently at {current_location}")
visited.append(current_location)
for node in simple_path[current_location]:
if node not in visited:
to_visit.append(node)
```

## Aside Drawing Graphs in Python¶

```
import networkx as nx
from matplotlib.pyplot import subplots, show
from matplotlib import style
simple_path = {'A' : 'B',
'B' : 'C',
'C' : 'D',
'D' : 'E',
'E' : 'F',
'F' : 'A'
}
fig, ax = subplots(figsize=(6,6))
g = nx.DiGraph(simple_path)
pos = nx.spring_layout(g)
nx.draw(g, pos=pos, ax=ax, with_labels=True, font_size=12)
fig.tight_layout()
fig.savefig('circular_graph.png')
show()
```