Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/mis.py: 32%

1""" 

2Algorithm to find a maximal (not maximum) independent set. 

3 

4""" 

5import networkx as nx 

6from networkx.utils import not_implemented_for, py_random_state 

7 

8__all__ = ["maximal_independent_set"] 

9 

10 

11@not_implemented_for("directed") 

12@py_random_state(2) 

13@nx._dispatch 

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