CODEWITHSUNDEEP
pythongraphtreedependenciesconstraints
sten
sten

Reputation: 7476

Building a dependency tree

I have N-nodes and want to build a dependency pairs-graph given weight matrix by maximizing the sum:

 [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]

Positioned along a line.

Then I have a matrix of connection weights. This matrix is symmetric i.e. the nodes potential connections are not directed, F.e. :

   [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
   [23,  0,  0,  0,  0,  0,  0,  0,  0,  0],
   [34, 96,  0,  0,  0,  0,  0,  0,  0,  0],
   [39, 30, 33,  0,  0,  0,  0,  0,  0,  0],
   [50, 22, 53, 36,  0,  0,  0,  0,  0,  0],
   [63, 89, 26, 93, 42,  0,  0,  0,  0,  0],
   [56, 89, 46, 44, 72, 34,  0,  0,  0,  0],
   [22, 66, 15, 89, 72, 86, 60,  0,  0,  0],
   [23, 62, 99, 39, 92, 24, 55,  6,  0,  0],
   [43,  1, 32, 84, 27, 38, 84, 14,  6,  0]

(or u can mirror to fill the zeros, if the algorithm requires it)

I need to connect all nodes in pairs such that the SUM of the weights is MAXIMUM.

There is ONE condition:

the connections can not cross each other i.e. if there is pair (n,n+x) you cant have pair (m,p) where m > n and m < n+x and (p < n or p > n+x) i.e. a pair cant start/end inside another pair and at the same time end/start outside of it

F.e. : 1 <--> 3 and 2 <--> 4 is not allowed

but : 1 <--> 3 and 1 <--> 4 is OK i.e. a node can participate in multiple pairs

I'm thinking of Constraint programming, but does not seem to fit the pattern !

Any ideas ?

Visual example .. in my case directions dont matter, but if the algorithm is easier that is Ok too.

dep

Upvotes: 1

Views: 466

Answers (1)

Nikolay Zakirov
Nikolay Zakirov

Reputation: 1584

Not sure if this is what you want but here you have that connections don't cross each other and every word is connected (maybe multiple times but this is not against the rules).

import numpy as np
from typing import Optional, List, Tuple
import functools


weight_matrix = np.array([[ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
   [23,  0,  0,  0,  0,  0,  0,  0,  0,  0],
   [34, 96,  0,  0,  0,  0,  0,  0,  0,  0],
   [39, 30, 33,  0,  0,  0,  0,  0,  0,  0],
   [50, 22, 53, 36,  0,  0,  0,  0,  0,  0],
   [63, 89, 26, 93, 42,  0,  0,  0,  0,  0],
   [56, 89, 46, 44, 72, 34,  0,  0,  0,  0],
   [22, 66, 15, 89, 72, 86, 60,  0,  0,  0],
   [23, 62, 99, 39, 92, 24, 55,  6,  0,  0],
   [43,  1, 32, 84, 27, 38, 84, 14,  6,  0]])

@functools.cache
def find_max_pairs(
    first_node:int, 
    last_node:int) -> Tuple[List[Tuple[int, int]], int]:
    max_ = float('-inf')
    res = None
    if last_node == first_node + 1:
        return [(first_node, last_node, )], weight_matrix[last_node, first_node]
    for splitter in range(first_node + 1, last_node):
        left_pairs, left_max = find_max_pairs(first_node, splitter)
        right_pairs, right_max = find_max_pairs(splitter, last_node)
        if left_max + right_max > max_:
            max_ = left_max + right_max
            res = (left_pairs, right_pairs)
    return [(first_node, last_node, )] + res[0] + res[1], max_ + weight_matrix[last_node, first_node]
    

find_max_pairs(0, weight_matrix.shape[0] - 1)

Output:

([(0, 9),
  (0, 6),
  (0, 1),
  (1, 6),
  (1, 5),
  (1, 3),
  (1, 2),
  (2, 3),
  (3, 5),
  (3, 4),
  (4, 5),
  (5, 6),
  (6, 9),
  (6, 8),
  (6, 7),
  (7, 8),
  (8, 9)],
 875)
​

Upvotes: 1

Related Questions