Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/mis.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
2 # $Id: maximalIndependentSet.py 576 2011-03-01 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éguin-C. <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