-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathisGraphical.py
More file actions
137 lines (113 loc) · 3.38 KB
/
isGraphical.py
File metadata and controls
137 lines (113 loc) · 3.38 KB
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
import sys
def main():
"""
Determine if a degree sequence is graphical.
Grabs command line arguments that are space separated.
"""
# Script use to solve problems in:
# "A First Course in Graph Theory"
# by Gary Chartrand and Ping Zhang
# 2.32
# a = [5, 3, 3, 3, 3, 2, 2, 2, 1]
# b = [6, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1]
# c = [6, 5, 5, 4, 3, 2, 1]
# d = [7, 5, 4, 4, 4, 3, 2, 1]
# e = [7, 6, 5, 4, 4, 3, 2, 1]
# prob = [a, b, c, d, e]
# for part in prob:
# print(isGraphical(part))
# 2.33
# for x in range(6):
# a = [1, 2, 3, 5, 5]
# a.append(x)
# a.sort(reverse = True)
# print(isGraphical(a))
# 2.34
# for x in range(8):
# a = [7, 6, 5, 4, 4, 3, 2, 1]
# a.append(x)
# print(isGraphical(a, False))
# if (isGraphical(a, False)):
# print(x)
# 2.35
# for x in range(8):
# a = [7, 7, 5, 5, 4, 3, 2]
# a.append(x)
# a.sort(reverse = True)
# print(str(x) + " : " + str(isGraphical(a)))
degSeq = []
verbose = False
# Grab command line arguments.
for k in range(1, len(sys.argv)):
# Allows for the "-v" flag to be appear anywhere.
if (sys.argv[k] == "-v"):
verbose = True
else:
degSeq.append(int(sys.argv[k]))
# Sort it in descending order.
degSeq.sort(reverse = True)
# Print Value(s).
print(isGraphical(degSeq, verbose))
def isGraphical(degSeq, verbose = False):
"""
Checks if a given degSeq is Graphical.
Arguments:
:type degSeq : list
List of integers representing a graphs degree sequence.
Optional Parameters:
:type verbose : boolean
Flag used to print each stage of the degSeq.
Returns True if degSeq is Graphical.
False otherwise.
"""
# Main Loop.
while (isValid(degSeq)):
# Grab first element.
current = degSeq[0]
# Print stage if verbose.
if (verbose):
print(degSeq)
# Decrement degSeg.
# If IndexError, it is not graphical.
try:
for k in range(1, current + 1):
degSeq[k] -= 1
except IndexError:
return False
degSeq.remove(current)
degSeq.sort(reverse = True)
# Passing condition.
if (isZero(degSeq)):
return True
return False
def isZero(degSeq):
"""
Checks if a given degSeq is all zeros.
Arguments:
:type degSeq : list
List of integers representing a graphs degree sequence.
Returns True if degSeq contains only zero.
False otherwise.
"""
for element in degSeq:
if (element != 0):
return False
return True
def isValid(degSeq):
"""
Checks if a given degSeq is still valid (no negatives).
Arguments:
:type degSeq : list
List of integers representing a graphs degree sequence.
Returns True if degSeq contains no negatives.
False otherwise.
"""
# Ensure that degSeq is not empty.
if (len(degSeq) == 0):
return False
for element in degSeq:
if (element < 0):
return False
return True
if __name__ == "__main__":
main()