Hacktech2017/Vertex.py at master · mandarker/Hacktech2017 · 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
class Vertex:
    def __init__(self, node):
        self.data = node
        self.adjacent = {}

    def __str__(self):
        return str(self.data) + ' adjacent: ' + str([x.data for x in self.adjacent])

    def __contains__(self, key):
        return key in self.adjacent

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight

    def get_connections(self):
        return self.adjacent.keys()

    def get_data(self):
        return self.data

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

class Graph:
    def __init__(self):
        self.vert_dict = {}
        self.num_vertices = 0

    def __iter__(self):
        return iter(self.vert_dict.keys())

    def add_vertex(self, node):
        self.num_vertices = self.num_vertices + 1
        new_vertex = Vertex(node)
        self.vert_dict[node] = new_vertex
        return new_vertex

    def has_edge(self, v1, v2):
        return v1 in self.vert_dict and v2 in self.vert_dict and \
                self.vert_dict[v1] in self.vert_dict[v2]

    def get_vertex(self, n):
        if n in self.vert_dict:
            return self.vert_dict[n]
        else:
            return None

    def add_edge(self, frm, to, cost = 0):
        if frm not in self.vert_dict:
            self.add_vertex(frm)
        if to not in self.vert_dict:
            self.add_vertex(to)

        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

    def get_vertices(self):
        return self.vert_dict.keys()

# if __name__ == '__main__':
#
#     g = Graph()
#
#     g.add_vertex('a')
#     g.add_vertex('b')
#     g.add_vertex('c')
#     g.add_vertex('d')
#     g.add_vertex('e')
#     g.add_vertex('f')
#
#     g.add_edge('a', 'b', 7)
#     g.add_edge('a', 'c', 9)
#     g.add_edge('c', 'f', 2)
#     g.add_edge('d', 'e', 6)
#     g.add_edge('a', 'f', 14)
#     g.add_edge('b', 'c', 10)
#     g.add_edge('b', 'd', 15)
#     g.add_edge('c', 'd', 11)
#     g.add_edge('e', 'f', 9)
#
#     for v in g:
#         for w in v.get_connections():
#             v_data = v.get_data()
#             w_data = w.get_data()
#             print ('( %s , %s, %3d)'  % ( v_data, w_data, v.get_weight(w)))
#
#     for v in g:
#         print ('g.vert_dict[%s]=%s' %(v.get_data(), g.vert_dict[v.get_data()]))