python-algoritmic-thinking/graph.py at master · rstewart2702/python-algoritmic-thinking · 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
138
139
140
# bfs graph traversal:
# Need adjacency-list representation of a graph.
#
class Vertex:
    def __init__(self, vName):
        self.adjList = []
        self.vtx = vName

    @classmethod
    def newV(cls, vName):
        vee = cls(vName)
        return vee

    def adjAdd(self, adjList):
        for i in adjList:
            self.adjList.append(i)
        return self

class Graph:
    def __init__(self):
        self.nodes = {}

    def vtxAdd(self, vtx):
        self.nodes[vtx.vtx] = vtx
        return self

    @classmethod
    def gBuild(cls, vList):
        gee = cls()
        for i in vList:
            gee.vtxAdd(i)
        return gee

    def bfs(self, startVtx):
        """Performs breadth-first-search of the graph, building a list
of vertices to return, which provides a breath-first-ordering of the
vertices in the graph."""
        currV = None
        queue = [startVtx] # the "what to visit next"
        seen = {startVtx : True}  # set of seen vertices, as a dictionary
        visited = [] # start out with an empty "visited list"
        # append to back, pop off front
        while(len(queue) != 0):
            currV = queue.pop(0)
            self.visit(currV,visited)
            self.enqueue(queue,self.nodes[currV].adjList,seen)
            #
            # print(currV,visited,queue,seen,sep='::')
            # print('\n')
        #
        return visited
    #
    def visit(self,vertex,visited):
        """default implementation of \"visit a vertex.\""""
        visited.append(vertex)
    #
    def enqueue(self, fifoQ, adjList, seenDict):
        """default implementation of \"handle the adjacency list of a vertex.\""""
        for locVertex in adjList:
            if seenDict.get(locVertex) is None:
                seenDict[locVertex]=True
                fifoQ.append(locVertex)


class GraphPaths(Graph):
    """Derived from class Graph.
The methods bfs and enqueue are overridden since the behavior is different...
"""
    def bfs(self, startVtx):
        """Derives a \"visited list\" and a \"list-of-paths-for-each-destination.\""""
        currV = None
        queue = [startVtx]
        seen = {startVtx : True}
        visited = []
        paths = {startVtx : [] }
        for v in self.nodes[startVtx].adjList:
            paths[v] = [v]
        #
        while(len(queue) != 0):
            currV = queue.pop(0)
            self.visit(currV,visited)
            self.enqueue(queue,self.nodes[currV].adjList,seen,paths,currV)
        #
        return (visited, paths)
    #
    def enqueue(self, fifoQ, adjList, seenDict, paths,currV):
        # print('before enqueue:',paths,sep=' ')
        for locVertex in adjList:
            if seenDict.get(locVertex) is None:
                seenDict[locVertex]=True
                fifoQ.append(locVertex)
                paths[locVertex]=paths[currV].copy()
                paths[locVertex].append(locVertex)
                # paths[locVertex]=[locVertex]
            else:
                # The adjacent vertex has been seen before.
                #
                # print('Evaluating:',paths[locVertex])
                # print('against:',paths[currV])
                currLen = len(paths[locVertex])
                newLen = len(paths[currV])+1
                if newLen < currLen:
                    # if the length of the "newer path" is shorter
                    # then it should replace the existing path
                    # print('Replacing path:',paths[locVertex])
                    paths[locVertex] = paths[currV].copy()
                    paths[locVertex].append(locVertex)
                    # print('With path:',paths[locVertex])
        # print('after enqueue:',paths,sep=' ')


class GraphWPaths(GraphPaths):
    """Derived from class GraphPaths, but overrides the enqueue method, as its behavior
is again different.
Also, the assumption is that adjacency lists will be ordered in ascending order by
weight of the corresponding edge."""
    #
    def enqueue(self, queue, adjList, seenDict, paths, currV):
        for locVertex in adjList:
            if seenDict.get(locVertex) is None:
                seenDict[locVertex] = True
                queue.append(locVertex)
                paths[locVertex]=paths[currV].copy()
                paths[locVertex].append(locVertex)
            else:
                currLen = 0
                for li in paths[locVertex]:
                    currLen = currLen + li[1]
                #
                newLen = 0
                for li in paths[currV]:
                    newLen = newLen + li[1]
                #
                # If the length of the "newer path" is shorter
                # then it should replace the existing path.
                if newLen < currLen:
                    paths[locVertex] = paths[currV].copy()
                    paths[locVertex].append(locVertex)