1. Graphs

# Graphs¶

## Königsberg bridges¶

The introductory notes of MATH20902 - Discrete Mathematics start with the description of the well-known Königsberg bridge problem:

The panel on the left shows the seven bridges and four land masses that provide the setting for the Königsberg bridge problem, which asks whether it is possible to make a circular walking tour of the city that crosses every bridge exactly once. The panel on the right includes a graph-theoretic abstraction that helps one prove that no such tour exists.

First we need to find the official term for "a graph in which we can visit each edge exactly once". Let us ask Google:

Opening that page will, indeed, tell us that what we really want is to check if the graph above is Eulerian (i.e., we can visit all the nodes by passing each edge exactly once and endig up where we started).

Python's package for working with graphs is NetworkX. To observe its basic functionality, let us solve the above.

Let us create an empty multigraph (some nodes will be connected by more than one edge):

In [ ]:
import networkx as nx

G = nx.MultiGraph()


In [ ]:
G.add_nodes_from(["C", "A", "D", "B"])


In [ ]:
G.add_edges_from([("C","A"), ("C","A"), ("A","B"), ("A","B"), ("C", "D"), ("A", "D"), ("B", "D")])


Print nodes and edges, to make sure all is fine:

In [ ]:
print("Nodes:", G.nodes())
print("Edges:", G.edges())


Come on, you can do better than that!

In [ ]:
print("Nodes:", ", ".join(sorted(G.nodes())))
print("Edges:", ", ".join(sorted("{{{}}}".format(",".join(sorted(t))) for t in G.edges())))


So, is this graph Eulerian?

In [ ]:
print(nx.is_eulerian(G))


No, it is not. We can even get Python to print it more nicely:

In [ ]:
print("The graph {} Eulerian.".format("is" if nx.is_eulerian(G) else "is not"))


Let us now require to pass the bridges $c$ (top left) and $f$ (lower right) twice. How do we do that?

Instead of messing with the graph theory and adding additional parameter "you may pass this edge <this many> times", we simply add two more edges and keep the constraint "pass each edge exactly once":

In [ ]:
import networkx as nx

G = nx.MultiGraph()

("C","A"), ("C","A"), ("A","B"), ("A","B"), ("C", "D"), ("A", "D"), ("B", "D"),
("A", "C"), ("B", "D")  # new edges
])

print("Nodes:", ", ".join(sorted(G.nodes())))
print("Edges:", ", ".join(sorted("{{{}}}".format(",".join(sorted(t))) for t in G.edges())))
print("The graph {} Eulerian.".format("is" if nx.is_eulerian(G) else "is not"))
print("Eulerian circuit:", list(nx.eulerian_circuit(G)))
ec = list(nx.eulerian_circuit(G))
print("A bit prettier: {}->{}".format(ec[0][0], "->".join(t[1] for t in ec)))


## Isomorphic ("pretty much identical") graphs¶

The notes of the second MATH20902 lecture introduce the term graph isomorphism which defines when two graphs can be considered the same. The lectures also provide an example of three (not obviously) isomporhic graphs:

Let us first create these graphs in Python:

In [ ]:
import networkx as nx

G1 = nx.Graph()
(1,2), (2,4), (4,3), (3,1),
(1,5), (2,6), (4,8), (3,7),
(5,6), (6,8), (8,7), (7,5),
])
G2 = nx.Graph()
("000", "001"), ("000", "010"), ("000", "100"),
("011", "001"), ("011", "010"), ("011", "111"),
("110", "010"), ("110", "100"), ("110", "111"),
("101", "001"), ("101", "100"), ("101", "111"),
])
G3 = nx.Graph()
("a","b"), ("b","d"), ("d","c"), ("c","a"),
("a","e"), ("b","f"), ("d","h"), ("c","g"),
("e","f"), ("f","h"), ("h","g"), ("g","e"),
])


Note: As you can see, we don't need to add the nodes explicitly (except those that have no edges connected to them).

Now we can easily check if they are isommorphic:

In [ ]:
print("Are G1 and G2 isomorphic?", nx.is_isomorphic(G1, G2))
print("Are G1 and G3 isomorphic?", nx.is_isomorphic(G1, G3))
print("Are G2 and G3 isomorphic?", nx.is_isomorphic(G2, G3))


The lecture notes also explain how hard of a task it is to determine if two graphs are isomorphic or not, it gives some criterions to help us find the negative answer more quickly in many cases, and it gives the following two graphs that evade the (fast) criterion of degree sequences:

These criteria are also supported by NetworkX, so let us test all that this module has to offer:

In [ ]:
import networkx as nx

G1 = nx.Graph()
("v1", "v2"), ("v2", "v3"), ("v3", "v4"), ("v4", "v5"), ("v2", "v5")
])

G2 = nx.Graph()
("u1", "u2"), ("u2", "u3"), ("u3", "u4"), ("u4", "u5"), ("u3", "u5")
])

print("Could G1 and G2 be isomorphic (faster)?", nx.faster_could_be_isomorphic(G1, G2))
print("Could G1 and G2 be isomorphic (fast)?", nx.fast_could_be_isomorphic(G1, G2))
print("Could G1 and G2 be isomorphic?", nx.could_be_isomorphic(G1, G2))
print("Are G1 and G2 isomorphic?", nx.is_isomorphic(G1, G2))


The functions used here are:

## Plotting graphs¶

NetworkX has some ability to plot graphs, but this is not its primary purpose. There are several interfaces that can be used, but some of them have to be installed separately. However, the support for plotting graphs via Matplotlib usually comes with the default installation. Let us first prepare Matplotlib for use in this document:

In [ ]:
%matplotlib inline
import matplotlib.pylab as pylab
pylab.rcParams['figure.figsize'] = (4, 3)


Here is a simple way to draw the previous two graphs:

In [ ]:
import matplotlib.pyplot as plt

nx.draw_networkx(G1)
plt.axis("off")
plt.show()

nx.draw_networkx(G2)
plt.axis("off")
plt.show()


Sometimes, it may be more convenient to draw graphs by putting their nodes on a circle:

In [ ]:
nx.draw_networkx(G1, pos=nx.circular_layout(G1))
plt.axis("off")
plt.show()

nx.draw_networkx(G2, pos=nx.circular_layout(G2))
plt.axis("off")
plt.show()


Other (automatic) layouts are possible as well. You can find them here.

We can also do plenty of other customizations, like positions of nodes, the sizes of the nodes, color changes, and custom edge width:

In [ ]:
plt.figure(figsize=(6,2))
nx.draw_networkx(G1,
pos={"v1": (0,1), "v2": (2,1), "v3": (3.5,2), "v4": (5,1), "v5": (3.5,0)},
node_size=750, node_color="yellow",
edge_color="red", width=2
)
plt.axis("off")
plt.show()


We can also use the fact that Matplotlib can process $\LaTeX$. With a more precise color adjustment (using the HTML color codes) and changing the thickness of the nodes circles, we can get a plot fairly similar to the one from the lecture notes:

In [ ]:
G2 = nx.Graph()
("$u_1$", "$u_2$"), ("$u_2$", "$u_3$"), ("$u_3$", "$u_4$"), ("$u_4$", "$u_5$"), ("$u_3$", "$u_5$")
])
plt.figure(figsize=(6,2))
nx.draw_networkx(G2,
pos={"$u_1$": (0,1), "$u_2$": (2,1), "$u_3$": (4,1), "$u_4$": (5.5,2), "$u_5$": (5.5,0)},
font_size=17,
node_size=750, node_color="#caeeeb", linewidths=2,
width=2
)
plt.axis("off")
plt.show()


Plotting multigraphs, however, requires more advanced solutions, because the simple one that we used above will not show multiple edges, as we can see if we try to plot the original Königsberg bridges graph (the one with the exactly one walk over each bridge):

In [ ]:
import networkx as nx

G = nx.MultiGraph()

# The original Königsberg bridges graph
("C","A"), ("C","A"), ("A","B"), ("A","B"), ("C", "D"), ("A", "D"), ("B", "D"),
])

nx.draw_networkx(G, pos=nx.circular_layout(G))
plt.axis("off")
plt.show()


For those interested in better visual representations of graphs, you can plot your graphs using draw_graphviz. However, this requires Graphviz and its Python module.

Without extra installations, you also export your graphs as DOT files which can then be handled or drawn by Graphviz or some other program recognizing the format, without installing Graphviz Python module.

Without much adjustments, the Königsberg bridges graph plotted with Graphviz looks like this:

As a program specialized for plotting graphs, Graphviz can do much more.

## Paths and trees¶

The notes of the third MATH20902 lecture introduce walks, trails, paths, and many other terms which go beyond the scope of this lecture. In the notes of the fourth MATH20902 lecture, this builds up to trees and forests. Let us observe the following four graphs from that lecture's Figure 4.1:

First, we define these graphs:

In [ ]:
import networkx as nx

white = nx.Graph()

yellow = nx.Graph()
yellow.add_path(list(range(1,9)))  # from bottom left to the lower one on the far right
(2,9),   # far left
(3,10),  # next to it
(4,11), (11,12), (11,13),  # the left "Y"
(5,14), (14,15), (14,16),  # the bottom right "Y"
(6,17), (7,18)  # the remaining two branches on the top right
])

green = nx.Graph()
(1,2), (3,4),  # two small trees
])
green.add_path([5, 6, 7])  # the V-shaped tree

grey = nx.Graph()
grey.add_path([list(range(1,10))])  # from top right, through the cycle, until almost closed
(3,9),  # close the cycle
(8,10), # the node inside the cycle
(2,11), (4,12), (5,13)  # the remaining nodes and edges
])


So, which of these are trees?

NetworkX documentation isn't helping much. There is no is_tree function nor anything similar. However, the solution is not hard: we can use Theorem 4.13 from the aforementioned notes:

Theorem 4.13 (Jungnickel’s Theorem 1.2.8). For a graph $G(V, E)$ on $|V| = n$ vertices, any two of the following imply the third:
(a) $G$ is connected.
(b) $G$ is acyclic.
(c) $G$ has $n-1$ edges.

So, we can just compare the number of edges and the number of nodes and check that the graph is connected. A simple Googling will even give us a ready-made solution by the user Aric in this answer on Stack Overflow:

In [ ]:
def is_tree(G):
"""
Returns True if G is a tree and False otherwise.
"""
if nx.number_of_nodes(G) != nx.number_of_edges(G) + 1:
return False
return nx.is_connected(G)


Let us now check our three graphs:

In [ ]:
print("Is the white graph a tree?", is_tree(white))
print("Is the yellow graph a tree?", is_tree(yellow))
print("Is the green graph a tree?", is_tree(green))
print("Is the grey graph a tree?", is_tree(grey))


Let us now plot the yellow graph:

In [ ]:
pos = {
# Main path
1: (0.1,0),
2: (1,0.9),
3: (1.9,1.7),
4: (3,2.2),
5: (4,2),
6: (4.5,2.5),
7: (5.5,2.2),
8: (6.5,1.5),
# Far left
9: (0,1),
# Next to it
10: (0.5,2.3),
# The left "Y"
11: (2.1,2.7),
12: (1,2.9),
13: (1.2,3.5),
# The bottom right "Y"
14: (5,1.5),
15: (4.5,0.75),
16: (5.7,0.7),
# The remaining two branches on the top right
17: (5.5,3.2),
18: (6.5,2.6),
}
plt.figure(figsize=(7,4))
nx.draw_networkx(yellow,
pos=pos,
node_size=350, node_color="#fdde57", linewidths=1,
width=1
)
plt.axis("off")
plt.show()


Not a perfect match of the positions, but close enough to see that it is the same graph.

Now, let us plot the same graph without the labels:

In [ ]:
plt.figure(figsize=(7,4))
nx.draw(yellow,
pos=pos,
node_size=350, node_color="#fdde57", linewidths=1,
width=1
)
plt.axis("off")
plt.show()


And now let us plot the graph in the way that the leaves remain yellow, but the rest of the nodes are white.

To achieve this, we shall plot our graph in three steps:

1. Draw the edges,

2. Draw the leaves,

3. Draw the remaining nodes.

In [ ]:
plt.figure(figsize=(7,4))

# Draw the edges
nx.draw_networkx_edges(yellow,
pos=pos,
width=1
)
# Draw the leaves
nx.draw_networkx_nodes(yellow,
pos=pos,
node_size=350, node_color="#fdde57", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) == 1]
)
# Draw the remaining nodes
nx.draw_networkx_nodes(yellow,
pos=pos,
node_size=350, node_color="white", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) != 1]
)
plt.axis("off")
plt.show()


Let us draw the same, but with the labels and with the path $(10, 3, 4, 5, 14, 15)$ marked light green (lime):

In [ ]:
plt.figure(figsize=(7,4))

path = [10, 3, 4, 5, 14, 15]

# Draw the edges
nx.draw_networkx_edges(yellow,
pos=pos,
width=1
)
# Draw the leaves
nx.draw_networkx_nodes(yellow,
pos=pos,
node_size=450, node_color="#fdde57", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) == 1]
)
# Draw the remaining nodes
nx.draw_networkx_nodes(yellow,
pos=pos,
node_size=450, node_color="white", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) != 1]
)
# Draw labels
nx.draw_networkx_labels(yellow,
pos=pos,
)

# Draw the path nodes in light red with a "glow" effect
# (actually, a "strong" red with a low alpha and thick lines)
nodes = nx.draw_networkx_nodes(yellow,
pos=pos,
alpha=0.2,
node_size=450, node_color="lime", linewidths=5,
nodelist=path
)
nodes.set_edgecolor('lime')
nx.draw_networkx_edges(yellow,
pos=pos,
alpha=0.2, edge_color="lime",
width=5,
edgelist=[ (f,t) for f,t in zip(path, path[1:])]
)

plt.axis("off")
plt.show()


Note: Be careful when plotting graphs in several steps, as the positions of the nodes are given randomly by some layouts (for example, the spring layout). For example, our above "yellow leaves, white inner nodes, no labels" plot, with the positions defined by the spring_layout function, might not look as glamourous as before:

In [ ]:
plt.figure(figsize=(7,4))

# Draw the edges
nx.draw_networkx_edges(yellow,
pos=nx.spring_layout(yellow),
width=1
)
# Draw the leaves
nx.draw_networkx_nodes(yellow,
pos=nx.spring_layout(yellow),
node_size=350, node_color="#fdde57", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) == 1]
)
# Draw the remaining nodes
nx.draw_networkx_nodes(yellow,
pos=nx.spring_layout(yellow),
node_size=350, node_color="white", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) != 1]
)
plt.axis("off")
plt.show()


The proper way to do this is to preserve the positions in a variable and then use it in all three calls to the draw_networkx_* functions:

In [ ]:
plt.figure(figsize=(7,4))

# Define the positions via Fruchterman-Reingold force-directed algorithm
spos = nx.spring_layout(yellow)

# Draw the edges
nx.draw_networkx_edges(yellow,
pos=spos,
width=1
)
# Draw the leaves
nx.draw_networkx_nodes(yellow,
pos=spos,
node_size=350, node_color="#fdde57", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) == 1]
)
# Draw the remaining nodes
nx.draw_networkx_nodes(yellow,
pos=spos,
node_size=350, node_color="white", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) != 1]
)
plt.axis("off")
plt.show()


Not the prettiest sight, but at least it is correct now.

Here is a simple display of all the available layouts in action (each one twice, to see which are randomized):

In [ ]:
for layout in [ nx.circular_layout, nx.random_layout,
nx.shell_layout, nx.spring_layout, nx.spectral_layout ]:
for k in range(1,3):

print("{} ({})".format(layout.__name__, k))

plt.figure(figsize=(7,4))

# Define the positions via Fruchterman-Reingold force-directed algorithm
spos = layout(yellow)

# Draw the edges
nx.draw_networkx_edges(yellow,
pos=spos,
width=1
)
# Draw the leaves
nx.draw_networkx_nodes(yellow,
pos=spos,
node_size=350, node_color="#fdde57", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) == 1]
)
# Draw the remaining nodes
nx.draw_networkx_nodes(yellow,
pos=spos,
node_size=350, node_color="white", linewidths=1,
nodelist=[node for node in yellow.nodes() if len(yellow.neighbors(node)) != 1]
)
plt.axis("off")
plt.show()


## What more can be done?¶

We can do a lot more:

• The plots can be saved, the same way anything else in Matplotlib is saved: using the savefig function.

• We can work with weighted and with directed graphs.

• We can do most of the usual things that are done with graphs, using NetworkX' rich algorithms collection.