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

https://en.wikipedia.org/wiki/Bipartite_graphUandVsuch that every edge connects a vertex inUto one inV

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

- 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. - Doc-string
- Declare the params; this is a unary function, it takes one arg:
*graph* - Bind the elem “:nodes” to
*nodes* - Loop through each node, initially binding the first node to
*cur-node* - Bind the rest of the nodes to
*rest-of-nodes* - We will alternate between keys “:a” and “:b”, so we just start with “:a” and bind it to
*cur-key* - We are going to hold ids that have already been assigned here in the
*maps*var - Test the “:relationships” key of
*cur-node*and see if any of the values within match the associated list of ids in*maps* - If there is a match, cut the function short and return
*false* - Otherwise, test if there are no nodes left in
*rest-of-nodes* - If this be the case, the function has succeeded
- Otherwise, begin recursion
- Bind the next node to
*cur-node* - Bind the rest of the nodes to
*rest-of-nodes* - Test if
*cur-key*is “:a” - If so, bind
*cur-key*to “:b” - Otherwise, bind
*cur-key*to “:a” - End of if
- 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*.