isGraphicalScript/isGraphical.py at master · lamdav/isGraphicalScript · GitHub

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()