The Challenge >>> Find a common parent for list of nodes

denisT · 2019-02-25 16:24:34 UTC

For anyone who wants to practice in MXS and test your logic skills try:

Find a common parent for list of nodes

The goal is to find a node that closest parent for all nodes in the list (if there is any), and find the minimum hierarchical distance to this common parent.

examples:

there are two nodes and both are root nodes:
no common parent (except max root)
there are two nodes and the second is a child of the first:
the first is the common parent and minimum distance is 0
two nodes have the same parent:
this parent is the common parent and distance for both is 1
etc.

as you can guess for big scenes and lists of source nodes the fastest algorithm has to use minimum iterations.

so the best algorithm has to be fast and use minimum memory

martinez · 2019-02-26 20:30:06 UTC

I’m interested in the results because I have a lot of rigging tools like Select Opposite Limb, Mirror Pose and they all are based on finding a common parent.

I’m embarrassed to post this because I wrote it 8+ years ago, but it’s worked pretty solid over that time. I don’t count the number of ancestor because I didn’t need that.

For example, make a Biped select a bone and run.

(
	fn getMirroredNodeByName ThisNode =
	(
		local L = " L "
		local R = " R "
		local Lcheck
		
		local Lcheck = findString ThisNode.name " L "
		
		if Lcheck == undefined do
		(
			Lcheck = findString ThisNode.name " R "
			swap L R
		)
		
		if Lcheck == undefined then
		(
			ThisNode
		)
		else
		(
			getNodeByName (replace ThisNode.name Lcheck 3 R)
		)
	)


	fn getNonMirroredParent ThisNode =
	(
		CurrentNode = ThisNode
		MirrorNode = getMirroredNodeByName ThisNode

		while MirrorNode != CurrentNode do
		(
			CurrentNode = CurrentNode.Parent
			if currentNode == undefined do return undefined
			MirrorNode = getMirroredNodeByName CurrentNode
		)

		return CurrentNode
	)
	
	select (getNonMirroredParent $)
)

denisT · 2019-02-26 21:04:07 UTC

you code is for a special case.
we need it for more general …

like:

all fingers of one hand are children of the hand
all fingers are children of upper spine
legs are children of hip
legs, hands, and head are children of hip (or base, depends on your hierarchy solution)

MZ1 · 2019-02-27 21:20:56 UTC

Would you please explain a little more what you mean by “hierarchical distance”?

Serejah · 2019-02-28 22:58:22 UTC

Some test scene would be just great to have.
I have another one, which can return common parent and the distance, but I don’t like the solution at all

fn GetCommonParent =
(
	local nodes = selection as array
	local n1_parents_handles = #{}
		
	for i=1 to nodes.count-1 do
	(
		local n1 = nodes[i]
				
		do 
		(
			h = getHandleByAnim n1
			n1_parents_handles[h] = true
			n1 = n1.parent
		)
		while n1 != undefined
		
		n1 = nodes[i]
		
		for j=i+1 to nodes.count do
		(
			local n2 = nodes[j]
			local n2_parents_handles = #{}
			
			do 
			(
				h = getHandleByAnim n2
				n2_parents_handles[h] = true
				n2 = n2.parent
			)
			while n2 != undefined
			
			n2 = nodes[j]
			
			common = n1_parents_handles * n2_parents_handles
			
			if common.isEmpty then 
			(
				return rootnode
			)
			else
			(
				n1_parents_handles *= n2_parents_handles
			)
			
		)
		
	)
			
	n1 = nodes[1]
	h = getHandleByAnim n1
	
	while n1_parents_handles[h] == false do
	(
		n1 = n1.parent		
		if n1 == undefined do return rootnode
			
		h = getHandleByAnim n1	
	)
	
	n1
	
)

denisT · 2019-02-28 23:29:39 UTC

it’s a distance of relation between parent and child…
if parent and child the same node the distance is 0
if a node is direct child of another node (parent) the distance is 1
if a node is a grand child of another node (grand-parent) the distance is 2
and etc.
if two nodes don’t have common parent the distance between them is -1

Serejah · 2019-03-01 08:20:52 UTC

… deleted second time…
what a shame

denisT · 2019-03-02 06:29:55 UTC

Because there is no one who was interested this is just a code without comments:

test scene setup:

delete objects
gc()

nodes = 
(
	local num = 1000
	local nodes = for k=1 to num collect box()
	seed 0
	for k=1 to num*10 do try
	(
		nodes[random 1 num].parent = nodes[random 1 num]
	)
	catch()
	seed 3
	select (for k=1 to num/2 collect nodes[random 1 num])
	nodes
)

my solution:

fn getNodeParents node = 
(
	local parents = #()
	while (node != undefined) do 
	(
		insertitem node parents 1
		node = node.parent
	)
	parents
)
fn findCommonParent nodes first:on &dist:-1 &depth:0 = if nodes.count > 0 do
(	
	parents = getNodeParents nodes[1]
	dist = 0
	for k=2 to nodes.count while parents.count > 0 do
	(
		_parents = getNodeParents nodes[k]

		num = amin parents.count _parents.count
		
		n = 0
		for i = 1 to num while (_parents[i] == parents[i]) do n = i
		dist = if (n > 0) then (num - n) else -1; 

		parents.count = n
	)
	depth = parents.count-1
	
	if first then
	(
		if parents.count > 0 do parents[parents.count]
	)
	else parents
)

/*
(
	t0 = timestamp()
	h0 = heapfree

	cp = findCommonParent $ first:on dist:&d depth:&p

	format "time:% heap:%\n" (timestamp() - t0) (h0 - heapfree)
	format "\tcommon:% distance:% depth:%\n" cp d p
)
*/

Sapienti sat

PS. also there is a little bug in the solution… fix it yourself

martinez · 2019-03-04 03:21:52 UTC

@denisT Mine is only 2x or 3x slower than yours. So I’m getting better.

I was focused on using little memory because I thought that would make it faster. But yours uses more memory and is faster.

(
    fn scoreTheParents nodeSet objSet =
    (
        parentScores = #()

        for i = 1 to objSet.count do parentScores[i] = 0

        for n in nodeSet do
        (
            parent = n

            while parent != undefined do
            (
                parent = parent.parent
                parentIndex = findItem objSet parent

                if parentIndex != 0 do
                (
                    parentScores[parentIndex] += 1
                )
            )
        )

        parentScores
    )

    fn findCommonParent =
    (

        local objSet = objects as array
        local nodeSet = getCurrentSelection()

        commonParent = undefined
        dist = 0

        if nodeSet.count > 0 do
        (
            scores = scoreTheParents nodeSet objSet
            targetScore = amax scores

            parent = nodeSet[1]
            currentScore = 0

            while commonParent == undefined do
            (
                dist += 1
                parent = parent.parent

                parentIndex = findItem objSet parent
                currentScore = scores[parentIndex]

                if currentScore == targetScore do commonParent = parent

                if dist > scores.count do
                (
                    dist = 0
                    exit
                )
            )
        )

        #(commonParent,dist)
    )

    (
        t0 = timestamp()
        h0 = heapfree

        cp = findCommonParent()

        format "time:% heap:%\n" (timestamp() - t0) (h0 - heapfree)
        format "\tcommon:% distance:%\n" cp[1] cp[2]
    )
)

My results

time:52 heap:432L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:40

time:53 heap:492L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:40

time:48 heap:492L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:40

time:55 heap:492L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:40

time:60 heap:432L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:40

denisT results

time:22 heap:29996L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:0 depth:0

time:21 heap:29996L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:0 depth:0

time:22 heap:30016L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:0 depth:0

time:18 heap:29996L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:0 depth:0

time:22 heap:30036L
	common:$Box:Box148 @ [0.000000,0.000000,0.000000] distance:0 depth:0

martinez · 2019-03-04 03:31:07 UTC

Serejah’s results, returned a different answer than mine and denisT’s. But the scene is 1000 boxes on top of each other, so it’s hard to tell which is correct.

time:6708 heap:2631168L
	common:$Box:Box771 @ [0.000000,0.000000,0.000000]

time:6188 heap:2685956L
	common:$Box:Box771 @ [0.000000,0.000000,0.000000]

time:5979 heap:-5363744L
	common:$Box:Box771 @ [0.000000,0.000000,0.000000]

time:5814 heap:2689876L
	common:$Box:Box771 @ [0.000000,0.000000,0.000000]

Serejah · 2019-03-04 09:44:04 UTC

I couldn’t make my version return correct mindist value
Denis, what do you think of this optimization?
And probably we can also check if there’re at least two nodes without a parent and return undefined in this case.

fn findCommonParent nodes first:on &dist:-1 &depth:0 = if nodes.count > 0 do
(		
	nodes_handles = #{}
	for n in nodes do nodes_handles[ getHandleByAnim n ] = true
	nodes = for n in nodes collect 
	(
		if n.parent != undefined and nodes_handles[ getHandleByAnim n.parent ] then dontCollect else n		
	)

	parents = getNodeParents nodes[1]
...

duCaMJobV1

my test scene


(
	size = 70
	delete objects
	gc()
	max create mode
	seed 53535
	b = box showlinks:true
	b.scale *= 0.4
	boxes = #( b )
	for i=1 to size collect
	(
		append boxes (instance b pos:(b.pos + [0,-i*15,0]) parent:boxes[i] showlinks:true)
	)

	for b in boxes where random 0.0 1.0 > 0.5 do
	(
		
		dir = if (random -1 1) > 0 then 1 else -1
		
		clr = random green (random red blue)
		
		root = b
		for i=1 to random (size*0.5) (size*1.5) do
		(		
			x = instance b pos:(b.pos + [i*15*dir,-4*i,0])	wirecolor:clr parent:root showlinks:true
			x.scale *= 0.7
			root = x
		)
	)

	select (for o in objects where random 0.0 1.0 > 0.9 collect o)
)

denisT · 2019-03-05 00:20:29 UTC

@martinez
your algorithm is not correct in some situations. you can check it by selection any not root node and it’s child.
(for example in my test scene select Box827 and Box875). In your case it returns Box148 instead of Box827

your algorithm uses less memory than mine just in some situations. more often it uses more (try to select many nodes) .

also I fixed my algorithm (because I see some interest now) and changed using of second array. Now I use the same second array every next node instead of creating a new one. It helps me avoid the new allocation of memory add saves the memory:

fn getNodeParents node parents:#() = 
(
	parents.count = 0
	while (node != undefined) do 
	(
		insertitem node parents 1
		node = node.parent
	)
	parents
)

fn findCommonParent nodes first:on &dist: &depth: = if nodes.count > 0 do
(
	_parents = #()
	parents = getNodeParents nodes[1]
	num = parents.count
	dist = 0	
	for k=2 to nodes.count while parents.count > 0 do
	(
		getNodeParents nodes[k] parents:_parents
		num = amin num _parents.count
		
		out = off
		n = 0
		for i=1 to num while not out do
		(
			if parents[i] != _parents[i] then out = on
			else n = i
		)
		dist = if (n > 0) then (num - n) else -1
		parents.count = n
	)
	depth = parents.count - 1
	
	if first then
	(
		if parents.count > 0 do parents[parents.count]
	)
	else parents
)

@Serejah
i also thought about using of bittarrays and handlers as bits. But the problem is that in general case handler id order doesn’t match hierarchical order. So we can’t say who is a parent and who is a child in the list.
Also with handler ids we can potentially have very big bitarrays (high bits) which will cause slowdown and high memory use