Source code for ccpn.util.Graph

"""General graph handling code

"""
#=========================================================================================
# Licence, Reference and Credits
#=========================================================================================
__copyright__ = "Copyright (C) CCPN project (http://www.ccpn.ac.uk) 2014 - 2019"
__credits__ = ("Ed Brooksbank, Luca Mureddu, Timothy J Ragan & Geerten W Vuister")
__licence__ = ("CCPN licence. See http://www.ccpn.ac.uk/v3-software/downloads/license")
__reference__ = ("Skinner, S.P., Fogh, R.H., Boucher, W., Ragan, T.J., Mureddu, L.G., & Vuister, G.W.",
                 "CcpNmr AnalysisAssign: a flexible platform for integrated NMR analysis",
                 "J.Biomol.Nmr (2016), 66, 111-124, http://doi.org/10.1007/s10858-016-0060-y")
#=========================================================================================
# Last code modification
#=========================================================================================
__modifiedBy__ = "$modifiedBy: CCPN $"
__dateModified__ = "$dateModified: 2017-07-07 16:32:58 +0100 (Fri, July 07, 2017) $"
__version__ = "$Revision: 3.0.0 $"
#=========================================================================================
# Created
#=========================================================================================
__author__ = "$Author: CCPN $"
__date__ = "$Date: 2017-04-07 10:28:41 +0000 (Fri, April 07, 2017) $"
#=========================================================================================
# Start of code
#=========================================================================================

import collections
from typing import Tuple


[docs]def minimumStepPath(graph: dict, startNode, endNode=None) -> Tuple[dict, dict]: """ Minimum-step-path by breadth-first traversal, inspired by Dijkstras algorithm Each edge has the same weight; among paths of the same length the function selects the first encountered. Breadth-first search guarantees that the paths with fewest steps are encountered first. Input: graph is given in form {node:{node:edgeInfo}} nodes can be any object that can be used as a dictionary key Output: (costDict, predecessorDict) tuple, where costDict is {node:Tuple[edgeInfo, ...]}, with the edgeInfo along the path from start to node predecessorDict is {node:predecessor} the predecessor of node in the shortest path from start """ costDict = {startNode: tuple()} predecessorDict = {} traversal = [startNode] for node in traversal: cost = costDict[node] if node == endNode: break for node2, edgeInfo in graph[node].items(): if node2 not in traversal: costDict[node2] = cost + (edgeInfo,) predecessorDict[node2] = node traversal.append((node2)) # return costDict, predecessorDict