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.
Submit an article or tip