KCC: improve directed_double_ring graph check
authorDouglas Bagnall <douglas.bagnall@catalyst.net.nz>
Thu, 9 Apr 2015 01:55:40 +0000 (13:55 +1200)
committerAndrew Bartlett <abartlet@samba.org>
Fri, 29 May 2015 09:08:22 +0000 (11:08 +0200)
commitcb8b99e335101c5454a1e448275993aa18f77e10
tree2d298c935ca40a69e9e19fcc045053987a674866
parent75eedf85b1516f0b2370d23d6ff1058a70b093b0
KCC: improve directed_double_ring graph check

The previous test assumed there would be only a double directed ring
but in fact there could be other edges.  In large graphs there are
certain to be more edges.

Now we want to be sure there is a complete ring apart from any other
connections. This is called the Hamiltonian path problem and takes
exponential time in general, so now our test is that it looks *quite*
a lot like a complete ring.

Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Garming Sam <garming@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>
python/samba/graph_utils.py
source4/scripting/bin/samba_kcc