IMP logo
IMP Reference Guide  2.21.0
The Integrative Modeling Platform
score_graph.py
1 """@namespace IMP.spatiotemporal.score_graph
2  Functions to traverse and score the spatiotemporal graphs.
3 """
4 
5 import numpy as np
6 
7 
8 def get_graph_as_dict(nodes):
9  """
10  converts a list of graphNode objects (nodes), which have been initiated
11  with scores and edges into a dictionary representation of a graph (graph).
12  Each node in the graph is a key, which returns edges in the next state.
13 
14  @param nodes: list of graphNode objects
15  @return graph: dictionary where each node is a key and the values are
16  the edges in the graph for that node
17  """
18  graph = {}
19 
20  for node in nodes:
21  graph[node] = node.get_edges()
22 
23  return graph
24 
25 
26 def find_all_paths(graph, start, end, path=[]):
27  """
28  Finds all paths between nodes, which already have edges drawn between them.
29 
30  @param graph: dictionary representation of the graph, acquired
31  in get_graph_as_dict()
32  @param start: graphNode, candidate for starting the graph
33  @param end: graphNode, candidate to end the graph
34  @param path: list of graphNodes on the path, which is defined recursively.
35  @return paths: list of all paths that exist between the starting node
36  and ending node
37  """
38 
39  path = path + [start]
40  if start == end:
41  return [path]
42  if start not in graph.keys():
43  return []
44  paths = []
45  for node in graph[start]:
46  if node not in path:
47  newpaths = find_all_paths(graph, node, end, path)
48  for newpath in newpaths:
49  paths.append(newpath)
50 
51  return paths
52 
53 
54 # Function to score a graph based on nodes, which has scores and edges,
55 # as well as keys, which is a list of the states visited
56 def score_graph(nodes, keys):
57  """
58  Function to score a graph based on nodes, which has scores and edges,
59  as well as keys, which is a list of the states visited. Note that all
60  edges must be drawn and scores must be added to nodes before calling
61  this function.
62 
63  @param nodes: list of graphNode objects, which has been initialized with
64  all weights and edges
65  @param keys: list of all ordered states (strings) visited along the graph.
66  Paths will be determined in sequential order passed to this
67  function.
68  @return all_paths: list of all paths through the graph. Each path is a
69  list of graphNode objects that correspond to the states visited
70  along the path.
71  @return path_prob: list of probabilities for each path, ordered in the
72  same order as all_paths
73  @return path_scores: list of tuples, where the first object is the path
74  (list of graphNode objects for each state along the trajectory),
75  and the second object is the score of the path, which can be used
76  to calculate the probability.
77  """
78  # nodes - graphNode object, which has been initialized with all
79  # weights and edges
80  # keys - Ordered list of all states. Paths will be determined in
81  # sequential order passed to this function.
82 
83  # Determine starting state and final state
84  time_start = keys[0]
85  time_end = keys[-1]
86 
87  # enumerate all paths by iterating over all possible starting and
88  # ending points
89  starting_nodes = [n for n in nodes if n.get_time() == time_start]
90 
91  # get mature pore
92  ending_nodes = [n for n in nodes if n.get_time() == time_end]
93 
94  graph = get_graph_as_dict(nodes)
95 
96  all_paths = []
97  for sn in starting_nodes:
98  for en in ending_nodes:
99  all_paths += find_all_paths(graph, sn, en)
100 
101  # compute all path scores as a np array.
102  path_scores = [(path, np.array([n.get_weight() for n in path]).sum())
103  for path in all_paths]
104  s = np.array([p[1] for p in path_scores])
105  s -= s.min()
106  path_prob = np.exp(-s) / np.exp(-s).sum()
107 
108  return all_paths, path_prob, path_scores
def get_graph_as_dict
converts a list of graphNode objects (nodes), which have been initiated with scores and edges into a ...
Definition: score_graph.py:13
def score_graph
Function to score a graph based on nodes, which has scores and edges, as well as keys, which is a list of the states visited.
Definition: score_graph.py:56
def find_all_paths
Finds all paths between nodes, which already have edges drawn between them.
Definition: score_graph.py:26