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
G.add_node("One")
G.add_nodes_from(["Hello","World"]) ### adding a list of nodes
G.add_edge("Hello","World")
G.add_edges_from([("One","Hello"),("One","World")])
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

This website has more information about Graphviz and the different types of layouts.

(Here is more information on how to use Graphviz with NetworkX.)

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:

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?