graph

Recover the graph of recursive functions calls

The RecursionVisualizer decorator records several pieces of information:

  1. nodes records all the nodes encountered
  2. history records the time at which each node is first visited and finished being visited

nodes and history capture the graph of recursive function calls but in a convoluted, inaccessible way. (For example, given a node, it is not immediately clear how to use nodes and history to figure out which nodes are its parents.) The functions get_graph take in nodes and history and return a list of nodes and edges that define the graph of recursive function calls. Specifically, the nodes and edges are represented as a networkx graph object which has many additional helpful features.

(Technically, RecursionVisualizer records one last piece of information: node_to_edge_labels which maps a node to an edge label. Due to the limited capabilities of the RecursionVisualizer decorator, it is only possible to map an edge label to one of the nodes in the edge. We cannot easily map an edge label to both nodes that make up the edge. The function get_graph are also responsible for correctly mapping each edge label to the proper edge.)

source

get_preorder_traversal

 get_preorder_traversal (history:List[int])

Extract the preorder traversal from history by recording the order of when each node is first discovered.

Type Details
history List list of node ids recording when each node is first visited and finished being visited
Returns List preorder traversal of the graph

source

get_graph_edges

 get_graph_edges (nodes:Dict[int,recursion_visualizer.node.Node],
                  preorder:List[int], node_to_edge_labels:Dict[int,str])

Convert the preorder traversal preorder into a list of edges that define the graph of recursive function calls.

Extract the edges from the preorder traversal by analyzing the depth of each node. Collect all the edges and then map each edges to a string label.

References:

  1. Inspired by lee215’s solution to Leetcode 1028. Recover a Tree From Preorder Traversal.
Type Details
nodes Dict map from node id to node
preorder List list of node ids where each node id is recorded when it is first discovered and finished being explored,
node_to_edge_labels Dict map from node id to edge label
Returns Dict map from an edge to label (an edge is a tuple of two node ids)

source

get_graph

 get_graph (history:List[int],
            nodes:Dict[int,recursion_visualizer.node.Node],
            node_to_edge_labels:Dict[tuple,str])

Convert the history of recursive function calls, into a networkx graph of recursive function calls with optionally labeled edges.

The graph is constructed by 1) extracting the preorder traversal of the graph from history and then 2) extracting the edges of the graph based on the depth of each node in the preorder traversal.

Type Details
history List list of node ids recording when each node is first visited and finished being visited
nodes Dict map from node id to node
node_to_edge_labels Dict map from a node to an edge label