"""
Graph classes
=============

Graph

   A simple graph that has no self-loops or multiple (parallel) edges.

   An empty graph is created with

   >>> G=Graph()
   
DiGraph

   A directed graph that has no self-loops or multiple (parallel) edges.
   Subclass of Graph.

   An empty digraph is created with

   >>> G=DiGraph()

XGraph

   A graph that has (optional) self-loops or multiple (parallel) edges
   and arbitrary data on the edges.
   Subclass of Graph.

   An empty graph is created with

   >>> G=XGraph()
   
XDiGraph

   A directed graph that has (optional) self-loops or multiple (parallel)
   edges and arbitrary data on the edges.

   A simple digraph that has no self-loops or multiple (parallel) edges.
   Subclass of DiGraph which is a subclass of Graph.

   An empty digraph is created with

   >>> G=XDiGraph()


The XGraph and XDiGraph classes extend the Graph and DiGraph classes
by allowing (optional) self loops, multiedges and by decorating
each edge with an object x.  

Each XDiGraph or XGraph edge is a 3-tuple e=(n1,n2,x), 
representing an edge between nodes n1 and n2 that 
is decorated with the object x. Here n1 and n2 are (hashable) 
node objects and x is a (not necessarily hashable) edge object. 
If multiedges are allowed, G.get_edge(n1,n2) returns a 
list of edge objects.

Whether an XGraph or XDiGraph allow self-loops or multiple edges is
determined initially via parameters selfloops=True/False and 
multiedges=True/False. 
For example, the example empty XGraph created above is equivalent to

>>> G=XGraph(selfloops=False, multiedges=False)

Similar defaults hold for XDiGraph.  The command

>>> G=XDiGraph(multiedges=True)

creates an empty digraph G that does not allow selfloops 
but does allow for multiple (parallel) edges.  Methods exist 
for allowing or disallowing each feature after instatiation as well.

Note that if G is an XGraph then G.add_edge(n1,n2) will add 
the edge (n1,n2,None), and G.delete_edge(n1,n2) will attempt 
to delete the edge (n1,n2,None).
In the case of multiple edges between nodes n1 and n2, one can use
G.delete_multiedge(n1,n2) to delete all edges between n1 and n2.


Notation
========

The following shorthand 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 (vertices)

nlist:
   a list of nodes (vertices)

nbunch:
   a "bunch" of nodes (vertices).
   An nbunch is either a single node of the graph or
   any iterable container/iterator of nodes.  The distinction
   is determined by checking if nbunch is in the graph.
   If you use iterable containers as nodes you should be 
   careful when using nbunch.

e=(n1,n2):
   an edge (a python "2-tuple"), also written n1-n2 (if undirected)
   and n1->n2 (if directed). 
   
e=(n1,n2,x):
   an edge triple ("3-tuple") containing the two nodes connected and the 
   edge data/label/object stored associated with the edge. The object x,
   or a list of objects (if multiedges=True), can be obtained using
   G.get_edge(n1,n2)

elist:
   a list of edges (as 2- or 3-tuples)

ebunch:
   a bunch of edges (as 2- or 3-tuples).
   An ebunch is any iterable (non-string) container
   of edge-tuples (either 2-tuples, 3-tuples or a mixture).

Warning:
  - The ordering of objects within an arbitrary nbunch/ebunch can be
    machine-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
=======

Each class provides basic graph methods.

Mutating Graph methods
----------------------
   
    - G.add_node(n), G.add_nodes_from(nlist)
    - G.delete_node(n), G.delete_nodes_from(nlist)
    - 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)
    - G.has_node(n)
    - n in G (equivalent to G.has_node(n))
    - for n in G: (iterate through the nodes of G)
    - G.nodes()
    - G.nodes_iter()
    - G.has_edge(n1,n2), G.has_neighbor(n1,n2), G.get_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.order()
    - G.number_of_edges(), G.size()
    - G.edge_boundary(nbunch1), G.node_boundary(nbunch1)
    - G.degree(n), G.degree(nbunch)
    - G.degree_iter(n), G.degree_iter(nbunch)
    - G.is_directed()
    - G.info()  # print variaous info about a graph
    - G.prepare_nbunch(nbunch)  # return list of nodes in G and nbunch

Methods returning a new graph
-----------------------------

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



Implementation Notes
====================

The graph classes implement 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 None (the Python None type) for Graph and DiGraph or
user specified (default is None) for XGraph and XDiGraph.
The dictionary of dictionary structure  allows fast addition,
deletion and lookup of nodes and neighbors in large graphs.  

Similarities between XGraph and Graph
-------------------------------------

XGraph and Graph differ in the way edge data is handled.
XGraph edges are 3-tuples (n1,n2,x) and Graph edges are 2-tuples (n1,n2).
XGraph inherits from the Graph class, and XDiGraph from the DiGraph class.

Graph and XGraph are similar in the following ways:

1. Edgeless graphs are the same in XGraph and Graph.
   For an edgeless graph, represented by G (member of the Graph class)
   and XG (member of XGraph class), there is no difference between
   the datastructures G.adj and XG.adj, other than possibly
   in the ordering of the keys in the adj dict.


2. Basic graph construction code for G=Graph() will also work for
   G=XGraph().  In the Graph class, the simplest graph construction
   consists of a graph creation command G=Graph() followed by a list
   of graph construction commands, consisting of successive calls to
   the methods:

   G.add_node, G.add_nodes_from, G.add_edge, G.add_edges, G.add_path,
   G.add_cycle G.delete_node, G.delete_nodes_from, G.delete_edge,
   G.delete_edges_from

   with all edges specified as 2-tuples,  

   If one replaces the graph creation command with G=XGraph(), and then
   apply the identical list of construction commands, the resulting XGraph
   object will be a simple graph G with identical datastructure G.adj. 
   This property ensures reuse of code developed for graph generation 
   in the Graph class.


"""
