bipartite_soln.ipynb

Kernel: Python 3

Bipartite graphs

Code examples from Think Complexity, 2nd edition.

Copyright 2019 Allen Downey, MIT License

%matplotlib inline

import numpy as np
import pandas as pd

import networkx as nx

The following examples are from the NetworkX documentation on bipartite graphs

B = nx.Graph()
# Add nodes with the node attribute "bipartite"
B.add_nodes_from([1, 2, 3, 4], bipartite=0)
B.add_nodes_from(['a', 'b', 'c'], bipartite=1)
# Add edges only between nodes of opposite node sets
B.add_edges_from([(1, 'a'), (1, 'b'), (2, 'b'), (2, 'c'), (3, 'c'), (4, 'a')])

from networkx.algorithms import bipartite

bottom_nodes, top_nodes = bipartite.sets(B)
bottom_nodes, top_nodes

({1, 2, 3, 4}, {'a', 'b', 'c'})

bipartite.is_bipartite(B)

True

B.add_edge(1, 2)
bipartite.is_bipartite(B)

False

Exercise: Write a generator function called cross_edges that takes a NetworkX Graph object, G, and a Python set object, top, that contains nodes.

It should compute another set called bottom that contains all nodes in G that are not in top.

Then it should yield all edges in G that connect a node in top to a node in bottom.

top = set([1, 2, 3, 4])
bottom = set(['a', 'b', 'c'])

def flip(p):
    return np.random.random() < p

from itertools import product

G = nx.Graph()
p = 0.5
for u, v in product(top, bottom):
    if flip(p):
        G.add_edge(u, v)

bipartite.is_bipartite(G)

True

# Solution

def cross_edges(G, top):
    bottom = set(G) - top
    for u, v in G.edges():
        if (u in top) == (v in bottom):
            yield(u, v)

for edge in cross_edges(G, top):
    print(edge)

(1, 'a')
('a', 3)
(2, 'c')
('c', 3)
('c', 4)
(4, 'b')

len(list(cross_edges(G, top)))

6

sum(1 for edge in cross_edges(G, top))

6

G.number_of_edges()

6

G.size()

6

Exercise: Write a function called is_bipartite that takes a Graph and a set of top nodes, and checks whether a graph is bipartite.

# Solution

def is_bipartite(G, top):
    m = sum(1 for edge in cross_edges(G, top))
    return m == G.number_of_edges()

is_bipartite(G, top)

True

is_bipartite(B, top)

False

# Solution

def is_bipartite(G, top):
    bottom = set(G) - top
    for u, v in G.edges():
        if (u in top) != (v in bottom):
            return False
    return True

is_bipartite(G, top)

True

is_bipartite(B, top)

False