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
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")
