Search code examples
pythonnetworkx

Implementing DFS for networkX graph traversal

I have implemented DFS to print out the path from one tube station to another in a networkX graph for this data:

enter image description here

def dfs(nxobject, initial, goal, compute_exploration_cost=False, reverse=False):

    frontier = [{'label':initial, 'parent':None}]  
    explored = {initial}
    number_of_explored_nodes = 1 

    while frontier:
        node = frontier.pop() 
        number_of_explored_nodes += 1
        if node['label']==goal:
            if compute_exploration_cost:
                print('number of explorations = {}'.format(number_of_explored_nodes))
            return node

        neighbours = reversed(list(nxobject.neighbors(node['label']))) if reverse else nxobject.neighbors(node['label'])
        for child_label in neighbours:

            child = {'label':child_label, 'parent':node}
            if child_label not in explored:
                frontier.append(child) # added to the right of the list, so it is a LIFO
                explored.add(child_label)      
    return None

import networkx as nx
import pandas as pd

data = pd.read_csv('tubedata.csv',header=None)

edgelist = data.apply(lambda x: (x[0],x[1],x[3]),axis=1).to_list()

G = nx.DiGraph()
G.add_weighted_edges_from(edgelist)

However, when I call the dfs method, I keep getting None:

solution = dfs(G, 'Euston', '"Victoria"')

The output should be as:

['Euston', 'WarrenStreet', 'OxfordCircus', 'GreenPark', 'Victoria']

Any suggestions? Thanks.

Solution

  • Remove double quotes on '"Victoria"':

    >>> dfs(G, 'Euston', 'Victoria')
{'label': 'Victoria',
 'parent': {'label': 'Green Park',
  'parent': {'label': 'Piccadilly Circus',
   'parent': {'label': 'Leicester Square',
    'parent': {'label': 'Covent Garden',
     'parent': {'label': 'Holborn',
      'parent': {'label': 'Russell Square',
       'parent': {'label': "King's Cross St. Pancras",
        'parent': {'label': 'Euston', 'parent': None}}}}}}}}}

    But you can use nx.shortest_path:

    >>> nx.shortest_path(G, 'Euston', 'Victoria')
['Euston', 'Warren Street', 'Oxford Circus', 'Green Park', 'Victoria']