Repository: networkx/networkx

Issue:
Multigraph key simplification?
It seems that the way we handle multigraph edge keys is sometimes hard to maintain (see #2107 but true elsewhere too).  Is there a way to handle it more simply?

Some thoughts include: 
- defaulting to ```key=None``` for all add_edge actions. The first ```G.add_edge(1,2)``` gives ```(1,2,None)```. The second does nothing! To get a multiedge one must specify a key.
- default to using a UUID for the key to each multiedge.  (unique key within the MultiGraph and actually across all MultiGraphs).  Here ```G.add_edge(1,2)``` twice does add two separate edges.

Other thoughts?

Discussion:

Patch:
diff --git a/doc/source/reference/classes.multidigraph.rst b/doc/source/reference/classes.multidigraph.rst
index ab613964a..ef34f4664 100644
--- a/doc/source/reference/classes.multidigraph.rst
+++ b/doc/source/reference/classes.multidigraph.rst
@@ -28,6 +28,7 @@ Adding and Removing Nodes and Edges
    MultiDiGraph.add_edge
    MultiDiGraph.add_edges_from
    MultiDiGraph.add_weighted_edges_from
+   MultiDiGraph.new_edge_key
    MultiDiGraph.remove_edge
    MultiDiGraph.remove_edges_from
    MultiDiGraph.clear
diff --git a/doc/source/reference/classes.multigraph.rst b/doc/source/reference/classes.multigraph.rst
index 1d598ccfd..5d3984986 100644
--- a/doc/source/reference/classes.multigraph.rst
+++ b/doc/source/reference/classes.multigraph.rst
@@ -27,6 +27,7 @@ Adding and removing nodes and edges
    MultiGraph.add_edge
    MultiGraph.add_edges_from
    MultiGraph.add_weighted_edges_from
+   MultiGraph.new_edge_key
    MultiGraph.remove_edge
    MultiGraph.remove_edges_from
    MultiGraph.clear
diff --git a/doc/source/tutorial/tutorial.rst b/doc/source/tutorial/tutorial.rst
index c86741f95..3875c1a65 100644
--- a/doc/source/tutorial/tutorial.rst
+++ b/doc/source/tutorial/tutorial.rst
@@ -388,8 +388,8 @@ functions such as:
 >>> G.add_edges_from([(1,2),(1,3)])
 >>> G.add_node("spam")       # adds node "spam"
 
->>> list(nx.connected_components(G))
-[{1, 2, 3}, {'spam'}]
+>>> nx.connected_components(G)
+[[1, 2, 3], ['spam']]
 
 >>> sorted(d for n, d in G.degree())
 [0, 1, 1, 2]
diff --git a/networkx/algorithms/centrality/eigenvector.py b/networkx/algorithms/centrality/eigenvector.py
index a73611c37..f7fac9601 100644
--- a/networkx/algorithms/centrality/eigenvector.py
+++ b/networkx/algorithms/centrality/eigenvector.py
@@ -78,11 +78,6 @@ def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None,
     NetworkXError
         If each value in `nstart` is zero.
 
-    PowerIterationFailedConvergence
-        If the algorithm fails to converge to the specified tolerance
-        within the specified number of iterations of the power iteration
-        method.
-
     See Also
     --------
     eigenvector_centrality_numpy
@@ -146,7 +141,8 @@ def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None,
         # Check for convergence (in the L_1 norm).
         if sum(abs(x[n] - xlast[n]) for n in x) < nnodes * tol:
             return x
-    raise nx.PowerIterationFailedConvergence(max_iter)
+    raise nx.NetworkXError('power iteration failed to converge within {}'
+                           ' iterations'.format(max_iter))
 
 
 def eigenvector_centrality_numpy(G, weight='weight', max_iter=50, tol=0):
diff --git a/networkx/algorithms/centrality/katz.py b/networkx/algorithms/centrality/katz.py
index 39ec75f44..537c8a3af 100644
--- a/networkx/algorithms/centrality/katz.py
+++ b/networkx/algorithms/centrality/katz.py
@@ -94,11 +94,6 @@ def katz_centrality(G, alpha=0.1, beta=1.0,
        If the parameter `beta` is not a scalar but lacks a value for at least
        one node
 
-    PowerIterationFailedConvergence
-        If the algorithm fails to converge to the specified tolerance
-        within the specified number of iterations of the power iteration
-        method.
-
     Examples
     --------
     >>> import math
@@ -195,8 +190,9 @@ def katz_centrality(G, alpha=0.1, beta=1.0,
             for n in x:
                 x[n] *= s
             return x
-    raise nx.PowerIterationFailedConvergence(max_iter)
 
+    raise nx.NetworkXError('Power iteration failed to converge in '
+                           '%d iterations.' % max_iter)
 
 @not_implemented_for('multigraph')
 def katz_centrality_numpy(G, alpha=0.1, beta=1.0, normalized=True,
diff --git a/networkx/algorithms/community/community_generators.py b/networkx/algorithms/community/community_generators.py
index a12fe87db..3cdb948b2 100644
--- a/networkx/algorithms/community/community_generators.py
+++ b/networkx/algorithms/community/community_generators.py
@@ -77,7 +77,7 @@ def _powerlaw_sequence(gamma, low, high, condition, length, max_iters):
 
     ``max_iters`` indicates the number of times to generate a list
     satisfying ``length``. If the number of iterations exceeds this
-    value, :exc:`~networkx.exception.ExceededMaxIterations` is raised.
+    value, :exc:`~networkx.exception.NetworkXError` is raised.
 
     """
     for i in range(max_iters):
@@ -86,7 +86,7 @@ def _powerlaw_sequence(gamma, low, high, condition, length, max_iters):
             seq.append(_zipf_rv_below(gamma, low, high))
         if condition(seq):
             return seq
-    raise nx.ExceededMaxIterations("Could not create power law sequence")
+    raise nx.NetworkXError("Could not create power law sequence")
 
 
 # TODO Needs documentation.
@@ -100,7 +100,7 @@ def _generate_min_degree(gamma, average_degree, max_degree, tolerance,
     mid_avg_deg = 0
     while abs(mid_avg_deg - average_degree) > tolerance:
         if itrs > max_iters:
-            raise nx.ExceededMaxIterations("Could not match average_degree")
+            raise nx.NetworkXError("Could not match average_degree")
         mid_avg_deg = 0
         for x in range(int(min_deg_mid), max_degree + 1):
             mid_avg_deg += (x ** (-gamma + 1)) / zeta(gamma, min_deg_mid,
@@ -129,11 +129,15 @@ def _generate_communities(degree_sequence, community_sizes, mu, max_iters):
     ``mu`` is a float in the interval [0, 1] indicating the fraction of
     intra-community edges incident to each node.
 
+    ``max_iters`` indicates the number of times to generate a list
+    satisfying ``length``. If the number of iterations exceeds this
+    value, :exc:`~networkx.exception.NetworkXError` is raised.
+
     ``max_iters`` is the number of times to try to add a node to a
     community. This must be greater than the length of
     ``degree_sequence``, otherwise this function will always fail. If
     the number of iterations exceeds this value,
-    :exc:`~networkx.exception.ExceededMaxIterations` is raised.
+    :exc:`~networkx.exception.NetworkXError` is raised.
 
     The communities returned by this are sets of integers in the set {0,
     ..., *n* - 1}, where *n* is the length of ``degree_sequence``.
@@ -160,8 +164,8 @@ def _generate_communities(degree_sequence, community_sizes, mu, max_iters):
             free.append(result[c].pop())
         if not free:
             return result
-    msg = 'Could not assign communities; try increasing min_community'
-    raise nx.ExceededMaxIterations(msg)
+    raise nx.NetworkXError('Could not assign communities; try increasing'
+                           ' min_community')
 
 
 def LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=None,
@@ -280,7 +284,6 @@ def LFR_benchmark_graph(n, tau1, tau2, mu, average_degree=None,
         If ``min_degree`` is not specified and a suitable ``min_degree``
         cannot be found.
 
-    ExceededMaxIterations
         If a valid degree sequence cannot be created within
         ``max_iters`` number of iterations.
 
diff --git a/networkx/algorithms/isomorphism/isomorph.py b/networkx/algorithms/isomorphism/isomorph.py
index 8f1d4a478..42ff26496 100644
--- a/networkx/algorithms/isomorphism/isomorph.py
+++ b/networkx/algorithms/isomorphism/isomorph.py
@@ -186,7 +186,9 @@ def is_isomorphic(G1, G2, node_match=None, edge_match=None):
     For multidigraphs G1 and G2, using 'weight' edge attribute (default: 7)
 
     >>> G1.add_edge(1,2, weight=7)
+    1
     >>> G2.add_edge(10,20)
+    1
     >>> em = iso.numerical_multiedge_match('weight', 7, rtol=1e-6)
     >>> nx.is_isomorphic(G1, G2, edge_match=em)
     True
diff --git a/networkx/algorithms/link_analysis/hits_alg.py b/networkx/algorithms/link_analysis/hits_alg.py
index 2ca56beaf..7325352c4 100644
--- a/networkx/algorithms/link_analysis/hits_alg.py
+++ b/networkx/algorithms/link_analysis/hits_alg.py
@@ -42,13 +42,6 @@ def hits(G,max_iter=100,tol=1.0e-8,nstart=None,normalized=True):
        Two dictionaries keyed by node containing the hub and authority
        values.
 
-    Raises
-    ------
-    PowerIterationFailedConvergence
-        If the algorithm fails to converge to the specified tolerance
-        within the specified number of iterations of the power iteration
-        method.
-
     Examples
     --------
     >>> G=nx.path_graph(4)
@@ -89,7 +82,8 @@ def hits(G,max_iter=100,tol=1.0e-8,nstart=None,normalized=True):
         s=1.0/sum(h.values())
         for k in h:
             h[k]*=s
-    for _ in range(max_iter):  # power iteration: make up to max_iter iterations
+    i=0
+    while True: # power iteration: make up to max_iter iterations
         hlast=h
         h=dict.fromkeys(hlast.keys(),0)
         a=dict.fromkeys(hlast.keys(),0)
@@ -112,8 +106,10 @@ def hits(G,max_iter=100,tol=1.0e-8,nstart=None,normalized=True):
         err=sum([abs(h[n]-hlast[n]) for n in h])
         if err < tol:
             break
-    else:
-        raise nx.PowerIterationFailedConvergence(max_iter)
+        if i>max_iter:
+            raise NetworkXError(\
+            "HITS: power iteration failed to converge in %d iterations."%(i+1))
+        i+=1
     if normalized:
         s = 1.0/sum(a.values())
         for n in a:
@@ -251,13 +247,6 @@ def hits_scipy(G,max_iter=100,tol=1.0e-6,normalized=True):
     algorithm does not check if the input graph is directed and will
     execute on undirected graphs.
 
-    Raises
-    ------
-    PowerIterationFailedConvergence
-        If the algorithm fails to converge to the specified tolerance
-        within the specified number of iterations of the power iteration
-        method.
-
     References
     ----------
     .. [1] A. Langville and C. Meyer,
@@ -292,7 +281,8 @@ def hits_scipy(G,max_iter=100,tol=1.0e-6,normalized=True):
         if err < tol:
             break
         if i>max_iter:
-            raise nx.PowerIterationFailedConvergence(max_iter)
+            raise NetworkXError(\
+            "HITS: power iteration failed to converge in %d iterations."%(i+1))
         i+=1
 
     a=np.asarray(x).flatten()
diff --git a/networkx/algorithms/link_analysis/pagerank_alg.py b/networkx/algorithms/link_analysis/pagerank_alg.py
index a105f8f28..050179075 100644
--- a/networkx/algorithms/link_analysis/pagerank_alg.py
+++ b/networkx/algorithms/link_analysis/pagerank_alg.py
@@ -35,8 +35,7 @@ def pagerank(G, alpha=0.85, personalization=None,
 
     personalization: dict, optional
       The "personalization vector" consisting of a dictionary with a
-      key for every graph node and personalization value for each node.
-      At least one personalization value must be non-zero.
+      key for every graph node and nonzero personalization value for each node.
       By default, a uniform distribution is used.
 
     max_iter : integer, optional
@@ -73,11 +72,9 @@ def pagerank(G, alpha=0.85, personalization=None,
     Notes
     -----
     The eigenvector calculation is done by the power iteration method
-    and has no guarantee of convergence.  The iteration will stop after
-    an error tolerance of ``len(G) * tol`` has been reached. If the
-    number of iterations exceed `max_iter`, a
-    :exc:`networkx.exception.PowerIterationFailedConvergence` exception
-    is raised.
+    and has no guarantee of convergence.  The iteration will stop
+    after max_iter iterations or an error tolerance of
+    number_of_nodes(G)*tol has been reached.
 
     The PageRank algorithm was designed for directed graphs but this
     algorithm does not check if the input graph is directed and will
@@ -88,13 +85,6 @@ def pagerank(G, alpha=0.85, personalization=None,
     --------
     pagerank_numpy, pagerank_scipy, google_matrix
 
-    Raises
-    ------
-    PowerIterationFailedConvergence
-        If the algorithm fails to converge to the specified tolerance
-        within the specified number of iterations of the power iteration
-        method.
-
     References
     ----------
     .. [1] A. Langville and C. Meyer,
@@ -103,7 +93,6 @@ def pagerank(G, alpha=0.85, personalization=None,
     .. [2] Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry,
        The PageRank citation ranking: Bringing order to the Web. 1999
        http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf
-
     """
     if len(G) == 0:
         return {}
@@ -165,7 +154,8 @@ def pagerank(G, alpha=0.85, personalization=None,
         err = sum([abs(x[n] - xlast[n]) for n in x])
         if err < N*tol:
             return x
-    raise nx.PowerIterationFailedConvergence(max_iter)
+    raise NetworkXError('pagerank: power iteration failed to converge '
+                        'in %d iterations.' % max_iter)
 
 
 def google_matrix(G, alpha=0.85, personalization=None,
@@ -415,13 +405,6 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
     --------
     pagerank, pagerank_numpy, google_matrix
 
-    Raises
-    ------
-    PowerIterationFailedConvergence
-        If the algorithm fails to converge to the specified tolerance
-        within the specified number of iterations of the power iteration
-        method.
-
     References
     ----------
     .. [1] A. Langville and C. Meyer,
@@ -485,7 +468,8 @@ def pagerank_scipy(G, alpha=0.85, personalization=None,
         err = scipy.absolute(x - xlast).sum()
         if err < N * tol:
             return dict(zip(nodelist, map(float, x)))
-    raise nx.PowerIterationFailedConvergence(max_iter)
+    raise NetworkXError('pagerank_scipy: power iteration failed to converge '
+                        'in %d iterations.' % max_iter)
 
 
 # fixture for nose tests
diff --git a/networkx/algorithms/traversal/depth_first_search.py b/networkx/algorithms/traversal/depth_first_search.py
index 73897cf1c..2b5cea636 100644
--- a/networkx/algorithms/traversal/depth_first_search.py
+++ b/networkx/algorithms/traversal/depth_first_search.py
@@ -69,7 +69,7 @@ def dfs_edges(G, source=None):
             except StopIteration:
                 stack.pop()
 
-def dfs_tree(G, source=None):
+def dfs_tree(G, source):
     """Return oriented tree constructed from a depth-first-search from source.
 
     Parameters
diff --git a/networkx/classes/multidigraph.py b/networkx/classes/multidigraph.py
index 22bfed174..2b850483c 100644
--- a/networkx/classes/multidigraph.py
+++ b/networkx/classes/multidigraph.py
@@ -83,22 +83,22 @@ class MultiDiGraph(MultiGraph,DiGraph):
 
     Add one edge,
 
-    >>> G.add_edge(1, 2)
+    >>> key = G.add_edge(1, 2)
 
     a list of edges,
 
-    >>> G.add_edges_from([(1,2),(1,3)])
+    >>> keys = G.add_edges_from([(1,2),(1,3)])
 
     or a collection of edges,
 
-    >>> G.add_edges_from(H.edges())
+    >>> keys = G.add_edges_from(H.edges())
 
     If some edges connect nodes not yet in the graph, the nodes
     are added automatically.  If an edge already exists, an additional
     edge is created and stored using a key to identify the edge.
     By default the key is the lowest unused integer.
 
-    >>> G.add_edges_from([(4,5,dict(route=282)), (4,5,dict(route=37))])
+    >>> keys = G.add_edges_from([(4,5,dict(route=282)), (4,5,dict(route=37))])
     >>> G[4]
     {5: {0: {}, 1: {'route': 282}, 2: {'route': 37}}}
 
@@ -130,9 +130,9 @@ class MultiDiGraph(MultiGraph,DiGraph):
     Add edge attributes using add_edge(), add_edges_from(), subscript
     notation, or G.edge.
 
-    >>> G.add_edge(1, 2, weight=4.7 )
-    >>> G.add_edges_from([(3,4),(4,5)], color='red')
-    >>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
+    >>> key = G.add_edge(1, 2, weight=4.7 )
+    >>> keys = G.add_edges_from([(3,4),(4,5)], color='red')
+    >>> keys = G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
     >>> G[1][2][0]['weight'] = 4.7
     >>> G.edge[1][2][0]['weight'] = 4
 
@@ -222,7 +222,7 @@ class MultiDiGraph(MultiGraph,DiGraph):
     >>> G.add_nodes_from( (2,1) )
     >>> list(G.nodes())
     [2, 1]
-    >>> G.add_edges_from( ((2,2), (2,1), (2,1), (1,1)) )
+    >>> keys = G.add_edges_from( ((2,2), (2,1), (2,1), (1,1)) )
     >>> list(G.edges())
     [(2, 1), (2, 1), (2, 2), (1, 1)]
 
@@ -238,7 +238,8 @@ class MultiDiGraph(MultiGraph,DiGraph):
     >>> G.add_nodes_from( (2,1) )
     >>> list(G.nodes())
     [2, 1]
-    >>> G.add_edges_from( ((2,2), (2,1,2,{'weight':0.1}), (2,1,1,{'weight':0.2}), (1,1)) )
+    >>> elist = ((2,2), (2,1,2,{'weight':0.1}), (2,1,1,{'weight':0.2}), (1,1))
+    >>> keys = G.add_edges_from(elist)
     >>> list(G.edges(keys=True))
     [(2, 2, 0), (2, 1, 2), (2, 1, 1), (1, 1, 0)]
 
@@ -275,6 +276,10 @@ class MultiDiGraph(MultiGraph,DiGraph):
             Edge data (or labels or objects) can be assigned using
             keyword arguments.
 
+        Returns
+        -------
+        The edge key assigned to the edge.
+
         See Also
         --------
         add_edges_from : add a collection of edges
@@ -289,21 +294,27 @@ class MultiDiGraph(MultiGraph,DiGraph):
         multiedge weights.  Convert to Graph using edge attribute
         'weight' to enable weighted graph algorithms.
 
+        Default keys are generated using the method `new_edge_key()`.
+        This method can be overridden by subclassing the base class and
+        providing a custom `new_edge_key()` method.
+
         Examples
         --------
         The following all add the edge e=(1,2) to graph G:
 
         >>> G = nx.MultiDiGraph()
         >>> e = (1,2)
-        >>> G.add_edge(1, 2)           # explicit two-node form
+        >>> key = G.add_edge(1, 2)     # explicit two-node form
         >>> G.add_edge(*e)             # single edge as tuple of two nodes
+        1
         >>> G.add_edges_from( [(1,2)] ) # add edges from iterable container
+        [2]
 
         Associate data to edges using keywords:
 
-        >>> G.add_edge(1, 2, weight=3)
-        >>> G.add_edge(1, 2, key=0, weight=4)   # update data for key=0
-        >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
+        >>> key = G.add_edge(1, 2, weight=3)
+        >>> key = G.add_edge(1, 2, key=0, weight=4)  # update data for key=0
+        >>> key = G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
 
         For non-string associations, directly access the edge's attribute
         dictionary.
@@ -317,27 +328,22 @@ class MultiDiGraph(MultiGraph,DiGraph):
             self.succ[v] = self.adjlist_dict_factory()
             self.pred[v] = self.adjlist_dict_factory()
             self.node[v] = {}
+        if key is None:
+            key = self.new_edge_key(u, v)
         if v in self.succ[u]:
             keydict = self.adj[u][v]
-            if key is None:
-                # find a unique integer key
-                # other methods might be better here?
-                key = len(keydict)
-                while key in keydict:
-                    key += 1
             datadict = keydict.get(key, self.edge_key_dict_factory())
             datadict.update(attr)
             keydict[key] = datadict
         else:
             # selfloops work this way without special treatment
-            if key is None:
-                key = 0
             datadict = self.edge_attr_dict_factory()
             datadict.update(attr)
             keydict = self.edge_key_dict_factory()
             keydict[key] = datadict
             self.succ[u][v] = keydict
             self.pred[v][u] = keydict
+        return key
 
 
     def remove_edge(self, u, v, key=None):
@@ -372,14 +378,17 @@ class MultiDiGraph(MultiGraph,DiGraph):
         For multiple edges
 
         >>> G = nx.MultiDiGraph()
-        >>> G.add_edges_from([(1,2),(1,2),(1,2)])
+        >>> G.add_edges_from([(1,2),(1,2),(1,2)])  # key_list returned
+        [0, 1, 2]
         >>> G.remove_edge(1,2) # remove a single (arbitrary) edge
 
         For edges with keys
 
         >>> G = nx.MultiDiGraph()
         >>> G.add_edge(1,2,key='first')
+        'first'
         >>> G.add_edge(1,2,key='second')
+        'second'
         >>> G.remove_edge(1,2,key='second')
 
         """
@@ -437,7 +446,7 @@ class MultiDiGraph(MultiGraph,DiGraph):
         --------
         >>> G = nx.MultiDiGraph()
         >>> nx.add_path(G, [0, 1, 2])
-        >>> G.add_edge(2,3,weight=5)
+        >>> key = G.add_edge(2,3,weight=5)
         >>> [e for e in G.edges()]
         [(0, 1), (1, 2), (2, 3)]
         >>> list(G.edges(data=True)) # default data is {} (empty dict)
@@ -795,7 +804,7 @@ class MultiDiGraph(MultiGraph,DiGraph):
         If already directed, return a (deep) copy
 
         >>> G = nx.MultiDiGraph()
-        >>> G.add_edge(0, 1)
+        >>> key = G.add_edge(0, 1)
         >>> H = G.to_directed()
         >>> list(H.edges())
         [(0, 1)]
@@ -833,7 +842,7 @@ class MultiDiGraph(MultiGraph,DiGraph):
         See the Python copy module for more information on shallow
         and deep copies, http://docs.python.org/library/copy.html.
 
-        Warning: If you have subclassed MultiGraph to use dict-like objects 
+        Warning: If you have subclassed MultiGraph to use dict-like objects
         in the data structure, those changes do not transfer to the MultiDiGraph
         created by this method.
 
@@ -964,10 +973,10 @@ class MultiDiGraph(MultiGraph,DiGraph):
 
             >>> # Create a graph in which some edges are "good" and some "bad".
             >>> G = nx.MultiDiGraph()
-            >>> G.add_edge(0, 1, key=0, good=True)
-            >>> G.add_edge(0, 1, key=1, good=False)
-            >>> G.add_edge(1, 2, key=0, good=False)
-            >>> G.add_edge(1, 2, key=1, good=True)
+            >>> key = G.add_edge(0, 1, key=0, good=True)
+            >>> key = G.add_edge(0, 1, key=1, good=False)
+            >>> key = G.add_edge(1, 2, key=0, good=False)
+            >>> key = G.add_edge(1, 2, key=1, good=True)
             >>> # Keep only those edges that are marked as "good".
             >>> edges = G.edges(keys=True, data='good')
             >>> edges = ((u, v, k) for (u, v, k, good) in edges if good)
diff --git a/networkx/classes/multigraph.py b/networkx/classes/multigraph.py
index d6f925d0c..0b58059d7 100644
--- a/networkx/classes/multigraph.py
+++ b/networkx/classes/multigraph.py
@@ -82,22 +82,22 @@ class MultiGraph(Graph):
 
     Add one edge,
 
-    >>> G.add_edge(1, 2)
+    >>> key = G.add_edge(1, 2)
 
     a list of edges,
 
-    >>> G.add_edges_from([(1,2),(1,3)])
+    >>> keys = G.add_edges_from([(1,2),(1,3)])
 
     or a collection of edges,
 
-    >>> G.add_edges_from(list(H.edges()))
+    >>> keys = G.add_edges_from(list(H.edges()))
 
     If some edges connect nodes not yet in the graph, the nodes
     are added automatically.  If an edge already exists, an additional
     edge is created and stored using a key to identify the edge.
     By default the key is the lowest unused integer.
 
-    >>> G.add_edges_from([(4,5,dict(route=282)), (4,5,dict(route=37))])
+    >>> keys = G.add_edges_from([(4,5,dict(route=282)), (4,5,dict(route=37))])
     >>> G[4]
     {3: {0: {}}, 5: {0: {}, 1: {'route': 282}, 2: {'route': 37}}}
 
@@ -129,9 +129,9 @@ class MultiGraph(Graph):
     Add edge attributes using add_edge(), add_edges_from(), subscript
     notation, or G.edge.
 
-    >>> G.add_edge(1, 2, weight=4.7 )
-    >>> G.add_edges_from([(3,4),(4,5)], color='red')
-    >>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
+    >>> key = G.add_edge(1, 2, weight=4.7 )
+    >>> keys = G.add_edges_from([(3,4),(4,5)], color='red')
+    >>> keys = G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
     >>> G[1][2][0]['weight'] = 4.7
     >>> G.edge[1][2][0]['weight'] = 4
 
@@ -223,7 +223,7 @@ class MultiGraph(Graph):
     >>> G.add_nodes_from( (2,1) )
     >>> list(G.nodes())
     [2, 1]
-    >>> G.add_edges_from( ((2,2), (2,1), (2,1), (1,1)) )
+    >>> keys = G.add_edges_from( ((2,2), (2,1), (2,1), (1,1)) )
     >>> list(G.edges())
     [(2, 1), (2, 1), (2, 2), (1, 1)]
 
@@ -239,7 +239,8 @@ class MultiGraph(Graph):
     >>> G.add_nodes_from( (2,1) )
     >>> list(G.nodes())
     [2, 1]
-    >>> G.add_edges_from( ((2,2), (2,1,2,{'weight':0.1}), (2,1,1,{'weight':0.2}), (1,1)) )
+    >>> elist = ((2,2), (2,1,2,{'weight':0.1}), (2,1,1,{'weight':0.2}), (1,1))
+    >>> keys = G.add_edges_from(elist)
     >>> list(G.edges(keys=True))
     [(2, 2, 0), (2, 1, 2), (2, 1, 1), (1, 1, 0)]
 
@@ -253,6 +254,36 @@ class MultiGraph(Graph):
         self.edge_key_dict_factory = self.edge_key_dict_factory
         Graph.__init__(self, data, **attr)
 
+    def new_edge_key(self, u, v):
+        """Return an unused key for edges between nodes `u` and `v`.
+
+        The nodes `u` and `v` do not need to be already in the graph.
+
+        Notes
+        -----
+
+        In the standard MultiGraph class the new key is the number of existing
+        edges between `u` and `v` (increased if necessary to ensure unused).
+        The first edge will have key 0, then 1, etc. If an edge is removed
+        further new_edge_keys may not be in this order.
+
+        Parameters
+        ----------
+        u, v : nodes
+
+        Returns
+        -------
+        key : int
+        """
+        try:
+            keydict = self.adj[u][v]
+        except KeyError:
+            return 0
+        key = len(keydict)
+        while key in keydict:
+            key += 1
+        return key
+
     def add_edge(self, u, v, key=None, **attr):
         """Add an edge between u and v.
 
@@ -273,6 +304,10 @@ class MultiGraph(Graph):
             Edge data (or labels or objects) can be assigned using
             keyword arguments.
 
+        Returns
+        -------
+        The edge key assigned to the edge.
+
         See Also
         --------
         add_edges_from : add a collection of edges
@@ -287,6 +322,10 @@ class MultiGraph(Graph):
         multiedge weights.  Convert to Graph using edge attribute
         'weight' to enable weighted graph algorithms.
 
+        Default keys are generated using the method `new_edge_key()`.
+        This method can be overridden by subclassing the base class and
+        providing a custom `new_edge_key()` method.
+
         Examples
         --------
         The following all add the edge e=(1,2) to graph G:
@@ -310,27 +349,22 @@ class MultiGraph(Graph):
         if v not in self.adj:
             self.adj[v] = self.adjlist_dict_factory()
             self.node[v] = {}
+        if key is None:
+            key = self.new_edge_key(u, v)
         if v in self.adj[u]:
             keydict = self.adj[u][v]
-            if key is None:
-                # find a unique integer key
-                # other methods might be better here?
-                key = len(keydict)
-                while key in keydict:
-                    key += 1
             datadict = keydict.get(key, self.edge_attr_dict_factory())
             datadict.update(attr)
             keydict[key] = datadict
         else:
             # selfloops work this way without special treatment
-            if key is None:
-                key = 0
             datadict = self.edge_attr_dict_factory()
             datadict.update(attr)
             keydict = self.edge_key_dict_factory()
             keydict[key] = datadict
             self.adj[u][v] = keydict
             self.adj[v][u] = keydict
+        return key
 
     def add_edges_from(self, ebunch, **attr):
         """Add all the edges in ebunch.
@@ -349,6 +383,10 @@ class MultiGraph(Graph):
             Edge data (or labels or objects) can be assigned using
             keyword arguments.
 
+        Returns
+        -------
+        A list of edge keys assigned to the edges in `ebunch`.
+
         See Also
         --------
         add_edge : add a single edge
@@ -359,9 +397,13 @@ class MultiGraph(Graph):
         Adding the same edge twice has no effect but any edge data
         will be updated when each duplicate edge is added.
 
-        Edge attributes specified in an ebunch take precedence over 
+        Edge attributes specified in an ebunch take precedence over
         attributes specified via keyword arguments.
 
+        Default keys are generated using the method ``new_edge_key()``.
+        This method can be overridden by subclassing the base class and
+        providing a custom ``new_edge_key()`` method.
+
         Examples
         --------
         >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -374,6 +416,7 @@ class MultiGraph(Graph):
         >>> G.add_edges_from([(1,2),(2,3)], weight=3)
         >>> G.add_edges_from([(3,4),(1,4)], label='WN2898')
         """
+        keylist=[]
         # process ebunch
         for e in ebunch:
             ne = len(e)
@@ -392,15 +435,10 @@ class MultiGraph(Graph):
             ddd = {}
             ddd.update(attr)
             ddd.update(dd)
-            if key is None:
-                k = 0
-                if u in self and v in self[u]:
-                    while k in self[u][v]:
-                        k += 1
-            else:
-                k = key
-            self.add_edge(u, v, k)
-            self[u][v][k].update(ddd)
+            key = self.add_edge(u, v, key)
+            self[u][v][key].update(ddd)
+            keylist.append(key)
+        return keylist
 
     def remove_edge(self, u, v, key=None):
         """Remove an edge between u and v.
@@ -434,14 +472,17 @@ class MultiGraph(Graph):
         For multiple edges
 
         >>> G = nx.MultiGraph()   # or MultiDiGraph, etc
-        >>> G.add_edges_from([(1,2),(1,2),(1,2)])
+        >>> G.add_edges_from([(1,2),(1,2),(1,2)])  # key_list returned
+        [0, 1, 2]
         >>> G.remove_edge(1,2) # remove a single (arbitrary) edge
 
         For edges with keys
 
         >>> G = nx.MultiGraph()   # or MultiDiGraph, etc
         >>> G.add_edge(1,2,key='first')
+        'first'
         >>> G.add_edge(1,2,key='second')
+        'second'
         >>> G.remove_edge(1,2,key='second')
 
         """
@@ -496,7 +537,7 @@ class MultiGraph(Graph):
         Removing multiple copies of edges
 
         >>> G = nx.MultiGraph()
-        >>> G.add_edges_from([(1,2),(1,2),(1,2)])
+        >>> keys = G.add_edges_from([(1,2),(1,2),(1,2)])
         >>> G.remove_edges_from([(1,2),(1,2)])
         >>> list(G.edges())
         [(1, 2)]
@@ -540,6 +581,7 @@ class MultiGraph(Graph):
         >>> G.has_edge(*e)  #  e is a 2-tuple (u,v)
         True
         >>> G.add_edge(0,1,key='a')
+        'a'
         >>> G.has_edge(0,1,key='a')  # specify key
         True
         >>> e=(0,1,'a')
@@ -600,7 +642,7 @@ class MultiGraph(Graph):
         --------
         >>> G = nx.MultiGraph()   # or MultiDiGraph
         >>> nx.add_path(G, [0, 1, 2])
-        >>> G.add_edge(2,3,weight=5)
+        >>> key = G.add_edge(2,3,weight=5)
         >>> [e for e in G.edges()]
         [(0, 1), (1, 2), (2, 3)]
         >>> list(G.edges(data=True)) # default data is {} (empty dict)
@@ -672,7 +714,7 @@ class MultiGraph(Graph):
         It is faster to use G[u][v][key].
 
         >>> G = nx.MultiGraph() # or MultiDiGraph
-        >>> G.add_edge(0,1,key='a',weight=7)
+        >>> key = G.add_edge(0,1,key='a',weight=7)
         >>> G[0][1]['a']  # key='a'
         {'weight': 7}
 
@@ -868,7 +910,9 @@ class MultiGraph(Graph):
         --------
         >>> G = nx.MultiGraph()   # or MultiDiGraph
         >>> G.add_edge(1,1)
+        0
         >>> G.add_edge(1,2)
+        0
         >>> list(G.selfloop_edges())
         [(1, 1)]
         >>> list(G.selfloop_edges(data=True))
@@ -1048,10 +1092,10 @@ class MultiGraph(Graph):
 
             >>> # Create a graph in which some edges are "good" and some "bad".
             >>> G = nx.MultiGraph()
-            >>> G.add_edge(0, 1, key=0, good=True)
-            >>> G.add_edge(0, 1, key=1, good=False)
-            >>> G.add_edge(1, 2, key=0, good=False)
-            >>> G.add_edge(1, 2, key=1, good=True)
+            >>> key = G.add_edge(0, 1, key=0, good=True)
+            >>> key = G.add_edge(0, 1, key=1, good=False)
+            >>> key = G.add_edge(1, 2, key=0, good=False)
+            >>> key = G.add_edge(1, 2, key=1, good=True)
             >>> # Keep only those edges that are marked as "good".
             >>> edges = G.edges(keys=True, data='good')
             >>> edges = ((u, v, k) for (u, v, k, good) in edges if good)
diff --git a/networkx/convert_matrix.py b/networkx/convert_matrix.py
index 3aab7db79..c89704c79 100644
--- a/networkx/convert_matrix.py
+++ b/networkx/convert_matrix.py
@@ -105,9 +105,13 @@ def to_pandas_dataframe(G, nodelist=None, dtype=None, order=None,
     --------
     >>> G = nx.MultiDiGraph()
     >>> G.add_edge(0,1,weight=2)
+    0
     >>> G.add_edge(1,0)
+    0
     >>> G.add_edge(2,2,weight=3)
+    0
     >>> G.add_edge(2,2)
+    1
     >>> nx.to_pandas_dataframe(G, nodelist=[0,1,2], dtype=int)
        0  1  2
     0  0  2  0
@@ -304,9 +308,13 @@ def to_numpy_matrix(G, nodelist=None, dtype=None, order=None,
     --------
     >>> G = nx.MultiDiGraph()
     >>> G.add_edge(0,1,weight=2)
+    0
     >>> G.add_edge(1,0)
+    0
     >>> G.add_edge(2,2,weight=3)
+    0
     >>> G.add_edge(2,2)
+    1
     >>> nx.to_numpy_matrix(G, nodelist=[0,1,2])
     matrix([[ 0.,  2.,  0.],
             [ 1.,  0.,  0.],
@@ -680,9 +688,13 @@ def to_scipy_sparse_matrix(G, nodelist=None, dtype=None,
     --------
     >>> G = nx.MultiDiGraph()
     >>> G.add_edge(0,1,weight=2)
+    0
     >>> G.add_edge(1,0)
+    0
     >>> G.add_edge(2,2,weight=3)
+    0
     >>> G.add_edge(2,2)
+    1
     >>> S = nx.to_scipy_sparse_matrix(G, nodelist=[0,1,2])
     >>> print(S.todense())
     [[0 2 0]
diff --git a/networkx/drawing/layout.py b/networkx/drawing/layout.py
index 8dbb77262..872787d04 100644
--- a/networkx/drawing/layout.py
+++ b/networkx/drawing/layout.py
@@ -139,7 +139,7 @@ def circular_layout(G, scale=1, center=None, dim=2):
     if len(G) == 0:
         pos = {}
     elif len(G) == 1:
-        pos = {nx.utils.arbitrary_element(G): center}
+        pos = {G.nodes()[0]: center}
     else:
         # Discard the extra angle since it matches 0 radians.
         theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi
@@ -287,7 +287,7 @@ def fruchterman_reingold_layout(G, k=None,
 
     if pos is not None:
         # Determine size of existing domain to adjust initial positions
-        dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)
+        dom_size = max(coord for coord in pos_tup for pos_tup in pos.values())
         shape = (len(G), dim)
         pos_arr = np.random.random(shape) * dom_size + center
         for i, n in enumerate(G):
diff --git a/networkx/exception.py b/networkx/exception.py
index 01aec88b1..7d0880248 100644
--- a/networkx/exception.py
+++ b/networkx/exception.py
@@ -55,29 +55,3 @@ class NetworkXNotImplemented(NetworkXException):
 
 class NodeNotFound(NetworkXException):
     """Exception raised if requested node is not present in the graph"""
-
-
-class ExceededMaxIterations(NetworkXException):
-    """Raised if a loop iterates too many times without breaking.
-
-    This may occur, for example, in an algorithm that computes
-    progressively better approximations to a value but exceeds an
-    iteration bound specified by the user.
-
-    """
-
-
-class PowerIterationFailedConvergence(ExceededMaxIterations):
-    """Raised when the power iteration method fails to converge within a
-    specified iteration limit.
-
-    `num_iterations` is the number of iterations that have been
-    completed when this exception was raised.
-
-    """
-
-    def __init__(self, num_iterations, *args, **kw):
-        msg = 'power iteration failed to converge within {} iterations'
-        msg = msg.format(num_iterations)
-        superinit = super(PowerIterationFailedConvergence, self).__init__
-        superinit(self, msg, *args, **kw)


Test patch:
diff --git a/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py b/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py
index babe0039c..465415f32 100644
--- a/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py
+++ b/networkx/algorithms/centrality/tests/test_eigenvector_centrality.py
@@ -56,7 +56,7 @@ class TestEigenvectorCentrality(object):
 
 
 
-    @raises(nx.PowerIterationFailedConvergence)
+    @raises(nx.NetworkXError)
     def test_maxiter(self):
         G=nx.path_graph(3)
         b=nx.eigenvector_centrality(G,max_iter=0)
diff --git a/networkx/algorithms/centrality/tests/test_katz_centrality.py b/networkx/algorithms/centrality/tests/test_katz_centrality.py
index 8886711e3..69b015f12 100644
--- a/networkx/algorithms/centrality/tests/test_katz_centrality.py
+++ b/networkx/algorithms/centrality/tests/test_katz_centrality.py
@@ -30,7 +30,7 @@ class TestKatzCentrality(object):
         for n in sorted(G):
             assert_almost_equal(b[n], b_answer[n], places=4)
 
-    @raises(nx.PowerIterationFailedConvergence)
+    @raises(nx.NetworkXError)
     def test_maxiter(self):
         alpha = 0.1
         G = nx.path_graph(3)
diff --git a/networkx/algorithms/link_analysis/tests/test_hits.py b/networkx/algorithms/link_analysis/tests/test_hits.py
index b8849bc7a..7092d1dfd 100644
--- a/networkx/algorithms/link_analysis/tests/test_hits.py
+++ b/networkx/algorithms/link_analysis/tests/test_hits.py
@@ -91,9 +91,3 @@ class TestHITS:
             raise SkipTest('scipy not available.')
         G=networkx.Graph()
         assert_equal(networkx.hits_scipy(G),({},{}))
-
-
-    @raises(networkx.PowerIterationFailedConvergence)
-    def test_hits_not_convergent(self):
-        G = self.G
-        networkx.hits(G, max_iter=0)
diff --git a/networkx/algorithms/link_analysis/tests/test_pagerank.py b/networkx/algorithms/link_analysis/tests/test_pagerank.py
index a64899d5f..d27ea2454 100644
--- a/networkx/algorithms/link_analysis/tests/test_pagerank.py
+++ b/networkx/algorithms/link_analysis/tests/test_pagerank.py
@@ -52,9 +52,8 @@ class TestPageRank(object):
         for n in G:
             assert_almost_equal(p[n], G.pagerank[n], places=4)
 
-    @raises(networkx.PowerIterationFailedConvergence)
-    def test_pagerank_max_iter(self):
-        networkx.pagerank(self.G, max_iter=0)
+        assert_raises(networkx.NetworkXError, networkx.pagerank, G,
+                      max_iter=0)
 
     def test_numpy_pagerank(self):
         G = self.G
@@ -81,28 +80,14 @@ class TestPageRank(object):
     def test_personalization(self):
         G = networkx.complete_graph(4)
         personalize = {0: 1, 1: 1, 2: 4, 3: 4}
-        answer = {0: 0.23246732615667579, 1: 0.23246732615667579, 2: 0.267532673843324, 3: 0.2675326738433241}
-        p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
+        answer = {0: 0.1, 1: 0.1, 2: 0.4, 3: 0.4}
+        p = networkx.pagerank(G, alpha=0.0, personalization=personalize)
         for n in G:
             assert_almost_equal(p[n], answer[n], places=4)
         personalize.pop(0)
         assert_raises(networkx.NetworkXError, networkx.pagerank, G,
                       personalization=personalize)
 
-    def test_zero_personalization_vector(self):
-        G = networkx.complete_graph(4)
-        personalize = {0: 0, 1: 0, 2: 0, 3: 0}
-        assert_raises(ZeroDivisionError, networkx.pagerank, G,
-                  personalization=personalize)
-
-    def test_one_nonzero_personalization_value(self):
-        G = networkx.complete_graph(4)
-        personalize = {0: 0, 1: 0, 2: 0, 3: 1}
-        answer = {0: 0.22077931820379187, 1: 0.22077931820379187, 2: 0.22077931820379187, 3: 0.3376620453886241}
-        p = networkx.pagerank(G, alpha=0.85, personalization=personalize)
-        for n in G:
-            assert_almost_equal(p[n], answer[n], places=4)
-
     def test_dangling_matrix(self):
         """
         Tests that the google_matrix doesn't change except for the dangling
@@ -162,9 +147,8 @@ class TestPageRankScipy(TestPageRank):
         p = networkx.pagerank_scipy(G, alpha=0.9, tol=1.e-08,
                                     personalization=personalize)
 
-    @raises(networkx.PowerIterationFailedConvergence)
-    def test_scipy_pagerank_max_iter(self):
-        networkx.pagerank_scipy(self.G, max_iter=0)
+        assert_raises(networkx.NetworkXError, networkx.pagerank_scipy, G,
+                      max_iter=0)
 
     def test_dangling_scipy_pagerank(self):
         pr = networkx.pagerank_scipy(self.G, dangling=self.dangling_edges)
diff --git a/networkx/algorithms/traversal/tests/test_dfs.py b/networkx/algorithms/traversal/tests/test_dfs.py
index 3d0d13e4d..9fad98584 100644
--- a/networkx/algorithms/traversal/tests/test_dfs.py
+++ b/networkx/algorithms/traversal/tests/test_dfs.py
@@ -36,20 +36,9 @@ class TestDFS:
         assert_equal(nx.dfs_predecessors(self.D), {1: 0, 3: 2})
 
     def test_dfs_tree(self):
-        exp_nodes = sorted(self.G.nodes())
-        exp_edges = [(0, 1), (1, 2), (2, 4), (4, 3)]
-        # Search from first node
         T=nx.dfs_tree(self.G,source=0)
-        assert_equal(sorted(T.nodes()), exp_nodes)
-        assert_equal(sorted(T.edges()), exp_edges)
-        # Check source=None
-        T = nx.dfs_tree(self.G, source=None)
-        assert_equal(sorted(T.nodes()), exp_nodes)
-        assert_equal(sorted(T.edges()), exp_edges)
-        # Check source=None is the default
-        T = nx.dfs_tree(self.G)
-        assert_equal(sorted(T.nodes()), exp_nodes)
-        assert_equal(sorted(T.edges()), exp_edges)
+        assert_equal(sorted(T.nodes()),sorted(self.G.nodes()))
+        assert_equal(sorted(T.edges()),[(0, 1), (1, 2), (2, 4), (4, 3)])
 
     def test_dfs_edges(self):
         edges=nx.dfs_edges(self.G,source=0)
diff --git a/networkx/drawing/tests/test_layout.py b/networkx/drawing/tests/test_layout.py
index 12b47be70..5763eca5e 100644
--- a/networkx/drawing/tests/test_layout.py
+++ b/networkx/drawing/tests/test_layout.py
@@ -1,7 +1,7 @@
 """Unit tests for layout functions."""
 import sys
 from nose import SkipTest
-from nose.tools import assert_equal, assert_false, assert_raises
+from nose.tools import assert_equal
 import networkx as nx
 
 
@@ -16,10 +16,10 @@ class TestLayout(object):
             raise SkipTest('numpy not available.')
 
     def setUp(self):
-        self.Gi = nx.grid_2d_graph(5, 5)
+        self.Gi = nx.grid_2d_graph(5,5)
         self.Gs = nx.Graph()
         nx.add_path(self.Gs, 'abcdef')
-        self.bigG = nx.grid_2d_graph(25, 25) #bigger than 500 nodes for sparse
+        self.bigG = nx.grid_2d_graph(25,25) #bigger than 500 nodes for sparse
 
     def test_smoke_int(self):
         G = self.Gi
@@ -27,7 +27,6 @@ class TestLayout(object):
         vpos = nx.circular_layout(G)
         vpos = nx.spring_layout(G)
         vpos = nx.fruchterman_reingold_layout(G)
-        vpos = nx.fruchterman_reingold_layout(self.bigG)
         vpos = nx.spectral_layout(G)
         vpos = nx.spectral_layout(self.bigG)
         vpos = nx.shell_layout(G)
@@ -44,9 +43,8 @@ class TestLayout(object):
     def test_adjacency_interface_numpy(self):
         A = nx.to_numpy_matrix(self.Gs)
         pos = nx.drawing.layout._fruchterman_reingold(A)
-        assert_equal(pos.shape, (6, 2))
         pos = nx.drawing.layout._fruchterman_reingold(A, dim=3)
-        assert_equal(pos.shape, (6, 3))
+        assert_equal(pos.shape, (6,3))
 
     def test_adjacency_interface_scipy(self):
         try:
@@ -55,70 +53,14 @@ class TestLayout(object):
             raise SkipTest('scipy not available.')
         A = nx.to_scipy_sparse_matrix(self.Gs, dtype='d')
         pos = nx.drawing.layout._sparse_fruchterman_reingold(A)
-        assert_equal(pos.shape, (6, 2))
         pos = nx.drawing.layout._sparse_spectral(A)
-        assert_equal(pos.shape, (6, 2))
         pos = nx.drawing.layout._sparse_fruchterman_reingold(A, dim=3)
-        assert_equal(pos.shape, (6, 3))
+        assert_equal(pos.shape, (6,3))
 
     def test_single_nodes(self):
         G = nx.path_graph(1)
         vpos = nx.shell_layout(G)
-        assert_false(vpos[0].any())
+        assert(vpos[0].any() == False)
         G = nx.path_graph(3)
-        vpos = nx.shell_layout(G, [[0], [1, 2]])
-        assert_false(vpos[0].any())
-
-    def test_smoke_initial_pos_fruchterman_reingold(self):
-        pos = nx.circular_layout(self.Gi)
-        npos = nx.fruchterman_reingold_layout(self.Gi, pos=pos)
-
-    def test_fixed_node_fruchterman_reingold(self):
-        # Dense version (numpy based)
-        pos = nx.circular_layout(self.Gi)
-        npos = nx.fruchterman_reingold_layout(self.Gi, pos=pos, fixed=[(0, 0)])
-        assert_equal(tuple(pos[(0, 0)]), tuple(npos[(0, 0)]))
-        # Sparse version (scipy based)
-        pos = nx.circular_layout(self.bigG)
-        npos = nx.fruchterman_reingold_layout(self.bigG, pos=pos, fixed=[(0, 0)])
-        assert_equal(tuple(pos[(0, 0)]), tuple(npos[(0, 0)]))
-
-    def test_center_parameter(self):
-        G =  nx.path_graph(1)
-        vpos = nx.random_layout(G, center=(1, 1))
-        vpos = nx.circular_layout(G, center=(1, 1))
-        assert_equal(tuple(vpos[0]), (1, 1))
-        vpos = nx.spring_layout(G, center=(1, 1))
-        assert_equal(tuple(vpos[0]), (1, 1))
-        vpos = nx.fruchterman_reingold_layout(G, center=(1, 1))
-        assert_equal(tuple(vpos[0]), (1, 1))
-        vpos = nx.spectral_layout(G, center=(1, 1))
-        assert_equal(tuple(vpos[0]), (1, 1))
-        vpos = nx.shell_layout(G, center=(1, 1))
-        assert_equal(tuple(vpos[0]), (1, 1))
-
-    def test_center_wrong_dimensions(self):
-        G =  nx.path_graph(1)
-        assert_raises(ValueError, nx.random_layout, G, center=(1, 1, 1))
-        assert_raises(ValueError, nx.circular_layout, G, center=(1, 1, 1))
-        assert_raises(ValueError, nx.spring_layout, G, center=(1, 1, 1))
-        assert_raises(ValueError, nx.fruchterman_reingold_layout, G, center=(1, 1, 1))
-        assert_raises(ValueError, nx.fruchterman_reingold_layout, G, dim=3, center=(1, 1))
-        assert_raises(ValueError, nx.spectral_layout, G, center=(1, 1, 1))
-        assert_raises(ValueError, nx.spectral_layout, G, dim=3, center=(1, 1))
-        assert_raises(ValueError, nx.shell_layout, G, center=(1, 1, 1))
-
-    def test_empty_graph(self):
-        G =  nx.empty_graph()
-        vpos = nx.random_layout(G, center=(1, 1))
-        assert_equal(vpos, {})
-        vpos = nx.circular_layout(G, center=(1, 1))
-        assert_equal(vpos, {})
-        vpos = nx.spring_layout(G, center=(1, 1))
-        assert_equal(vpos, {})
-        vpos = nx.fruchterman_reingold_layout(G, center=(1, 1))
-        assert_equal(vpos, {})
-        vpos = nx.spectral_layout(G, center=(1, 1))
-        assert_equal(vpos, {})
-        vpos = nx.shell_layout(G, center=(1, 1))
-        assert_equal(vpos, {})
+        vpos = nx.shell_layout(G, [[0], [1,2]])
+        assert(vpos[0].any() == False)