Merge branch 'master' into masterfix-d-separation-conflicts

14 files changed, 212 insertions, 170 deletions

diff --git a/CONTRIBUTORS.rst b/CONTRIBUTORS.rst
index 58b5ee3b..ed4f347c 100644
--- a/CONTRIBUTORS.rst
+++ b/CONTRIBUTORS.rst
@@ -171,6 +171,7 @@ is partially historical, and now, mostly arbitrary.
 - Alessandro Luongo
 - Huston Hedinger
 - Oleguer Sagarra
+- Gaetano Pietro Paolo Carpinato, Github `<https://github.com/Carghaez>`_, LinkedIn `<https://linkedin.com/in/gaetanocarpinato/>`_
 - Arun Nampally, GitHub `<https://github.com/arunwise>`_, LinkedIn `<https://www.linkedin.com/in/arun-nampally-b57845b7/>`_
 
 Support
diff --git a/doc/reference/utils.rst b/doc/reference/utils.rst
index 9ca2feaa..4d79ae78 100644
--- a/doc/reference/utils.rst
+++ b/doc/reference/utils.rst
@@ -65,11 +65,3 @@ Cuthill-Mckee Ordering
 
    cuthill_mckee_ordering
    reverse_cuthill_mckee_ordering
-
-Context Managers
-----------------
-.. automodule:: networkx.utils.contextmanagers
-.. autosummary::
-   :toctree: generated/
-
-   reversed
diff --git a/networkx/algorithms/centrality/voterank_alg.py b/networkx/algorithms/centrality/voterank_alg.py
index 0f5b8f75..4e262180 100644
--- a/networkx/algorithms/centrality/voterank_alg.py
+++ b/networkx/algorithms/centrality/voterank_alg.py
@@ -73,4 +73,5 @@ def voterank(G, number_of_nodes=None, max_iter=10000):
         # step 4 - update voterank properties
         for nbr in G.neighbors(n):
             G.nodes[nbr]['voterank'][1] -= 1 / avgDegree
+            G.nodes[nbr]['voterank'][1] = max(G.nodes[nbr]['voterank'][1], 0)
     return voterank
diff --git a/networkx/algorithms/communicability_alg.py b/networkx/algorithms/communicability_alg.py
index e066e373..d8c3b811 100644
--- a/networkx/algorithms/communicability_alg.py
+++ b/networkx/algorithms/communicability_alg.py
@@ -15,7 +15,7 @@ def communicability(G):
     r"""Returns communicability between all pairs of nodes in G.
 
     The communicability between pairs of nodes in G is the sum of
-    closed walks of different lengths starting at node u and ending at node v.
+    walks of different lengths starting at node u and ending at node v.
 
     Parameters
     ----------
@@ -96,7 +96,7 @@ def communicability_exp(G):
     r"""Returns communicability between all pairs of nodes in G.
 
     Communicability between pair of node (u,v) of node in G is the sum of
-    closed walks of different lengths starting at node u and ending at node v.
+    walks of different lengths starting at node u and ending at node v.
 
     Parameters
     ----------
diff --git a/networkx/algorithms/community/kernighan_lin.py b/networkx/algorithms/community/kernighan_lin.py
index ad3da951..7534ed0a 100644
--- a/networkx/algorithms/community/kernighan_lin.py
+++ b/networkx/algorithms/community/kernighan_lin.py
@@ -1,81 +1,40 @@
 """Functions for computing the Kernighan–Lin bipartition algorithm."""
 
-from collections import defaultdict
-from itertools import accumulate, islice
-from operator import itemgetter
-
 import networkx as nx
-from networkx.utils import not_implemented_for, py_random_state
+from itertools import count
+from networkx.utils import not_implemented_for, py_random_state, BinaryHeap
 from networkx.algorithms.community.community_utils import is_partition
 
 __all__ = ['kernighan_lin_bisection']
 
 
-def _compute_delta(G, A, B, weight):
-    # helper to compute initial swap deltas for a pass
-    delta = defaultdict(float)
-    for u, v, d in G.edges(data=True):
-        w = d.get(weight, 1)
-        if u in A:
-            if v in A:
-                delta[u] -= w
-                delta[v] -= w
-            elif v in B:
-                delta[u] += w
-                delta[v] += w
-        elif u in B:
-            if v in A:
-                delta[u] += w
-                delta[v] += w
-            elif v in B:
-                delta[u] -= w
-                delta[v] -= w
-    return delta
-
-
-def _update_delta(delta, G, A, B, u, v, weight):
-    # helper to update swap deltas during single pass
-    for _, nbr, d in G.edges(u, data=True):
-        w = d.get(weight, 1)
-        if nbr in A:
-            delta[nbr] += 2 * w
-        if nbr in B:
-            delta[nbr] -= 2 * w
-    for _, nbr, d in G.edges(v, data=True):
-        w = d.get(weight, 1)
-        if nbr in A:
-            delta[nbr] -= 2 * w
-        if nbr in B:
-            delta[nbr] += 2 * w
-    return delta
-
-
-def _kernighan_lin_pass(G, A, B, weight):
-    # do a single iteration of Kernighan–Lin algorithm
-    # returns list of  (g_i,u_i,v_i) for i node pairs u_i,v_i
-    multigraph = G.is_multigraph()
-    delta = _compute_delta(G, A, B, weight)
-    swapped = set()
-    gains = []
-    while len(swapped) < len(G):
-        gain = []
-        for u in A - swapped:
-            for v in B - swapped:
-                try:
-                    if multigraph:
-                        w = sum(d.get(weight, 1) for d in G[u][v].values())
-                    else:
-                        w = G[u][v].get(weight, 1)
-                except KeyError:
-                    w = 0
-                gain.append((delta[u] + delta[v] - 2 * w, u, v))
-        if len(gain) == 0:
-            break
-        maxg, u, v = max(gain, key=itemgetter(0))
-        swapped |= {u, v}
-        gains.append((maxg, u, v))
-        delta = _update_delta(delta, G, A - swapped, B - swapped, u, v, weight)
-    return gains
+def _kernighan_lin_sweep(edges, side):
+    """
+    This is a modified form of Kernighan-Lin, which moves single nodes at a
+    time, alternating between sides to keep the bisection balanced.  We keep
+    two min-heaps of swap costs to make optimal-next-move selection fast.
+    """
+    costs0, costs1 = costs = BinaryHeap(), BinaryHeap()
+    for u, side_u, edges_u in zip(count(), side, edges):
+        cost_u = sum(w if side[v] else -w for v, w in edges_u)
+        costs[side_u].insert(u, cost_u if side_u else -cost_u)
+
+    def _update_costs(costs_x, x):
+        for y, w in edges[x]:
+            costs_y = costs[side[y]]
+            cost_y = costs_y.get(y)
+            if cost_y is not None:
+                cost_y += 2 * (-w if costs_x is costs_y else w)
+                costs_y.insert(y, cost_y, True)
+
+    i = totcost = 0
+    while costs0 and costs1:
+        u, cost_u = costs0.pop()
+        _update_costs(costs0, u)
+        v, cost_v = costs1.pop()
+        _update_costs(costs1, v)
+        totcost += cost_u + cost_v
+        yield totcost, i, (u, v)
 
 
 @py_random_state(4)
@@ -85,8 +44,11 @@ def kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight',
     """Partition a graph into two blocks using the Kernighan–Lin
     algorithm.
 
-    This algorithm paritions a network into two sets by iteratively
-    swapping pairs of nodes to reduce the edge cut between the two sets.
+    This algorithm partitions a network into two sets by iteratively
+    swapping pairs of nodes to reduce the edge cut between the two sets.  The
+    pairs are chosen according to a modified form of Kernighan-Lin, which
+    moves node individually, alternating between sides to keep the bisection
+    balanced.
 
     Parameters
     ----------
@@ -127,36 +89,41 @@ def kernighan_lin_bisection(G, partition=None, max_iter=10, weight='weight',
        Oxford University Press 2011.
 
     """
-    # If no partition is provided, split the nodes randomly into a
-    # balanced partition.
+    n = len(G)
+    labels = list(G)
+    seed.shuffle(labels)
+    index = {v: i for i, v in enumerate(labels)}
+
     if partition is None:
-        nodes = list(G)
-        seed.shuffle(nodes)
-        h = len(nodes) // 2
-        partition = (nodes[:h], nodes[h:])
-    # Make a copy of the partition as a pair of sets.
-    try:
-        A, B = set(partition[0]), set(partition[1])
-    except:
-        raise ValueError('partition must be two sets')
-    if not is_partition(G, (A, B)):
-        raise nx.NetworkXError('partition invalid')
+        side = [0] * (n // 2) + [1] * ((n + 1) // 2)
+    else:
+        try:
+            A, B = partition
+        except (TypeError, ValueError):
+            raise nx.NetworkXError('partition must be two sets')
+        if not is_partition(G, (A, B)):
+            raise nx.NetworkXError('partition invalid')
+        side = [0] * n
+        for a in A:
+            side[a] = 1
+
+    if G.is_multigraph():
+        edges = [[(index[u], sum(e.get(weight, 1) for e in d.values()))
+                  for u, d in G[v].items()] for v in labels]
+    else:
+        edges = [[(index[u], e.get(weight, 1)) for u, e in G[v].items()]
+                 for v in labels]
+
     for i in range(max_iter):
-        # `gains` is a list of triples of the form (g, u, v) for each
-        # node pair (u, v), where `g` is the gain of that node pair.
-        gains = _kernighan_lin_pass(G, A, B, weight)
-        csum = list(accumulate(g for g, u, v in gains))
-        max_cgain = max(csum)
-        if max_cgain <= 0:
+        costs = list(_kernighan_lin_sweep(edges, side))
+        min_cost, min_i, _ = min(costs)
+        if min_cost >= 0:
             break
-        # Get the node pairs up to the index of the maximum cumulative
-        # gain, and collect each `u` into `anodes` and each `v` into
-        # `bnodes`, for each pair `(u, v)`.
-        index = csum.index(max_cgain)
-        nodesets = islice(zip(*gains[:index + 1]), 1, 3)
-        anodes, bnodes = (set(s) for s in nodesets)
-        A |= bnodes
-        A -= anodes
-        B |= anodes
-        B -= bnodes
+
+        for _, _, (u, v) in costs[:min_i + 1]:
+            side[u] = 1
+            side[v] = 0
+
+    A = set(u for u, s in zip(labels, side) if s == 0)
+    B = set(u for u, s in zip(labels, side) if s == 1)
     return A, B
diff --git a/networkx/algorithms/community/tests/test_kernighan_lin.py b/networkx/algorithms/community/tests/test_kernighan_lin.py
index 8b41ff91..3038fa58 100644
--- a/networkx/algorithms/community/tests/test_kernighan_lin.py
+++ b/networkx/algorithms/community/tests/test_kernighan_lin.py
@@ -6,7 +6,7 @@ import pytest
 
 import networkx as nx
 from networkx.algorithms.community import kernighan_lin_bisection
-
+from itertools import permutations
 
 def assert_partition_equal(x, y):
     assert set(map(frozenset, x)) == set(map(frozenset, y))
@@ -18,6 +18,13 @@ def test_partition():
     assert_partition_equal(C, [{0, 1, 2}, {3, 4, 5}])
 
 
+def test_partition_argument():
+    G = nx.barbell_graph(3, 0)
+    partition = [{0, 1, 2}, {3, 4, 5}]
+    C = kernighan_lin_bisection(G, partition)
+    assert_partition_equal(C, partition)
+
+
 def test_seed_argument():
     G = nx.barbell_graph(3, 0)
     C = kernighan_lin_bisection(G, seed=1)
@@ -43,5 +50,9 @@ def test_multigraph():
     M = nx.MultiGraph(G.edges())
     M.add_edges_from(G.edges())
     M.remove_edge(1, 2)
-    A, B = kernighan_lin_bisection(M)
-    assert_partition_equal([A, B], [{0, 1}, {2, 3}])
+    for labels in permutations(range(4)):
+        mapping = dict(zip(M, labels))
+        A, B = kernighan_lin_bisection(nx.relabel_nodes(M, mapping), seed=0)
+        assert_partition_equal([A, B],
+                               [{mapping[0], mapping[1]},
+                                {mapping[2], mapping[3]}])
diff --git a/networkx/algorithms/components/strongly_connected.py b/networkx/algorithms/components/strongly_connected.py
index 193bb312..a4347704 100644
--- a/networkx/algorithms/components/strongly_connected.py
+++ b/networkx/algorithms/components/strongly_connected.py
@@ -149,8 +149,7 @@ def kosaraju_strongly_connected_components(G, source=None):
     Uses Kosaraju's algorithm.
 
     """
-    with nx.utils.reversed(G):
-        post = list(nx.dfs_postorder_nodes(G, source=source))
+    post = list(nx.dfs_postorder_nodes(G.reverse(copy=False), source=source))
 
     seen = set()
     while post:
diff --git a/networkx/algorithms/shortest_paths/generic.py b/networkx/algorithms/shortest_paths/generic.py
index a34447b5..2edcb4b5 100644
--- a/networkx/algorithms/shortest_paths/generic.py
+++ b/networkx/algorithms/shortest_paths/generic.py
@@ -131,18 +131,19 @@ def shortest_path(G, source=None, target=None, weight=None, method='dijkstra'):
                 paths = dict(nx.all_pairs_bellman_ford_path(G, weight=weight))
         else:
             # Find paths from all nodes co-accessible to the target.
-            with nx.utils.reversed(G):
-                if method == 'unweighted':
-                    paths = nx.single_source_shortest_path(G, target)
-                elif method == 'dijkstra':
-                    paths = nx.single_source_dijkstra_path(G, target,
+            if G.is_directed():
+                G = G.reverse(copy=False)
+            if method == 'unweighted':
+                paths = nx.single_source_shortest_path(G, target)
+            elif method == 'dijkstra':
+                paths = nx.single_source_dijkstra_path(G, target,
+                                                       weight=weight)
+            else:  # method == 'bellman-ford':
+                paths = nx.single_source_bellman_ford_path(G, target,
                                                            weight=weight)
-                else:  # method == 'bellman-ford':
-                    paths = nx.single_source_bellman_ford_path(G, target,
-                                                               weight=weight)
-                # Now flip the paths so they go from a source to the target.
-                for target in paths:
-                    paths[target] = list(reversed(paths[target]))
+            # Now flip the paths so they go from a source to the target.
+            for target in paths:
+                paths[target] = list(reversed(paths[target]))
     else:
         if target is None:
             # Find paths to all nodes accessible from the source.
@@ -273,18 +274,17 @@ def shortest_path_length(G,
                 paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight)
         else:
             # Find paths from all nodes co-accessible to the target.
-            with nx.utils.reversed(G):
-                if method == 'unweighted':
-                    # We need to exhaust the iterator as Graph needs
-                    # to be reversed.
-                    path_length = nx.single_source_shortest_path_length
-                    paths = path_length(G, target)
-                elif method == 'dijkstra':
-                    path_length = nx.single_source_dijkstra_path_length
-                    paths = path_length(G, target, weight=weight)
-                else:  # method == 'bellman-ford':
-                    path_length = nx.single_source_bellman_ford_path_length
-                    paths = path_length(G, target, weight=weight)
+            if G.is_directed():
+                G = G.reverse(copy=False)
+            if method == 'unweighted':
+                path_length = nx.single_source_shortest_path_length
+                paths = path_length(G, target)
+            elif method == 'dijkstra':
+                path_length = nx.single_source_dijkstra_path_length
+                paths = path_length(G, target, weight=weight)
+            else:  # method == 'bellman-ford':
+                path_length = nx.single_source_bellman_ford_path_length
+                paths = path_length(G, target, weight=weight)
     else:
         if target is None:
             # Find paths to all nodes accessible from the source.
diff --git a/networkx/algorithms/similarity.py b/networkx/algorithms/similarity.py
index 2868b1c8..4e2d4556 100644
--- a/networkx/algorithms/similarity.py
+++ b/networkx/algorithms/similarity.py
@@ -1270,7 +1270,8 @@ def simrank_similarity(
         return sum(newsim[w][x] for (w, x) in s) / len(s) if s else 0.0
 
     def sim(u, v):
-        return importance_factor * avg_sim(list(product(G[u], G[v])))
+        Gadj = G.pred if G.is_directed() else G.adj
+        return importance_factor * avg_sim(list(product(Gadj[u], Gadj[v])))
 
     for _ in range(max_iterations):
         if prevsim and _is_close(prevsim, newsim, tolerance):
diff --git a/networkx/algorithms/tests/test_dominance.py b/networkx/algorithms/tests/test_dominance.py
index fccfde8b..5acd643a 100644
--- a/networkx/algorithms/tests/test_dominance.py
+++ b/networkx/algorithms/tests/test_dominance.py
@@ -57,19 +57,18 @@ class TestImmediateDominators:
         edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1),
                  (6, 4), (6, 5)]
         G = nx.DiGraph(edges)
-        assert (nx.immediate_dominators(G, 6) ==
-                {i: 6 for i in range(1, 7)})
+        result = nx.immediate_dominators(G, 6)
+        assert (result == {i: 6 for i in range(1, 7)})
 
     def test_domrel_png(self):
         # Graph taken from https://commons.wikipedia.org/wiki/File:Domrel.png
         edges = [(1, 2), (2, 3), (2, 4), (2, 6), (3, 5), (4, 5), (5, 2)]
         G = nx.DiGraph(edges)
-        assert (nx.immediate_dominators(G, 1) ==
-                {1: 1, 2: 1, 3: 2, 4: 2, 5: 2, 6: 2})
+        result = nx.immediate_dominators(G, 1)
+        assert (result == {1: 1, 2: 1, 3: 2, 4: 2, 5: 2, 6: 2})
         # Test postdominance.
-        with nx.utils.reversed(G):
-            assert (nx.immediate_dominators(G, 6) ==
-                    {1: 2, 2: 6, 3: 5, 4: 5, 5: 2, 6: 6})
+        result = nx.immediate_dominators(G.reverse(copy=False), 6)
+        assert (result == {1: 2, 2: 6, 3: 5, 4: 5, 5: 2, 6: 6})
 
     def test_boost_example(self):
         # Graph taken from Figure 1 of
@@ -77,12 +76,11 @@ class TestImmediateDominators:
         edges = [(0, 1), (1, 2), (1, 3), (2, 7), (3, 4), (4, 5), (4, 6),
                  (5, 7), (6, 4)]
         G = nx.DiGraph(edges)
-        assert (nx.immediate_dominators(G, 0) ==
-                {0: 0, 1: 0, 2: 1, 3: 1, 4: 3, 5: 4, 6: 4, 7: 1})
+        result = nx.immediate_dominators(G, 0)
+        assert (result == {0: 0, 1: 0, 2: 1, 3: 1, 4: 3, 5: 4, 6: 4, 7: 1})
         # Test postdominance.
-        with nx.utils.reversed(G):
-            assert (nx.immediate_dominators(G, 7) ==
-                    {0: 1, 1: 7, 2: 7, 3: 4, 4: 5, 5: 7, 6: 4, 7: 7})
+        result = nx.immediate_dominators(G.reverse(copy=False), 7)
+        assert (result == {0: 1, 1: 7, 2: 7, 3: 4, 4: 5, 5: 7, 6: 4, 7: 7})
 
 
 class TestDominanceFrontiers:
@@ -150,13 +148,10 @@ class TestDominanceFrontiers:
         edges = [(1, 2), (2, 3), (2, 4), (2, 6), (3, 5), (4, 5), (5, 2)]
         G = nx.DiGraph(edges)
         assert (nx.dominance_frontiers(G, 1) ==
-                {1: set(), 2: {2}, 3: {5}, 4: {5},
-                 5: {2}, 6: set()})
+                {1: set(), 2: {2}, 3: {5}, 4: {5}, 5: {2}, 6: set()})
         # Test postdominance.
-        with nx.utils.reversed(G):
-            assert (nx.dominance_frontiers(G, 6) ==
-                    {1: set(), 2: {2}, 3: {2}, 4: {2},
-                     5: {2}, 6: set()})
+        result = nx.dominance_frontiers(G.reverse(copy=False), 6)
+        assert (result == {1: set(), 2: {2}, 3: {2}, 4: {2}, 5: {2}, 6: set()})
 
     def test_boost_example(self):
         # Graph taken from Figure 1 of
@@ -168,10 +163,10 @@ class TestDominanceFrontiers:
                 {0: set(), 1: set(), 2: {7}, 3: {7},
                  4: {4, 7}, 5: {7}, 6: {4}, 7: set()})
         # Test postdominance.
-        with nx.utils.reversed(G):
-            assert (nx.dominance_frontiers(G, 7) ==
-                    {0: set(), 1: set(), 2: {1}, 3: {1},
-                     4: {1, 4}, 5: {1}, 6: {4}, 7: set()})
+        result = nx.dominance_frontiers(G.reverse(copy=False), 7)
+        expected = {0: set(), 1: set(), 2: {1}, 3: {1},
+                    4: {1, 4}, 5: {1}, 6: {4}, 7: set()}
+        assert result == expected
 
     def test_discard_issue(self):
         # https://github.com/networkx/networkx/issues/2071
diff --git a/networkx/algorithms/tests/test_similarity.py b/networkx/algorithms/tests/test_similarity.py
index 33bf390d..cfaffdb8 100644
--- a/networkx/algorithms/tests/test_similarity.py
+++ b/networkx/algorithms/tests/test_similarity.py
@@ -454,16 +454,74 @@ class TestSimilarity:
         actual = nx.simrank_similarity(G)
         assert expected == actual
 
+        # For a DiGraph test, use the first graph from the paper cited in
+        # the docs: https://dl.acm.org/doi/pdf/10.1145/775047.775126
+        G = nx.DiGraph()
+        G.add_node(0, label='Univ')
+        G.add_node(1, label='ProfA')
+        G.add_node(2, label='ProfB')
+        G.add_node(3, label='StudentA')
+        G.add_node(4, label='StudentB')
+        G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 4), (4, 2), (3, 0)])
+
+        expected = {
+            0: {0: 1, 1: 0.0, 2: 0.1323363991265798, 3: 0.0,
+                4: 0.03387811817640443},
+            1: {0: 0.0, 1: 1, 2: 0.4135512472705618, 3: 0.0,
+                4: 0.10586911930126384},
+            2: {0: 0.1323363991265798, 1: 0.4135512472705618, 2: 1,
+                3: 0.04234764772050554, 4: 0.08822426608438655},
+            3: {0: 0.0, 1: 0.0, 2: 0.04234764772050554, 3: 1,
+                4: 0.3308409978164495},
+            4: {0: 0.03387811817640443, 1: 0.10586911930126384,
+                2: 0.08822426608438655, 3: 0.3308409978164495, 4: 1}
+                   }
+        # Use the importance_factor from the paper to get the same numbers.
+        actual = nx.algorithms.similarity.simrank_similarity(G, importance_factor=0.8)
+        assert expected == actual
+
     def test_simrank_source_no_target(self):
         G = nx.cycle_graph(5)
         expected = {0: 1, 1: 0.3951219505902448, 2: 0.5707317069281646, 3: 0.5707317069281646, 4: 0.3951219505902449}
         actual = nx.simrank_similarity(G, source=0)
         assert expected == actual
 
+        # For a DiGraph test, use the first graph from the paper cited in
+        # the docs: https://dl.acm.org/doi/pdf/10.1145/775047.775126
+        G = nx.DiGraph()
+        G.add_node(0, label='Univ')
+        G.add_node(1, label='ProfA')
+        G.add_node(2, label='ProfB')
+        G.add_node(3, label='StudentA')
+        G.add_node(4, label='StudentB')
+        G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 4), (4, 2), (3, 0)])
+
+        expected = {0: 1, 1: 0.0, 2: 0.1323363991265798, 3: 0.0, 4: 0.03387811817640443}
+        # Use the importance_factor from the paper to get the same numbers.
+        actual = nx.algorithms.similarity.simrank_similarity(G, importance_factor=0.8,
+                                                             source=0)
+        assert expected == actual
+
     def test_simrank_source_and_target(self):
         G = nx.cycle_graph(5)
         expected = 1
         actual = nx.simrank_similarity(G, source=0, target=0)
+
+        # For a DiGraph test, use the first graph from the paper cited in
+        # the docs: https://dl.acm.org/doi/pdf/10.1145/775047.775126
+        G = nx.DiGraph()
+        G.add_node(0, label='Univ')
+        G.add_node(1, label='ProfA')
+        G.add_node(2, label='ProfB')
+        G.add_node(3, label='StudentA')
+        G.add_node(4, label='StudentB')
+        G.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 4), (4, 2), (3, 0)])
+
+        expected = 0.1323363991265798
+        # Use the importance_factor from the paper to get the same numbers.
+        # Use the pair (0,2) because (0,0) and (0,1) have trivial results.
+        actual = nx.algorithms.similarity.simrank_similarity(G, importance_factor=0.8,
+                                                             source=0, target=2)
         assert expected == actual
 
     def test_simrank_numpy_no_source_no_target(self):
diff --git a/networkx/conftest.py b/networkx/conftest.py
index a7e6e169..dfdcd325 100644
--- a/networkx/conftest.py
+++ b/networkx/conftest.py
@@ -28,24 +28,27 @@ def pytest_collection_modifyitems(config, items):
 @pytest.fixture(autouse=True)
 def set_warnings():
     warnings.filterwarnings(
-        "ignore",
-        category=DeprecationWarning,
+        "ignore", category=DeprecationWarning,
         message="literal_stringizer is deprecated*",
     )
     warnings.filterwarnings(
-        "ignore",
-        category=DeprecationWarning,
+        "ignore", category=DeprecationWarning,
         message="literal_destringizer is deprecated*",
     )
     warnings.filterwarnings(
-        "ignore", category=DeprecationWarning, message="is_string_like is deprecated*"
+        "ignore", category=DeprecationWarning,
+        message="is_string_like is deprecated*"
     )
     warnings.filterwarnings(
-        "ignore", category=DeprecationWarning, message="make_str is deprecated*"
+        "ignore", category=DeprecationWarning,
+        message="make_str is deprecated*"
     )
     warnings.filterwarnings(
-        "ignore",
-        category=PendingDeprecationWarning,
+        "ignore", category=DeprecationWarning,
+        message="context_manager reversed is deprecated*"
+    )
+    warnings.filterwarnings(
+        "ignore", category=PendingDeprecationWarning,
         message="the matrix subclass is not the recommended way*",
     )
 
diff --git a/networkx/generators/tests/test_community.py b/networkx/generators/tests/test_community.py
index 7f8a181a..69a1290a 100644
--- a/networkx/generators/tests/test_community.py
+++ b/networkx/generators/tests/test_community.py
@@ -121,9 +121,11 @@ def test_gaussian_random_partition_graph():
     G = nx.gaussian_random_partition_graph(100, 10, 10, 0.3, 0.01,
                                            directed=False, seed=42)
     assert len(G) == 100
+    assert not isinstance(G, nx.DiGraph)
     G = nx.gaussian_random_partition_graph(100, 10, 10, 0.3, 0.01,
                                            directed=True, seed=42)
     assert len(G) == 100
+    assert isinstance(G, nx.DiGraph)
     pytest.raises(nx.NetworkXError,
                   nx.gaussian_random_partition_graph, 100, 101, 10, 1, 0)
 
diff --git a/networkx/utils/contextmanagers.py b/networkx/utils/contextmanagers.py
index 7932daa3..1dac72bc 100644
--- a/networkx/utils/contextmanagers.py
+++ b/networkx/utils/contextmanagers.py
@@ -1,4 +1,5 @@
 from contextlib import contextmanager
+import warnings
 
 __all__ = [
     'reversed',
@@ -15,7 +16,18 @@ def reversed(G):
     ----------
     G : graph
         A NetworkX graph.
+
+    Warning
+    -------
+    The reversed context manager is deprecated in favor
+    of G.reverse(copy=False). The view allows multiple threads to use the
+    same graph without confusion while the context manager does not.
+    This context manager is scheduled to be removed in version 2.7.
     """
+    msg = "context manager reversed is deprecated and to be removed in 2.7." \
+          "Use G.reverse(copy=False) if G.is_directed() else G instead."
+    warnings.warn(msg, DeprecationWarning)
+
     directed = G.is_directed()
     if directed:
         G._pred, G._succ = G._succ, G._pred