Dictionary best data structure for train routes?

by

I will go against the grain — and say that a straight flat dict is not the best for this.

Let’s say you have 100 stops and multiple routes that are non-alphabetical and non-numeric. Think the Paris subway:

Paris Subway

Now try and use a straight Python dict to calculate the time between FDR and La Fourche? That involves two or more different routes and multiple options.

A tree or some form of graph is a better structure. A dict is fabulous for a 1 to 1 mapping; tree are better for a rich description of nodes that relate to each other. You would then use something like Dijkstra’s Algorithm to navigate it.

Since a nested dict of dicts or dict of lists IS a graph, it is easy to come up with a recursive example:

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in graph:
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths       

def min_path(graph, start, end):
    paths=find_all_paths(graph,start,end)
    mt=10**99
    mpath=[]
    print '\tAll paths:',paths
    for path in paths:
        t=sum(graph[i][j] for i,j in zip(path,path[1::]))
        print '\t\tevaluating:',path, t
        if t<mt: 
            mt=t
            mpath=path

    e1=' '.join('{}->{}:{}'.format(i,j,graph[i][j]) for i,j in zip(mpath,mpath[1::]))
    e2=str(sum(graph[i][j] for i,j in zip(mpath,mpath[1::])))
    print 'Best path: '+e1+'   Total: '+e2+'\n'  

if __name__ == "__main__":
    graph = {'A': {'B':5, 'C':4},
             'B': {'C':3, 'D':10},
             'C': {'D':12},
             'D': {'C':5, 'E':9},
             'E': {'F':8},
             'F': {'C':7}}
    min_path(graph,'A','E')
    min_path(graph,'A','D')
    min_path(graph,'A','F')

Prints:

    All paths: [['A', 'C', 'D', 'E'], ['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'D', 'E']]
        evaluating: ['A', 'C', 'D', 'E'] 25
        evaluating: ['A', 'B', 'C', 'D', 'E'] 29
        evaluating: ['A', 'B', 'D', 'E'] 24
Best path: A->B:5 B->D:10 D->E:9   Total: 24

    All paths: [['A', 'C', 'D'], ['A', 'B', 'C', 'D'], ['A', 'B', 'D']]
        evaluating: ['A', 'C', 'D'] 16
        evaluating: ['A', 'B', 'C', 'D'] 20
        evaluating: ['A', 'B', 'D'] 15
Best path: A->B:5 B->D:10   Total: 15

    All paths: [['A', 'C', 'D', 'E', 'F'], ['A', 'B', 'C', 'D', 'E', 'F'], ['A', 'B', 'D', 'E', 'F']]
        evaluating: ['A', 'C', 'D', 'E', 'F'] 33
        evaluating: ['A', 'B', 'C', 'D', 'E', 'F'] 37
        evaluating: ['A', 'B', 'D', 'E', 'F'] 32
Best path: A->B:5 B->D:10 D->E:9 E->F:8   Total: 32

More Related Contents:

  1. Connecting data in python to spreadsheets
  2. How can I add new keys to a dictionary?
  3. Why is the order in dictionaries and sets arbitrary?
  4. How do I convert two lists into a dictionary?
  5. Convert a Pandas DataFrame to a dictionary
  6. Convert nested Python dict to object?
  7. Passing a dictionary to a function as keyword parameters
  8. Return a default value if a dictionary key is not available
  9. How to filter a dictionary according to an arbitrary condition function?
  10. Convert Django Model object to dict with all of the fields intact
  11. Flatten nested dictionaries, compressing keys
  12. Nested dictionary to multiindex dataframe where dictionary keys are column labels
  13. Comparing Python dictionaries and nested dictionaries
  14. Python “extend” for a dictionary
  15. Convert dictionary entries into variables [duplicate]
  16. Creating a list of dictionaries with same keys? [duplicate]
  17. Is there a ‘multimap’ implementation in Python?
  18. Subclassing dict: should dict.__init__() be called?
  19. Append a dictionary to a dictionary [duplicate]
  20. Why is a class __dict__ a mappingproxy?
  21. Check if a given key already exists in a dictionary and increment it
  22. How can I use a dictionary to do multiple search-and-replace operations? [duplicate]
  23. How to get count dict of items but maintain the order in which they appear?
  24. Only add to a dict if a condition is met
  25. Accepting a dictionary as an argument with argparse and python [duplicate]
  26. Getting the difference (delta) between two lists of dictionaries
  27. Python: iterating over list vs over dict items efficiency
  28. How to synchronize a python dict with multiprocessing
  29. Python Accessing Values in A List of Dictionaries
  30. morse code to english python3

Leave a Comment