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
10
11
12
13
14
15
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
25 degrees=G.degree(with_labels=True)
26
27
28 valuesfirst= [ [a[1],a[0]] for a in degrees.items() ]
29 valuesfirst.sort()
30 verts= [ vf[1] for vf in valuesfirst]
31
32
33 core= degrees
34 nbrs={}
35 for v in verts:
36 nbrs[v]=G.neighbors(v)
37
38
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
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
68 nxbase=sys.path[0]+os.sep+os.pardir
69 sys.path.insert(0,nxbase)
70 unittest.TextTestRunner().run(_test_suite())
71