Data structure to store graphs (based on adjacency lists)
| 1 | class Graph: |
| 2 | """ |
| 3 | Data structure to store graphs (based on adjacency lists) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self): |
| 7 | self.num_vertices = 0 |
| 8 | self.num_edges = 0 |
| 9 | self.adjacency = {} |
| 10 | |
| 11 | def add_vertex(self, vertex): |
| 12 | """ |
| 13 | Adds a vertex to the graph |
| 14 | |
| 15 | """ |
| 16 | if vertex not in self.adjacency: |
| 17 | self.adjacency[vertex] = {} |
| 18 | self.num_vertices += 1 |
| 19 | |
| 20 | def add_edge(self, head, tail, weight): |
| 21 | """ |
| 22 | Adds an edge to the graph |
| 23 | |
| 24 | """ |
| 25 | |
| 26 | self.add_vertex(head) |
| 27 | self.add_vertex(tail) |
| 28 | |
| 29 | if head == tail: |
| 30 | return |
| 31 | |
| 32 | self.adjacency[head][tail] = weight |
| 33 | self.adjacency[tail][head] = weight |
| 34 | |
| 35 | def distinct_weight(self): |
| 36 | """ |
| 37 | For Boruvks's algorithm the weights should be distinct |
| 38 | Converts the weights to be distinct |
| 39 | |
| 40 | """ |
| 41 | edges = self.get_edges() |
| 42 | for edge in edges: |
| 43 | head, tail, weight = edge |
| 44 | edges.remove((tail, head, weight)) |
| 45 | for i in range(len(edges)): |
| 46 | edges[i] = list(edges[i]) |
| 47 | |
| 48 | edges.sort(key=lambda e: e[2]) |
| 49 | for i in range(len(edges) - 1): |
| 50 | if edges[i][2] >= edges[i + 1][2]: |
| 51 | edges[i + 1][2] = edges[i][2] + 1 |
| 52 | for edge in edges: |
| 53 | head, tail, weight = edge |
| 54 | self.adjacency[head][tail] = weight |
| 55 | self.adjacency[tail][head] = weight |
| 56 | |
| 57 | def __str__(self): |
| 58 | """ |
| 59 | Returns string representation of the graph |
| 60 | """ |