CODEWITHSUNDEEP
python
kauray
kauray

Reputation: 719

Finding all combinations represented using lists

We have several complete bipartite graphs represented as lists.

enter image description here

For example in the figure there are 3 bipartite graphs, the first one consists of nodes 0 and 1 say Layer 1, the second one consists of nodes 2 and 3 say Layer 2 and the third one consists of node 4 say Layer 3. The nodes between Layer i and Layer i+1 are all connected to each other. In addition there could be some weight assigned to such an edge. There is a weight edge between 0 and 2 with weight 30 and another edge between 2 and 4 with weight 10. This is represented as a dictionary {(0, 2): 30, (2, 4): 10}. The layers are represented as lists as in the following code:

    l=[
        [
            [[0], [30]], [[1], [20]] #first set of bipartite nodes
        ], 

        [   
            [[2], [10]], [[3], [20]] #second set of bipartite nodes
        ], 

        [   
            [[4], [20]] #third set of bipartite nodes
        ]
    ]

We would like to calculate all possible combinations selecting one node from each layer. For each combination, the total value would be the sum of the values of the individual nodes and in that combination if there is any weighted edge, those edge weights would be subtracted. For example, for combination 0,2,4 the sum of the nodes would be 30 + 10 + 20 and we have weighted edges betwwen 0 and 2 and 2 and 4 thus these edge weights would be subtracted to give a total weight of 30 + 10 + 20 - 30 - 10. For the combination 1,3,4 the value would be just 20 + 20 + 20 since there are no weighted edges between them Thus all possible combinations in the above would be 

 0,2,4 value = 30 + 10 + 20 - 30 - 10
 0,3,4 value = 30 + 20 + 20
 1,2,4 value = 20 + 10 + 20 - 10
 1,3,4 value = 20 + 20 + 20

How to calculate all such possible combinations and their values using the list data structure as described above?

Code I have tried:

for element in itertools.product(*l):
    print(element)

This gives me the cartesian product and all possible combinations. But how to account for the subtraction part for edges. What would be the efficent way to do this?

Upvotes: 0

Views: 181

Answers (1)

Zaccharie Ramzi
Zaccharie Ramzi

Reputation: 2326

So taking your l notation this is what I have come up with (this gives the expected result):

edge_weights = {(0, 2): 30, (2, 4): 10}
combinations = dict()
for element in itertools.product(*l):
    combination = tuple([node_id[0] for node_id, node_value in element])
    value = sum([node_value[0] for node_id, node_value in element])
    combinations[combination] = value
print(combinations)  # first print without considering the edge weights
for combination in combinations.keys():
    for edge in zip(combination[:-1], combination[1:]):
        combinations[combination] -= edge_weights.get(edge, 0)
print(combinations)

Note that this assumes at least 2 complete bipartite graphs.

You could definitely change the variable name l as was pointed out in this comment. I don't know how flexible this list of bipartite graphs is but I wouldn't have the node id or its value inside lists, it makes the problem more complicated and less readable.

Upvotes: 1

Related Questions