Solved

# chain

Posted on 2002-05-20
404 Views
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
Question by:Mongster
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 2

Expert Comment

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

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

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

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

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

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

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).

Good Luck.
0

LVL 6

Accepted Solution

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

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

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

ID: 7098625
No comment???
0

## Featured Post

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
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 how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
###### Suggested Courses
Course of the Month7 days, 23 hours left to enroll