Gallery example for Maximum Independent Set (#5563)

* Update mayavi2_spring.py

trial commit

* Example map for GSoC

* Changing errors in the example graph file

* Rename example_map.py to example_map_2.py

* style change to map code

* Trial-map

* Undo mayavi example change.

* Mv example to gallery and use spx-gallery naming scheme.

* Add docstring to MIS gallery example.

* Simplify example.

* Make node coloring more clear.

---------

Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

1 files changed, 44 insertions, 0 deletions

diff --git a/examples/algorithms/plot_maximum_independent_set.py b/examples/algorithms/plot_maximum_independent_set.py
new file mode 100644
index 00000000..670edf96
--- /dev/null
+++ b/examples/algorithms/plot_maximum_independent_set.py
@@ -0,0 +1,44 @@
+"""
+=======================
+Maximum Independent Set
+=======================
+
+An independent set is a set of vertices in a graph where no two vertices in the
+set are adjacent. The maximum independent set is the independent set of largest
+possible size for a given graph.
+"""
+
+import numpy as np
+import matplotlib.pyplot as plt
+import networkx as nx
+from networkx.algorithms import approximation as approx
+
+G = nx.Graph(
+    [
+        (1, 2),
+        (7, 2),
+        (3, 9),
+        (3, 2),
+        (7, 6),
+        (5, 2),
+        (1, 5),
+        (2, 8),
+        (10, 2),
+        (1, 7),
+        (6, 1),
+        (6, 9),
+        (8, 4),
+        (9, 4),
+    ]
+)
+
+I = approx.maximum_independent_set(G)
+print(f"Maximum independent set of G: {I}")
+
+pos = nx.spring_layout(G, seed=39299899)
+nx.draw(
+    G,
+    pos=pos,
+    with_labels=True,
+    node_color=["tab:red" if n in I else "tab:blue" for n in G],
+)