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.

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