Package networkx :: Module base

[frames | no frames]

## Module networkx.base

Base classes for graphs and digraphs.

Unless otherwise specified, by graph we mean a simple graph that has no self-loops or multiple (parallel) edges. (See the module xbase.py for graph classes XGraph and XDiGraph that allow for self-loops, mutiple edges and arbitrary objects associated with edges.)

The following classes are provided:

Graph
  The basic operations common to graph-like classes.
DiGraph
  Operations common to digraphs, a graph with directed edges. Subclass of Graph.
An empty graph or digraph is created with
  - G=Graph()
  - G=DiGraph()

This module implements graphs using data structures based on an adjacency list implemented as a node-centric dictionary of dictionaries. The dictionary contains keys corresponding to the nodes and the values are dictionaries of neighboring node keys with the value 1. This allows fast addition, deletion and lookup of nodes and neighbors in large graphs. The underlying datastructure should only be visible in this module. In all other modules, instances of graph-like objects are manipulated solely via the methods defined here and not by acting directly on the datastructure.

The following notation is used throughout NetworkX documentation and code: (we use mathematical notation n,v,w,... to indicate a node, v=vertex=node).

G,G1,G2,H,etc:
  Graphs
n,n1,n2,u,v,v1,v2:
  nodes (v stands for vertex=node)
nlist,vlist:
  a list of nodes
nbunch:
  a "bunch" of nodes (vertices). an nbunch is any iterable container of nodes that is not itself a node in the graph. (It can be an iterable or an iterator, e.g. a list, set, graph, file, etc..)
e=(n1,n2):
  an edge (a python "2-tuple"), also written u-v. In Xgraph G.add_edge(n1,n2) is equivalent to add_edge(n1,n2,1). However, G.delete_edge(n1,n2) will delete all edges between n1 and n2.
elist:
  a list of edges (as tuples)
ebunch:
  a bunch of edges (as tuples) an ebunch is any iterable (non-string) container of edge-tuples. (Similar to nbunch, also see add_edge).
Warning:
  - The ordering of objects within an arbitrary nbunch/ebunch can be machine- or implementation-dependent.
  - Algorithms should treat an arbitrary nbunch/ebunch as once-through-and-exhausted iterable containers.
  - len(nbunch) and len(ebunch) need not be defined.

# Methods

The Graph class provides rudimentary graph operations:

## Mutating Graph methods

> - G.add_node(n), G.add_nodes_from(nbunch)
> - G.delete_node(n), G.delete_nodes_from(nbunch)
> - G.add_edge(n1,n2), G.add_edge(e), where e=(u,v)
> - G.add_edges_from(ebunch)
> - G.delete_edge(n1,n2), G.delete_edge(e), where e=(u,v)
> - G.delete_edges_from(ebunch)
> - G.add_path(nlist)
> - G.add_cycle(nlist)
> - G.clear()
> - G.subgraph(nbunch,inplace=True)

## Non-mutating Graph methods

> - len(G)
> - n in G (equivalent to G.has_node(n))
> - G.has_node(n)
> - G.nodes()
> - G.nodes_iter()
> - G.has_edge(n1,n2)
> - G.edges(), G.edges(n), G.edges(nbunch)
> - G.edges_iter(), G.edges_iter(n), G.edges_iter(nbunch)
> - G.neighbors(n)
> - G[n] (equivalent to G.neighbors(n))
> - G.neighbors_iter(n) # iterator over neighbors
> - G.number_of_nodes()
> - G.number_of_edges()
> - G.degree(n), G.degree(nbunch)
> - G.degree_iter(n), G.degree_iter(nbunch)
> - G.is_directed()

## Methods returning a new graph

> - G.subgraph(nbunch)
> - G.subgraph(nbunch,create_using=H)
> - G.copy()
> - G.to_undirected()
> - G.to_directed()

# Examples

Create an empty graph structure (a "null graph") with zero nodes and zero edges.

    >>> from networkx import *
    >>> G=Graph()

G can be grown in several ways. By adding one node at a time:

    >>> G.add_node(1)

by adding a list of nodes:

    >>> G.add_nodes_from([2,3])

by using an iterator:

    >>> G.add_nodes_from(xrange(100,110))

or by adding any nbunch of nodes (see above definition of an nbunch):

    >>> H=path_graph(10)
    >>> G.add_nodes_from( H )

(H can be another graph, or dict, or set, or even a file.)

    >>> G.add_node( H )

(Any hashable object can represent a node, e.g. a Graph, a customized node object, etc.)

G can also be grown by adding one edge at a time:

    >>> G.add_edge( (1,2) )

by adding a list of edges:

    >>> G.add_edges_from([(1,2),(1,3)])

or by adding any ebunch of edges (see above definition of an ebunch):

    >>> G.add_edges_from(H.edges())

There are no complaints when adding existing nodes or edges:

    >>> G=Graph()
    >>> G.add_edge([(1,2),(1,3)])

will add new nodes as required.

Classes
`DiGraph` | A graph with directed edges.
`Graph` | Graph is a simple graph without any multiple (parallel) edges or self-loops.

Exceptions
`NetworkXError` | Exception for a serious error in NetworkX
`NetworkXException` | Base class for exceptions in NetworkX.

Function Summary
| ``degree`(G, nbunch, with_labels)` Return degree of single node or of nbunch of nodes.
| ``degree_histogram`(G)` Return a list of the frequency of each degree value.
| ``density`(G)` Return the density of a graph.
| ``edges`(G, nbunch, with_labels)` Return list of edges adjacent to nodes in nbunch.
| ``edges_iter`(G, nbunch, with_labels)` Return iterator over edges adjacent to nodes in nbunch.
| ``neighbors`(G, n, with_labels)` Return a list of nodes connected to node n.
| ``nodes`(G)` Return a copy of the graph nodes in a list.
| ``nodes_iter`(G)` Return an iterator over the graph nodes.
| ``number_of_edges`(G)` Return the size of a graph = number of edges.
| ``number_of_nodes`(G)` Return the order of a graph = number of nodes.

Variable Summary
`str` | `__author__` = `'Aric Hagberg (hagberg@lanl.gov)\nPieter Sw...`
`str` | `__credits__` = `''`
`str` | `__date__` = `'$Date: 2005-06-24 14:16:40 -0600 (Fri, 24 Ju...`
`str` | `__revision__` = `'$Revision: 1061 $'`

Function Details

### degree(G, nbunch=None, with_labels=False)

Return degree of single node or of nbunch of nodes. If nbunch is ommitted, then return degrees of all nodes.

### degree_histogram(G)

Return a list of the frequency of each degree value.

The degree values are the index in the list. Note: the bins are width one, hence len(list) can be large (Order(number_of_edges))

### density(G)

Return the density of a graph.

density = size/(order*(order-1)/2) density()=0.0 for an edge-less graph and 1.0 for a complete graph.

### edges(G, nbunch=None, with_labels=False)

Return list of edges adjacent to nodes in nbunch. Return all edges if nbunch is unspecified or nbunch=None.

### edges_iter(G, nbunch=None, with_labels=False)

Return iterator over edges adjacent to nodes in nbunch. Return all edges if nbunch is unspecified or nbunch=None.

### neighbors(G, n, with_labels=False)

Return a list of nodes connected to node n.

### nodes(G)

Return a copy of the graph nodes in a list.

### nodes_iter(G)

Return an iterator over the graph nodes.

### number_of_edges(G)

Return the size of a graph = number of edges.

### number_of_nodes(G)

Return the order of a graph = number of nodes.

Variable Details

### __author__

  Type:
    `str`
  Value:

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

### __credits__

  Type:
    `str`
  Value:

        ''

### __date__

  Type:
    `str`
  Value:

        '$Date: 2005-06-24 14:16:40 -0600 (Fri, 24 Jun 2005) $'

### __revision__

  Type:
    `str`
  Value:

        '$Revision: 1061 $'

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