Implementing a Graph bipartition checker in Python

As a software developer I try make a routine that includes the practicing of my skills to solve mathematic/algorithm problems. Some days ago I found out a Google annual code competition called Code Jam and the very first problem I saw puzzled me (I will talk about it). After some research I was able to solve it through a graph bipartition checker algorithm and decided to write the path I took to come up with the solution.
Let’s do it.

Graph

A Graph is a non-linear abstract data structure well known in mathematics. They are used to model pairwise relations between objects through structures/concepts as nodes (or simply “points”) and edges (also called “links”, “arcs” or “lines” that connects two nodes) [1][2]. The study of graphs and its properties is called Graph Theory and was developed by Dénes König in 1936, a brilliant mathematician which wrote the very first book about graph theory [3]. Graphs are used to model lots of situations that happens in real world like most efficient airplane path from x to y or shortest distance between two points of a city (GPS algorithms), and so on.

The problem

2014 Grad Test — Practice round.

Bad Horse Problem

As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so much so that Bad Horse has decided to split the league into two departments in order to separate troublesome members. Being the Thoroughbred of Sin, Bad Horse isn’t about to spend his valuable time figuring out how to split the League members by himself. That what he’s got you — his loyal henchman — for.

https://code.google.com/codejam/contest/2933486/dashboard

Solution

After reading the description some ideas came to my mind before initiate to code a possible solution.

First, I will have to store pair’s names and somehow represent the relation between then. Also, I have to be able to check the possibility to separate the pairs into 2 groups — No pair should be in the same group. With a bit more searches I’ve found out that this is classic problem of graph bipartite.

I’ve realized it’s a important step before start coding in super matrix hacker style. Analyse it, get into problem’s head.

Bipartite Graph

A bipartite graph is a graph which all its nodes can be separated in two groups so that each element of one group is only related to elements of the other group. It’s also knows as bicolored graph (each group would represent a color, so every element in the graph is only related to another color element). They are very used in Petri Networks (Concurrency Systems resources simulation) and others real world situations [4].

Algorithm

The algorithm to check a graph bipartition can be very similar to DFS in trees data structures (Depth First Search). DFS algorithm it’s used to find the depth of a tree and works by choosing the root element and dive into their neighbors until there aren’t no element’s child or leaf.

Curious fact: Every tree is a graph bipartite

To add the function of bipartition check we need to initiate another structure to store the group (or color) information of each element. Besides that, it’s necessary also to check the groups belonging to each graph node given its neighbors group

The pseudocode analysis will be divided in two parts to a better understanding.

Pseudocode - Controller

Let’s check the pseudo algorithm.

The first part will function as a initialize or “controller” assuring that the routine will be executed for all nodes in graph.

OBS: To explain the pseudocode I’m going to assume the following constants
V = graph node
C1 = group 01 value
graph = the data structure represented in code
C2 = group 02 value

FOR each graph node v
    Initialize v group/color c with a neutral value, representing no color/group
end FOR

FOR each graph node V
    Initialize V group value C = C1
end FOR
FOR every graph node V
    IF group C is C1:
        IF NOT SET_GROUP_VALUE(graph, V, C1)
            return FALSE
        end IF
    end IF
end FOR
return TRUE

At the first loop we’re going to initiate all nodes with group 01 value. At the second loop for every node that has the group 01 value we’re going to check its neighbors and, if possible, set it a different group value.

Pseudocode — Recursive Search

The second part is the recursive algorithm that holds the logic to check if a node can be part of a different group than his neighbors.

-- Start a routine SET_GROUP_VALUE(graph, V, C) -- Ignore this line

SET the group of V as C
FOR every neighbors W of V
    IF group value C of W is neutral
        IF NOT SET_GROUP_VALUE(graph, W, C2)
            return FALSE
        end IF
    ELSE
        IF group value of W is C
            return FALSE
        end IF
    end ELSE
end FOR
return TRUE

The first loop start to dive into the subset of V nodes (subtree with root in V). If V’s neighbor W have group 01 value then the algorithm will check if it’s possible to give group 02 value.

Implementation

As described in the problem, our goal is to execute T test cases of M element pairs described in a file. The first line of this file will contain the T value followed by M number of pairs, thus, the next M lines will contain the M pairs information. The output will be also a file that describes the test case number and if the set of M pairs names can be divided into two groups, or, if the set of pairs can be represented as a bipartite graph.

-- Input file example -- Ignore this line
2
1
Dead_Bowie Fake_Thomas_Jefferson
3
Dead_Bowie Fake_Thomas_Jefferson
Fake_Thomas_Jefferson Fury_Leika
Fury_Leika Dead_Bowie

-- Output file example -- Ignore this line
Case #1: Yes
Case #2: No

There are some ways to represent a graph in code [5], one of them is an adjacency matrix and that is how it’s gonna be represent in this article, but with some small modifications the solution can be able to work as well. Here, I will represent it as a python dictionary: The keys will be the nodes and the key’s value will be a list of all its neighbors. Here’s an example

g = { 
    “a” : [“d”],
    “b” : [“c”],
    “c” : [“b”, “c”, “d”, “e”],
    “d” : [“a”, “c”],
    “e” : [“c”],
    “f” : []
}

Code

Let’s check my implementation of pseudocode.
OBS: color = group value

From line 1 to 27 is implemented the algorithm we’ve seen before in the pseudocode. In line 31, I’m getting from input file (which was in the same directory of this code) the number of tests which will be done.

From line 35 until the end of the file we’re going to:

• For each test case (iTestCase), retrieve the number of pairs (nPairs) that’s going to be analyzed.
• For each pair, we’re going to get the names described.
• From line 40 until 50, it’s going to construct the dictionary based on the pair connection described in file.

The output tell us which test case is represents a bipartite graph or not.

...

I’m a Junior software developer in Brazil and I just fascinated by technology and programming.

So please, any doubts, hints or comments are more than welcome!

Follow me in Github, Twitter or Linkedin.

...

References

[1] https://mathworld.wolfram.com/Graph.html
[2] https://en.wikipedia.org/wiki/Graph_theory
[3] https://pt.wikipedia.org/wiki/D%C3%A9nes_K%C3%B6nig
[4] https://pt.wikipedia.org/wiki/Grafo_bipartido
[5] https://www.geeksforgeeks.org/graph-and-its-representations/