spectral bisection for graphs using fiedler vector (#6404)

Add spectral_bisection function to bisect node sets based on the
Fiedler vector

Co-authored-by: Benjamin Edwards <bedwards@cs.unm.edu>
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

1 files changed, 15 insertions, 0 deletions

diff --git a/networkx/linalg/tests/test_algebraic_connectivity.py b/networkx/linalg/tests/test_algebraic_connectivity.py
index 7a86bd0a..16ee09c1 100644
--- a/networkx/linalg/tests/test_algebraic_connectivity.py
+++ b/networkx/linalg/tests/test_algebraic_connectivity.py
@@ -46,6 +46,21 @@ def test_fiedler_vector_tracemin_unknown():
         )
 
 
+def test_spectral_bisection():
+    pytest.importorskip("scipy")
+    G = nx.barbell_graph(3, 0)
+    C = nx.spectral_bisection(G)
+    assert C == ({0, 1, 2}, {3, 4, 5})
+
+    mapping = dict(enumerate("badfec"))
+    G = nx.relabel_nodes(G, mapping)
+    C = nx.spectral_bisection(G)
+    assert C == (
+        {mapping[0], mapping[1], mapping[2]},
+        {mapping[3], mapping[4], mapping[5]},
+    )
+
+
 def check_eigenvector(A, l, x):
     nx = np.linalg.norm(x)
     # Check zeroness.