Bipartite Graphs: A Functional Approach to Solving the Conundrum

I was recently introduced to a concept in graph theory called bipartite graphs. A bipartite graph is essentially a graph where no node (vertex) has an odd number of hops back to itself (cycles). Wikipedia defines it this way:

a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V

https://en.wikipedia.org/wiki/Bipartite_graph

Essentially, you divide a graph into two subsets, U and V. If any vertex in U connects to another vertex in U, or one in V connects to another in V, the graph is not bipartite. Vertices in U may only connect to vertices in V, and vice versa.

I was confronted with the problem where you are given a graph in the following format (EDN, or Clojure), and asked to determine whether it is bipartite or not:

{:nodes [
  {:id 1 :relationships [2 6]}
  {:id 2 :relationships [1 3]}
  {:id 3 :relationships [2 4]}
  {:id 4 :relationships [3 5]}
  {:id 5 :relationships [4 6]}
  {:id 6 :relationships [5 1]}
  ]
}

Here is a visualization of this graph:

Determining whether this graph is bitartite requires three/four main steps:
1. The graph must be grouped into two groups, “a” and “b”.
2. You must determine whether any vertex in “a” is connected to another in “a”, or any vertex in “b” is connected to another in “b”.
3. If so, return false.
4. Otherwise, return true.

In practice, you check this as you go, so if you ever find a single vertex which fails this predicate, the function shortcuts. There is no need to keep checking the rest of the nodes; it’s a binary proposition: either the graph is bipartite, or it isn’t.

Here is my solution in Clojure:

1  (defn bipartite?
2   "Determines whether a given graph is bipartite."
3   [graph]
4   (let [nodes (:nodes graph)]
5     (loop [cur-node (first nodes)
6            rest-of-nodes (rest nodes)
7            cur-key :a
8            maps {:a [] :b []}]
9       (if (some #(.contains (get maps cur-key) %) (:relationships cur-node))
10         false
11         (if (zero? (count rest-of-nodes))
12           true
13           (recur
14            (first rest-of-nodes)
15            (rest rest-of-nodes)
16            (if (= :a cur-key)
17              :b
18              :a
19              )
20            (merge-with into maps {cur-key [(:id cur-node)]})))))))

Yes, it does work! I will walk through it line-by-line.

  1. Declare a function called bipartite? In Clojure, it’s convention to name a predicate function (one which returns a boolean) with a question-mark at the end.
  2. Doc-string
  3. Declare the params; this is a unary function, it takes one arg: graph
  4. Bind the elem “:nodes” to nodes
  5. Loop through each node, initially binding the first node to cur-node
  6. Bind the rest of the nodes to rest-of-nodes
  7. We will alternate between keys “:a” and “:b”, so we just start with “:a” and bind it to cur-key
  8. We are going to hold ids that have already been assigned here in the maps var
  9. Test the “:relationships” key of cur-node and see if any of the values within match the associated list of ids in maps
  10. If there is a match, cut the function short and return false
  11. Otherwise, test if there are no nodes left in rest-of-nodes
  12. If this be the case, the function has succeeded
  13. Otherwise, begin recursion
  14. Bind the next node to cur-node
  15. Bind the rest of the nodes to rest-of-nodes
  16. Test if cur-key is “:a”
  17. If so, bind cur-key to “:b”
  18. Otherwise, bind cur-key to “:a”
  19. End of if
  20. Merge the id of cur-node with its respective vector in maps and bind the result to maps in the next iteration of loop

And…that’s it! It’s fairly straightforward, although it took some time to think through. If you would like to test the code yourself, you can clone it from my git repo:

git clone https://github.com/abtrumpet/bipartite-graphs-problem.git

You will need Leiningen build tool to run this code. After cloning, in the clojure directory, run

lein run

This will result in 4 things:
1. The first example-graph printed out
2. The result of the this graph being applied to bipartite? (true)
3. The second example-graph-2 (shown below) printed out
4. The result of this graph being applied to bipartite? (false)

example-graph-2

(def example-graph-2
  {:nodes [
   {:id 1 :relationships [2 6 9]}
   {:id 2 :relationships [1 3]}
   {:id 3 :relationships [2 4]}
   {:id 4 :relationships [3 5]}
   {:id 5 :relationships [4 6]}
   {:id 6 :relationships [5 1 9]}
   {:id 7 :relationships [6 8]}
   {:id 8 :relationships [5 7]}
   {:id 9 :relationships [1 6]}
    ]
  }
)

A similar (tail-recursive) implementation in JavaScript:

function isBipartite(graph) {
  const { nodes } = graph;
  
  function _isBipartite(curNode = {}, restOfNodes = [], curKey = "a", maps = {a: [], b: []}) {
    if(curNode.relationships.some(x =>
      maps[curKey] && maps[curKey].includes(x)
    )) return false;

    if (restOfNodes.length == 0)
      return true;

    return _isBipartite(
      restOfNodes[0], 
      restOfNodes.splice(1), 
      curKey == "a" ? "b" : "a",
      {...maps, [curKey]: [...maps[curKey], curNode.id]}
    );
  }

  return _isBipartite(nodes[0], nodes.splice(1));
}

Next steps:

I plan on writing similar implementations in Elixir and Haskell.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.