Formalizing an array type problem, looking for solution

[melmoth]

An array of hashes, each hash containing one path, its ID, and its order ( foreward (F) or reverse (R) )

each path is initialized in the F position

my @paths = [ { id => 1, path => [A,B], order => 'F' }, { id => 2, pat
+h => [C,D,E], order => 'F' }, { id => 3, path => [E,B], order => 'F' 
+} ];

each node or vertex of each path also has an orientation ( + or - )

my %plus_minus;
$plus_minus{1}{A} = '+';
$plus_minus{1}{B} = '+';
$plus_minus{2}{C} = '+';
$plus_minus{2}{D} = '-';
$plus_minus{2}{E} = '-';
$plus_minus{3}{E} = '-';
$plus_minus{3}{B} = '-';

You can reverse the order of a path ( e.g., A, B to B, A )

When you reverse order from F => R or R => F you also switch the orientation of each node in the path from + to - or - to +

The paths with orientations look like this:

1 .A+ : B+

2. C+ : D- : E-

3. E- : B-

this is the problem input for output, i'd like to know whether or not it is possible by reverseing path orders to create a consensus path and also what is the way to do this such that you are guaranteed to find the consensus path

for example, if we reversed path 1 we'd get:

1. B- : A-

2. C+ : D- : E-

3. E- : B-

and the resulting consensus path would be:

C+ : D- : E- : B- : A-

but it's not clear to reverse path 1 first; for example; what if started by reversing path 3? So you can't proceed randomly. Does anyone recognize this problem? Does it have a solution? Thanks.

[NetWallah]

Try one of the Graph modules like Graph::Easy.

[Anonymous Monk]

#!/usr/bin/perl -l

# http://perlmonks.org/?node_id=1170935

use strict;
use warnings;

sub flip { join '', reverse map tr/-+/+-/r, /\w./g }

my $all = ' ' . join ' ', map { "$_," . flip() . ' ' } map tr/ :\n//dr
+, <DATA>;

my %firsts;
@firsts{ $all =~ /[, ](\w[+-])/g } = ();
my @queue = map "$_ $all", sort keys %firsts;

while( $_ = shift @queue )
  {
  if( /^(\S+)\s*$/ )
    {
    print join ' : ', $1 =~ /\w./g;
    }
  else
    {
    /^(\S*)(\w.)( .*? )\2([\w+-]*),[\w+-]*( .*)$(?{
      push @queue, "$1$2$4$3$5" })(*FAIL)/;
    /^(\S*)(\w.)( .*? )[\w+-]*,\2([\w+-]*)( .*)$(?{
      push @queue, "$1$2$4$3$5" })(*FAIL)/;
    }
  }

__DATA__
A+ : B+
C+ : D- : E-
E- : B-

[GrandFather]

I've no idea what a "consensus path" is so the following code, while fun to write, is probably wildly wide of what you want to achieve. It may act as a starting point for discussion though.

#!/usr/bin/perl -l
use strict;
use warnings;

my @paths;

push @paths, [map {chomp; $_} split /\s*:\s*/] while <DATA>;

my @pattern = @{pop @paths};

for my $part (@pattern) {
    my ($node, $dir) = split '', $part;

    for my $testPattern (@paths) {
        if ($dir eq '+') {
            next if $testPattern->[0] !~ $node;
            $part = $testPattern;
            last;
        } else {
            next if $testPattern->[-1] !~ $node;
            $part = [map {tr~+-~-+~; $_} reverse @$testPattern];
            last;
        }
    }
    
    die "Can't match $part in '@pattern'\n" if 'ARRAY' ne ref $part;
}

print join ' : ', map {@$_} @pattern;

__DATA__
A+ : B+
C+ : D- : E-
C+ : E-

Prints:

C- : D+ : E+ : E+ : D+ : C-

[Anonymous Monk]

I think the OP means a consensus path is a join of all the segments where the segments are joined by overlaying identical elements (thus deleting one) at the joining ends. By this rule the two valid "consensus paths" are

A+ : B+ : E+ : D+ : C-
C+ : D- : E- : B- : A-

which are the reverse (and sign change) of each other.

I do wish the OP would speak up because I have a sneaking suspicion his real data is not all single letters, and so my solution Re: Formalizing an array type problem, looking for solution above will need "tweaking".

[GrandFather]

Give us a context and explain how this is a Perl problem. At present it looks like an algorithm that you are struggling with independent of implementation. When you turn it into an implementation issue using Perl we are likely to be more use to you.

If it's just the algorithm you are having trouble with, at least mark the question off topic (put [OT] at the start of the title.

[Anonymous Monk]

sorry I'll use OT from now on I didn't know anyways, yes, I tried a solution to the problem in Perl and I have the code and can post it but ~5% of the time it doesn't work, at least with the data that I'm using as input.

[GrandFather]

It's only OT if there is no Perl content. Posting the code and getting help with it is exactly the sort of thing this site is for.

[BrowserUk]

explain how this is a Perl problem

Cos this place is so hopping and jumping with vital Perl questions that we don't have time to consider anything that isn't Perl.

The fact that Perl is possibly the ideal language for exploring algorithms to solve this problem doesn't matter because you don't see an immediate solution and you're too lazy to investigate it.

Way to go man. You used to be one of the most tolerant, hardworking and helpful guys around here...