patternpythonMinor

Modified BFS code optimizations

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codemodifiedbfsoptimizations

Problem

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

Code needs to be optimized for speed (so I need to make sure I am doing things the good, Pythonic way)

Any alterations to code that can cut down the LoC.

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

Param

Solution

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  i2) else 0
    elif (e0 > i0):
        if (e1 > i1):
            if (e2 > i2):
                return 1    
            elif (e2 == i2):
                return -1    
            else:
                assert(e2  i2) else 0
    else:
        assert (e0  i1):
            assert(e2 > i2)
            return 1        
        elif (e1  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.

Code Snippets

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[2] >= incoming_path[2]):
            return 1
        else:
            return -1

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

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

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

Context

StackExchange Code Review Q#42708, answer score: 4

Revisions (0)

No revisions yet.