pairs of number forming chains

mailbox-1691 · 08-10-2015, 10:54 AM

Hello,
I have pairs of numbers which are related with each other,for example, (1,10),(10,19),(1,48),(48,39),(39,30), thus all these pairs forms a chain i.e) 19-10-1-48-39-30. I have many pairs like this corresponding to different chains.

Now, I have two questions, Given a series of pairs how to order them such that they form a chain. Also if I were interested in smaller chains that is a subset of longer chain, how to obtain the possible smaller chain formations?

i.e) in the above example of 19-10-1-48-39-30, smaller chains may be constructed like these
19-10-1, 10-1-48, 1-48-39, 48-39-30
or 19-10-1-48, 10-1-48-39, 1-48-39-30
or 19-10-1-48-39, 10-1-48-39-30

I would like to implement this preferably in FORTRAN. ( I tried many different ways before posting this forum, none of them worked for me and also I apologize if this is a naive question to post here). I would really appreciate any suggestions.

Thanks

millgates · 08-10-2015, 11:33 AM

So what have you tried and where are you stuck?
Is there a reason you need to do this in FORTRAN?
Also, I noticed there are multiple pairings for 1.

Code:

(1,10),(10,19),(1,48),(48,39),(39,30)

Is that a typo? Because if not, then the numbers form something I wouldn't exactly call a "chain".

That said, there should be an easy solution using an (associative) array.
If the pairs are ambiguous, you'll need a graph.

rtmistler · 08-10-2015, 11:51 AM

Hi and welcome to LQ mailbox-1691,

While some of your question is understandable, you may wish to review the LQ Faq where it discusses some more effective ways of asking a question. Millgates is correct in asking "What have you tried?" You discussed that you have tried. A first thing to do might be to write some logic, even in pseudocode to describe your intended tasks.

There are also missing parameters here, such as the definition of each number within the pairs. Are they only positive counting numbers? The set of real numbers? What can they be? How many total pairs can you have? And if given a set of pairs, do you need to construct just one, or all possible chains, and must you use all pairs given all the time, or can you use different combinations as well as permutations?

mailbox-1691 · 08-11-2015, 05:20 AM

The number represent sort of labels that correspond to real space object that are connected linearly. Yes they are integer, and no typo with it, each label can have maximum of two neighbors ( as in the case of real space coordinates ). Not necessarily with FORTRAN, C is also fine. I tried in fortran. First reading all the possible pairs and subjected to recursive search I ended up getting pairs that are connected with other pairs that forms a chain.

Code:

  use common_variables
  do i=1,N
   read, x_1,x_2  ( x_1 and x_2 are in the range of (1,N) )
   store(x1,neighour_count) = x2
  end do
 
 
  do i = 1, N 
   call recursive_chain(i)
   write connected pairs)
 end do

 recursive_chain(tmpi)
 use common_variables
   ....... 
  call recursive_chain(tmpj)
 end recursive_chain

And I do get all the possible pairs that forms a chain.

if I feed in

Code:

I do get two chains, but not in the order as I mentioned here, i.e) 19-10-1-48-39-30 and 50-51-64.

My question is, after my recursive call solves my problem of finding which labels belong to which chain, but I need that in a linear chain order such that edges are terminated with inner members having two neighbours. Also the possible smaller chain combinations as I mentioned in the first post.

rtmistler · 08-11-2015, 06:40 AM

Your code attempts on this? Please post them in [code][/code] tags.

I do see that you've added code tags for reply #4, but the further point of my question was for you to post C or FORTRAN code that you've written and tried. And further to note that you've stated and re-stated your problem statement, however have shown nothing about the actual algorithm you're thinking about. This recursive_chain() function is the core of what you wish to do, but you've shown absolutely nothing about how that works.

Please understand that members of LQ are volunteers, they are not here to do your work for you, the idea behind LQ is that you are here, interested in Linux or associated topics, in this case Programming. And that you need help, but also that you're invested in really learning it and not being fully guided by others.

danielbmartin · 08-11-2015, 09:35 AM

Quote:

Originally Posted by mailbox-1691

... in the above example of 19-10-1-48-39-30, smaller chains may be constructed like these
19-10-1, 10-1-48, 1-48-39, 48-39-30
or 19-10-1-48, 10-1-48-39, 1-48-39-30
or 19-10-1-48-39, 10-1-48-39-30

You provided examples of what you call chains, and that is helpful. Can you also provide a rigorous definition of "chain?" Expressing it in words will (in many cases) get you halfway to expressing it in executable code.

Daniel B. Martin

mailbox-1691 · 08-11-2015, 10:17 AM

Quote:

Originally Posted by danielbmartin

You provided examples of what you call chains, and that is helpful. Can you also provide a rigorous definition of "chain?" Expressing it in words will (in many cases) get you halfway to expressing it in executable code.

Daniel B. Martin

These numbers are integers that represent molecules in real world. The molecules are connected with each other(let us say bonded) in linear fashion, thus forming a chain of connection or chain of bonds. I am mapping those molecules in terms of integer number. ( n^th molecules corresponds to n^th integer, a pair of numbers (i,j) corresponds to i^th and j^th molecule).

millgates · 08-11-2015, 10:39 AM

OK, so each element in the set can have up to to links to other elements, but don't forget that each link has two elements.
And I agree with rtmistler -- you should explain the algorithm you use in the recursive_chain function.

danielbmartin · 08-11-2015, 11:50 AM

Quote:

Originally Posted by mailbox-1691

These numbers are integers that represent molecules in real world. The molecules are connected with each other(let us say bonded) in linear fashion, thus forming a chain of connection or chain of bonds. I am mapping those molecules in terms of integer number. ( n^th molecules corresponds to n^th integer, a pair of numbers (i,j) corresponds to i^th and j^th molecule).

You were asked for a definition of chains and delivered a description of what the numbers mean and where they came from. You meant well but that is not helpful.

It might be better if you said something like this...
"The input file consists of integer pairs (or triples or quads), one per line. The output file consists of integer triples (or quads or five-tuples) which are formed from input lines which have the following properties ... etc. etc." The actual numbers may have been derived from molecules or raindrops or NYSE common stock prices or something else. That background has nothing to do with the definition of "chain."

Daniel B. Martin

rtmistler · 08-11-2015, 12:44 PM

To add to the recent comments, you also are not describing your problem clearly. It's insufficient to just say that there are pairs and you need to combine them. You've been asked the full scope of the problem, which is given the list of pairs, does the algorithm need to always use all pairs to construct chains, or may it use fewer than the entire list of pairs, thus making this not just about permutations, but also about combinations. You also haven't stated whether or not you want more than a single output or if there is to be a primer for the start of given sequences. And that might be nice to know if you prefer certain things like that as parameters and options to your code.

We fully get that you're studying biological sequences and that math is a great aid to this, however if you want help deriving the algorithm, then you have to understand how these various changes will affect the possible outcomes. It will also help you to add flexibility to the coded algorithm in advance versus having to redesign code with each new analytical thought that comes to mind.

astrogeek · 08-11-2015, 01:16 PM

I have been attempting to make some sense of this from the information provided so far, and agree that we need a much better definition of terms, chains and ordering in particular.

Here are some thoughts that have occurred to me that might help...

Your number pairs are the edges of a graph (i.e. your bonds), the numbers being the node labels (i.e. molecules).

Each node may have exactly one or two edges, if one then it is obviously one end of a chain. So in this example...

Code:

(1,10),(10,19),(1,48),(48,39),(39,30)

...we may identify 19 and 30 as end nodes because they only occur once. Traversing the graph along connected edges beginning at node 19 yeilds the node order that you give as the desired result...

Code:

19-10-1-48-39-30

So I would suggest that by "chain" you mean exactly this ordering of nodes. In this view the pairs are strictly unordered pairs, the implied order being given by the direction in which you traverse the graph.

You also state...

Quote:

Originally Posted by mailbox-1691

These numbers are integers that represent molecules in real world. The molecules are connected with each other(let us say bonded) in linear fashion, thus forming a chain of connection or chain of bonds. I am mapping those molecules in terms of integer number. ( n^th molecules corresponds to n^th integer, a pair of numbers (i,j) corresponds to i^th and j^th molecule).

Which is a contradiction within the other information provided. The pair (i,j) certainly does NOT correspond to the i^th and j^th nodes within the ordering of connected nodes (i.e. molecules) as determined from the given edge pairs. As you do not provide any other frame of reference for the (i,j) ordering it becomes very confusing for those tryng to make sense of the chain idea - and probably irrelevant too.

So it is obvious that there is some other, as yet unknown ordering, (i,j) from which the node labels are generated. And the ordering of the node labels (which are only incidentally integers) generated by traversing the graph that results from the given pairing of nodes defines your "chain".

So your ultimate solution will come from an algorithm which identifies the end nodes, picks a direction and traverses the graph of your pair identifiers... regardless of where they come from.

Selecting sub-chains comes down to selecting a starting node (end point) and specifying the number of edges to traverse (length), so you will need to provide some criteria for doing that as well.

Hope this helps to clear some confusion without adding more!

mailbox-1691 · 08-12-2015, 02:29 AM

Quote:

Originally Posted by astrogeek

...we may identify 19 and 30 as end nodes because they only occur once. Traversing the graph along connected edges beginning at node 19 yeilds the node order that you give as the desired result...

Code:

19-10-1-48-39-30

So I would suggest that by "chain" you mean exactly this ordering of nodes. In this view the pairs are strictly unordered pairs, the implied order being given by the direction in which you traverse the graph.

Ahh, this is indeed useful and if I think of some algorithm that transverse either through 19 or 30 ( any one of the edges(say 19) at starting point, and perhaps with a check of whether the other edge(say 30) has been reached at the end), I could get what I desired to expect. This solves my first question.

Thanks astrogeek!

astrogeek · 08-12-2015, 01:12 PM

Quote:

Originally Posted by mailbox-1691

Ahh, this is indeed useful...

Thanks astrogeek!

You are welcome, glad that points in the right direction!

I have thought more about the problem and I wonder if it might not be best solved by a lexer application.

I also think that instead of trying to implement it with arrays, it might be better to think of a linked list. So using a simple flex lexer to build a doubly-linked list of nodes, would be relatively simple to implement and would closely mirror your problem space as well.

astrogeek · 08-12-2015, 07:18 PM

OK, once I had the thought of doing this with a lexer I could not let it go. And as I have a one track brain cell these days it was blocking everything else I needed to do! So having recommended a lexer solution, I decided to see if my own lexer skills were up to the task.

I wrote the flex source code found below from scratch, although I very loosely used an example from the O'Reilly Flex & Bison book as a kind of template.

How it works:

It processes (x,y) pairs from the input into one or more linked lists of node structures.

After processing all input it walks through all nodes identifying end points (nodes with a single edge).

For each end point found it walks the linked list (your chain) begining at that node until it reaches the other end point of that linked list, printing all nodes along the way, in order, in 1-2-3 format (with optional leader text).

This results in each chain being printed twice, once from each end point. You will need to apply your own criteria for selecting a single end point if desired.

Attempting to create a node with more than two edges will produce an error.

C-style single and multi-line comments, and shell style comments are ignored.

You can process multiple disjoint graphs from the same input stream (i.e., chains with no common nodes).

To produce sub-chains you will need to select a starting node of your choice and walk the list to some ending node of your choice. As you have not provided any insight as to how those would be selected I have not attempted to include that functionality. But once the linked list has been processed, all traversals will remain valid so you may safely write another print routine if you like.

To prevent having to read all the code first, I will post the source last, and provide instructions for use and an example first.

Copy and paste the contents of the example.txt file below. It includes two example chains, yours and one of my own.

Then copy and paste the lexer source code below to a file named chlex.lex.

Compile and use as follows... (obviously requires that you have GNU flex installed)

Code:

 --generate lexer code and compile --

# flex -o chlex.c chlex.lex
# gcc -g  -o chlex chlex.c

 -- process from stdin --

# ./chlex <example.txt
FROM: 19 -> 19-10-1-48-39-30
FROM: 30 -> 30-39-48-1-10-19
FROM: 91 -> 91-92-94-95-96
FROM: 96 -> 96-95-94-92-91
Total endpoints = 4

Code:

 -- save to example.txt --

/* Simple graphs with integer node labels */
(1,10),(10,19),(1,48),(48,39),(39,30)
(91,92)(94,92)(95,94)(95,96)

Code:

 -- save to chlex.lex --

/* Robert Allen Aug 12, 2015
 * All rights reserved, including Creator Endowed Unalienable Rights
 *
 * Acknowledgment of right to use, copy, modify and distribute:
 * You already have the right to use, modify and distribute this
 * or any other thought or idea, and need no license or other
 * permission from anyone to do so!
 *
 * Exercise it freely and never concede it to anyone!
 *
 * Abolish the pernicious impediment to human progress known as
 * intellectual property law which obstructs all our future paths
 * only for the immediate gain of a few.
 */
 /* Generates "chain" graph from list of edges (node1,node2)(node2,node3)...
 * Error on node with >2 edges
 * Ignores C and shell style comments
 */

%option noyywrap nodefault

 /* Includes and definitions... */
%{
#include <stdlib.h>
  struct anode {
    int id;
    int edg1;
    int edg2;
  };

  /* simple node lookup table
   * uses node labels (int) as index, must be as large as highest label integer
   */
  #define NUMNODES 256
  struct anode *nodetab[NUMNODES];
  void addnode(int, int);
  void printnodes();
  int x=0;
%}

%%
 /* The lexer rule set */
[0-9]+/,   { x=atoi(yytext); /* Capture on x */}
[0-9]+/\)   { addnode(x,atoi(yytext)); /* Process on y */}
"//".*\n {/* ignore C oneline comments */}
^"#".*\n {/* ignore shell style comments */}
"/*"[\.\n]*"*/" {/* ignore simple C multiline comments */}
.|\n {/* ignore everything else */}
%%

 /* Main function and utilities... */
void addnode(int x, int y)
{
  struct anode *xp=0, *yp=0;
  if(x >= NUMNODES || y >= NUMNODES){
        fputs("anode table overflow\n", stderr);
        abort(); /* table is too small! */
  }
  if(nodetab[x]==0){
        /* node not exists */
        if((xp = malloc(sizeof(struct anode)))==0)
                {
                        fputs("Failed allocating node\n", stderr);
                        abort(); /* fail! */
                }
        xp->id=x;
        xp->edg1=0;
        xp->edg2=0;
        nodetab[x]=xp;
  }
  if(nodetab[y]==0){
        /* node not exists */
        if((yp = malloc(sizeof(struct anode)))==0)
                {
                        fputs("Failed allocating node\n", stderr);
                        abort(); /* fail! */
                }
        yp->id=y;
        yp->edg1=0;
        yp->edg2=0;
        nodetab[y]=yp;
  }
 /* Now set the edge refs */
 if(!nodetab[x]->edg1){
        nodetab[x]->edg1 = y;
 }else if(!nodetab[x]->edg2){
        nodetab[x]->edg2 = y;
 }else{
        printf("Node %d error! ",x);
        fputs("More than 2 edges!\n", stderr);
        abort(); /* fail! */
 }
 if(!nodetab[y]->edg1){
        nodetab[y]->edg1 = x;
 }else if(!nodetab[y]->edg2){
        nodetab[y]->edg2 = x;
 }else{
        printf("Node %d error! ",y);
        fputs("More than 2 edges!\n", stderr);
        abort(); /* fail! */
 }
}

void printnodes()
{
  int i, l=0, f=0, n=0;
  int numends=0;
        /* Locate end nodes and walk them off...*/
        for(i=0;i<NUMNODES;i++){
                if(nodetab[i]){
                        if(nodetab[i]->edg1==0 || nodetab[i]->edg2==0){
                                numends++;
                                //Comment out/edit next line to suppress/alter leader text
                                printf("FROM: %d -> ",nodetab[i]->id);
                                f=i; l=n=0;
                                while(1){
                                        printf("%d",nodetab[f]->id);
                                        n = (nodetab[f]->edg1 && nodetab[f]->edg1!=l)
                                                ? nodetab[f]->edg1
                                                : nodetab[f]->edg2 ;
                                        if(n)
                                        {
                                                l = nodetab[f]->id;
                                                f = n;
                                                printf("-");
                                        }
                                        else{ printf("\n"); break;}
                                }
                 }
                }
        }
        printf("Total endpoints = %d\n",numends);
}

main(argc, argv)
int argc;
char **argv;
{
  int i;
  /* Initialize node list */
  for(i=0;i<NUMNODES;i++){
        nodetab[i]=0;
  }
  yylex();
  printnodes();
}

The lexer seems to be the right tool for this job. And walking the linked lists is much easier and less error prone that multiple orderings of multi-dimensional arrays.

I hope this is useful to you, at least as a good starting point! Writing it was satisfying on some level to myself!

mailbox-1691 · 08-13-2015, 10:23 AM

Quote:

Originally Posted by astrogeek

OK, once I had the thought of doing this with a lexer I could not let it go. And as I have a one track brain cell these days it was blocking everything else I needed to do! So having recommended a lexer solution, I decided to see if my own lexer skills were up to the task.

I wrote the flex source code found below from scratch, although I very loosely used an example from the O'Reilly Flex & Bison book as a kind of template.

Thanks and I am humbled. Didn't know lexer can easily handle things here.

Quote:

Originally Posted by astrogeek

This results in each chain being printed twice, once from each end point. You will need to apply your own criteria for selecting a single end point if desired.

To produce sub-chains you will need to select a starting node of your choice and walk the list to some ending node of your choice. As you have not provided any insight as to how those would be selected I have not attempted to include that functionality. But once the linked list has been processed, all traversals will remain valid so you may safely write another print routine if you like.

Parsing with the flex looks cryptic to me. I desired to get the chain with starting point as any one of the edges (not the both, anyway I have divided by two while doing the statistics). For the sub-chains I got it through with simple loop in fortran

Code:

  read (x(i), i=1,N)
! N is 6 in my example 19-10-1-48-39-30

 do i=1,N
   if(i+1.le.N) then
    write x(i),x(i+1)
   end if
   if(i+1.lt.N) then
    write x(i),x(i+1),x(i+2)
   end if
   if(i+1.lt.N-1) then
    write x(i),x(i+1),x(i+2),x(i+3)
   end if
   if(i+1).lt.N-2) then
    write x(i),x(i+1),x(i+2),x(i+3),x(i+4)
 end do



for the desired sub-chains of 
 
 1) 19-10,10-1,1-48,48-39,39-30 

 2)  19-10-1
     10-1-48
     1-48-39
     48-39-30

 3) 19-10-1-48
    10-1-48-39
    1-48-39-30

 4) 19-10-1-48-39
    10-1-48-39-30

I know my loop and write statements are not generic!, since I'm parsing for the same N( but different file for different N), it works.