Re: AoA data merging

[rjray]

Updated to fix a few errors, and replace "push" with "unshift" to cause the next loop iteration to work on the same running node as the previous iteration, until the node is shunted to @final

Woof, what a mess.

The core problem here looks to me as though your algorithm is specifically-designed to reduce the list sub-graphs to a single, contiguous graph. And since it doesn't appear to be designed to expect multiple resultant graphs, it doesn't like them.

There are two things I'm going to ignore for now: the possibility of floating-point-error in the == overload, and the possibility that more than one distinct entry in the initial list shares a starting or ending point. That is, two lists from the set that have the same starting point, or have the same ending point, but are otherwise totally different.

Disclaimer: this is totally pulled out of my ass, and has not been tested. If it doesn't work, fiddle with it a bit and I think you can get it to.

@pointset = (...);
@final = ();

# The basic premise is to pull the first point off of
# the queue and try to attach any of the remaining
# points in the queue to it. If one of them can be
# attached, remove it as well and attach correctly.
# Then, push the now-longer element onto the end of
# the queue.
#
# If you get through the queue without attaching any
# new elements to the top or bottom, then push it
# onto @final, instead. Eventually, @pointset will be
# empty.

while (defined($node = shift(@pointset)))
{
  for $index (0 .. $#pointset)
  {
    if ($node->[0] ==
        $pointset[$index]->[$#{$pointset[$index]}])
    {
      # Add to front of $node
      shift(@$node); # Avoid point at $node->[0] dup'd
      @$node = (@{$pointset[$index]}, @$node);
      # This splice could be used directly above, but I
      # am aiming for clarity in this example.
      splice(@pointset, $index, 1);
      unshift(@pointset, $node);
      next; # Go back to the top of the while-loop
    }
    elsif ($node->[$#$node] == $pointset[$index]->[0])
    {
      # Add to end of $node
      pop(@$node); # Avoid point at $node->[0] dup'd
      @$node = (@$node, @{$pointset[$index]});
      # Again, this splice could be used directly.
      splice(@pointset, $index, 1);
      unshift(@pointset, $node);
      next; # Go back to the top of the while-loop
    }

    # If we reach this point, then none of the other
    # segments could attach to $node, so move it out
    # of the way.
    push(@final, $node);
  }
}

print scalar(@final) . " resulting graphs\n";
print Data::Dumper::Dumper(\@final);

This isn't as efficient as it could be, since it re-queues the graph and drops out after attaching just one other graph. You could traverse the entire list of sub-graphs, but after enough iterations, you will have the same results (disclaimer about duplicated endpoints notwithstanding).

--rjray

[jasonk]

This is similar to some of my own attempts, and it does run after a few minor fixes (missing a ] bracket on the first if, replacing 'continue' with 'next'), but this attempt has an unusual bug that I can't quite identify that makes it impossible to call it iteratively. The source data contains ten arrayrefs, if you run that array through this function, the return value succesfully merges those ten sections into five, so it worked, but that isn't all the return data contains, it also contains thirty-one copies of those five elements. The second iteration will contain the same five merged elements, along with 625 copies. The third iteration will have 198,130 copies, since my actual source data may contain thousands of points, you can imagine this has a negative impact on memory consumption. :)

As for your other concerns, the actual code does deal with floats in a reasonable manner, and I have other code in another part of the application that checks to make sure I don't have multiple segments with the same starting or ending point.

[rjray]

I've tweaked the code a bit (the fixes you point out, and a change to keep the current node under consideration until such point as it gets sent to @final). But I don't think that my tweaks will solve the problems you describe. Have you created a test application with reasonable data that you could send to me to run myself? Something minimalist, like in the original node?

If so, feel free to email it to me at "rjray at blackperl.com".

--rjray

[jasonk]

The code contained in the original node is my test application, if you take the @data declaration, the merge sub, and the Point package, and put them in a file, all you need to add to get it to run is:

#!/usr/bin/perl -w
use strict;
use Data::Dumper;

# @data declaration here

splice(@data,7,1);
print Dumper(merge(@data));

# merge sub here
# point class declaration here

But see the node I just posted for a working implementation.