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

[BrowserUk]

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

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
...