CODEWITHSUNDEEP
pythonmatlabgraphnetworkx
Abdelrahman Farag
Abdelrahman Farag

Reputation: 3

Calculate all possible paths from nodes in chart

I need an advise how to calculate all possible paths from start node to end node with a program (Programatically) , I can use either C#, Python, or Matlab, but I dont know which one is easy and faster for coding and less effort , also I do not know from where to start, I need also to draw the edges between nodes automatically and calculate more formulas later. I have the following data

Node Date         Data
A    2020-01-01   2.09
B    2020-01-05   0.89
C    2020-01-08   3.17
D    2020-01-08   1.15
E    2020-01-15   3.65

I want to do the following:

  1. Create path from any node to another (one way and from lower date to higher date only) and must pass through all nodes between dates in the path, for example:

    1.1 from (A) to (E) should extract the following paths:

    • A,B,C,E
    • A,B,D,E

    since C and D are on the same date, so we have 2 different paths.

  2. List item

Upvotes: 0

Views: 273

Answers (2)

DarrylG
DarrylG

Reputation: 17166

Using Python groupby and product from Python itertools module

Code

from itertools import groupby, product

def all_paths(s):
    # Convert string to list of node triplets
    nodes = [n.strip().split() for n in s.split('\n')]
    
    # Skip header and sort by time 
    # (since time is padded, no need to convert to datetime object to sort)
    nodes = sorted(nodes[1:], key=lambda n: n[1])  # sorting by time which is second item in list (n[1])
    
    # Group nodes by time (i.e. list of list, with nodes with same time in same sublist)
    # Just keeping the node field of each item in sublist (i.e. node[0] is Node field)
    labels = [[node[0] for node in v] for k, v in groupby(nodes, lambda n:n[1])]
    
    # Path is the product of the labels (list of lists)
    return list(product(*labels))

Usage

Example 1: Data in string

data = '''Node Date Data
A 2020-01-01 2.09
B 2020-01-05 0.89
C 2020-01-08 3.17
D 2020-01-08 1.15
E 2020-01-15 3.65'''

print(all_paths(data))

Example 2: Data in file data.txt

with open('data.txt', 'r') as fin:
    print(all_paths(fin.read()))

Output (for both cases):

[('A', 'B', 'C', 'E'), ('A', 'B', 'D', 'E')]

Upvotes: 1

luthervespers
luthervespers

Reputation: 268

This will generate a list of chains of nodes for every path. It uses python lists and a dictionary to hash - so it will be very slow if you're working with large data sets. If this is the case, look into the pandas library (groupby). The same logic will work, but you will definitely save time in the nodes_by_date function. There may also be other tools in that library to generate the paths you need.

nodes = [('E',15,3.65), ('A',1,2.09), ('B',5,.89), ('C',8,3.17), ('D',8,1.15)]
#nodes = [('E',15,3.65), ('A',1,2.09), ('B',5,.89), ('C',8,3.17), ('D',8,1.15), ('F', 16, 100), ('G', 16, 200), ('H', 17, 1000)]

def all_paths(nodes):
    nbd = nodes_by_date(nodes)
    return get_chains(nbd, 0)

def nodes_by_date(nodes):
    # sort by date (not sure what format your data is in, but might be easier to convert to a datenum/utc time)
    nodes = sorted(nodes, key=lambda x: x[1])
    # build a list of lists, each containing all of the nodes with a certain date
    # if your data is larger, look into the pandas library's groupby operation
    dates = {}
    for n in nodes:
        d = dates.get(n[1], [])
        d.append(n)
        dates[n[1]]=d
    return list(dates.values())

def get_chains(nbd, i):
    if i == len(nbd):
        return []
    # depth-first recursion so tails are only generated once
    tails = get_chains(nbd, i+1)
    chains = []
    for n in nbd[i]:
        if len(tails):
            for t in tails:
                newchain = [n]
                # only performant for smaller data
                newchain.extend(t)
                chains.append(newchain)
        # end of recursion
        else:
            chains.append([n])
    return chains

Upvotes: 0

Related Questions