# Convert a list of tuples(edges) into list of longest paths in Python

Please look at the fig. below. As a part of my project, I am in need to convert a list of edges of a forest into a list of unique longest paths. The longest paths are actually paths which connect any root node to a leaf node or a leaf to a leaf node. The problem here is, I have only the list of edges as an input, from which, I am supposed to derive these paths.

I am trying to solve this problem recursively by looking for neighbor nodes using a dictionary(created using the list of edges), but it looks like it is not the proper way to handle the problem and also i am finding to hard to visualize. Please suggest if there is any known efficient algorithms/methods to solve this problem.

**P.S.:** Please neglect the weights(they are just labels). **"Longest"** means the path covering maximum nodes.

**Input:**
*List of Tuples(edges)*

edges = [('point', 'floating'), ('754', 'floating'), ('clock', 'IEEE'), ('ARM', 'barrel'), ('barrel', 'shifter clock'), ('shifter', 'barrel'), ('representation', 'representation'), ('cycles', '754'), ('point representation', 'point'), ('barrel shifter', 'point')]

**Expected Output:**

inference_paths = [ ['cycles', '754', 'floating', 'point', 'point representation'], ['cycles', '754', 'floating', 'point', 'barrel shifter'], ['point repr', 'point', 'barrel shifter'], ['ARM', 'barrel', 'shifter clock'], ['shifter', 'barrel', 'shifter clock'], ['ARM', 'barrel', 'shifter'], ['clock', 'IEEE'], ['representation'] ]

**My failed code:**

edges = [('point', 'floating'), ('754', 'floating'), ('clock', 'IEEE'), ('ARM', 'barrel'), ('barrel', 'shifter clock'), ('shifter', 'barrel'), ('representation', 'representation'), ('cycles', '754'), ('point representation', 'point'), ('barrel shifter', 'point')] neighbors = {} inference_paths = [] for edge in edges: neighbors[edge[0]] = edge[1] for edge in edges: neighbor = neighbors.get(edge[1]) if neighbor: if not edge[1] == edge[0] == neighbor: inference_paths.append([edge[0], edge[1], neighbor]) else: inference_paths.append([edge[0]]) else: inference_paths.append([edge[0], edge[1]]) for path in inference_paths: print path

**My Output:**

[['point', 'floating'], ['754', 'floating'], ['clock', 'IEEE'], ['ARM', 'barrel', 'shifter clock'], ['barrel', 'shifter clock'], ['shifter', 'barrel', 'shifter clock'], ['representation'], ['cycles', '754', 'floating'], ['point representation', 'point', 'floating'], ['barrel shifter', 'point', 'floating']]

**Forest:**

## Answers

I believe your problem is, you say you're using recursion, but you're not. Attempting to do this iteratively is painful. First lets look at a basic recursive tree traversal function.

function traverseTree(node) { if(node == NULL) return; traverseTree(node->leftSubTree); traverseTree(node->rightSubTree); }

The above function will visit all nodes in a tree, now we just have to figure out what logic we need calculate to figure out paths and such. Note: your answers appear to suggest that a given node can only be used once in a path and cannot be crossed again, this assumption is used.

arrayOfPaths; function traverseTree(node) { if(node == NULL) return emptyPathObject; leftPathObject = traverseTree(node->leftSubTree); rightPathObject = traverseTree(node->rightSubTree); arrayOfPaths.add(leftPathObject + node + rightPathObject); return ((node + leftPathObject) or (node + rightPathObject) whichever is longer); } //Code to figure out which paths are the longest here. This is simpler than the other one too! :)