5
\$\begingroup\$

I need some help reviewing this code in terms of making as fast as possible. This is a modified version of BFS that does quite a bit of processing on the side.

Use case:

I have a large graph (probably tens of thousands of nodes). Every edge is defined by three parameters currently - bandwidth, latency and cost. I need to compute a list of pareto optimal paths from source to destination (for simplicity sake, let us assume that BFS runs to completion). The way I am doing this is computing the paths to each neighbor from the current node as BFS runs and checking if any paths exist on the neighbor that are optimal as compared to the current path (check definition of optimality below). I then update the node's path tables accordingly.

Optimality Criteria

A pareto optimal path for my case is defined as one that is non-dominated by ANY other path in consideration. For our case, non-dominated means that a path should have more bandwidth, lesser latency and lesser cost than the one it is being compared to. If a decision cannot be made, we keep both paths.

What is important

  1. Code needs to be optimized for speed (so I need to make sure I am doing things the good, Pythonic way)
  2. Any alterations to code that can cut down the LoC.
  3. I have used the NetworkX code base, so any use of short hand methods are the same as what NetworkX supports. (I will provide my versions of graph.py and multigraph.py if required, though they are essentially stripped down versions of the NetworkX classes)

Observations

I know that there is repeated code, but I haven't figured out how to refactor it correctly. Inputs are welcome. Also, the big path comparison method at the end is a set of if-else blocks. Is there a better way to do this?

Code

def bfs_pathfinder(graph, source, destination):
    """ This method computes the pareto optimal paths during
    a BFS run of the graph. When the BFS run completes, the 
    destination will have a list of optimal paths in its
    table

    Parameters
    ----------
    graph: required
        This is the topology graph (or copy) to be operated on
    source, destination: required
        The source and destination vertices in the service request

    Returns
    -------
    A list of optimal path options

    Raises
    ------
    AlgorithmError on any error encountered during operation

    """

    initial_path, path_bound = astar.astar_path(graph, source, 
                                                destination, None)

    pf_logger.debug("Initial bound on path to destination : " + 
                   ', '.join(map(str, path_bound)))
    graph.node_list[source]['predecessor'] = None
    #---------------------------------------------------------------------- 
    # Set the initial AStar path as the bound on the destination node, 
    # use the whole path as the key. These are the only two types that 
    # can be used as a predecessor, a string for the initial path
    # and a vertex object for every other partial path created on the BFS 
    # search
    #---------------------------------------------------------------------- 
    graph.node_list[destination]['path_table'][(initial_path)] =         
        (path_bound)

    pf_logger.debug("Start Node : " + str(source))
    pf_logger.debug("End Node : " + str(destination))

    bfs_queue = deque(source)
    while bfs_queue:
        current_vertex = bfs_queue.popleft()
        try:
            # Calculate the new path for each existing path on the current 
                vertex - 
            # path - existing path to the current vertex
            # existing_cost - path cost to current vertex using 'path'
            # for path, existing_cost in graph.node_list[current_vertex]
            # ['path_table'].items():
            # entry = [nbrs for nbrs in G[current_vertex] - list of 
            # neighbors
            # G[current_vertex][entry][attr] - outgoing edge attributes from 
            # current vertex
            for neighbor in [nbrs for nbrs in graph[current_vertex]]:
                link_bandwidth = graph[current_vertex][neighbor]
                                ['bandwidth']
                link_latency = graph[current_vertex][neighbor]['latency']
                link_cost = graph[current_vertex][neighbor]['cost']

                updated_cost = ((existing_cost[0] if (existing_cost[0] < 
                                link_bandwidth) else link_bandwidth, 
                                (existing_cost[1] + link_latency), 
                                (existing_cost[2] + link_cost))
                # Check if node hasn't been visited at all, or has been 
                # queued for processing
                if (graph.node_list[neighbor]['color'] == 'White'):
                    # First, set color to 'Gray' to indicate it is queued, 
                    # then update 'path_table'
                    graph.node_list[neighbor]['color'] = 'Gray'
                    graph.node_list[neighbor]['predecessor'] = 
                        current_vertex
                    updated_path = list(path)
                    updated_path.append(current_vertex)
                    graph.node_list[neighbor]['path_table']                        
                        [tuple(updated_path)] = updated_cost
                    bfs_queue.append(neighbor)

                elif (graph.node_list[neighbor]['color'] == 'Gray'):
                    # If, by chance the queued neighbor doesn't have a 
                    # 'path_table' AT ALL, which normally should not happen
                    if not graph.node_list[neighbor]['path_table']:
                        updated_path = list(path)
                        updated_path.append(current_vertex)
                        graph.node_list[neighbor]['path_table']
                            [tuple(updated_path)] = updated_cost
                    # In the eventuality that the neighbor already has 
                    # calculated paths in the 'path_table',
                    # we need to compare the updated_path to the existing 
                    # ones on the node and update accordingly.
                    # This is taken care of by the _path_comparison method 
                    else:
                        for current_optimal_path, current_optimal_parameters 
                        in graph.node_list[neighbor]['path_table'].items():
                            # See _path_comparison for return value 
                            # indications
                            insert_decision = 
                                _path_comparison(current_optimal_parameters, 
                                                    updated_cost)
                            if (insert_decision == 1):
                                updated_path = list(path)
                                updated_path.append(current_vertex)
                                graph.node_list[neighbor]['path_table']
                                    [tuple(updated_path)] = updated_cost
                                del graph.node_list[neighbor]['path_table']
                                    [current_optimal_path]
                            elif (insert_decision == 0):
                                pass
                            elif (insert_decision == -1):
                                updated_path = list(path)
                                updated_path.append(current_vertex)
                                graph.node_list[neighbor]['path_table']
                                    [tuple(updated_path)] = updated_cost
                                continue
                            else:
                                pf_logger.error("This is an unaccounted 
                                                outcome.Re-check outcomes.")
                                raise AlgorithmError("This is an unaccounted 
                                                     outcome for path 
                                                     comparison.")
                else:
                    # Vertex is black and has already been evaluated. Skip 
                    # node (hopefully this is what controls
                    # infinite looping in the BFS traversal
                    pf_logger.debug("Vertex is colored black. Skipping 
                                    node.")
                    continue

            pf_logger.debug("All edges explored. Coloring " + 
                            str(current_vertex) + " black")
            graph.node_list[current_vertex]['color'] = 'Black'

    except NameError:
        # This means that the node doesn't have any existing 'path_table' 
        # entries
        for neighbor in [nbrs for nbrs in graph[current_vertex]]:
            link_bandwidth = graph[current_vertex][neighbor]['bandwidth']
            link_latency = graph[current_vertex][neighbor]['latency']
            link_cost = graph[current_vertex][neighbor]['cost']

            updated_cost = (link_bandwidth, link_latency, link_cost)
            # Check if node hasn't been visited at all, or has been queued 
            # for processing
            if (graph.node_list[neighbor]['color'] == 'White'):
                # First, set color to 'Gray' to indicate it is queued, then 
                # update 'path_table'
                graph.node_list[neighbor]['color'] = 'Gray'
                graph.node_list[neighbor]['predecessor'] = current_vertex
                updated_path = list(path)
                updated_path.append(current_vertex)
                graph.node_list[neighbor]['path_table'][tuple(updated_path)] 
                    = updated_cost
                bfs_queue.append(neighbor)

            elif (graph.node_list[neighbor]['color'] == 'Gray'):
                # If, by chance the queued neighbor doesn't have a 
                # 'path_table' AT ALL,
                # which normally should not happen
                if not graph.node_list[neighbor]['path_table']:
                    updated_path = list(path)
                    updated_path.append(current_vertex)
                    graph.node_list[neighbor]['path_table']
                        [tuple(updated_path)] = updated_cost
                # In the eventuality that the neighbor already has 
                # calculated paths in the 'path_table',
                # we need to compare the updated_path to the existing ones 
                # on the node and update accordingly.
                # This is taken care of by the _path_comparison method 
                else:
                    for current_optimal_path, current_optimal_parameters in 
                        graph.node_list[neighbor]['path_table'].items():
                        # See _path_comparison for return value indications
                        insert_decision = 
                            _path_comparison(current_optimal_parameters, 
                                            updated_cost)
                        if (insert_decision == 1):
                            updated_path = list(path)
                            updated_path.append(current_vertex)
                            graph.node_list[neighbor]['path_table']
                                [tuple(updated_path)] = updated_cost
                            del graph.node_list[neighbor]['path_table']
                                [current_optimal_path]
                        elif (insert_decision == 0):
                            pass
                        elif (insert_decision == -1):
                            updated_path = list(path)
                            updated_path.append(current_vertex)
                            graph.node_list[neighbor]['path_table']
                                [tuple(updated_path)] = updated_cost
                            continue
                        else:
                            pf_logger.error("This is an unaccounted 
                                            outcome.Re-check outcomes.")
                            raise AlgorithmError("This is an unaccounted 
                                                outcome for path 
                                                comparison.")
            else:
                # Vertex is black and has already been evaluated. Skip node 
                # (hopefully this is what controls
                # infinite looping in the BFS traversal
                pf_logger.debug("Vertex is colored black. Skipping node.")
                continue

    pf_logger.debug("All edges explored. Coloring " + str(current_vertex) + 
                    " black")
    graph.node_list[current_vertex]['color'] = 'Black'

#--------------------------------------------------------------------------- 
# This method compares an existing path on a node with a newly calculated
# partial path from a different predecessor.
# Use an insertFlag to figure out the scenario of Solution A vs Solution B
# 1. insert_decision = 0 -> nothing to insert, keep solution A
# 2. insert_decision = 1 -> Solution B is better. Add B, remove Solution A
# 3. insert_decision = -1 -> Both are optimal. Keep Solution A, add Solution 
#                             B
#---------------------------------------------------------------------------
def _path_comparison(existing_path, incoming_path):

    if (existing_path[0] == incoming_path[0]): 
        if (existing_path[1] > incoming_path[1]):
            if (existing_path[2] >= incoming_path[2]):
                return 1    
            elif (existing_path[2] < incoming_path[2]):
                return -1
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

        if (existing_path[1] < incoming_path[1]):
            if (existing_path[2] <= incoming_path[2]):
                return 0
            elif (existing_path[2] > incoming_path[2]):
                return -1
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

        if (existing_path[1] == incoming_path[1]):
            if (existing_path[2] > incoming_path[2]):
                return 1    
            elif (existing_path[2] <= incoming_path[2]):
                return 0
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

    if (existing_path[0] > incoming_path[0]):
        if (existing_path[1] > incoming_path[1]):
            if (existing_path[2] > incoming_path[2]):
                return 1    
            elif (existing_path[2] == incoming_path[2]):
                return -1    
            elif (existing_path[2] < incoming_path[2]):
                return 0
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

        if (existing_path[1] < incoming_path[1]):
            if ((existing_path[2] < incoming_path[2]) or
                 (existing_path[2] == incoming_path[2]) or
                 (existing_path[2] > incoming_path[2])):
                return 0
            else:   
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

        if (existing_path[1] == incoming_path[1]):
            if (existing_path[2] > incoming_path[2]):
                return -1    
            elif (existing_path[2] <= incoming_path[2]):
                return 0
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

    if (existing_path[0] < incoming_path[0]):
        if (existing_path[1] > incoming_path[1]):
            if ((existing_path[2] > incoming_path[2]) or
                 (existing_path[2] > incoming_path[2]) or
                 (existing_path[2] > incoming_path[2])):
                return 1    
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

        if (existing_path[1] < incoming_path[1]):
            if (existing_path[2] == incoming_path[2]):
                return -1
            elif (existing_path[2] < incoming_path[2]):
                return 0
            elif (existing_path[2] > incoming_path[2]):
                return 1
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")

        if (existing_path[1] == incoming_path[1]):
            if (existing_path[2] < incoming_path[2]):
                return -1    
            elif (existing_path[2] >= incoming_path[2]):
                return 1
            else:
                pf_logger.error("This is an outcome " + 
                               "that should not be encountered")
\$\endgroup\$
1
  • \$\begingroup\$ Wow...that is a lot of code. I won't even worry about the bfs implementation if I were you, instead I would be looking for a way to make that path comparison code have less code in it. \$\endgroup\$
    – smac89
    Feb 25, 2014 at 6:18

1 Answer 1

4
\$\begingroup\$

I'd suggest having a look at Why Your Python Runs Slow. Part 1: Data Structures as it seems to apply to your code.


Your _path_comparison is amazingly convoluted. Among other things, it involves unreachable code.

        if (existing_path[2] >= incoming_path[2]):
            return 1
        elif (existing_path[2] < incoming_path[2]):
            return -1
        else:
            pf_logger.error("This is an outcome that should not be encountered")

should be :

        if (existing_path[2] >= incoming_path[2]):
            return 1
        else:
            return -1

which could be :

        return 1 if (existing_path[2] >= incoming_path[2]) else -1

Also :

        if ((existing_path[2] > incoming_path[2]) or
             (existing_path[2] > incoming_path[2]) or
             (existing_path[2] > incoming_path[2])):
            return 1 

definitly looks wrong to me.

My re-written version of the code would be :

def _path_comparison(existing_path, incoming_path):
    e0,e1,e2 = existing_path 
    i0,i1,i2 = incoming_path
    if (e0 == i0): 
        if (e1 > i1):
            return 1 if (e2 >= i2) else -1
        elif (e1 < i1):
            return 0 if (e2 <= i2) else -1
        else:
            assert(e1 == i1)
            return 1 if (e2 > i2) else 0
    elif (e0 > i0):
        if (e1 > i1):
            if (e2 > i2):
                return 1    
            elif (e2 == i2):
                return -1    
            else:
                assert(e2 < i2)
                return 0
        elif (e1 < i1):
            return 0
        else:
            assert (e1 == i1)
            return -1 if (e2 > i2) else 0
    else:
        assert (e0 < i0)
        if (e1 > i1):
            assert(e2 > i2)
            return 1        
        elif (e1 < i1):
            if (e2 == i2):
                return -1
            elif (e2 < i2):
                return 0
            else:
                assert (e2 > i2)
                return 1
        else:
            assert (e1 == i1):
            return -1 (e2 < i2) else 1

If something was wrong before (which is likely to be the case), it is still wrong after my rewriting.

\$\endgroup\$
7
  • \$\begingroup\$ True that. It is convoluted in the sense that I went with the basic logic flow of evaluating triplet conditions. I had a flow-sheet for all the logic comparisons and just translated them as if-else blocks. This kind of help is what I was looking for. Thanks a ton. As for my data structures, they are the same as NetworkX uses. And given that NetworkX performs pretty well on large graph sets, I just wanted to make sure my code wasn't crappy, because I know the data structure usage is optimized. I did not want my usage to screw that up. \$\endgroup\$
    – adwaraki
    Feb 25, 2014 at 20:25
  • \$\begingroup\$ @adwaraki, if the answer isn't correct, state that in a comment, do not edit the code in the answer, let the Author do that \$\endgroup\$
    – Malachi
    Feb 25, 2014 at 20:39
  • \$\begingroup\$ @Malachi: He wasn't wrong in his answer. His answer transcribed my incorrect code correctly. I corrected mine from his comment and hence that renders the answer correctly incorrect? I thought it needed to be kept in sync? \$\endgroup\$
    – adwaraki
    Feb 25, 2014 at 21:17
  • \$\begingroup\$ so you changed your code after he reviewed and showed you what was wrong with it? you should have posted the new code as a new question \$\endgroup\$
    – Malachi
    Feb 25, 2014 at 21:30
  • 1
    \$\begingroup\$ @Malachi: Got it. Will do from next time. \$\endgroup\$
    – adwaraki
    Feb 26, 2014 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.