• C

chain

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
MongsterAsked:
Who is Participating?
 
TriskelionConnect With a Mentor Commented:
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
 
jonninCommented:
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
 
TriskelionCommented:
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
Managing Security & Risk at the Speed of Business

Gartner Research VP, Neil McDonald & AlgoSec CTO, Prof. Avishai Wool, discuss the business-driven approach to automated security policy management, its benefits and how to align security policy management with business processes to address today's security challenges.

 
z_skyCommented:
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
 
ygal02Commented:
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
 
MongsterAuthor Commented:
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
 
TriskelionCommented:
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
 
ygal02Commented:
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
 
shlezmanCommented:
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
 
ygal02Commented:
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
 
TriskelionCommented:
No comment???
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.