Package networkx :: Module cores
[hide private]
[frames] | no frames]

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