networkx.algorithms.chordal.find_induced_nodes¶
-
find_induced_nodes
(G, s, t, treewidth_bound=9223372036854775807)[source]¶ Returns the set of induced nodes in the path from s to t.
Parameters: - G (graph) – A chordal NetworkX graph
- s (node) – Source node to look for induced nodes
- t (node) – Destination node to look for induced nodes
- treewith_bound (float) – Maximum treewidth acceptable for the graph H. The search for induced nodes will end as soon as the treewidth_bound is exceeded.
Returns: I – The set of induced nodes in the path from s to t in G
Return type: Set of nodes
Raises: NetworkXError
– The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. If the input graph is an instance of one of these classes, aNetworkXError
is raised. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, aNetworkXError
is raised.Examples
>>> import networkx as nx >>> G=nx.Graph() >>> G = nx.generators.classic.path_graph(10) >>> I = nx.find_induced_nodes(G,1,9,2) >>> list(I) [1, 2, 3, 4, 5, 6, 7, 8, 9]
Notes
G must be a chordal graph and (s,t) an edge that is not in G.
If a treewidth_bound is provided, the search for induced nodes will end as soon as the treewidth_bound is exceeded.
The algorithm is inspired by Algorithm 4 in [1]. A formal definition of induced node can also be found on that reference.
References
[1] Learning Bounded Treewidth Bayesian Networks. Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699–2731, 2008. http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf