Comments/Help on Ring Element Id Subroutine? 
Author Message
 Comments/Help on Ring Element Id Subroutine?

Hey all,

After 6 weeks and many usenet posts my fragile baby is taking shape.
I'd appreciate any advice.

%ehash is a %HoH which contains all the nodes which 'might' (ring
-node -ring is a case I'll need to catch) be in a ring, multiple
individual rings, fused rings, or any combination thereof. %ehash is
the result of removing all the deadends from the original hash,
including branched linear chains.

%ehash{C0}{C1} = 3 is a triple bond between C0 and C1.
%ehash{C1}{O3} = 2 is a single bond between C1 and O3.

of course %ehash{C1}{C0} = 3 also exists...

something to worry about...but for now I can let this one go...

backtracking. Problem is I can't figure out how to implement this idea
if -for a 3 edge node - the path happened to go through one of those
'other' nodes...the ring will not be detected. This is the major
reason - besides near complete ignorance :) - for my post.

Can I find and identify all the elements of fused and unfused rings
with a setup like this one? Or will I need to ultimately compare
arrays anyway :) Don't know how to do this BTW:)




        $flast=$slipe; #make sure there are no damned 'uninit' errors..

    }

sub pick_cherries {#have no idea why I called it this

lot of #sense, had no idea what they were yesterday.
    my $fnexter;

        if ((exists ($ehash->{ $flast }->{ $fnexter })) &&

$fnexter was part of the sweep
#this will be false and the ring will be missed.



            if ((exists ($ehash->{ $slipe }->{ $fnexter })) && ( $flast ne
$slipe )) {




such a way it may be reasonably compared with other such arrays.

            }
            $flast = $fnexter;
            &pick_cherries($ehash, $slipe, $flast, $gt2, $bt);

        }
    }

Quote:
}

Help much appreciated!

Thanks,
entropy



Tue, 15 Nov 2005 06:22:28 GMT  
 Comments/Help on Ring Element Id Subroutine?

Quote:
> Hey all,

> After 6 weeks and many usenet posts my fragile baby is taking shape.
> I'd appreciate any advice.

> %ehash is a %HoH which contains all the nodes which 'might' (ring
> -node -ring is a case I'll need to catch) be in a ring, multiple
> individual rings, fused rings, or any combination thereof. %ehash is
> the result of removing all the deadends from the original hash,
> including branched linear chains.

> %ehash{C0}{C1} = 3 is a triple bond between C0 and C1.
> %ehash{C1}{O3} = 2 is a single bond between C1 and O3.

> of course %ehash{C1}{C0} = 3 also exists...

[snip code and algorithm and so on...]

I don't understand the problem domain or the representation of the algorithm
at all, and reading through the perl code by itself is too much work...

Sample input and output is needed.

An assignment to %ehash which doesn't contain a ring, and another which
does, and one which does but which the code doesn't find.

Searching for a ring still makes me instantly think of depth first search
as the solution, but sample cases dramatically reduce the work required to
understand the code.

--
Sam Holden



Tue, 15 Nov 2005 06:38:18 GMT  
 Comments/Help on Ring Element Id Subroutine?

now that you have posted some code, i will be glad to slice and dice
it.

enjoy the ride  :)




why clear it and then push one element onto it? do you mean to

  e>         $flast=$slipe; #make sure there are no damned 'uninit' errors..

        to just pass a new array with $slipe you could use:



  e>     }

  e> sub pick_cherries {#have no idea why I called it this

you should have an idea. the names that you choose are among the most
important coding decisions you ever make. the computer doesn't care
about the names you choose but humans do. so pick names other coders
will understand. the names should actually reflect how some thingy is being
used and they should not just be a mnemonic for you.


  e> lot of #sense, had no idea what they were yesterday.

have you read all of perlreftut, perlref, perldsc and perllol? then you
will learn all about refs.

  e>     my $fnexter;


  e>         if ((exists ($ehash->{ $flast }->{ $fnexter })) &&

you can remove internal -> ops.

        if ((exists ($ehash->{ $flast }{ $fnexter })) &&


don't call subs with & unless you want its special behavior.

  e> $fnexter was part of the sweep
  e> #this will be false and the ring will be missed.


above. you still can combine those two lines (way above) into:




  e>             if ((exists ($ehash->{ $slipe }->{ $fnexter })) && ( $flast ne
  e> $slipe )) {




  e> such a way it may be reasonably compared with other such arrays.

i just have the feeling this can be made much simpler. for one thing
using hashes might clean it all up. you can use them for any form of
structure and you can check for rings with a single lookup and not with
a loop over a list. i am sure someone else will actually show such a
version.

  e>             }
  e>             $flast = $fnexter;
  e>             &pick_cherries($ehash, $slipe, $flast, $gt2, $bt);

again, drop the &. that sub name and those var names need to be
changed. just looking at that single call tells me nothing about what
the hell it is. this is where the coder is making the code impenetrable
and perl has nothing to do with it.

consider picking good names to be a challenge to yourself. have you ever
used a thesaurus to find good names? have you ever made major global
name changes when your little birdie tells you to? have you ever slugged
a cow-orker because of their bad names?

uri

--

--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs  ----------------------------  http://jobs.perl.org



Tue, 15 Nov 2005 07:00:07 GMT  
 Comments/Help on Ring Element Id Subroutine?

Quote:

> I don't understand the problem domain or the representation of the algorithm
> at all, and reading through the perl code by itself is too much work...

Agreed :) I'm trying to put something more clear together right now...

Quote:
> Sample input and output is needed.

Ok, I'll try to use your earlier dfs examples.

Quote:

> Searching for a ring still makes me instantly think of depth first search
> as the solution, but sample cases dramatically reduce the work required to
> understand the code.

Sam, though I'm not quite sure how DFS works it sounds like its the way to
go. I tried making a go of it with your sub but didn't understand its
innards (my lack of perlknowledge) enough to make a stab at modification.

Be back in 1/2 hour...

entropy



Tue, 15 Nov 2005 07:35:12 GMT  
 Comments/Help on Ring Element Id Subroutine?
Ok,

I de-cuted the code and ran a ?simple? example -> Hope this makes it easier to help me out. Thanks!

##First the code:


Quote:
>2 connections


backtrack

        $last_node=$first_node;
        #The neighbor looks at neighboring molecules and, if the exist, adds them
to an array.

    }

sub the_neighbor {

    my $neighbor;

#consider each atom in the ring_atom list a possible neighbor

#if a bond/edge occurs between $last_n and $neighbor && $neighbor has not been looked at before




            if ((exists ($connect_node->{ $first_n }->{ $neighbor })) && ( $last_n ne $first_n )) {
#if a bond/edge occurs between first and neighbor and last is not the same as first




            }
            $last_n = $neighbor;
            &the_neighbor($connect_node, $first_n, $last_n, $ring_atoms, $path);
#go find another neighbor which is not a) the first atom or b) the last one

        }
    }

Quote:
}

For the input previously given me in the dfs routine this is the
input/output: If I have anything left tomorrow after class I will get a
molecule with ~20 atoms...

# H   H       H   H
# |   |       |   |
# C - C - C - C - C
#  \ /         \ /
#   C           C
#   |           |
#   H           H
my %graph2 = ( C1=>{H1=>1, C2=>1}, C2=>{H2=>1, C3=>1},
        C3=>{H3=>1, C1=>1, C4=>1}, C4=>{C5=>1}, C5=>{H4=>1, C6=>1},
        C6=>{H5=>1,C7=>1}, C7=>{H6=>1, C5=>1});

atoms_in_rings:C6 C5 C3 C7 C2 C1
Most Heavily Connected:C3
All Atoms In Rings:C6 C5 C7 C1 C2
C1 C3 are connected
C3 C1 C2 are connected

program ends without finding a ring. I'm not sure how my program would
handle hydrogens so I'll take a closer look in the am (is 4am now..)



Tue, 15 Nov 2005 10:25:10 GMT  
 Comments/Help on Ring Element Id Subroutine?

Quote:

> Ok,

[snip code and data]

That code isn't good enough, I can't copy and paste and run it.


qw/C1 C2 C3 C4 C5 C6 C7/. But the code didn't produce any output.

--
Sam Holden



Tue, 15 Nov 2005 11:30:59 GMT  
 Comments/Help on Ring Element Id Subroutine?

Quote:

> # H   H       H   H
> # |   |       |   |
> # C - C - C - C - C
> #  \ /         \ /
> #   C           C
> #   |           |
> #   H           H
> my %graph2 = ( C1=>{H1=>1, C2=>1}, C2=>{H2=>1, C3=>1},
>         C3=>{H3=>1, C1=>1, C4=>1}, C4=>{C5=>1}, C5=>{H4=>1, C6=>1},
>         C6=>{H5=>1,C7=>1}, C7=>{H6=>1, C5=>1});

> atoms_in_rings:C6 C5 C3 C7 C2 C1
> Most Heavily Connected:C3
> All Atoms In Rings:C6 C5 C7 C1 C2
> C1 C3 are connected
> C3 C1 C2 are connected

OK, now we are getting somewhere.  You show us the molecule (with many
open valences, but that's besides the point).  You show us the
representation of the molecule (Is it the entire representation? i.e.
is there also a list of atoms, or do you assume that "keys %graph2" will
return all atoms (i.e. is it possible for a graph to have isolated single
atoms?)).

And you show us the output.  Unfortunately, appears to be the actual ouput
you got,  not the desired output you want.  I'm having trouble figuring out
what it is you want.  I can think of many things you might want:

1) Given a molecule, does it have any rings?

2) Given a molecule, how many rings, if any, does it have?

3) Given a molecule, which of its atoms are in a ring?

4) Given a molecule, which of its bonds are in a ring?

5) Given a molecule and an atom in it, how many rings, if
any, is it in?

6) Given a molecule and a bond in it, how many rings, if
any, is it in?

7) Given a molecule and an atom in it, what is the size of the smallest
ring, if any, containing that atom?

8) Given a molecule and a bond in it, what is the size of the smallest
ring, if any, containing that bond?

and on and on and on.

Do you want exactly one of these things?  If so, which?  Do you want
all of these?  Do you want something else altogether?  If you want
more than one of the above, what kind of relative efficiencies would
you want?

Given a solution to question 8, questions 1-4 and 7 can all
be easily (but not necessarily efficiently) solved by creative application
of 8.  Heck, I bet 5 and 6 can be too, if I put my mind to it.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service              New Rate! $9.95/Month 50GB



Fri, 18 Nov 2005 23:19:21 GMT  
 Comments/Help on Ring Element Id Subroutine?

Quote:
> Given a solution to question 8, questions 1-4 and 7 can all
> be easily (but not necessarily efficiently) solved by creative application
> of 8.  Heck, I bet 5 and 6 can be too, if I put my mind to it.

> Xho

:) Xho, thanks for the comments. I've got the idea now, now I'm mostly
struggling with the programming part. Don't know why it took so long, I
think I was trying to do too much at once.

Here are my major problems :)

a) My 'rings' are trapped in a 'if statement' in a subroutine. (I can print them to screen,
but can't get them back to main as arrays, not sure how I would name them
as hashes - multiple rings w/same key).

b) I haven't managed to find a way to force perl evaluate a two degree
atom as the first element of a DFS. (When a 3 degree atom is first the DFS
doesn't work.

Other than that I think I'm out of the woods....

Thanks man,
entropy



Sat, 19 Nov 2005 05:47:11 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. how to get the widget id in the callback subroutine

2. automatic file name generation (id.01 id.02 ... id.10 id.11 ...)

3. Real user id and effective user id

4. performing subroutine on a strange set of elements from array

5. Can array elements be subroutines?

6. Help - Subroutine within a Subroutine Illegal?

7. looking for unique-id generator/need help with CPAN

8. Ring a bell?

9. please help - session id generators?

10. Set group id perl - HELP

11. A Three Ring Circus: multi-window perldb

12. Ringing the BEL in perl.

 

 
Powered by phpBB® Forum Software