Solved

chain

Posted on 2002-05-20
11
391 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

707 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

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now