Shortest path routing/Catalogs/Dijkstra59.py

The metadata subpage is missing. You can start it via filling in this form or by following the instructions that come up after clicking on the [show] link to the right.

Do you see this on PREVIEW? then SAVE! before following a link. To find out more about the use of metadata for the management of Citizendium pages, see CZ:Metadata. You may see this box for one of two reasons. Either: A - New page has been created, or subpages template was added to an existing page B - Cluster move is in progress Click either the A or B link for further instructions. [Feel free to recommend improvements to the text or links in this template] A - For a New Cluster use the following directions Subpages format requires a metadata page. Using the following instructions will complete the process of creating this article's subpages. Click the blue "metadata template" link below to create the page. On the edit page that appears paste in the article's title across from "pagename =". You might also fill out the checklist part of the form. Ignore the rest. For background, see Using the Subpages template Don't worry--you'll get the hang of it right away. Remember to hit Save! the "metadata template". However, you can create articles without subpages. Just delete the {{subpages}} template from the top of this page and this prompt will disappear. :) Don't feel obligated to use subpages, it's more important that you write sentences, which you can always do without writing fancy code. [Feel free to recommend improvements to the text or links in this template] B - For a Cluster Move use the following directions The metadata template should be moved to the new name as the first step. Please revert this move and start by using the Move Cluster link at the top left of the talk page. The name prior to this move can be found at the following link. [Feel free to recommend improvements to the text or links in this template]

---

This is an annotated version of the program in Shortest path routing, with notes for students not yet familiar with Python. You can run this code using an interpreter from python.org, version 3.0 or later.

# dijkstra59v05_A.py            Dijkstra's Algorithm                DMQ 12/23/09
'''
Use Dijkstra's algorithm to compute the shortest paths from a given source node
to all other nodes in a network. Links are bi-directional, with the same
distance in either direction.  Distance can be any measure of cost.

Python Notes:
This program will make good use of Python's standard data structures - sets,
lists, and dictionaries. Sets have curly brackets, and lists have square
brackets.  Tuples have parentheses.  Tuples are immutable lists.  They behave
like lists, except there are no methods to change the items in a tuple.
~'''

# Example from Figure 1 (8 nodes, 11 links)
nodeset = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}

linklist = [('A', 'B', 2), ('B', 'C', 7), ('C', 'D', 3), # (node,node,distance)
            ('B', 'E', 2), ('E', 'F', 2), ('F', 'C', 3),
            ('A', 'G', 6), ('G', 'E', 1), ('G', 'H', 4),
            ('F', 'H', 2), ('H', 'D', 2),               ]

INF = int(1e9)  # larger than any possible path
'''
The strategy is to start at the source node, send probes to each of its adjacent
nodes, pick the node with the shortest path from the source, and make that the
new working node.  Send probes from the new working node, pick the next shortest
path, and make that the next working node.  Continue selecting the shortest
possible path until every every node in the network has been selected.

Figure 1 shows the first few steps in our example network. Labels on each node
show its distance from the source, and the previous node on the path from which
that distance was computed.  As new nodes are first probed, they are added to a
working set, shown with a darkened open circle.  After each probe cycle, we look
at the entire set of working nodes.  The node with the shortest path is moved to
a final set, shown with a solid circle.  Figure 1b shows the situation after the
first probes from node 'A', with one node in the final set, and two nodes in the
working set.

The labels on nodes in the working set are tentative.  They will be replaced if
another probe arrives with a shorter total path.  Figure 1d shows node G getting
an update of its label after a probe from node E.  The updates at a node stop
when no other working set node has a shorter path.  This is the proof that the
method works.  The node with the shortest path in a working set can never get
any shorter, because subsequent probes can only come from other working nodes,
and those paths are already at least as long.  There are no negative links.

Figure 1i shows the final tree for node A.  The light dotted lines are links not
used in any shortest path from node A.  They might be used in another tree,
however.  Each node in a network can compute its own shortest path tree, given
the linklist for the entire network.
~'''

def get_LSDB(nodeset, linklist):
    '''Create a Link State Database to quickly look up the adjacent nodes for
any given node.

>>> get_LSDB(nodeset, linklist)
{'A': {('B', 2), ('G', 6)}, 'C': {('B', 7), ('F', 3), ('D', 3)}, \
'B': {('C', 7), ('E', 2), ('A', 2)}, 'E': {('B', 2), ('G', 1), ('F', 2)}, \
'D': {('H', 2), ('C', 3)}, 'G': {('A', 6), ('E', 1), ('H', 4)}, \
'F': {('H', 2), ('E', 2), ('C', 3)}, 'H': {('G', 4), ('D', 2), ('F', 2)}}

Python Notes:
This database is implemented as a Python dictionary, a set of {key: value}
pairs.  The keys in this case are just the names from the nodeset.  The values
are the set of nodes connected to each key node.  Notice how easily we can nest
data structures in Python.  Here we have a dictionary of sets of tuples.

The multiline string (enclosed in triple quotes) at the start of each module or
function is called the "docstring".  It is used in generating automatic
documentation.  The example code snippets are called "doctests".  They look just
like what you will see when you call the function from an interactive prompt
(>>>).  The example above was created using a copy-and-paste from an interactive
session (adding a few \ end-of-line escapes to make the single line of real
output appear within the margins of our docstring).

Doctests are not only excellent ways to show what your function does, but they
also serve as unit tests, running automatically and alerting you when some
change you just made breaks the existing doctests.

    ~'''
    LSDB = {n:set() for n in nodeset} # start with empty set for each node
    for (n1, n2, d) in linklist:
        LSDB[n1].add((n2, d))
        LSDB[n2].add((n1, d))
        
    return LSDB

'''
Python notes:
The code above shows a number of elegant features of Python.  The syntax to
create a dictionary of sets reads very much like set notation in mathematics {a
dictionary with an empty set for each node in nodeset}.  See footnote [1].

When you need to assign items in a structure, each to a simple variable, you can
do it all at once by putting the variable names in a tuple on the left side of
the assignment operator.  Each item from linklist is a triple, and it is
automatically unpacked and assign to the names in the triple on the left.

Finally, notice how easily we can add complex structures to a dictionary or set,
without a mind-boggling set of indices on multiple levels.  The add method adds
one item to a set.  The inner parens make a pair of items into one.

At this point, you may be thinking, lets just do it in C.  Trust me.  Once you
feel comfortable with Python's basic data structures, the four lines above will
be very intuitive, and you will avoid having to wrestle with all the low-level
details when you need a special structure like we have for our LSDB.
~'''

def build_tree(src, LSDB):
    '''Given a source node and a Link State Database for the network, return a
table with two values for each node - the distance on the shortest path from the
source to that node, and the name of the last node on that path before the final
node.  Saving the previous node makes it easy to re-construct an entire path,
from any leaf to the root of the tree.

>>> build_tree('A', LSDB)
{'A': ('A', 0), 'C': ('B', 9), 'B': ('A', 2), 'E': ('B', 4), \
'D': ('H', 10), 'G': ('E', 5), 'F': ('E', 6), 'H': ('F', 8)}

    ~'''
    # Current working node
    wrk = src
    
    # Nodes in the working set and final set, saved as dictionaries.
    #   {key: value} = {nodename: (previous node, distance from src) }
    Wset = {}; Fset = {}
    Wset[wrk] = (wrk, 0)            # {'A': ('A', 0)}

    while Wset:  # loop until the work set is empty
  
        # Select next wrk node
        dist = INF
        for node in Wset:           # Find the shortest distance in the
            (prev, d) = Wset[node]  # working set, and make that node the
            if d < dist:            # new working node. The distance of that
                dist = d            # node will never get smaller.
                wrk = node
        
        # Move the new working node to the final set.        
        Fset[wrk] = Wset[wrk]
        del Wset[wrk]
        last = wrk                  # last node before end of path

        # Expand the work set
        for (n, d) in LSDB[wrk]:      # Probe the nodes adjacent to wrk      

            new_dist = dist + d          # probe distance
            
            if n in Fset:
                continue                 # skip this node, already finalized
            
            elif (n in Wset) and (new_dist >= Wset[n][1]):
                continue                 # skip this node, probe too long           

            else:  # Add new node to working set, or update existing node
                Wset[n] = (last, new_dist)
    
    return Fset

def build_RT(src, LSDB):
    '''Given a source node and a Link State Database for the network, return a
table with three values for each node - the distance on the shortest path from
the source to that destination node, and the names of the first and last nodes
on the path, not including the endpoints.  The first node is needed in a routing
table.  The last node is needed to construct a tree with src at the root.

>>> build_RT('A', LSDB)
{'A': ('A', 'A', 0), 'C': ('B', 'B', 9), 'B': ('B', 'A', 2), \
'E': ('B', 'B', 4), 'D': ('B', 'H', 10), 'G': ('B', 'E', 5), \
'F': ('B', 'E', 6), 'H': ('B', 'F', 8)}

    ~~'''
    # Current working node
    wrk = src
    
    # Nodes in the working set and final set, saved as dictionaries.
    #   {key: value} = {nodename: (first, last, distance from src)}
    Wset = {}; Fset = {}

    # Special setup for first step
    Fset[wrk] = (wrk, wrk, 0)      # {'A': ('A', 'A', 0)}
    for (n, d) in LSDB[wrk]:
        first = n                  # first step on the new route
        last = wrk
        Wset[n] = (first, last, d) # {'B': ('B', 'A', 2), 'G': ('G', 'A', 6)}

    while Wset:  # loop until the working set is empty
  
        # Select next wrk node
        dist = INF
        for node in Wset:           # Find the shortest distance in the
            (first, last, d) = Wset[node]  # working set, and make that node
            if d < dist:            # the new working node. The distance of
                dist = d            # that node will never get smaller.
                wrk = node
        
        # Move the new working node to the final set        
        Fset[wrk] = Wset[wrk]
        del Wset[wrk]
        # Update first and last hops
        first = Fset[wrk][0]
        last = wrk

        # Expand the work set
        for (n, d) in LSDB[wrk]:      # Probe the nodes adjacent to wrk      

            new_dist = dist + d          # probe distance
            
            if n in Fset:
                continue                 # skip this node, already finalized
            
            elif (n in Wset) and (new_dist >= Wset[n][2]):
                continue                 # skip this node, probe too long           

            else:  # Add new node to working set, or update existing node
                Wset[n] = (first, last, new_dist)
    
    return Fset

def get_path(dest, RT):
    '''Given destination node and a Routing Table, return the shortest path
from the root of the tree to dest, and the total distance along that path.

>>> get_path('D', RT)
(['A', 'B', 'E', 'F', 'H', 'D'], 10)

    ~'''
    wrk = dest              # Work backward from the destination node.
    last = RT[wrk][1]       # one step back
    path = [wrk]
    dist = RT[wrk][2]
    
    while wrk != last:      # root has no step back (wrk = last)
        path.insert(0, last)    # insert at beginning of list
        wrk = last
        last = RT[wrk][1]

    return path, dist


if __name__ == '__main__':  # Test Bench setup

    class G: pass  # Global variables for diagnostics
##    G.numloops = 0                                                      ###
##    while Wset:  # loop until the working set is empty
####        print(len(Wset), end=' ')                                       ###
####        print(len(Wset), Wset)                                          ###
####        G.numloops += len(Wset)                                         ###
    
# Example 1 - small network
    nodeset = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}

    linklist = [('A', 'B', 2), ('B', 'C', 7), ('C', 'D', 3),
                ('B', 'E', 2), ('E', 'F', 2), ('F', 'C', 3),
                ('A', 'G', 6), ('G', 'E', 1), ('G', 'H', 4),
                ('F', 'H', 2), ('H', 'D', 2),               ]

    LSDB = get_LSDB(nodeset, linklist)  # Link State Database

    RT = build_RT('A', LSDB)            # Routing Table

# Example 2 - bigger networks
    from random import randint  # for generating random integers
    from time import time       # for timing tests

    for size in range(500, 1500, 500):
    
        t0 = time()
        nodeset1 = set(range(size))
        t1 = time()
        
        linklist1 = []
        for n1 in nodeset1:
            for lnk in range(3):   # 3 links per node
                n2 = randint(0, size-1)  # anywhere in network
                if n1 == n2: continue         # no link to self
                distance = abs(n1 - n2)
                link = (n1, n2, distance)
                if (n1, n2, distance) in linklist1: continue  # no duplicates
                if (n2, n1, distance) in linklist1: continue  
                linklist1.append(link)
        t2 = time()
        
        LSDB1 = get_LSDB(nodeset1, linklist1)
        t3 = time()

        RT1 = build_RT(1, LSDB1)
        t4 = time()

        print (size, t4-t3, len(linklist1))

    
    from doctest import testmod
    testmod(verbose=True)

Footnotes

[1] Set-builder notation