Solved

chain

Posted on 2002-05-20
11
400 Views
Last Modified: 2010-04-15
if I have this
{ (1,2), (2,3), (5,3), (6,7), (2,1), }
how do I detect that there is a chain in the
input? where each pair is ( start, destination )

(1,2),(2,1) forms a chain...

another example
{ (1,5), (3,4), (5,3), (3,1), (7,8) }
where (1,5),(5,3),(3,1) forms a chain...

thanks...
I have no understanding of a graphs.

regards,
Mongster
0
Comment
Question by:Mongster
11 Comments
 
LVL 2

Expert Comment

by:jonnin
ID: 7023785
it looks like a chain happens when a coordinate is repeated twice. (is this correct?)

so create an array from 0... max coordinate.
set the array to all zeros.

loop through all coordinates and increment array[value]

loop through the array. Find coordinates with 2 or more in the value. Those are in a chain.

0
 
LVL 6

Expert Comment

by:Triskelion
ID: 7024994
Will you ever have any repeats?

{(1,2)(1,3)(2,4)(4,1)}
Where
   1,2 chains with 4,1
and
   1,3 chains with 4,1
?
0
 

Expert Comment

by:z_sky
ID: 7026679
It sames not a complex question:

Suppose point is (l,r).

Repeat to search next point which's l is equal to the previos one's r, until its' r is equel to the first one's l.

And I suppose single point like (1,1) is a chain.

Here is the code:

#define ITEMS 100
typedef struct {
    int l;
    int r;
}point;

point data[ITEMS];
int index[ITEMS];

int i,j,k;

for(i=0;i<ITEMS;i++) {
    index[i] = 0;
    k = i;
    for(j=i;j<ITEMS;j++) {
        if (data[j].l==data[k].r) {
            index[k] = j;
            k = j;
            if (data[j].r==data[i].l) {
                //got a chain here
                index[j] = 0;
                for(k=index[i];k;k=index[k]) {
                    printf("%d(%d,%d) ",k,data[k].l,data[k].r);
                }
                printf("\n");
                break; //to find next chain
            }
        }
    }
}

Am I right? :-)
0
ScreenConnect 6.0 Free Trial

At ScreenConnect, partner feedback doesn't fall on deaf ears. We collected partner suggestions off of their virtual wish list and transformed them into one game-changing release: ScreenConnect 6.0. Explore all of the extras and enhancements for yourself!

 
LVL 3

Expert Comment

by:ygal02
ID: 7035149
What is the maximum number that might appear in each one of the nodes ? Do you have any limitation ? Or does the length of the set always finite ?
If one of the above answers is 'yes' then the problem is much simpler...

Good Luck
0
 

Author Comment

by:Mongster
ID: 7047284
this circular chain thing is like a air plane route.
for example,
( (Melbourne, Singapore), (Singapore, Hong Kong),
(Hong Kong, Osaka), (Osaka, Singapore), (Hong Kong, BeiJing) )

here, ( (Singapore, Hong Kong), (Hong Kong, Osaka),
(Osaka, Singapore) )
will form a circular chain.

Hopes this clarifies some doubts.

;)

regards,
Mongster
0
 
LVL 6

Expert Comment

by:Triskelion
ID: 7048161
Can you only start at the beginning of a chain?
What happens if you start at (Hong Kong, Osaka)?
Can you go to (Osaka, Singapore) and stop?

Or do you have to find the absolute beginning before running the entire chain?

If it's a circular chain, do you stop after one time through the chain?

Can chains cross each other?
((Singapore, Hong Kong), (Hong Kong, Osaka),
   (Osaka, Hong Kong))
0
 
LVL 3

Expert Comment

by:ygal02
ID: 7049343
Well, you'll have to get some basic graph knowledge for this (I don't see any other way around).
Anyway, you can get our help if you'll need it...

I suggest the following solution:
1.Build a graph with Vertices which are your 'places to go', and Edges according to the list of pairs you have, means if you have a pair (3,4) in your list then you will add an arc between the nodes 3 & 4 in your graph.
2.For each node in the graph perform a DFS (Depth First Search), which is a simple and easy to implement algroithm.
3. Return the longest path you found in step 2. (or all of them if you prefer) If the longest path is of length 2 this actually means that you have no path in the graph.

The graph can be implemented either with linked list of neighbours for each node, or with neighbour matrix (which is my prefered way in this case).

Tell us if you need more info...
Good Luck.
0
 
LVL 6

Accepted Solution

by:
Triskelion earned 100 total points
ID: 7049426
I was playing around with this.
It may trigger something for you.
I'm sure it's not perfect.
Modify the destinations in the xarrDest structure array.

#include <stdio.h>

typedef     enum {FALSE, TRUE} BOOL;

typedef     enum     {eNONE=-1, eSINGAPORE=0, eHONG_KONG, eOSAKA, eROME} eDESTINATIONS;
typedef     struct     tagDESTINATIONS
{
     char*     pstrCity;
     short     numOriginating;
     short     numConnecting;
     BOOL     blnFoundOrExhausted;
}     DESTINATIONS;

DESTINATIONS     xarrDest[]=
     {
          {"Singapore",     eSINGAPORE, eOSAKA,          FALSE},
          {"Hong Kong",     eHONG_KONG, eSINGAPORE,          FALSE},
          {"Osaka",          eOSAKA,          eHONG_KONG, FALSE},
          {"",                    eNONE,          eNONE,          FALSE}
     };


int main(void)
{
     auto     int     intPrintLoop=0;
     auto     int     intLoop=0;
     auto     int     intNumFlights=0;

     printf("%-15s Orig Dest\n%-15s ---- ----\n", "City", "----");
     for (intPrintLoop=0; xarrDest[intPrintLoop].numOriginating != eNONE; intPrintLoop++)
          {
          printf("%-15s %4d %4d\n",
               xarrDest[intPrintLoop].pstrCity,
               xarrDest[intPrintLoop].numOriginating,
               xarrDest[intPrintLoop].numConnecting);
          intNumFlights++;
          }

     printf("--------------------\n");
     while (intLoop < intNumFlights)
          {
          static     int     intInnerLoop=0;
          static     BOOL     blnMatch=FALSE;

          if (!xarrDest[intLoop].blnFoundOrExhausted)
               {
               printf("%s", xarrDest[intLoop].pstrCity);
               }

          for (intInnerLoop=0; intInnerLoop < intNumFlights; intInnerLoop++)
               {
               if ((xarrDest[intLoop].numConnecting==xarrDest[intInnerLoop].numOriginating))
                    {
                    if (!xarrDest[intLoop].blnFoundOrExhausted)
                         {
                         xarrDest[intLoop].blnFoundOrExhausted=TRUE;
                         printf(" -> %s",xarrDest[intInnerLoop].pstrCity);
                         blnMatch=TRUE;
                         intLoop=intInnerLoop;
                         intInnerLoop=-1;
                         }
                    }
               }
          if (!xarrDest[intLoop].blnFoundOrExhausted)
               {
               printf("\n");
               }
          if (!blnMatch)
               {
               intLoop++;
               }
          blnMatch=FALSE;
          }
     return 0;
}
0
 
LVL 2

Expert Comment

by:shlezman
ID: 7053774
you can label each parir,
{[index],c0,c1}
{{[0],0,1}{[1],2,4}{[2],1,3}{[3],4,5}{[4],3,2}}
sort the whole data, getting :
{[0],0}{[0],1}{[2],1}{[1],2}{[4],2}{[2],3}{[4],3} ...
then scanning for duplicate numbers (2,2 3,3) and using the index attched to go on with the scan while saving the other end of the chain, when reaching the end of the chain (on one side) restore the other side and go on scanning. you'll need an endless loop protection.

first pair detected :
{[0],1}{[2],1}
save {[2]}
check the pair of {[0],0,1} which is 0
thereis no pair to 0 ->
 one end of the cahin detected
restore {[2]}
check the pair of {[2],1,3} which is 3
there is a pair to 3 ->
 check the pair of {[4],3,2} which is 2
 ... {[1],2,4}
there is no need to scan the same node twice.

Hope it is clear (though it might look abit messy)
0
 
LVL 3

Expert Comment

by:ygal02
ID: 7055496
Mongster,
I'm missing something here, what exactly do you need ?
An algorithm or a code (in a specific language) ?
Or maybe just the concept ?
0
 
LVL 6

Expert Comment

by:Triskelion
ID: 7098625
No comment???
0

Featured Post

Back Up Your Microsoft Windows Server®

Back up all your Microsoft Windows Server – on-premises, in remote locations, in private and hybrid clouds. Your entire Windows Server will be backed up in one easy step with patented, block-level disk imaging. We achieve RTOs (recovery time objectives) as low as 15 seconds.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question