/usr/share/pyshared/networkx/algorithms/graphical.py is in python-networkx 1.6-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 | # -*- coding: utf-8 -*-
"""Generate graphs with a given degree sequence or expected degree sequence.
"""
# Copyright (C) 2004-2011 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
'Pieter Swart (swart@lanl.gov)',
'Dan Schult (dschult@colgate.edu)'
'Joel Miller (joel.c.miller.research@gmail.com)'
'Ben Edwards'])
__all__ = ['is_valid_degree_sequence',
'is_valid_degree_sequence_erdos_gallai',
'is_valid_degree_sequence_havel_hakimi']
def is_valid_degree_sequence(deg_sequence, method='hh'):
"""Returns True if deg_sequence is a valid degree sequence.
A degree sequence is valid if some graph can realize it.
Parameters
----------
deg_sequence : list
A list of integers where each element specifies the degree of a node
in a graph.
method : "eg" | "hh"
The method used to validate the degree sequence.
"eg" corresponds to the Erdős-Gallai algorithm, and
"hh" to the Havel-Hakimi algorithm.
Returns
-------
valid : bool
True if deg_sequence is a valid degree sequence and False if not.
References
----------
Erdős-Gallai
[EG1960]_, [choudum1986]_
Havel-Hakimi
[havel1955]_, [hakimi1962]_, [CL1996]_
"""
if method == 'eg':
valid = is_valid_degree_sequence_erdos_gallai(deg_sequence)
elif method == 'hh':
valid = is_valid_degree_sequence_havel_hakimi(deg_sequence)
else:
msg = "`method` must be 'eg' or 'hh'"
raise nx.NetworkXException(msg)
return valid
def is_valid_degree_sequence_havel_hakimi(deg_sequence):
"""Returns True if deg_sequence is a valid degree sequence.
A degree sequence is valid if some graph can realize it.
Validation proceeds via the Havel-Hakimi algorithm.
Worst-case run time is: O( n**(log n) )
Parameters
----------
deg_sequence : list
A list of integers where each element specifies the degree of a node
in a graph.
Returns
-------
valid : bool
True if deg_sequence is a valid degree sequence and False if not.
References
----------
[havel1955]_, [hakimi1962]_, [CL1996]_
"""
# some simple tests
if deg_sequence==[]:
return True # empty sequence = empty graph
if not nx.utils.is_list_of_ints(deg_sequence):
return False # list of ints
if min(deg_sequence)<0:
return False # each int not negative
if sum(deg_sequence)%2:
return False # must be even
# successively reduce degree sequence by removing node of maximum degree
# as in Havel-Hakimi algorithm
s=deg_sequence[:] # copy to s
while s:
s.sort() # sort in increasing order
if s[0]<0:
return False # check if removed too many from some node
d=s.pop() # pop largest degree
if d==0: return True # done! rest must be zero due to ordering
# degree must be <= number of available nodes
if d>len(s): return False
# remove edges to nodes of next higher degrees
#s.reverse() # to make it easy to get at higher degree nodes.
for i in range(len(s)-1,len(s)-(d+1),-1):
s[i]-=1
# should never get here b/c either d==0, d>len(s) or d<0 before s=[]
return False
def is_valid_degree_sequence_erdos_gallai(deg_sequence):
"""Returns True if deg_sequence is a valid degree sequence.
A degree sequence is valid if some graph can realize it.
Validation proceeds via the Erdős-Gallai algorithm.
Worst-case run time is: O( n**2 )
Parameters
----------
deg_sequence : list
A list of integers where each element specifies the degree of a node
in a graph.
Returns
-------
valid : bool
True if deg_sequence is a valid degree sequence and False if not.
References
----------
[EG1960]_, [choudum1986]_
"""
# some simple tests
if deg_sequence==[]:
return True # empty sequence = empty graph
if not nx.utils.is_list_of_ints(deg_sequence):
return False # list of ints
if min(deg_sequence)<0:
return False # each int not negative
if sum(deg_sequence)%2:
return False # must be even
n = len(deg_sequence)
deg_seq = sorted(deg_sequence,reverse=True)
sigk = [i for i in range(1, len(deg_seq)) if deg_seq[i] < deg_seq[i-1]]
for k in sigk:
sum_deg = sum(deg_seq[0:k])
sum_min = k*(k-1) + sum([min([k,deg_seq[i]])
for i in range(k,n)])
if sum_deg>sum_min:
return False
return True
|