Package networkx :: Module search

[frames | no frames]

## Module networkx.search

Search algorithms, shortest path, spanning trees, etc.

See also networkx.paths.

The following search methods available, see the documentation below.

> - number_connected_components(G)
> - connected_components(G)
> - connected_component_subgraphs(G)
> - dfs_preorder(G,v=None)
> - dfs_postorder(G,v=None)
> - dfs_predecessor(G,v=None)
> - dfs_successor(G,v=None)
> - bfs_length(G,source=None,target=None)
> - bfs_path(G,source,target=None)
> - dfs_forest(G,v=None)

These algorithms are based on Program 18.10 "Generalized graph search", page 128, Algorithms in C, Part 5, Graph Algorithms by Robert Sedgewick

Reference:

    @Book{sedgewick-2001-algorithms-5,
    author =       {Robert Sedgewick},
    title =        {Algorithms in C, Part 5: Graph Algorithms},
    publisher =    {Addison Wesley Professional},
    year =         {2001},
    edition =      {3rd},
    }

Function Summary
| ``bfs_length`(G, source, target)` Return a dictionary of nodes with the shortest path length from source.
| ``bfs_path`(G, source, target)` Return a dictionary of nodes with the paths from source to all reachable nodes.
| ``connected_component_subgraphs`(G)` Return a list of graphs of each connected component of G.
| ``connected_components`(G)` Return a list of lists of nodes in each connected component of G.
| ``dfs_forest`(G, v)` Return a forest of trees built from depth first search (DFS).
| ``dfs_postorder`(G, v)` Return a list of nodes ordered by depth first search (DFS) postorder.
| ``dfs_predecessor`(G, v)` Return a dictionary of nodes each with a list of predecessor nodes in depth first search (DFS) order.
| ``dfs_preorder`(G, v)` Return a list of nodes ordered by depth first search (DFS) preorder.
| ``dfs_successor`(G, v)` Return a dictionary of nodes each with a list of successor nodes in depth first search (DFS) order.
| ``is_connected`(G)` True if G is connected
| ``node_connected_component`(G, v)` Return the connected component to which v belongs as a list of nodes.
| ``number_connected_components`(G)` Return number of connected components of G.

Variable Summary
`str` | `__author__` = `'Aric Hagberg (hagberg@lanl.gov)\nDan Schul...`
`str` | `__credits__` = `''`
`str` | `__date__` = `'$Date: 2005-06-15 08:19:25 -0600 (Wed, 15 Ju...`
`str` | `__revision__` = `'$Revision: 1026 $'`

Function Details

### bfs_length(G, source, target=None)

Return a dictionary of nodes with the shortest path length from source.

### bfs_path(G, source, target=None)

Return a dictionary of nodes with the paths from source to all reachable nodes. Optional target=target produces only one path as a list.

### connected_component_subgraphs(G)

Return a list of graphs of each connected component of G. The list is ordered from largest connected component to smallest. To get the largest connected component:

    >>> H=connected_component_subgraphs(G)[0]

### connected_components(G)

Return a list of lists of nodes in each connected component of G. The list is ordered from largest connected component to smallest.

### dfs_forest(G, v=None)

Return a forest of trees built from depth first search (DFS). Optional v=v limits search to component of graph containing v and will return a single tree.

### dfs_postorder(G, v=None)

Return a list of nodes ordered by depth first search (DFS) postorder. If the graph has more than one component return a list of lists. Optional v=v limits search to component of graph containing v.

### dfs_predecessor(G, v=None)

Return a dictionary of nodes each with a list of predecessor nodes in depth first search (DFS) order. Optional v=v limits search to component of graph containing v.

### dfs_preorder(G, v=None)

Return a list of nodes ordered by depth first search (DFS) preorder. If the graph has more than one component return a list of lists. Optional v=v limits search to component of graph containing v.

### dfs_successor(G, v=None)

Return a dictionary of nodes each with a list of successor nodes in depth first search (DFS) order. Optional v=v limits search to component of graph containing v.

### is_connected(G)

True if G is connected

### node_connected_component(G, v)

Return the connected component to which v belongs as a list of nodes.

### number_connected_components(G)

Return number of connected components of G.

Variable Details

### __author__

  Type:
    `str`
  Value:

        '''Aric Hagberg (hagberg@lanl.gov)
        Dan Schult(dschult@colgate.edu)'''

### __credits__

  Type:
    `str`
  Value:

        ''

### __date__

  Type:
    `str`
  Value:

        '$Date: 2005-06-15 08:19:25 -0600 (Wed, 15 Jun 2005) $'

### __revision__

  Type:
    `str`
  Value:

        '$Revision: 1026 $'

Generated by Epydoc 2.1 on Sun Aug 21 08:06:58 2005 | http://epydoc.sf.net