Last week I wrote how to represent *graph* structure as
**adjacency list**.
This week time has come to describe how we can represent *graphs* in a a *matrix* representation.

Our requirements (the same as previous week):

- small amount of code (we want to code it fast on algorithmic contest)
- ability to change our structure dynamically (we want to add some edges or vertices after
*graph*initialization) *graph*is**undirected**(for each two vertices there can be at most one edge and edges don’t have directions)

*Graph* as matrix in **Python**

*Graph* represented as a *matrix* is a structure which is usually represented by a -dimensional *array* (table)
indexed with *vertices*. Value in cell described by *row-vertex* and *column-vertex* corresponds to an *edge*.
So for *graph* from this picture:

we can represent it by an array like this:

# cell | A | B | C | D |
---|---|---|---|---|

A |
0 | 1 | 1 | 1 |

B |
1 | 0 | 0 | 0 |

C |
1 | 0 | 0 | 1 |

D |
1 | 0 | 1 | 0 |

For example , because there is an edge between and , , because there is no edge between and .

In **C++** we can easily represent such structure using -dimensional arrays (`std::vector`

is better than regular
array):

Of course then we have to initialize every cell in our array:

In **Python** a *list* is an equivalent of an array. The most obvious implementation of a structure could look like this:

It seems in **Python** we can initialize this structure in much shorter way (actually in one line - look at `__init__`

).
For this implementation we need memory, where is number of vertices. Of course as *graph* is
**undirected** we can skip half of this array, because we duplicate edge information, but I’m not going to cover
it in this post, because for **Python** I’ve a better solution. So, think about this question:

*Is there a way to omit information about not existing edges?*

And now think about `dict`

.

### Using `dict`

for matrix graph implementation

Ok, so we want to store our **graph-matrix** in a `dict`

. As it’s a **key-value** store, we want to know what information
to store in *keys* and what *value* should they have. As we still want to be able to write something like
this: `graph[i][j]`

to access an edge it becomes clear that **values** are *edges* and as **keys** we should have
pairs of *vertices*. So let’s use ** tuple of vertices** as keys!

That’s it! When there is an *edge* between two vertices we will have a `not None`

value otherwise `None`

. For
**sparse graphs** we can save a lot of memory here, because we will actually use where is number
of edges. Of course, we are unable to tell easily how many *vertices* our *graph* has (we have to check all keys). If
we need this kind of information we can create a more sophisticated implementation:

Class `DictGraph`

derives from `dict`

, so we still can use it as dictionary, but we have also a `list`

of *vertices*.
Now it’s easy to check if *vertex* is in our *graph* - it’s enough that we check if it’s in `vertices`

*list*.

## Comparision of `dict`

and `list`

graph implementations

### Adding a vertex

Let’s see how to add a vertex in both `dict`

and `list`

implementations mentioned above.

#### Adding a vertex in `list`

implementation

To add a vertex we need to add to our *matrix* **new column** and **new row**. So we have to iterate over all
*vertices lists* and append there (you can think about it as adding a **new column**). Next
we have to create an array of vertices for (adding a **new row**). Time complexity is .
We also need about space.

#### Adding a vertex in `dict`

implementation

Here we have to append a vertex to vertices list (if we use one, it’s not necessary). As it doesn’t have any edges with other vertices it doesn’t require any action. Necessary time: (worst case is , space is .

### Removing an edge

In both implementation it’s easy:

#### Removing an edge in `list`

implementation

Just put in both ends of edge. Time . We don’t save any space.

#### Removing an edge in `dict`

implementation

Here we can actually delete both ends of edge from dictionary. Time , saving a little of space.

### Removing a vertex

Removing a vertex is more complicated, especially in `list`

implementation.

#### Removing a vertex in `list`

implementation

To remove *vertex* we have to remove its **column** and **row** in a table. So we have iterate over all
vertices lists, remove vertex from them (removing a **column**), finally remove whole list corresponding
to this vertex (removing **row**). Time complexity is .

#### Removing a vertex in `dict`

implementation

To remove *vertex* from dictionary *graph* we need to remove all its *edges*, so we have to
to check all **keys** (`tuple`

of two vertices) and if any of them has remove it - it is removing an edge.
After that we need to remove from *vertices list* if we use it.
Time complexity is , because we iterate over all edges, not vertices.
Actually for **dense graphs** it is worse than in `list`

implementation.

## Summing up

It seems that except removing a *vertex* in **dense graphs**, `dict`

implementation of *graph-matrix* is much better
than `list`

implementation. It saves much more *space*, because it doesn’t need to save information
about *non-existing* edges. Also for me it’s much *more readable*, because it allows usage of any kind of
names for vertices - you can name them using numbers, letters, whatever you want (as long as you don’t add the same
vertex twice, better to check it before adding?). Dictionaries in **Python** are really powerful - they are implemented
as **hash tables** that’s way it has really good time complexities for dictionary operations.

You can find code of both implementations and some tests as examples of usage here:
**gist**.
Hopefully you enjoyed reading about this approach for implementing *graph* structure. Let me know your thoughts or
remarks in comments!

## Leave a Comment