15,999,481 members
5.00/5 (1 vote)
See more:
I am trying to find intermediary activities between keys. There is different connectors between two keys and I want to find the ones which have minimum value due to a calculation which I will explain below. I have dictionaries such as
```dict2 = {'A': {'A': 'one', 'B': 'one', 'H': 'one', 'G': 'one'}}
dict1 = {'A': ['B', 'C', 'D', 'E'],
'B': ['E'],
'C': ['F', 'D'],
'D': ['G'],
'E': ['H', 'G'],
'F': ['G']}```

dict2 has the keys that I want to find the intermediary keys between them. dict1 has the keys and the list as a value and list represents the kids of each key. For instance, A has kids B,C,D, E. B has kid E. We create connections between each key from dict1. For instance, A has kid B and B is in dict2 so we directly create a connection between A and B.
However, in order to create a connection between A and H, at first we check kids of A. For instance, we have E and E has a kid H so we create a connection between A and H by having E as an intermediary activity. However, sometimes I can have more than one option between the keys.

For instance, all the possible connection between A and G is as follows:
```(('A', 'G'), ['C', 'F']),
(('A', 'G'), ['C', 'D']),
(('A', 'G'), ['D']),
(('A', 'G'), ['E'])```

I have another dictionary, which gives the values between each pair as:
```rel_relation={('A', 'B'): ['0.0', '-3.0'],
('A', 'C'): ['0.0', '-5.0'],
('A', 'D'): ['0.0', '3.0'],
('A', 'E'): ['0.0', '1.0'],
('B','E'): ['0.0', '1.0'],
('C','F'): ['0.0', '-2.0'],
('C','D'): ['0.0', '2.0'],
('D','G'): ['0.0', '3.0'],
('E','H'): ['0.0', '2.0'],
('E','G'): ['0.0', '1.0'],
('F','G'): ['0.0', '5.0']}```

the value that is interesting is the 2nd value in the list such as A and B has the value -3. we call that value float. We have also a total float of the first node 0. Here we should start from A as A is the first key of the nested dictionary dict2. A has a total float 0.

Then we should check its kids. For each kid we should compare the float and also the value which is sum of float to and the total float that it's parent (here it is A) has. adding float to its parent total float, we can call this value updated value. Then, take the minimum between float and updated float. if that kid is not in dict2 then we should continue the same process but this time updated value gets to be total float of that kid. Here, when I start from A then check the kid B, I see that B is in dict2 so I can directly create connections such as (('A', 'B'), []).
Then, in the case of A and H, I check the kid of A then I find E then E has H so I can also create the connection (('A', 'H'), ['E']). In the case of A and G, we have multiple connections so we should find the one where we have all the minimum values.

For instance, A has kids B, E, D and C. I do the calculations manually as:

- for B: current value=-3, updated value= =-3+0=-3, min(current value, updated value)=-3.
as I have B in dict2 then I directly create the path.
Then, I check for E and D and C. None of them is in dict2 so continue for calculation:

- for E: current value=1, updated value_A= =1+(0)=1, min(current
value, updated value)=1
- for D: current value=3, updated value_A=3+0=2, min(current value, updated value)=3
- for C: current value=-5, updated value_A= =-5+0=-5, min(current value, updated value)=-5

here C has the minimum so I go from A to C. then I check C kids which are D and F.
for D: current value=3, updated value_C =3+(-5)=-2, min(current value, updated value)=-2
for F: current value=-2, updated value_C= ==2+(-5)=-7, min(current value, updated value)=-7
As F has the smallest then we go from A to C then C to F. Then, F has G so we have the path from A to G as [C,F].
just a small note here D has 3 calculated from A then it keeps that value when we go from C to D as well.
Thus, I would like to modify the code to add that part to have the path from the possible paths which has minimum values and get an output as
```{'A': [(('A', 'B'), []),
(('A', 'G'), ['C', 'F']),
(('A', 'H'), ['E']),
(('B', 'H'), ['E']),
(('B', 'G'), ['E'])]}
<pre>

What I have tried:

<pre lang="Python">
results = {}

def make_path(sub, path, total_float):
if path[-1] in dict1 and path[-1] not in sub:
min_float = 0
min_path = None
for p in dict1[path[-1]]:
new_total_float = total_float + float(rel_relation[(path[-1], p)][1])
if min_path is None or new_total_float < min_float:
min_float = new_total_float
min_path = [p]
if min_path is not None:
yield from make_path(sub, path + min_path, min_float)
else:
yield path

for tgt, sub in dict2.items():
sub_list = list(sub.keys())
results[tgt] = []

for k in sub_list:
if k not in dict1:
if (tgt, k) in rel_relation or (k, tgt) in rel_relation:
results[tgt].append(((tgt, k), []))
continue

min_float = 0
min_path = None
for p in dict1[k]:
new_total_float = float(rel_relation[(k, p)][1])
if min_path is None or new_total_float < min_float:
min_float = new_total_float
min_path = [k, p]

if min_path is not None:
for res in make_path(sub, min_path, min_float):
if res[-1] not in sub_list or res[0] not in sub_list or res[-1] not in sub:
continue
elif res[0] != tgt and res[0] not in sub:
continue
if len(res) == 2:
results[tgt].append((tuple(res), []))
else:
results[tgt].append(((res[0], res[-1]), res[1:-1]))

# Check if direct connection exists without intermediary nodes
if (tgt, k) in rel_relation and k in dict2[tgt]:
results[tgt].append(((tgt, k), []))```

and this code provides the output as:
```
{'A': [(('A', 'G'), ['C', 'F']), (('B', 'G'), ['E']), (('A', 'B'), [])]}
```
However, my code is missing the connection between B and H and A and H.
I do not see what's wrong with the code or how I can improve it. If anyone sees it, I would appreciate the help.
Posted
Updated 4-Jul-23 21:11pm
v2

## Solution 1

I might be a little out of my depth here as Python is still an ongoing learning curve for me. From what I could gather, it looks like the logic to handle a case where there are multiple possible paths between two keys is missing. You need to change your code to look at all possible paths that will return the smallest float value. Make sure that your 'rel_relation' dictionary is properly filled with the float values for each connection between keys -
Python
```results = {}
# Initialize dictionary to store the results

def make_path(source, target, path, total_float):
# Recursive function to generate paths between source and target keys
if target == path[-1]:
return [(source, target, path)]
# Return the complete path when target is reached

paths = []
# List all multiple possible paths
if path[-1] in dict1:
# Check if the current key is a child in dict1
for p in dict1[path[-1]]:
new_total_float = total_float + float(rel_relation[(path[-1], p)][2])
# Calculate new total float
new_path = path + [p]
# Extend the current path
sub_paths = make_path(source, target, new_path, new_total_float)
# Recursive call to find sub-paths
paths.extend(sub_paths)
return paths

for source, sub in dict2.items():
results[source] = []
# Initialize list to store results for each source key
for target in sub:
if target not in dict1:
continue
# Skip if target key has no children in dict1

paths = []
# List to store possible paths from source to target

for p in dict1[target]:
total_float = float(rel_relation[(target, p)][1])
# Get total float for the connection
path = [target, p]
# Start a new path from the target key
sub_paths = make_path(source, target, path, total_float)
# Recursive call to find all paths
paths.extend(sub_paths)

if paths:
# Select path with minimum float value and add it to the results
min_path = min(paths, key=lambda x: (x[2], x[0], x[1]))
path = min_path[2][:-1]
# Extract the path without source and target keys
results[source].append(((source, target), path))
# Add the path to the results

print(results)  ```

I got an output where B and H and A and H were included in the connection -
```{
'A': [
(('A', 'B'), []),
(('A', 'G'), ['C', 'F']),
(('A', 'H'), ['E']),
(('B', 'G'), ['E']),
(('B', 'H'), ['E'])
]
}```

v2
CIZA_1 5-Jul-23 3:04am
@Andre Oosthuizen Thanks a lot for your answer. However, when I run it I get a solution {'A': []}. Python is also new to me and I tried to print paths in your code but it was an empty list. I would like to ask did you find all the paths between two activities (such as A and G has 4 paths, and you get all the 4 paths) and then did you try to find the one with minimum float? if it is the case, this will be costly when there will be large datasets. I was also trying to do this filtering while checking for the paths.
Andre Oosthuizen 5-Jul-23 6:10am
Only a pleasure. The paths were selected based on the minimum float values, as you described in your question and assuming the 'rel_relation' dictionary contains the necessary float values.

To find all paths, you can change your code to -
```results = {}

def find_paths(source, target, path, total_float):
if target == path[-1]:
return [(source, target, path, total_float)]

paths = []
if path[-1] in dict1:
for p in dict1[path[-1]]:
new_total_float = total_float + float(rel_relation[(path[-1], p)][2])
new_path = path + [p]
sub_paths = find_paths(source, target, new_path, new_total_float)
paths.extend(sub_paths)
return paths

for source, sub in dict2.items():
results[source] = []
for target in sub:
if target not in dict1:
continue

paths = []
for p in dict1[target]:
total_float = float(rel_relation[(target, p)][1])
path = [target, p]
sub_paths = find_paths(source, target, path, total_float)
paths.extend(sub_paths)

if paths:
min_path = min(paths, key=lambda x: x[3])
path = min_path[2][:-1]
results[source].append(((source, target), path))

print(results)```

The cost might indeed become costly, depending on the size and structure of your input data. The function 'find_paths' uses a recursive method (Python Function Recursion[^]), calling on itself to explore all possible paths. As the number of keys and connections increases, the number of recursive calls and the number of paths to consider can grow quite large.

You might have to look alternative algorithms or optimization techniques to drop the cost of the path-finding process, maybe using 'Graph-based' algorithms? as in How to find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm[^]
CIZA_1 5-Jul-23 7:35am
@Andre Oosthuizen thanks again. However,I do not want to get the all paths as I could achieve that. I am wondering what's the difference between this code and your previous one? Your previous code did not work and I am wondering how it was working on your side?