bipartite.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

bipartite.is_bipartite(B)

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

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)

# Solution goes here

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

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

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

G.number_of_edges()

G.size()

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 goes here

is_bipartite(G, top)

is_bipartite(B, top)

# Solution goes here

is_bipartite(G, top)

is_bipartite(B, top)