Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Algorithm to find a maximal (not maximum) independent set.
4"""
6import networkx as nx
7from networkx.utils import not_implemented_for, py_random_state
9__all__ = ["maximal_independent_set"]
12@not_implemented_for("directed")
13@py_random_state(2)
14@nx._dispatchable
15def maximal_independent_set(G, nodes=None, seed=None):
16 """Returns a random maximal independent set guaranteed to contain
17 a given set of nodes.
19 An independent set is a set of nodes such that the subgraph
20 of G induced by these nodes contains no edges. A maximal
21 independent set is an independent set such that it is not possible
22 to add a new node and still get an independent set.
24 Parameters
25 ----------
26 G : NetworkX graph
28 nodes : list or iterable
29 Nodes that must be part of the independent set. This set of nodes
30 must be independent.
32 seed : integer, random_state, or None (default)
33 Indicator of random number generation state.
34 See :ref:`Randomness<randomness>`.
36 Returns
37 -------
38 indep_nodes : list
39 List of nodes that are part of a maximal independent set.
41 Raises
42 ------
43 NetworkXUnfeasible
44 If the nodes in the provided list are not part of the graph or
45 do not form an independent set, an exception is raised.
47 NetworkXNotImplemented
48 If `G` is directed.
50 Examples
51 --------
52 >>> G = nx.path_graph(5)
53 >>> nx.maximal_independent_set(G) # doctest: +SKIP
54 [4, 0, 2]
55 >>> nx.maximal_independent_set(G, [1]) # doctest: +SKIP
56 [1, 3]
58 Notes
59 -----
60 This algorithm does not solve the maximum independent set problem.
62 """
63 if not nodes:
64 nodes = {seed.choice(list(G))}
65 else:
66 nodes = set(nodes)
67 if not nodes.issubset(G):
68 raise nx.NetworkXUnfeasible(f"{nodes} is not a subset of the nodes of G")
69 neighbors = set.union(*[set(G.adj[v]) for v in nodes])
70 if set.intersection(neighbors, nodes):
71 raise nx.NetworkXUnfeasible(f"{nodes} is not an independent set of G")
72 indep_nodes = list(nodes)
73 available_nodes = set(G.nodes()).difference(neighbors.union(nodes))
74 while available_nodes:
75 node = seed.choice(list(available_nodes))
76 indep_nodes.append(node)
77 available_nodes.difference_update(list(G.adj[node]) + [node])
78 return indep_nodes