As part of the node your homework effort, I present an algorithm to determine whether a graph is bi-partite or not.

In scheme.

One glance should make you realize why there's no such thing as an obfuscated scheme contest.

The algorithm does a depth first search of the graph, marking each vertex with a parity. If it encounters a back-edge to a vertex of the same parity as the vertex being examined, it knows the graph is not bi-partite.

To make things clearer:

The graph is defined as an adjacency list at the top of the code
The parity is 0 if the vertex is unvisited and either -1 or 1 depending on which side of the graph it's on
/msg me with any more clarifications you want here...

(define adjList

(vector

'(3 4)

'(3 4)

'(4)

'(0 1)

'(0 1 2)

)

)

(define parityList

(vector

0

0

0

0

0

)

)

(define dfs

(lambda (vertex parity)

(define bp #t)

(vector-set! parityList vertex parity)

(for-each

(

lambda (adjVertex)

(cond

((= (vector-ref parityList adjVertex) 0)

(set! bp (and bp (dfs adjVertex (* parity -1))))

)

((= (vector-ref parityList adjVertex) (vector-ref

parityList vertex))

(set! bp #f)

)

)

)

(vector-ref adjList vertex)

)

bp

)

)

(if (dfs 0 1)

(display "Graph is Bi-Partite.\n")

(display "Graph is not Bi-Partite.\n")

)