Preparation

As a preparation for todays exercises, save the following code in a file called write_gif.py in your current directory. (You don't need to read and understand this code. It is just a utility for saving graphs into gif files.)
```import networkx
import subprocess
from subprocess import Popen, PIPE
from networkx.utils import _get_fh

def write_gif(G, path, prgr="dot"):
"""
Write the graph G in gif format using Graphviz
"""

pathgif = path + ".gif"
pathdot = path + ".dot"

fh=_get_fh(pathdot,mode='w')

count=iter(range(G.number_of_nodes()))
node_id={}

if G.is_directed():
fh.write("digraph G{node [ ];\n")
else :
fh.write("graph G{node [ ];\n")
for n in G:
nid=G.node[n].get('id',count.next())
node_id[n]=nid
fh.write("%s ["%nid)
fh.write("label = \"%s\"];\n"%n)
for u,v,edgedata in G.edges_iter(data=True):
if G.is_directed():
fh.write("%s ->"%node_id[u])
else:
fh.write("%s --"%node_id[u])
fh.write("%s\n"%node_id[v])
fh.write("}\n")
cmd = prgr + ' -Tgif -o ' + pathgif + ' ' + pathdot
pipe = Popen(cmd, shell=True, stdin=PIPE).stdin
```

1 Graphs

1.1 Exercise

1) Which of the following graphs are isomorphic (i.e. they are the same but their layout is different)?

 1: 2: 3: 4: 5: 6:

It can be easier to determine that two graphs are not isomorphic than to show that they are. Which property of the nodes can be used to determine that two graphs are not isomorphic?

1.2 Creating graphs with NetworkX

In order to use the graph modules, the following is needed:
```from networkx import *
from write_gif import *
```
Commands for creating a graph and adding nodes and edges:
```G=Graph()                           ### initialises a new graph
H= DiGraph(G)                       ### creates a directed graph using G
```
Commands for displaying nodes and edges:
```G.nodes()
G.edges()
```
Removing edges:
```G.clear()
```

1.3 Exercise

2) Create Graph 1 from exercise 1).

1.4 Viewing graphs

The following command creates a gif file of a graph G:
```write_gif(G,"filename")
```
Instead of filename you should type a name of a file (without extension). After executing the command, two files, filename.gif and filename.dot (which can be ignored), will appear in the current directory. You can view the gif file via your I:-drive.

The software that creates the layouts is called Graphviz. These layout options are available:

 write_gif(G,"filename") hierarchical layout write_gif(G,"filename","neato") spring model layout write_gif(G,"filename","fdp") another spring model layout write_gif(G,"filename","twopi") radial layout write_gif(G,"filename","circo") circular layout

1.5 Exercises

3) Try different layouts for the graph you created in exercise 2.

4) NetworkX provides many standard graphs. Try different layouts for these:

```G1=house_x_graph()
G2=complete_bipartite_graph(3,5)
G3=lollipop_graph(10,20)
```
Where did you see the House Graph in the lecture?

1.6 Exercises: other graph operations

5) NetworkX provides many graph operations. Using the graphs G (from exercise 2) and G1, G2, G3 from exercise 4 determine the following:
• Which of the graphs are bipartite (using is_bipartite(G)?
• Generate the complement of G1 (using complement(G1). Look at the gif files for G1 and its complement. Can you figure out what is meant by "complement" here?
• Calculate the diameter(G) and the radius(G) of the graphs. The diameter is the maximum distance (shortest path) between two nodes in the graph; the radius is the minimum steps needed to reach all nodes from a single node. How much larger can the diameter be compared to the radius? Can you use these values to determine which of the graphs have a small-world effect with "six degrees of separation"?

1.7 Exercises with pen and paper

Using the graphs from exercise 1 and G1, G2, G3 from exercise 4 determine the following:

6) Determine the chromatic number of the graphs. (The chromatic number is the minimum number of colours needed to colour a graph so that neighbouring nodes have different colours.)

7) Which of the graphs have a Hamiltonian or Eulerian path?