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