Python compare list and store in new variable

Question

i need some help in python.

I'm using Aimsun traffic simulator to do some simulations, and the programming language is python.

My problem is:

I need to search all the possible route that a vehicle can do.

I get these incomplete routes:

 1. Route 1 - [967, 973]  
 2. Route 2 - [967, 970] 
 3. Route 3 - [970, 396]    
 4. Route 4 - [396, 3269] 
 5. Route 5 - [3269, 3275] 
 6. Route 6 - [3275, 3278]
 7. Route 7 - [3278, 404] 
 8. Route 8 - [3278, 408] 
 9. Route 9 - [404, 448]
 10. Route 10 - [408, 410] 
 11. Route 11 - [408, 411] 
 12. Route 12 - [448, 454] 
 13. Route 13 - [410, 419] 
 14. Route 14 - [410, 433] 
 15. Route 15 - [410, 437] 
 16. Route 17 - [411, 412]

The start point is 967, so any vehicle will start in this point.

This lists represent the connection of the sections, so if the value in second column it doesn't repeat in next values in first column, this value will represents a end point, so the vehicle will finish the travel.

So for the finish first route we have:

Route Finish 1 - [967, 973] because 973 don't repeat in first column.

In this case is simple i store a variable with this route.

Now starts the problem:

The second route is composed by route 2,3,4,5,6 so,

Route 2 - [967, 970, 396, 3269, 3275, 3278]

but the problem is that 3278 repeat two times in first column:

1. Route 7 - [3278, 404]
2. Route 8 - [3278, 408]

so i have more two routes:

1. Route x - [967, 970, 396, 3269, 3275, 3278, 404]
2. Route y - [967, 970, 396, 3269, 3275, 3278, 408]

and problem increases

1. Route a - [967, 970, 396, 3269, 3275, 3278, 404, 448]
2. Route b - [967, 970, 396, 3269, 3275, 3278, 408, 410]
3. Route c - [967, 970, 396, 3269, 3275, 3278, 408, 411]
4. Route d - [967, 970, 396, 3269, 3275, 3278, 408, 454]

and continues in the same way.

How can i merge this lists dynamically, and in the end i have all the routes in variables like:

1. Route Finish 1 - [....] 
2. Route Finish 2 - [....]

I try a lot of codes, with compare and store in variables, but doesn't work.

I hope that you guys have understood.

Answer 1

I apologize for not using python 3, as I don't have it installed. Please convert the print statements to functions and it should work.

Overview

Based on your problem statement, I graphed your routes as followed:

By looking at this graph, I came up with a few observations:

• If I start from 967, I will ended up at the following nodes (or station, or car stop): 973, 454, 419, 433, 437, and 412. I call those nodes leaf_nodes or end_points in the code.
• What you called "routes" in the problem statement are just segments of a complete route.
• Therefore, the number of "routes" are really the number of nodes in the end_points
• For this solution, I make use of the python module networkx. If you don't have it in your system, you will need to install it. Installation is beyond the scope of this discussion, but you can start by googling for python pip.
• The workhorse is in networks.all_simple_paths() function. This function looks at a graph, a starting point, and an end point and returns all the paths connecting the starting point to the end point.

My Approach

1. Define the data. How can I represent the input, preferably in a text file.
2. Read the text file, build the graph
3. Create a list of destination nodes (AKA the end_points)
4. For each node in the end_points, print the path from the starting node (967) to this node

The Data File

I represented the input as a text file (routes.txt) where each line consists of two nodes: a source and a destination.

967 973  
967 970 
970 396    
396 3269 
3269 3275 
3275 3278
3278 404 
3278 408 
404 448
408 410 
408 411 
448 454 
410 419 
410 433 
410 437 
411 412

The code

# routes.py
# Make sure you have `networkx` installed
import networkx

def build_routes():
    '''
    Reads a text file, where each line is a pair of nodes, then build
    a graph of all the nodes. Returns the graph and a list of leaf nodes
    '''
    routes = networkx.DiGraph()
    leaf_nodes = set()
    nonleaf_nodes = set()
    with open('routes.txt') as f:
        for line in f:
            # Each line consists of two nodes: a source and a
            # destination.
            source, destination = line.split()
            nonleaf_nodes.add(source)
            leaf_nodes.add(destination)
            routes.add_edge(source, destination)

    leaf_nodes.difference_update(nonleaf_nodes)
    return routes, leaf_nodes

def print_routes(routes, start_point, end_points):
    for end_point in end_points:
        for path in networkx.all_simple_paths(routes, start_point, end_point):
            print ' > '.join(path)

if __name__ == '__main__':
    routes, end_points = build_routes()
    print_routes(routes, '967', end_points)

Output

967 > 973
967 > 970 > 396 > 3269 > 3275 > 3278 > 404 > 448 > 454
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 410 > 419
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 411 > 412
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 410 > 437
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 410 > 433

Answer 2

As far as I understood, you want to find all the routes that start from 967 and can not be extend.

Here is a bit of code to find out the maximal routes, starting from 967.

First, we need to input the list of "incomplete routes". A possible route is a concatenation of these pairs.

steps = [
[967, 973],
[967, 970],
[970, 396],
[396, 3269],
[3269, 3275],
[3275, 3278],
[3278, 404],
[3278, 408],
[404, 448],
[408, 410],
[408, 411],
[448, 454],
[410, 419],
[410, 433],
[410, 437],
[411, 412],
]

Starting from 967, we extend the routes, maintaining all possibilities. Here, I define a function to increase lengths of intermediates routes.

def add_steps(routes, finished_routes):
    new_routes = []
    for r in routes:
        end = r[-1]
        r_finished = True
        for s in steps:
            if s[0] == end:
                new_routes.append(r + [s[1]])
                r_finished = False
        if r_finished:
            finished_routes.append(r)
    return new_routes, finished_routes

You can try

>>> add_steps([[967]], [])

And get

Out: ([[967, 973], [967, 970]], [])

Then, next

>>> add_steps([[967, 973], [967, 970]], [])
([[967, 970, 396]], [[967, 973]])

This means that "[967, 970, 396]" is a intermediate route, which can be extended and "[967, 973]" is a finished route which can not be extended any more.

Repeat application of this function until all routes got finished.

routes = [[967]]
finished_routes = []
for n in range(20):
    routes, finished_routes = add_steps(routes, finished_routes)
    if not routes:
        print finished_routes
        break

The result printed out is

[[967, 973], [967, 970, 396, 3269, 3275, 3278, 404, 448, 454], [967, 970, 396, 3269, 3275, 3278, 408, 410, 419], [967, 970, 396, 3269, 3275, 3278, 408, 410, 433], [967, 970, 396, 3269, 3275, 3278, 408, 410, 437], [967, 970, 396, 3269, 3275, 3278, 408, 411, 412]]