Repository: networkx/networkx

Issue:
inter_community_non_edges ignore directionality
Hi,

I think the function:

nx.algorithms.community.quality.inter_community_non_edges()

does not work properly for directed graph. It always return the non-edge of a undirected graph, basically halving the number of edges. This mean that the performance function (nx.algorithms.community.performance) will never by higher than 50% for a directed graph.

I'm using version '2.0.dev_20170801111157', python 3.5.1

Best,

Nicolas 

Discussion:

Patch:
diff --git a/networkx/algorithms/community/quality.py b/networkx/algorithms/community/quality.py
index 7de690af7..e04ff260d 100644
--- a/networkx/algorithms/community/quality.py
+++ b/networkx/algorithms/community/quality.py
@@ -114,7 +114,10 @@ def inter_community_edges(G, partition):
     #                                    for block in partition))
     #     return sum(1 for u, v in G.edges() if aff[u] != aff[v])
     #
-    return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()
+    if G.is_directed():
+        return nx.quotient_graph(G, partition, create_using=nx.MultiDiGraph()).size()
+    else:
+        return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()
 
 
 def inter_community_non_edges(G, partition):
diff --git a/networkx/algorithms/simple_paths.py b/networkx/algorithms/simple_paths.py
index 763fa24d7..a2ef79671 100644
--- a/networkx/algorithms/simple_paths.py
+++ b/networkx/algorithms/simple_paths.py
@@ -333,7 +333,6 @@ def shortest_simple_paths(G, source, target, weight=None):
                 for path in listA:
                     if path[:i] == root:
                         ignore_edges.add((path[i - 1], path[i]))
-                ignore_nodes.add(root[-1])
                 try:
                     length, spur = shortest_path_func(G, root[-1], target,
                                                       ignore_nodes=ignore_nodes,
@@ -343,6 +342,7 @@ def shortest_simple_paths(G, source, target, weight=None):
                     listB.push(root_length + length, path)
                 except nx.NetworkXNoPath:
                     pass
+                ignore_nodes.add(root[-1])
 
         if listB:
             path = listB.pop()
@@ -447,6 +447,8 @@ def _bidirectional_pred_succ(G, source, target, ignore_nodes=None, ignore_edges=
        succ is a dictionary of successors from w to the target.
     """
     # does BFS from both source and target and meets in the middle
+    if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
+        raise nx.NetworkXNoPath("No path between %s and %s." % (source, target))
     if target == source:
         return ({target: None}, {source: None}, source)
 
@@ -605,6 +607,8 @@ def _bidirectional_dijkstra(G, source, target, weight='weight',
     shortest_path
     shortest_path_length
     """
+    if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
+        raise nx.NetworkXNoPath("No path between %s and %s." % (source, target))
     if source == target:
         return (0, [source])
 


Test patch:
diff --git a/networkx/algorithms/community/tests/test_quality.py b/networkx/algorithms/community/tests/test_quality.py
index 0c5b94c5a..79ce7e7f6 100644
--- a/networkx/algorithms/community/tests/test_quality.py
+++ b/networkx/algorithms/community/tests/test_quality.py
@@ -12,6 +12,7 @@ module.
 """
 from __future__ import division
 
+from nose.tools import assert_equal
 from nose.tools import assert_almost_equal
 
 import networkx as nx
@@ -19,6 +20,7 @@ from networkx import barbell_graph
 from networkx.algorithms.community import coverage
 from networkx.algorithms.community import modularity
 from networkx.algorithms.community import performance
+from networkx.algorithms.community.quality import inter_community_edges
 
 
 class TestPerformance(object):
@@ -61,3 +63,17 @@ def test_modularity():
     assert_almost_equal(-16 / (14 ** 2), modularity(G, C))
     C = [{0, 1, 2}, {3, 4, 5}]
     assert_almost_equal((35 * 2) / (14 ** 2), modularity(G, C))
+
+
+def test_inter_community_edges_with_digraphs():
+    G = nx.complete_graph(2, create_using = nx.DiGraph())
+    partition = [{0}, {1}]
+    assert_equal(inter_community_edges(G, partition), 2)
+
+    G = nx.complete_graph(10, create_using = nx.DiGraph())
+    partition = [{0}, {1, 2}, {3, 4, 5}, {6, 7, 8, 9}]
+    assert_equal(inter_community_edges(G, partition), 70)
+
+    G = nx.cycle_graph(4, create_using = nx.DiGraph())
+    partition = [{0, 1}, {2, 3}]
+    assert_equal(inter_community_edges(G, partition), 2)
diff --git a/networkx/algorithms/tests/test_simple_paths.py b/networkx/algorithms/tests/test_simple_paths.py
index e29255c32..4c701e487 100644
--- a/networkx/algorithms/tests/test_simple_paths.py
+++ b/networkx/algorithms/tests/test_simple_paths.py
@@ -220,6 +220,40 @@ def test_directed_weighted_shortest_simple_path():
         cost = this_cost
 
 
+def test_weighted_shortest_simple_path_issue2427():
+    G = nx.Graph()
+    G.add_edge('IN', 'OUT', weight = 2)
+    G.add_edge('IN', 'A', weight = 1)
+    G.add_edge('IN', 'B', weight = 2)
+    G.add_edge('B', 'OUT', weight = 2)
+    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight = "weight")),
+                 [['IN', 'OUT'], ['IN', 'B', 'OUT']])
+    G = nx.Graph()
+    G.add_edge('IN', 'OUT', weight = 10)
+    G.add_edge('IN', 'A', weight = 1)
+    G.add_edge('IN', 'B', weight = 1)
+    G.add_edge('B', 'OUT', weight = 1)
+    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight = "weight")),
+                 [['IN', 'B', 'OUT'], ['IN', 'OUT']])
+
+
+def test_directed_weighted_shortest_simple_path_issue2427():
+    G = nx.DiGraph()
+    G.add_edge('IN', 'OUT', weight = 2)
+    G.add_edge('IN', 'A', weight = 1)
+    G.add_edge('IN', 'B', weight = 2)
+    G.add_edge('B', 'OUT', weight = 2)
+    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight = "weight")),
+                 [['IN', 'OUT'], ['IN', 'B', 'OUT']])
+    G = nx.DiGraph()
+    G.add_edge('IN', 'OUT', weight = 10)
+    G.add_edge('IN', 'A', weight = 1)
+    G.add_edge('IN', 'B', weight = 1)
+    G.add_edge('B', 'OUT', weight = 1)
+    assert_equal(list(nx.shortest_simple_paths(G, 'IN', 'OUT', weight = "weight")),
+                 [['IN', 'B', 'OUT'], ['IN', 'OUT']])
+
+
 def test_weight_name():
     G = nx.cycle_graph(7)
     nx.set_edge_attributes(G, 1, 'weight')
@@ -303,6 +337,38 @@ def test_bidirectional_shortest_path_restricted_directed_cycle():
     )
 
 
+def test_bidirectional_shortest_path_ignore():
+    G = nx.Graph()
+    nx.add_path(G, [1, 2])
+    nx.add_path(G, [1, 3])
+    nx.add_path(G, [1, 4])
+    assert_raises(
+        nx.NetworkXNoPath,
+        _bidirectional_shortest_path,
+        G,
+        1, 2,
+        ignore_nodes=[1],
+    )
+    assert_raises(
+        nx.NetworkXNoPath,
+        _bidirectional_shortest_path,
+        G,
+        1, 2,
+        ignore_nodes=[2],
+    )
+    G = nx.Graph()
+    nx.add_path(G, [1, 3])
+    nx.add_path(G, [1, 4])
+    nx.add_path(G, [3, 2])
+    assert_raises(
+        nx.NetworkXNoPath,
+        _bidirectional_shortest_path,
+        G,
+        1, 2,
+        ignore_nodes=[1, 2],
+    )
+
+
 def validate_path(G, s, t, soln_len, path):
     assert_equal(path[0], s)
     assert_equal(path[-1], t)
@@ -362,3 +428,30 @@ def test_bidirectional_dijkstra_no_path():
     nx.add_path(G, [1, 2, 3])
     nx.add_path(G, [4, 5, 6])
     path = _bidirectional_dijkstra(G, 1, 6)
+
+
+def test_bidirectional_dijkstra_ignore():
+    G = nx.Graph()
+    nx.add_path(G, [1, 2, 10])
+    nx.add_path(G, [1, 3, 10])
+    assert_raises(
+        nx.NetworkXNoPath,
+        _bidirectional_dijkstra,
+        G,
+        1, 2,
+        ignore_nodes=[1],
+    )
+    assert_raises(
+        nx.NetworkXNoPath,
+        _bidirectional_dijkstra,
+        G,
+        1, 2,
+        ignore_nodes=[2],
+    )
+    assert_raises(
+        nx.NetworkXNoPath,
+        _bidirectional_dijkstra,
+        G,
+        1, 2,
+        ignore_nodes=[1, 2],
+    )