Undirected Graph, with graph represented as an adjacency matrix
| 2 | |
| 3 | |
| 4 | class UndirectedGraph(object): |
| 5 | """ |
| 6 | Undirected Graph, with graph represented as an adjacency matrix |
| 7 | """ |
| 8 | |
| 9 | def __init__(self, vertices): |
| 10 | self.adjacency_matrix = [] |
| 11 | for i in range(vertices): |
| 12 | self.adjacency_matrix.append([0] * vertices) |
| 13 | |
| 14 | def add_edge(self, source, destination): |
| 15 | """ |
| 16 | Adds an edge defined by vertices from source to destination |
| 17 | then destination to source in matrix |
| 18 | :param source: |
| 19 | :param destination: |
| 20 | :return: |
| 21 | """ |
| 22 | self.adjacency_matrix[source][destination] = 1 |
| 23 | self.adjacency_matrix[destination][source] = 1 |
| 24 | |
| 25 | def get_vertex(self): |
| 26 | """ |
| 27 | Generator for returning the next vertex from the adjacency list |
| 28 | :return: |
| 29 | """ |
| 30 | for v, __ in enumerate(self.adjacency_matrix): |
| 31 | yield v |
| 32 | |
| 33 | def get_neighbor(self, vertex): |
| 34 | """ |
| 35 | Generator for returning the next vertex adjacent to the given vertex |
| 36 | :param vertex: |
| 37 | :return: |
| 38 | """ |
| 39 | for i, flag in enumerate(self.adjacency_matrix[vertex]): |
| 40 | if flag == 1: |
| 41 | yield i |
| 42 | |
| 43 | def dfs_recursive(self): |
| 44 | """ |
| 45 | Computes the parents for each vertex as determined through depth-first-search |
| 46 | (though not too meaningful in an undirected weightless graph) |
| 47 | :return: parents for each vertex |
| 48 | :rtype: dict |
| 49 | """ |
| 50 | parents = {} |
| 51 | |
| 52 | self.dfs_util(0, parents) |
| 53 | |
| 54 | return parents |
| 55 | |
| 56 | def dfs_util(self, vertex, parents): |
| 57 | for u in self.get_neighbor(vertex): |
| 58 | if u not in parents: |
| 59 | parents[u] = vertex |
| 60 | self.dfs_util(u, parents) |
| 61 |
no outgoing calls
no test coverage detected