"""GraphDegeneracy.py Compute the degeneracy of graphs, and degeneracy orderings of graphs. D. Eppstein, July 2016. """ import unittest from Graphs import isUndirected from BucketQueue import BucketQueue def degeneracySequence(G): """Generate pairs (vertex,number of later neighbors) in degeneracy order.""" if not isUndirected(G): raise TypeError("Graph must be undirected") Q = BucketQueue() for v in G: Q[v] = len(G[v]) # prioritize vertices by degree for v,d in Q.items(): yield v,d # output vertices in priority order for w in G[v]: if w in Q: Q[w] -= 1 # one fewer remaining neighbor def degeneracy(G): """Calculate the degeneracy of a given graph""" return max(d for v,d in degeneracySequence(G)) def degeneracyOrientation(G): """Directed version of G with <= degeneracy out-neighbors per vertex.""" D = {} for v,d in degeneracySequence(G): D[v] = {w for w in G[v] if w not in D} return D def core(G,k=None): """The k-core of G, or the deepest core if k is not given. The return value is a set of vertices; use Graphs.InducedSubgraph if the edges are also needed.""" level = 0 coreset = set() for v,d in degeneracySequence(G): if d > level: # new depth record? if k == None or level < k: # we care about new records? coreset = set() # yes, restart core level = d coreset.add(v) return coreset def triangles(G): """Use degeneracy to list all the triangles in G""" G = degeneracyOrientation(G) return ((u,v,w) for u in G for v in G[u] for w in G[u] if w in G[v]) # ============================================================ # If run from command line, perform unit tests # ============================================================ class DegeneracyTest(unittest.TestCase): G = {1:[2,5],2:[1,3,5],3:[2,4],4:[3,5,6],5:[1,2,4],6:[4]} #File:6n-graf.svg def testDegeneracy(self): self.assertEqual(degeneracy(DegeneracyTest.G),2) def testCore(self): self.assertEqual(core(DegeneracyTest.G),{1,2,3,4,5}) def testTriangles(self): T = list(triangles(DegeneracyTest.G)) self.assertEqual(len(T),1) self.assertEqual(set(T[0]),{1,2,5}) if __name__ == "__main__": unittest.main()