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
Induced_nodes – 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, a
NetworkXError
is raised. The algorithm can only be applied to chordal graphs. If the input graph is found to be nonchordal, aNetworkXError
is raised.
Examples
>>> import networkx as nx >>> G=nx.Graph() >>> G = nx.generators.classic.path_graph(10) >>> Induced_nodes = nx.find_induced_nodes(G,1,9,2) >>> sorted(Induced_nodes) [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