Repository: networkx/networkx

Issue:
k-core algorithm produces incorrect output for DiGraph


As per title, calling `nx.k_core(G, k = x)` does not return the x-core of a graph, if `G` is a `DiGraph`.

See attached file.

[6954_2011.txt](https://github.com/networkx/networkx/files/105086/6954_2011.txt)


To reproduce, run:

```python
import networkx as nx

G = nx.DiGraph()
with open("6954_2011.txt", 'r') as f:
   for line in f:
      fields = line.strip().split('\t')
      G.add_edge(fields[0], fields[1])

core = nx.k_core(G, k = 12)
core.number_of_nodes() # Outputs "24"; expected output: "12"
```

There are only 12 nodes with (in+out) degree 12 once you remove recursively all those which don't qualify. These are:

IND
AUT
CHE
BEL
USA
ESP
CHN
FRA
NLD
GBR
ITA
DEU

While
```python
core.nodes()
```
says `['BEL', 'SWE', 'DEU', 'GBR', 'KOR', 'USA', 'SGP', 'MYS', 'POL', 'NLD', 'HKG', 'FRA', 'CHE', 'ESP', 'CHN', 'AUT', 'THA', 'JPN', 'TUR', 'ITA', 'IND', 'RUS', 'NOR', 'CZE']`

The method seems to work ok for `nx.Graph`, or at least I've yet to find a counter-example.

Discussion:

Patch:
diff --git a/networkx/algorithms/core.py b/networkx/algorithms/core.py
index 2091bb97f..c98c7d77c 100644
--- a/networkx/algorithms/core.py
+++ b/networkx/algorithms/core.py
@@ -4,30 +4,41 @@
 #    Pieter Swart <swart@lanl.gov>
 #    All rights reserved.
 #    BSD license.
+#
+# Authors: Dan Schult (dschult@colgate.edu)
+#          Jason Grout (jason-sage@creativetrax.com)
+#          Aric Hagberg (hagberg@lanl.gov)
 """
 Find the k-cores of a graph.
 
 The k-core is found by recursively pruning nodes with degrees less than k.
 
-See the following reference for details:
+See the following references for details:
 
 An O(m) Algorithm for Cores Decomposition of Networks
 Vladimir Batagelj and Matjaz Zaversnik, 2003.
 http://arxiv.org/abs/cs.DS/0310049
 
-"""
-
-__author__ = "\n".join(['Dan Schult (dschult@colgate.edu)',
-                        'Jason Grout (jason-sage@creativetrax.com)',
-                        'Aric Hagberg (hagberg@lanl.gov)'])
+Generalized Cores
+Vladimir Batagelj and Matjaz Zaversnik, 2002.
+http://arxiv.org/pdf/cs/0202039
 
-__all__ = ['core_number','k_core','k_shell','k_crust','k_corona','find_cores']
+For directed graphs a more general notion is that of D-cores which
+looks at (k, l) restrictions on (in, out) degree. The (k, k) D-core
+is the k-core.
 
+D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy
+Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis, ICDM 2011.
+http://www.graphdegeneracy.org/dcores_ICDM_2011.pdf
+"""
 import networkx as nx
-from networkx import all_neighbors
 from networkx.exception import NetworkXError
 from networkx.utils import not_implemented_for
 
+__all__ = ['core_number', 'find_cores', 'k_core',
+           'k_shell', 'k_crust', 'k_corona']
+
+
 @not_implemented_for('multigraph')
 def core_number(G):
     """Return the core number for each vertex.
@@ -50,7 +61,8 @@ def core_number(G):
     Raises
     ------
     NetworkXError
-        The k-core is not defined for graphs with self loops or parallel edges.
+        The k-core is not implemented for graphs with self loops
+        or parallel edges.
 
     Notes
     -----
@@ -66,9 +78,9 @@ def core_number(G):
        http://arxiv.org/abs/cs.DS/0310049
     """
     if G.number_of_selfloops() > 0:
-        raise NetworkXError(
-                'Input graph has self loops; the core number is not defined.'
-                ' Consider using G.remove_edges_from(G.selfloop_edges()).')
+        msg = ('Input graph has self loops which is not permitted; '
+               'Consider using G.remove_edges_from(G.selfloop_edges()).')
+        raise NetworkXError(msg)
     degrees = dict(G.degree())
     # Sort nodes by degree.
     nodes = sorted(degrees, key=degrees.get)
@@ -81,7 +93,7 @@ def core_number(G):
     node_pos = {v: pos for pos, v in enumerate(nodes)}
     # The initial guess for the core number of a node is its degree.
     core = degrees
-    nbrs = {v: set(all_neighbors(G, v)) for v in G}
+    nbrs = {v: list(nx.all_neighbors(G, v)) for v in G}
     for v in nodes:
         for u in nbrs[v]:
             if core[u] > core[v]:
@@ -99,34 +111,34 @@ def core_number(G):
 find_cores = core_number
 
 
-def _core_helper(G, func, k=None, core=None):
-    """Returns the subgraph induced by all nodes for which ``func``
-    returns ``True``.
-
-    ``G`` is a NetworkX graph.
-
-    ``func`` is a function that takes three inputs: a node of ``G``, the
-    maximum core value, and the core number of the graph. The function
-    must return a Boolean value.
+def _core_subgraph(G, k_filter, k=None, core=None):
+    """Returns the subgraph induced by nodes passing filter ``k_filter``.
 
-    ``k`` is the order of the core. If not specified, the maximum over
-    all core values will be returned.
-
-    ``core`` is a dictionary mapping node to core numbers for that
-    node. If you have already computed it, you should provide it
-    here. If not specified, the core numbers will be computed from the
-    graph.
+    Parameters
+    ----------
+    G : NetworkX graph
+       The graph or directed graph to process
+    k_filter : filter function
+       This function filters the nodes chosen. It takes three inputs:
+       A node of G, the filter's cutoff, and the core dict of the graph.
+       The function should return a Boolean value.
+    k : int, optional
+      The order of the core. If not specified use the max core number.
+      This value is used as the cutoff for the filter.
+    core : dict, optional
+      Precomputed core numbers keyed by node for the graph ``G``.
+      If not specified, the core numbers will be computed from ``G``.
 
     """
     if core is None:
         core = core_number(G)
     if k is None:
         k = max(core.values())
-    nodes = [v for v in core if func(v, k, core)]
+    nodes = (v for v in core if k_filter(v, k, core))
     return G.subgraph(nodes).copy()
 
 
-def k_core(G,k=None,core_number=None):
+def k_core(G, k=None, core_number=None):
     """Return the k-core of G.
 
     A k-core is a maximal subgraph that contains nodes of degree k or more.
@@ -171,21 +183,23 @@ def k_core(G,k=None,core_number=None):
        Vladimir Batagelj and Matjaz Zaversnik,  2003.
        http://arxiv.org/abs/cs.DS/0310049
     """
-    func = lambda v, k, core_number: core_number[v] >= k
-    return _core_helper(G, func, k, core_number)
+    def k_filter(v, k, c):
+        return c[v] >= k
+    return _core_subgraph(G, k_filter, k, core_number)
 
 
-def k_shell(G,k=None,core_number=None):
+def k_shell(G, k=None, core_number=None):
     """Return the k-shell of G.
 
-    The k-shell is the subgraph of nodes in the k-core but not in the (k+1)-core.
+    The k-shell is the subgraph induced by nodes with core number k.
+    That is, nodes in the k-core that are not in the (k+1)-core.
 
     Parameters
     ----------
     G : NetworkX graph
       A graph or directed graph.
     k : int, optional
-      The order of the shell.  If not specified return the main shell.
+      The order of the shell. If not specified return the outer shell.
     core_number : dictionary, optional
       Precomputed core numbers for the graph G.
 
@@ -198,7 +212,8 @@ def k_shell(G,k=None,core_number=None):
     Raises
     ------
     NetworkXError
-        The k-shell is not defined for graphs with self loops or parallel edges.
+        The k-shell is not implemented for graphs with self loops
+        or parallel edges.
 
     Notes
     -----
@@ -225,11 +240,12 @@ def k_shell(G,k=None,core_number=None):
        and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
        http://www.pnas.org/content/104/27/11150.full
     """
-    func = lambda v, k, core_number: core_number[v] == k
-    return _core_helper(G, func, k, core_number)
+    def k_filter(v, k, c):
+        return c[v] == k
+    return _core_subgraph(G, k_filter, k, core_number)
 
 
-def k_crust(G,k=None,core_number=None):
+def k_crust(G, k=None, core_number=None):
     """Return the k-crust of G.
 
     The k-crust is the graph G with the k-core removed.
@@ -251,7 +267,8 @@ def k_crust(G,k=None,core_number=None):
     Raises
     ------
     NetworkXError
-        The k-crust is not defined for graphs with self loops or parallel edges.
+        The k-crust is not implemented for graphs with self loops
+        or parallel edges.
 
     Notes
     -----
@@ -276,16 +293,14 @@ def k_crust(G,k=None,core_number=None):
        and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
        http://www.pnas.org/content/104/27/11150.full
     """
-    func = lambda v, k, core_number: core_number[v] <= k
-    # HACK These two checks are done in _core_helper, but this function
-    # requires k to be one less than the maximum core value instead of
-    # just the maximum. Therefore we duplicate the checks here. A better
-    # solution should exist...
+    # Default for k is one less than in _core_subgraph, so just inline.
+    #    Filter is c[v] <= k
     if core_number is None:
-        core_number = nx.core_number(G)
+        core_number = find_cores(G)
     if k is None:
         k = max(core_number.values()) - 1
-    return _core_helper(G, func, k, core_number)
+    nodes = (v for v in core_number if core_number[v] <= k)
+    return G.subgraph(nodes).copy()
 
 
 def k_corona(G, k, core_number=None):
@@ -335,5 +350,6 @@ def k_corona(G, k, core_number=None):
        Phys. Rev. E 73, 056101 (2006)
        http://link.aps.org/doi/10.1103/PhysRevE.73.056101
     """
-    func = lambda v, k, c: c[v] == k and sum(1 for w in G[v] if c[w] >= k) == k
-    return _core_helper(G, func, k, core_number)
+    def func(v, k, c):
+        return c[v] == k and k == sum(1 for w in G[v] if c[w] >= k)
+    return _core_subgraph(G, func, k, core_number)


Test patch:
diff --git a/networkx/algorithms/tests/test_core.py b/networkx/algorithms/tests/test_core.py
index 48399aeed..7119159c8 100644
--- a/networkx/algorithms/tests/test_core.py
+++ b/networkx/algorithms/tests/test_core.py
@@ -2,8 +2,8 @@
 from nose.tools import *
 import networkx as nx
 
-class TestCore:
 
+class TestCore:
     def setUp(self):
         # G is the example graph in Figure 1 from Batagelj and
         # Zaversnik's paper titled An O(m) Algorithm for Cores
@@ -12,103 +12,114 @@ class TestCore:
         # shown, the 3-core is given by nodes 1-8, the 2-core by nodes
         # 9-16, the 1-core by nodes 17-20 and node 21 is in the
         # 0-core.
-        t1=nx.convert_node_labels_to_integers(nx.tetrahedral_graph(),1)
-        t2=nx.convert_node_labels_to_integers(t1,5)
-        G=nx.union(t1,t2)
-        G.add_edges_from( [(3,7), (2,11), (11,5), (11,12), (5,12), (12,19),
-                           (12,18), (3,9), (7,9), (7,10), (9,10), (9,20),
-                           (17,13), (13,14), (14,15), (15,16), (16,13)])
+        t1 = nx.convert_node_labels_to_integers(nx.tetrahedral_graph(), 1)
+        t2 = nx.convert_node_labels_to_integers(t1, 5)
+        G = nx.union(t1, t2)
+        G.add_edges_from([(3, 7), (2, 11), (11, 5), (11, 12), (5, 12),
+                          (12, 19), (12, 18), (3, 9), (7, 9), (7, 10),
+                          (9, 10), (9, 20), (17, 13), (13, 14), (14, 15),
+                          (15, 16), (16, 13)])
         G.add_node(21)
-        self.G=G
+        self.G = G
 
         # Create the graph H resulting from the degree sequence
-        # [0,1,2,2,2,2,3] when using the Havel-Hakimi algorithm. 
+        # [0, 1, 2, 2, 2, 2, 3] when using the Havel-Hakimi algorithm.
 
-        degseq=[0,1,2,2,2,2,3]
+        degseq = [0, 1, 2, 2, 2, 2, 3]
         H = nx.havel_hakimi_graph(degseq)
-        mapping = {6:0, 0:1, 4:3, 5:6, 3:4, 1:2, 2:5 }
+        mapping = {6: 0, 0: 1, 4: 3, 5: 6, 3: 4, 1: 2, 2: 5}
         self.H = nx.relabel_nodes(H, mapping)
 
     def test_trivial(self):
         """Empty graph"""
         G = nx.Graph()
-        assert_equal(nx.find_cores(G),{})
+        assert_equal(nx.find_cores(G), {})
 
     def test_find_cores(self):
-        cores=nx.find_cores(self.G)
-        nodes_by_core=[]
-        for val in [0,1,2,3]:
-            nodes_by_core.append( sorted([k for k in cores if cores[k]==val]))
-        assert_equal(nodes_by_core[0],[21])
-        assert_equal(nodes_by_core[1],[17, 18, 19, 20])
-        assert_equal(nodes_by_core[2],[9, 10, 11, 12, 13, 14, 15, 16])
+        core = nx.find_cores(self.G)
+        nodes_by_core = [sorted([n for n in core if core[n] == val])
+                         for val in range(4)]
+        assert_equal(nodes_by_core[0], [21])
+        assert_equal(nodes_by_core[1], [17, 18, 19, 20])
+        assert_equal(nodes_by_core[2], [9, 10, 11, 12, 13, 14, 15, 16])
         assert_equal(nodes_by_core[3], [1, 2, 3, 4, 5, 6, 7, 8])
 
     def test_core_number(self):
         # smoke test real name
-        cores=nx.core_number(self.G)
+        cores = nx.core_number(self.G)
 
     def test_find_cores2(self):
-        cores=nx.find_cores(self.H)
-        nodes_by_core=[]
-        for val in [0,1,2]:
-            nodes_by_core.append( sorted([k for k in cores if cores[k]==val]))
-        assert_equal(nodes_by_core[0],[0])
-        assert_equal(nodes_by_core[1],[1, 3])
-        assert_equal(nodes_by_core[2],[2, 4, 5, 6])
+        core = nx.find_cores(self.H)
+        nodes_by_core = [sorted([n for n in core if core[n] == val])
+                         for val in range(3)]
+        assert_equal(nodes_by_core[0], [0])
+        assert_equal(nodes_by_core[1], [1, 3])
+        assert_equal(nodes_by_core[2], [2, 4, 5, 6])
+
+    def test_directed_find_cores(Self):
+        '''core number had a bug for directed graphs found in issue #1959'''
+        # small example where too timid edge removal can make cn[2] = 3
+        G = nx.DiGraph()
+        edges = [(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)]
+        G.add_edges_from(edges)
+        assert_equal(nx.core_number(G), {1: 2, 2: 2, 3: 2, 4: 2})
+        # small example where too aggressive edge removal can make cn[2] = 2
+        more_edges = [(1, 5), (3, 5), (4, 5), (3, 6), (4, 6), (5, 6)]
+        G.add_edges_from(more_edges)
+        assert_equal(nx.core_number(G), {1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3})
 
     def test_main_core(self):
-        main_core_subgraph=nx.k_core(self.H)
-        assert_equal(sorted(main_core_subgraph.nodes()),[2,4,5,6])
+        main_core_subgraph = nx.k_core(self.H)
+        assert_equal(sorted(main_core_subgraph.nodes()), [2, 4, 5, 6])
 
     def test_k_core(self):
         # k=0
-        k_core_subgraph=nx.k_core(self.H,k=0)
-        assert_equal(sorted(k_core_subgraph.nodes()),sorted(self.H.nodes()))
+        k_core_subgraph = nx.k_core(self.H, k=0)
+        assert_equal(sorted(k_core_subgraph.nodes()), sorted(self.H.nodes()))
         # k=1
-        k_core_subgraph=nx.k_core(self.H,k=1)
-        assert_equal(sorted(k_core_subgraph.nodes()),[1,2,3,4,5,6])
-        # k=2
-        k_core_subgraph=nx.k_core(self.H,k=2)
-        assert_equal(sorted(k_core_subgraph.nodes()),[2,4,5,6])
+        k_core_subgraph = nx.k_core(self.H, k=1)
+        assert_equal(sorted(k_core_subgraph.nodes()), [1, 2, 3, 4, 5, 6])
+        # k = 2
+        k_core_subgraph = nx.k_core(self.H, k=2)
+        assert_equal(sorted(k_core_subgraph.nodes()), [2, 4, 5, 6])
 
     def test_main_crust(self):
-        main_crust_subgraph=nx.k_crust(self.H)
-        assert_equal(sorted(main_crust_subgraph.nodes()),[0,1,3])
+        main_crust_subgraph = nx.k_crust(self.H)
+        assert_equal(sorted(main_crust_subgraph.nodes()), [0, 1, 3])
 
     def test_k_crust(self):
-        # k=0
-        k_crust_subgraph=nx.k_crust(self.H,k=2)
-        assert_equal(sorted(k_crust_subgraph.nodes()),sorted(self.H.nodes()))
+        # k = 0
+        k_crust_subgraph = nx.k_crust(self.H, k=2)
+        assert_equal(sorted(k_crust_subgraph.nodes()), sorted(self.H.nodes()))
         # k=1
-        k_crust_subgraph=nx.k_crust(self.H,k=1)
-        assert_equal(sorted(k_crust_subgraph.nodes()),[0,1,3])
+        k_crust_subgraph = nx.k_crust(self.H, k=1)
+        assert_equal(sorted(k_crust_subgraph.nodes()), [0, 1, 3])
         # k=2
-        k_crust_subgraph=nx.k_crust(self.H,k=0)
-        assert_equal(sorted(k_crust_subgraph.nodes()),[0])
+        k_crust_subgraph = nx.k_crust(self.H, k=0)
+        assert_equal(sorted(k_crust_subgraph.nodes()), [0])
 
     def test_main_shell(self):
-        main_shell_subgraph=nx.k_shell(self.H)
-        assert_equal(sorted(main_shell_subgraph.nodes()),[2,4,5,6])
+        main_shell_subgraph = nx.k_shell(self.H)
+        assert_equal(sorted(main_shell_subgraph.nodes()), [2, 4, 5, 6])
 
     def test_k_shell(self):
         # k=0
-        k_shell_subgraph=nx.k_shell(self.H,k=2)
-        assert_equal(sorted(k_shell_subgraph.nodes()),[2,4,5,6])
+        k_shell_subgraph = nx.k_shell(self.H, k=2)
+        assert_equal(sorted(k_shell_subgraph.nodes()), [2, 4, 5, 6])
         # k=1
-        k_shell_subgraph=nx.k_shell(self.H,k=1)
-        assert_equal(sorted(k_shell_subgraph.nodes()),[1,3])
+        k_shell_subgraph = nx.k_shell(self.H, k=1)
+        assert_equal(sorted(k_shell_subgraph.nodes()), [1, 3])
         # k=2
-        k_shell_subgraph=nx.k_shell(self.H,k=0)
-        assert_equal(sorted(k_shell_subgraph.nodes()),[0])
+        k_shell_subgraph = nx.k_shell(self.H, k=0)
+        assert_equal(sorted(k_shell_subgraph.nodes()), [0])
 
     def test_k_corona(self):
         # k=0
-        k_corona_subgraph=nx.k_corona(self.H,k=2)
-        assert_equal(sorted(k_corona_subgraph.nodes()),[2,4,5,6])
+        k_corona_subgraph = nx.k_corona(self.H, k=2)
+        assert_equal(sorted(k_corona_subgraph.nodes()), [2, 4, 5, 6])
         # k=1
-        k_corona_subgraph=nx.k_corona(self.H,k=1)
-        assert_equal(sorted(k_corona_subgraph.nodes()),[1])
+        k_corona_subgraph = nx.k_corona(self.H, k=1)
+        assert_equal(sorted(k_corona_subgraph.nodes()), [1])
         # k=2
-        k_corona_subgraph=nx.k_corona(self.H,k=0)
-        assert_equal(sorted(k_corona_subgraph.nodes()),[0])
+        k_corona_subgraph = nx.k_corona(self.H, k=0)
+        assert_equal(sorted(k_corona_subgraph.nodes()), [0])