ioftools / networkxMiCe / networkxmaster / networkx / algorithms / mis.py @ 5cef0f13
History  View  Annotate  Download (2.7 KB)
1 
# * coding: utf8 *


2 
# $Id: maximalIndependentSet.py 576 20110301 05:50:34Z lleeoo $

3 
# Leo Lopes <leo.lopes@monash.edu>

4 
# Aric Hagberg <hagberg@lanl.gov>

5 
# Dan Schult <dschult@colgate.edu>

6 
# Pieter Swart <swart@lanl.gov>

7 
# All rights reserved.

8 
# BSD license.

9 
#

10 
# Authors: Leo Lopes <leo.lopes@monash.edu>

11 
# Loïc SéguinC. <loicseguin@gmail.com>

12 
"""

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

14 

15 
"""

16 
import networkx as nx 
17 
from networkx.utils import not_implemented_for 
18 
from networkx.utils import py_random_state 
19  
20 
__all__ = ['maximal_independent_set']

21  
22  
23 
@py_random_state(2) 
24 
@not_implemented_for('directed') 
25 
def maximal_independent_set(G, nodes=None, seed=None): 
26 
"""Returns a random maximal independent set guaranteed to contain

27 
a given set of nodes.

28 

29 
An independent set is a set of nodes such that the subgraph

30 
of G induced by these nodes contains no edges. A maximal

31 
independent set is an independent set such that it is not possible

32 
to add a new node and still get an independent set.

33 

34 
Parameters

35 


36 
G : NetworkX graph

37 

38 
nodes : list or iterable

39 
Nodes that must be part of the independent set. This set of nodes

40 
must be independent.

41 

42 
seed : integer, random_state, or None (default)

43 
Indicator of random number generation state.

44 
See :ref:`Randomness<randomness>`.

45 

46 
Returns

47 


48 
indep_nodes : list

49 
List of nodes that are part of a maximal independent set.

50 

51 
Raises

52 


53 
NetworkXUnfeasible

54 
If the nodes in the provided list are not part of the graph or

55 
do not form an independent set, an exception is raised.

56 

57 
NetworkXNotImplemented

58 
If `G` is directed.

59 

60 
Examples

61 


62 
>>> G = nx.path_graph(5)

63 
>>> nx.maximal_independent_set(G) # doctest: +SKIP

64 
[4, 0, 2]

65 
>>> nx.maximal_independent_set(G, [1]) # doctest: +SKIP

66 
[1, 3]

67 

68 
Notes

69 


70 
This algorithm does not solve the maximum independent set problem.

71 

72 
"""

73 
if not nodes: 
74 
nodes = set([seed.choice(list(G))]) 
75 
else:

76 
nodes = set(nodes)

77 
if not nodes.issubset(G): 
78 
raise nx.NetworkXUnfeasible(

79 
"%s is not a subset of the nodes of G" % nodes)

80 
neighbors = set.union(*[set(G.adj[v]) for v in nodes]) 
81 
if set.intersection(neighbors, nodes): 
82 
raise nx.NetworkXUnfeasible(

83 
"%s is not an independent set of G" % nodes)

84 
indep_nodes = list(nodes)

85 
available_nodes = set(G.nodes()).difference(neighbors.union(nodes))

86 
while available_nodes:

87 
node = seed.choice(list(available_nodes))

88 
indep_nodes.append(node) 
89 
available_nodes.difference_update(list(G.adj[node]) + [node])

90 
return indep_nodes
