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 breadth-first-search (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 breadth-first 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