in libs/apls/apls.py [0:0]
def path_sim_metric(all_pairs_lengths_gt, all_pairs_lengths_prop,
control_nodes=[], min_path_length=10,
diff_max=1, missing_path_len=-1, normalize=True,
verbose=False):
"""
Compute metric for multiple paths.
Notes
-----
Assume nodes in ground truth and proposed graph have the same names.
Assume graph is undirected so don't evaluate routes in both directions
control_nodes is the list of nodes to actually evaluate; if empty do all
in all_pairs_lenghts_gt
min_path_length is the minimum path length to evaluate
https://networkx.github.io/documentation/networkx-2.2/reference/algorithms/shortest_paths.html
Parameters
----------
all_pairs_lengths_gt : dict
Dictionary of path lengths for ground truth graph.
all_pairs_lengths_prop : dict
Dictionary of path lengths for proposal graph.
control_nodes : list
List of control nodes to evaluate.
min_path_length : float
Minimum path length to evaluate.
diff_max : float
Maximum value to return. Defaults to ``1``.
missing_path_len : float
Value to assign a missing path. Defaults to ``-1``.
normalize : boolean
Switch to normalize outputs. Defaults to ``True``.
verbose : boolean
Switch to print relevant values to screen. Defaults to ``False``.
Returns
-------
C, diffs, routes, diff_dic
C is the APLS score
diffs is a list of the the route differences
routes is a list of routes
diff_dic is a dictionary of path differences
"""
diffs = []
routes = []
diff_dic = {}
gt_start_nodes_set = set(all_pairs_lengths_gt.keys())
prop_start_nodes_set = set(all_pairs_lengths_prop.keys())
t0 = time.time()
if len(gt_start_nodes_set) == 0:
return 0, [], [], {}
# set nodes to inspect
if len(control_nodes) == 0:
good_nodes = list(all_pairs_lengths_gt.keys())
else:
good_nodes = control_nodes
if verbose:
print("\nComputing path_sim_metric()...")
print("good_nodes:", good_nodes)
# iterate overall start nodes
for start_node in good_nodes:
if verbose:
print("start node:", start_node)
node_dic_tmp = {}
# if we are not careful with control nodes, it's possible that the
# start node will not be in all_pairs_lengths_gt, in this case use max
# diff for all routes to that node
# if the start node is missing from proposal, use maximum diff for
# all possible routes to that node
if start_node not in gt_start_nodes_set:
for end_node, len_prop in all_pairs_lengths_prop[start_node].items():
diffs.append(diff_max)
routes.append([start_node, end_node])
node_dic_tmp[end_node] = diff_max
return
paths = all_pairs_lengths_gt[start_node]
# CASE 1
# if the start node is missing from proposal, use maximum diff for
# all possible routes to the start node
if start_node not in prop_start_nodes_set:
for end_node, len_gt in paths.items():
if (end_node != start_node) and (end_node in good_nodes):
diffs.append(diff_max)
routes.append([start_node, end_node])
node_dic_tmp[end_node] = diff_max
diff_dic[start_node] = node_dic_tmp
continue
# else get proposed paths
else:
paths_prop = all_pairs_lengths_prop[start_node]
# get set of all nodes in paths_prop, and missing_nodes
end_nodes_gt_set = set(paths.keys()).intersection(good_nodes)
end_nodes_prop_set = set(paths_prop.keys())
missing_nodes = end_nodes_gt_set - end_nodes_prop_set
if verbose:
print("missing nodes:", missing_nodes)
# iterate over all paths from node
for end_node in end_nodes_gt_set:
len_gt = paths[end_node]
# skip if too short
if len_gt < min_path_length:
continue
# get proposed path
if end_node in end_nodes_prop_set:
# CASE 2, end_node in both paths and paths_prop, so
# valid path exists
len_prop = paths_prop[end_node]
else:
# CASE 3: end_node in paths but not paths_prop, so assign
# length as diff_max
len_prop = missing_path_len
if verbose:
print("end_node:", end_node)
print(" len_gt:", len_gt)
print(" len_prop:", len_prop)
# compute path difference metric
diff = single_path_metric(len_gt, len_prop, diff_max=diff_max)
diffs.append(diff)
routes.append([start_node, end_node])
node_dic_tmp[end_node] = diff
diff_dic[start_node] = node_dic_tmp
if len(diffs) == 0:
return 0, [], [], {}
# compute Cost
diff_tot = np.sum(diffs)
if normalize:
norm = len(diffs)
diff_norm = diff_tot / norm
C = 1. - diff_norm
else:
C = diff_tot
if verbose:
print("Time to compute metric (score = ", C, ") for ", len(diffs),
"routes:", time.time() - t0, "seconds")
return C, diffs, routes, diff_dic