Questions

[naceee]

I will probably have a lot of questions, so I decided to create this issue and write them here to not get lost somewhere in the chats. Hopefully @MilaNedic or @ttusar can help me with some of them.

[naceee]

In the agorithm described by the paper, the input of preprocessing should contain a set X of nondominated points, however I don't think we do this in any of the tests, and it looks like our code works fine even with a set of dominated points.

If I understand correctly, we identify dominated points in preprocessing, and remove them from the avl_tree (T in the paper) but I think we don't remove them from the linked list (Q in the paper). I think we should do this as linked list Q is probably the state that we need to keep updated at all times for hypervolume calculation to be efficient. Am I thinking correctly? Any idea if removing them could break some of the properties of other nodes (for example the cx and cy values)?

# Check if current node is dominated by any previous node in avl_tree
dominated = False
for node in avl_tree:
    if node != current and all(node.x[i] <= current.x[i] for i in range(3)) and any(node.x[i] < current.x[i] for i in range(3)):
        dominated = True
        break

if dominated:
    current.ndomr = 1
    avl_tree.remove(current)
else:
    # Remove nodes dominated by the current node
    nodes_to_remove = [node for node in avl_tree if node != current and all(current.x[i] <= node.x[i] for i in range(3)) and any(current.x[i] < node.x[i] for i in range(3))]
    for node in nodes_to_remove:
        avl_tree.remove(node)
        node.ndomr = 1

[MilaNedic]

I don't think anything is wrong with removing dominated points since our SortedList (perhaps not very smartly named avl_tree - I should change that) works as a binary balanced tree described in the paper (and we only remove dominated points from T since they aren't candidates for cx and cy values). However, as far as I understand, nodes are not removed from Q - the doubly linked list of DLNodes. Preprocessing sets the .ndomr attribute to 1 if the node is dominated and then, when calculating the hypervolume in 3-D using hv3dplus, it is checked if the node is dominated (if yes, the function simply doesn't take it into account).

[naceee]

we only remove dominated points from T since they aren't candidates for cx and cy values

Yeah that makes sense, so removing them shouldn't be a problem.

[naceee]

Also I see now that we are actually removing dominated points from the linked list using remove_from_z function, but only when calculating hypervolume. Not sure if it makes any difference, but will need to keep in mind when implementing other functions.

[naceee]

I know I asked you this before @MilaNedic, but can you explain me the meaning of this attributes of the DLNode again? I am not sure about the difference between self.closest and self.cnext (and which one corresponds to cx/cy in the paper). Also am I right that self.next[i] gives you the point that is the next by the order of i-th coordinate (and the previous one for self.prev)?

class DLNode:
    def __init__(self, x=None, info=None):
        self.x = x if x else [None, None, None, None]
        self.closest = [None, None]  # closest in x coordinate, closest in y coordinate
        self.cnext = [None, None]  # current next
        self.next = [None, None, None, None]
        self.prev = [None, None, None, None]
        self.ndomr = 0  # number of dominators
        self.info = info # information about the point

[MilaNedic]

Attributes self.closest[0] (smallest q such that q_x > p_x and q_y < p_y)andself.closest[1]smallest q such that q_x < p_x and q_y > p_y correspond to .cx/.cy mentioned in the paper. You are correct about self.next[i] - it points to the nearest next point in i-th coordinate. Attributes self.cnext are a bit tricky, I haven't found their explicit definition anywhere in the paper but it's likely that I missed it. Usually, self.cnext and self.closest are set to the same value when initializing certain calculation. But I think self.cnext serves as the "update" attribute of self.closest when new closest nodes need to be taken into account. I would say it kind of serves as a pointer to the next outer delimiters needed in algorithms. I need to check the original paper again for details, will keep you posted if I find anything useful.

[naceee]

Hey @MilaNedic, do you maybe remember what one_contribution_3d(head, new) function does? I see it is only used in hv4dplusU function. I probably need something similar to calculate both the contributions of an element not in the archive and contribution of an element that is already in the archive.

[MilaNedic]

The one_contributon_3d(head, new) calculated the contribution of the new point to an already existing "archive". This is then multiplied by height to get the hypervolume in 3-D. I think what may be the problem is the fact that this is a 3-D contribution so for 4-D points, you are missing the height?? But the idea should be very similar to this function.

[naceee]

It turns out this is exactly what we need for hypervolume_improvement in 3D, so that's perfect. I still need to figure it out if it can be modified to work for contributing_hypervolume as well.