Algorithms - Graphs

Graphs Module

msproteomicstoolslib.algorithms.graphs.graphs.getAdjacencyList(tree)

Convert a tree into a adjacency list

Args:

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

Args:

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.

Args:

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 (list(str)) : A path represented as list of nodes to be visited in that order