# Modified BFS code optimizations

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]]:
['bandwidth']

updated_cost = ((existing_cost if (existing_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]]:

# 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 == incoming_path):
if (existing_path > incoming_path):
if (existing_path >= incoming_path):
return 1
elif (existing_path < incoming_path):
return -1
else:
pf_logger.error("This is an outcome " +
"that should not be encountered")

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

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

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

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

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

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

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

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

• 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. – smac89 Feb 25 '14 at 6:18

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 >= incoming_path):
return 1
elif (existing_path < incoming_path):
return -1
else:
pf_logger.error("This is an outcome that should not be encountered")


should be :

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


which could be :

        return 1 if (existing_path >= incoming_path) else -1


Also :

        if ((existing_path > incoming_path) or
(existing_path > incoming_path) or
(existing_path > incoming_path)):
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.

• 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. – adwaraki Feb 25 '14 at 20:25
• @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 – Malachi Feb 25 '14 at 20:39
• @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? – adwaraki Feb 25 '14 at 21:17
• 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 – Malachi Feb 25 '14 at 21:30
• @Malachi: Got it. Will do from next time. – adwaraki Feb 26 '14 at 0:35