Source Code for Module networkx.cores

 1  """ 
 2  Find and manipulate the k-cores of a graph 
 3   
 4  """ 
 5  __author__ = """Dan Schult(dschult@colgate.edu)""" 
 6  __date__ = "$Date: 2005-03-30 16:56:28 -0700 (Wed, 30 Mar 2005) $" 
 7  __credits__ = """""" 
 8  __revision__ = "$Revision: 911 $" 
 9  #    Copyright (C) 2004,2005 by  
10  #    Aric Hagberg <hagberg@lanl.gov> 
11  #    Dan Schult <dschult@colgate.edu> 
12  #    Pieter Swart <swart@lanl.gov> 
13  #    Distributed under the terms of the GNU Lesser General Public License 
14  #    http://www.gnu.org/copyleft/lesser.html 
15   
16 -def find_cores(G,with_labels=True): 
17     """Return the core number for each vertex. 
18   
19     See: arXiv:cs.DS/0310049 by Batagelj and Zaversnik 
20   
21     If with_labels is True a dict is returned keyed by node to the core number.  
22     If with_labels is False a list of the core numbers is returned. 
23     """ 
24     # compute the degrees of each vertex 
25     degrees=G.degree(with_labels=True) 
26      
27     # sort verticies by degree 
28     valuesfirst= [ [a[1],a[0]] for a in degrees.items() ] 
29     valuesfirst.sort() 
30     verts= [ vf[1] for vf in valuesfirst]  # vertices 
31      
32     # Set up initial guesses for core and lists of neighbors. 
33     core= degrees 
34     nbrs={} 
35     for v in verts: 
36         nbrs[v]=G.neighbors(v) 
37      
38     # form vertex core building up from smallest 
39     for v in verts: 
40         for u in nbrs[v]: 
41            if core[u] > core[v]: 
42               nbrs[u].remove(v) 
43               posu=verts.index(u) 
44               while core[verts[posu]]==core[u]: 
45                   posu -= 1 
46               verts.remove(u) 
47               verts.insert(posu+1,u) 
48               core[u] -= 1 
49     if with_labels: 
50        return core 
51     else: 
52        return core.values() 
53   
54   
55 -def _test_suite(): 
56      import doctest 
57      suite = doctest.DocFileSuite('tests/cores.txt',package='networkx') 
58      return suite 
59   
60  if __name__ == "__main__": 
61      import os 
62      import sys 
63      import unittest 
64      if sys.version_info[:2] < (2, 4): 
65          print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2] 
66          sys.exit(-1) 
67      # directory of networkx package (relative to this) 
68      nxbase=sys.path[0]+os.sep+os.pardir 
69      sys.path.insert(0,nxbase) # prepend to search path 
70      unittest.TextTestRunner().run(_test_suite()) 
71