pytype.typegraph.cfg._PathFinder

class documentation

class _PathFinder: (source)

View In Hierarchy

Finds a path between two nodes and collects nodes with conditions.

Method __init__ Undocumented
Method FindAnyPathToNode Determine whether we can reach a node at all.
Method FindHighestReachableWeight Determine the highest weighted node we can reach, going backwards.
Method FindNodeBackwards Determine whether we can reach a CFG node, going backwards.
Method FindShortestPathToNode Find a shortest path from start to finish, going backwards.
Instance Variable _solved_find_queries Undocumented
def __init__(self): (source)

Undocumented

def FindAnyPathToNode(self, start, finish, blocked): (source)

Determine whether we can reach a node at all. Args: start: The node to start at. If this node appears in blocked, we can't reach finish (unless start==finish). finish: The node we're trying to reach. This node is always considered traversable, even if it appears in blocked. blocked: A set of nodes we're not allowed to traverse. Returns: True if we can reach finish from start, False otherwise.

def FindHighestReachableWeight(self, start, seen, weight_map): (source)

Determine the highest weighted node we can reach, going backwards. Args: start: The node to start at. This node is always expanded, even if it appears in seen. The start node's weight is never considered, even if it's the only node with a weight. seen: Modified by this function. A set of nodes we're not allowed to traverse. This doesn't apply to the node with the highest weight, as long as we can reach it without traversing any other nodes in "seen". weight_map: A mapping from node to integer, specifying the weights, for nodes that have one. Returns: The node with the highest weight, or None if we didn't find any nodes with weights (or if the start node is the only node that has a weight).

def FindNodeBackwards(self, start, finish, blocked): (source)

Determine whether we can reach a CFG node, going backwards. This also determines the "articulation points" of the graph, between the start and the finish node. In other words, it finds the nodes (only considering nodes with conditions) that are on *all* possible paths from start to finish. Arguments: start: The node to start at. If this node appears in blocked, we can't reach finish (unless start==finish). finish: The node we're trying to reach. This node is always considered traversable, even if it appears in blocked. blocked: A set of nodes we're not allowed to traverse. Returns: A tuple (Boolean, Iterable[CFGNode]). The boolean is true iff a path exists from start to finish. The Iterable contains all nodes with a condition, that are on *all* paths from start to finish, ordered by when they occur on said path(s).

def FindShortestPathToNode(self, start, finish, blocked): (source)

Find a shortest path from start to finish, going backwards. Args: start: The node to start at. If this node appears in blocked, we can't reach finish (unless start==finish). finish: The node we're trying to reach. This node is always considered reachable, even if it appears in blocked. blocked: A set of nodes we're not allowed to traverse. Returns: An iterable over nodes, representing the shortest path (as [start, ..., finish]), or None if no path exists.

_solved_find_queries: dict = (source)

Undocumented