Algorithms  Graphs¶
Graphs
Module¶

msproteomicstoolslib.algorithms.graphs.graphs.
getAdjacencyList
(tree)¶ Convert a tree into a adjacency list
Parameters: tree (list(tuple) – a tree represented as list of edges (for example [(‘0’, ‘1’), (‘1’, ‘2’)] ).

msproteomicstoolslib.algorithms.graphs.graphs.
doBFS
(tree, start_node)¶ Perform breadthfirstsearch (BFS) on a given tree
Parameters:  tree (list(tuple) – a tree represented as list of edges (for example [(‘0’, ‘1’), (‘1’, ‘2’)] ).
 start_node (str) – starting node
Yields: node (str) – current node during search

msproteomicstoolslib.algorithms.graphs.graphs.
findShortestMSTPath
(graph, start, end)¶ Finds a path in an MST from start to one of the end elements
The algorithm will look for the shortest path in a minimum spanning tree (MST) to one of the elements contained in end. It will do a breadthfirst search (BFS) through the MST to find the first element in “end” which has minimal distance to start. If there are multiple elements in “end” with equal distance, whichever comes first in the BFS will be chosen.
It will then return the path between this element and the start element.
Parameters:  graph (list(tuple) – a graph represented as list of edges (for example [(‘0’, ‘1’), (‘1’, ‘2’)] ).
 start (str) – Starting node
 end (list(str) – List of possible end nodes (closest will be chosen)
Returns: path – A path represented as list of nodes to be visited in that order
Return type: list(str