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")
)