\r\n\r\nimport matplotlib.pyplot as plt\r\nimport networkx as nx\r\n\r\n# Populate the graph...\r\nmap_graph = nx.Graph()\r\n\r\nmap_graph.add_edge('Issaquah','Bellevue', weight=0.11 )\r\nmap_graph.add_edge('Bellevue','Kirkland', weight=0.05 )\r\nmap_graph.add_edge('Bellevue','Redmond', weight=0.06 )\r\nmap_graph.add_edge('Kirkland','Redmond', weight=0.24 )\r\nmap_graph.add_edge('Bellevue','Seattle', weight=0.01 )\r\nmap_graph.add_edge('Renton','Seattle', weight=0.03 )\r\nmap_graph.add_edge('Renton','Bellevue', weight=0.48 )\r\n\r\n# Determine the layout of points in the graph. Some other layouts that \r\n# would work here are spring_layout, shell_layout, and random_layout \r\npos = nx.circular_layout( map_graph ) # Sets positions for nodes\r\n\r\n# Put \"dots\" down for each node \r\nnx.draw_networkx_nodes( map_graph, pos, node_size=700)\r\n\r\n# Attaches Labesl to each node \r\nnx.draw_networkx_labels( map_graph, pos, font_size=14, font_family='sans-serif')\r\n\r\nmap_edges = [(u,v) for (u, v, d) in map_graph.edges(data=True) ]\r\n\r\nnx.draw_networkx_edges( map_graph,\r\n pos, # Spring\r\n map_edges, # List of edges \r\n width=5, alpha=0.5, edge_color='b', style='dashed' )\r\n\r\nplt.axis('off')\r\nplt.show()\r\n<\/CODE>\r\n<\/pre>\nThe plotted graph looks something like this. <\/p>\n
![\"Screen](\"https:\/\/www.hhhh.org\/joeboy\/blog\/wp-content\/uploads\/2018\/04\/Screen-Shot-2018-04-29-at-5.01.30-PM.png\")
<\/a><\/p>\nOne of the things I want from a graph library is the standard graph algorithms – like finding me the shortest path between nodes, or testing for the presence of a path at all. So for example to find the shortest path from Issaquah to Renton we could add the following code to the example above?:<\/p>\n
\r\n\r\n# Generates the shortest path - but since there could be more than \r\n# one of them what you get back is a \"generator\" from which you \r\n# need to pluck the shortest path. \r\na_shortest_path = nx.all_shortest_paths(map_graph, source='Issaquah', target='Renton') \r\n\r\nprint( [p for p in a_shortest_path] ) \r\n<\/CODE>\r\n<\/pre>\nThe added code will give the path [[‘Issaquah’, ‘Bellevue’, ‘Renton’]]<\/CODE>, which is the shortest path by number of edges traversed. To obtain the shortest path by edge weight we can use dijkstras like so:<\/p>\n
\na_shortest_path = nx.dijkstra_path(map_graph, ‘Issaquah’, ‘Renton’)
\nprint( a_shortest_path )
\n<\/CODE><\/p>\nWhich gives the path: [‘Issaquah’, ‘Bellevue’, ‘Seattle’, ‘Renton’]<\/CODE><\/p>\nThe problem is that this implementation of dijkstra’s fails when a path is not present between the origin and destination nodes. So for example if we add a disconnected vertex with no edges like below, searches on a path to that vertex will cause the call to fail. <\/p>\n
![\"Screen](\"https:\/\/www.hhhh.org\/joeboy\/blog\/wp-content\/uploads\/2018\/04\/Screen-Shot-2018-04-29-at-8.15.15-PM.png\")
<\/a><\/p>\n![\"Screen](\"https:\/\/www.hhhh.org\/joeboy\/blog\/wp-content\/uploads\/2018\/04\/Screen-Shot-2018-04-29-at-9.49.43-PM.png\")
<\/a><\/p>\n