Currently I am experimenting with Kernighan-Lin algorithm to produce coarse representation of navigation mesh for hierarchical pathfinding.
Based on the use case, my requirement is that partitions produced are a connected graph on its own.
For example, a bisection of the below grid
x--x--x--x--x--x | | | | | | x--x--x--x--x--x | | | | | | x--x--x--x--x--x
Should produce something along the lines of
a--a--a--b--b--b | | | | | | a--a--a--b--b--b | | | | | | a--a--a--b--b--b
where all nodes in partition A can be reached from a node in partition A without crossing a node in partition B.
However in quite a number of tests, I am getting disconnected partitions such as.
a--b--b--b--a--a | | | | | | a--b--b--b--a--a | | | | | | b--b--b--a--a--a
I am not able to judge if this is a bug in my code or whether the Kernighan-Lin algorithm by nature does not guarantee connected partitions.
I know that KL algorithm works towards a locally optimal solution for minimum cut, but does the algorithm not guarantee connected partitions?