| 211 | |
| 212 | |
| 213 | class Graph: |
| 214 | def __init__(self, num): |
| 215 | """ |
| 216 | Graph class constructor |
| 217 | |
| 218 | Examples: |
| 219 | >>> graph_test = Graph(1) |
| 220 | >>> graph_test.num_nodes |
| 221 | 1 |
| 222 | >>> graph_test.dist |
| 223 | [0] |
| 224 | >>> graph_test.par |
| 225 | [-1] |
| 226 | >>> graph_test.adjList |
| 227 | {} |
| 228 | """ |
| 229 | self.adjList = {} # To store graph: u -> (v,w) |
| 230 | self.num_nodes = num # Number of nodes in graph |
| 231 | # To store the distance from source vertex |
| 232 | self.dist = [0] * self.num_nodes |
| 233 | self.par = [-1] * self.num_nodes # To store the path |
| 234 | |
| 235 | def add_edge(self, u, v, w): |
| 236 | """ |
| 237 | Add edge going from node u to v and v to u with weight w: u (w)-> v, v (w) -> u |
| 238 | |
| 239 | Examples: |
| 240 | >>> graph_test = Graph(1) |
| 241 | >>> graph_test.add_edge(1, 2, 1) |
| 242 | >>> graph_test.add_edge(2, 3, 2) |
| 243 | >>> graph_test.adjList |
| 244 | {1: [(2, 1)], 2: [(1, 1), (3, 2)], 3: [(2, 2)]} |
| 245 | """ |
| 246 | # Check if u already in graph |
| 247 | if u in self.adjList: |
| 248 | self.adjList[u].append((v, w)) |
| 249 | else: |
| 250 | self.adjList[u] = [(v, w)] |
| 251 | |
| 252 | # Assuming undirected graph |
| 253 | if v in self.adjList: |
| 254 | self.adjList[v].append((u, w)) |
| 255 | else: |
| 256 | self.adjList[v] = [(u, w)] |
| 257 | |
| 258 | def show_graph(self): |
| 259 | """ |
| 260 | Show the graph: u -> v(w) |
| 261 | |
| 262 | Examples: |
| 263 | >>> graph_test = Graph(1) |
| 264 | >>> graph_test.add_edge(1, 2, 1) |
| 265 | >>> graph_test.show_graph() |
| 266 | 1 -> 2(1) |
| 267 | 2 -> 1(1) |
| 268 | >>> graph_test.add_edge(2, 3, 2) |
| 269 | >>> graph_test.show_graph() |
| 270 | 1 -> 2(1) |