Skip to main content
`Ctrl`+`K`

# find_induced_nodes

find_induced_nodes(G, s, t, treewidth_bound=9223372036854775807)

  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

    treewidth_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 Set of nodes

      The set of induced nodes in the path from s to t in G

  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 non-chordal, a `NetworkXError` is raised.

  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.

  Self Loops are ignored

  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

  Examples

      >>> 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]