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! :)

Need Your Help

reorder pages in FragmentStatePagerAdapter using getItemPosition(Object object)

android android-viewpager fragmentpageradapter

I believe that FragmentStatePagerAdapter does not behave correctly when overriding getItemPosition(Object object) with the purpose of reordering the pages.

How can I call a function in DB2

sql db2

I have implement a function fn_getDate()

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.