Re^19: Finding All Paths From a Graph From a Given Source and End Node

That dataset is an excellent test sample. Thankyou.

BTW. CSV (Comma Seperated Values) data normally actually has commas separating the values :). Using white space to separate values that themselves contain whitespace gave me pause for thought. (I wonder how the thou-shalt-not-parse-csv-yourself brigade would handle that?)

For my purposes, I just ignored the middle column. I tacked the data on the end of my test script and it found and output all possible paths from all possible starting points in 0.04 seconds. Including remembering which starting point generated the longest path, which turned out to be "2,4,4-Trimethyl-1-pentanol":

c:\test>904729-3 >nul
Took 0.04846
2,4,4-Trimethyl-1-pentanol
        ->2,4,4-Trimethylpentanal
        ->2,4,4-Trimethylpentanoate
        ->2,4,4-Trimethylpentanoyl-CoA
        ->2,4,4-Trimethylpent-2-enoyl-CoA
        ->2,4,4-Trimethyl-3-hydroxypentanoyl-CoA
        ->2,4,4-Trimethyl-3-oxopentanoyl-CoA
        ->2,4,4-Trimethyl-3-oxopentanoate
        ->2,2-Dimethyl-3-pentanone
        ->1-Hydroxy-4,4-dimethylpentan-3-one
        ->4,4-Dimethyl-3-oxopentanal
2,4,4-Trimethyl-1-pentanol
        ->2,4,4-Trimethylpentanal
        ->2,4,4-Trimethylpentanoate
        ->2,4,4-Trimethylpentanoyl-CoA
        ->2,4,4-Trimethylpent-2-enoyl-CoA
        ->2,4,4-Trimethyl-3-hydroxypentanoyl-CoA
        ->2,4,4-Trimethyl-3-oxopentanoyl-CoA
        ->Pivalyl-CoA
2,4,4-Trimethyl-1-pentanol
        ->2,4,4-Trimethylpentanal
        ->2,4,4-Trimethylpentanoate
        ->2,4,4-Trimethylpentanoyl-CoA
        ->2,4,4-Trimethylpent-2-enoyl-CoA
        ->2,4,4-Trimethyl-3-hydroxypentanoyl-CoA
        ->2,4,4-Trimethyl-3-oxopentanoyl-CoA
        ->Propanoyl-CoA
[download]

The script excluding most of the data:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use List::Util qw[ shuffle ];
use Time::HiRes qw[ time ];

sub _pathsFrom2 {
    use enum qw[ CODE GRAPH START PATH SEEN ];

    return $_[CODE]->( @{ $_[PATH] }, $_[START] )
        unless exists $_[GRAPH]->{ $_[START] };

    for ( @{ $_[GRAPH]->{ $_[START] } } ) {
        if( exists $_[SEEN]->{ $_[START] . "-$_" } ) {
            return $_[CODE]->( @{ $_[PATH] }, $_[START] );
        }
        else {
            _pathsFrom2(
                @_[ CODE, GRAPH ], $_,
                [ @{ $_[PATH] }, $_[START] ], 
                { %{ $_[SEEN] }, $_[START] . "-$_", undef }
            );
        }
    }
}
sub pathsFrom2(&@) { _pathsFrom2( @_, [], {} ) }

my %graph;

<DATA>;

while( <DATA> ) {
    chomp;
    my @fields = split '\s{2,}';
    push @{ $graph{ $fields[0] } }, $fields[ 2 ];
}

my $start = time;

my @best = ( 0, 0 );
for my $start ( keys %graph ) {
    pathsFrom2{
        @best = ( scalar @_, $start ) if scalar @_ > $best[ 0 ];
        print join "\n\t->", @_;
    } \%graph, $start;
}

printf STDERR "Took %.5f\n", time() - $start;

pathsFrom2{
    print STDERR join "\n\t->", @_;
} \%graph, $best[ 1 ];


__DATA__
Substrate    Enzyme    Product
(-)-(1R,2S,5R)-Menthol    menthol dehydrogenase    (-)-(2S,5R)-Menthon
+e
(-)-(2S,5R)-Menthone    menthone dehydrogenase    (5R)-Menth-2-enone
(+)-(3S,4R)-cis-3,4-Dihydroxy-3,4-dihydrofluorene    3,4-dihydroxy-3,4
+-dihydrofluorene dehydrogenase    3,4-Dihydroxyfluorene
(+)-(4R)-Limonene    limonene 1,2-monooxygenase    (4R)-Limonene-1,2-e
+poxide
(+)-Camphor    camphor 5-monooxygenase    5-exo-Hydroxycamphor
(+)-cis-3,4-Dihydrophenanthrene-3,4-diol     cis-3,4-dihydrophenanthre
+ne-3,4-diol dehydrogenase    Phenanthrene-3,4-diol
(1-Methylpentyl)succinate    succinyl-CoA transferase    (1-Methylpent
+yl)succinyl-CoA
(1-Methylpentyl)succinyl-CoA    methylmalonyl-CoA mutase    (2-Methylh
+exyl)malonyl-CoA
(1R)-Glutathionyl-(2R)-hydroxy-1,2-dihydronaphthalene    No Kegg enzym
+e supplied    (1R)-N-Acetyl-L-cysteinyl-(2R)-hydroxy-1,2-dihydronapht
+halene
(1R)-Glutathionyl-(2R)-hydroxy-1,2-dihydronaphthalene    No Kegg enzym
+e supplied    (1R,2R)-3-[(1,2-Dihydro-2-hydroxy-1-naphthalenyl)thio]-
+2-oxopropanoic acid
(1R)-Hydroxy-(2R)-glutathionyl-1,2-dihydronaphthalene    No Kegg enzym
+e supplied    (1R)-Hydroxy-(2R)-N-acetyl-L-cysteinyl-1,2-dihydronapht
+halene
...
[download]

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^19: Finding All Paths From a Graph From a Given Source and End Node Select or Download Code