Pardon the seemingly confusing phrasing of the question. Here is what I'd like to do.
Given a dataframe df
Fruit1 Fruit2 Weight
orange apple 0.2
orange grape 0.4
orange pineapple 0.6
orange banana 0.8
apple grape 0.9
apple pineapple 0.3
apple banana 0.2
grape pineapple 0.1
pineapple banana 0.8
and a constraint to the highest allowed path length, L
I wish to return a dataframe that has the highest average path (i.e. summation of all edges between points/path length to be maximum), where an edge is represented by the weight column, given that it does not exceed the length L.
To illustrate with an example of what I mean by highest average path:
Let's say we only have 4 points A, B, C & D. We are interested in finding the highest average path between A & D.
The highest average path would be max( (A->D)/1, (A->B + B->D)/2, (A->C + C->D)/2, (A->B + B->C + C-> D)/3, (A->C + C->B + B-> D)/3 ) in the case of L=3
For L=2, it would be max( (A->D)/1, (A->B + B->D)/2, (A->C + C->D)/2 )
In the case of df, for L=2 we would get something like
Fruit1 Fruit2 Weight MaxAvgPath(L=2)
orange apple 0.2 [orange, grape, apple]
orange grape 0.4 [orange, apple, grape]
orange pineapple 0.6 [orange, banana, pineapple]
orange banana 0.8 [orange, banana]
apple grape 0.9 [apple, grape]
apple pineapple 0.3 [apple, grape, pineapple]
apple banana 0.2 [apple, pineapple, banana]
grape pineapple 0.1 [grape, orange, pineapple]
grape banana 0.1 [grape, apple, banana]
pineapple banana 0.8 [pineapple, banana]
Note: This edge set contains just enough rows to represent the entire network. For instance, while (orange, apple) exists, (apple, orange) does not because the weight for (apple, orange) would be the same. However, if including those helps in creating the solution, feel free to use them and leave them out in the final output. The returned paths of the mirror pairs should be equal to the returned paths of the original pairs.