[C++] How to check if a graph is in a cycle

[saiz66]

Basically I am trying to check if a graph is in a cycle. It might be a little hard to explain but in the pics I have below you can see P1, P2, P3. There are arrows from one to others. If one array leads to one and to another and back to itself then its in a cycle. The graph below is not in a cycle. I have stored the information such that the P's correspond to the indexes of the array and the linked lists tell where that P is pointing to. P1 is pointing to both P2 and P3 therefore the array's index is 1 for P1 and with links of 2 and 3, meaning its arrows are pointing to P2 and P3. The problem is I am trying to find a simple and easy way to figure out how to find if there is a cycle. For example if P1 is pointing to P2 and P2 is pointing to P3 and P3 is pointing back to P1 that would be a cycle. Thanks for any help!!!!

Edited August 10, 2004 by saiz66

[Genesi]

You might need two pointers one that points to the next one and one that points to the previous. If all three points then theirs your circle. Not sure if thatmake since but I'll check into it and look it up a bit.

[LlamaTrauma]

First off, I don't think that an array of linked lists is the best way to do this. Though it's just my preference, I'd recommend setting up a 2d array as your adjacency matrix. Whenever using graphs, adjacency matrices tend to be the way to go. A recursive or iterative function(Your personal preference) will easily do the rest :D

[saiz66]

I thought of an idea.. but it would be very complicated.. well not that complicated but it would have many steps.. first trace the P1 of the first node it is pointing to in this case 2 and since index 2 is pointing to 3 go to index 3 and look up 1 and since we started from 1, that is P1 it is in a cycle.. even though I stated in my frist post that it wasnt in a cycle.. I guess I was wrong... this way seems to be the "hard" way of doing it.. i was just wondering if there was an easier way.

[saiz66]

To Llama Trauma:

I guess you could be right.. but this was the way suggested by the prof so I was just following his suggestions.

[LlamaTrauma]

Well if that is the way your teacher wants you to do it...then do it that way. It's definetly possible. Just store the starting node in memory and hop between array positions searching the linked lists.

[saiz66]

hmmm.. any way i can make this recursive?

[saiz66]

^bump

[kjordan2001]

You could. Although you have to decide if it's overkill since recursive is a little harder on your mind. Either way, you're just comparing to see if the end is the same as the start.

[benjaminzsj]

Try "Topological Sort".

[saiz66]

What, and how would I use topologicaal sort to find if there is a cycle?

[benjaminzsj]

find a vertex that has no in degree, delete it from the graph together with the edge attached to it.if there is any vertex left,then the graph is in a cycle.

[benjaminzsj]

but i think your graph IS in a cycle.

[saiz66]

sorry for this dumb question.. but I am not sure what u mean by "in degree"? Actually u are right, my graph has 3 cycles:

P1->P3->P1

P2->P3->P2

P1->P3->P2->P1

lol... thanks for any help!

[shake]

degree means number of edges connected to a vertex.

as u have a more tree like structure, u may want to traverse the whole tree in a depth first or breadth first manner, keeping a history of all the nodes visited. If any are repeated, that means it has cycle (this method may become too extensive when trying to traverse large number or nodes)

[Blivrail]

What you could do is do a recursive algorithm... something like this...

For your example above you should create linked list elements like this:

struct element {

int x;

element next;

};

where x contains the subscript (1, 2 3) and P.next would point to an element this P would connect to with an arrow

Then create a P object with x =1 (that would be P1), and do a recursive search:

element currNode = p;

do {

if (currNode.next == p)

{

// then the loop hits back to start, and is a cycle

cout << "Is a cycle";

break;

}

currNode = currNode.next;

} while (currNode != NULL)

// if the currNode == NULL then the end of the list is found and no cycle exists

Finally just extend this to have more than just one node per element... as in

struct element {

int x;

element next1;

element next2;

};

Hope that helps!

[saiz66]

I am using the lists from the library.

std::list<int> waitFor[Max];

I am not sure if you are familiar with this. I am not too good with c++ but it seems to me that your code only checks for if the node is an elment but what if look at my graph at the bottom... P1 points to P2 and P2 points to P3 and P4... so then I gotta check if P3 or P4 is pointing to P1... This is really confusing me... Could you explain how yours works? It seems much simpler than what I was thinking. Thanks by the way!

[kjordan2001]

  saiz66 said:

I am using the lists from the library. 

std::list<int> waitFor[Max];

I am not sure if you are familiar with this.  I am not too good with c++ but it seems to me that your code only checks for if the node is an elment but what if look at my graph at the bottom... P1 points to P2 and P2 points to P3 and P4... so then I gotta check if P3 or P4 is pointing to P1... This is really confusing me... Could you explain how yours works?  It seems much simpler than what I was thinking.  Thanks by the way!

I'm still confused on what you're trying to do. Your memory map of the lists show something completely different than your state diagram. What you need to do is go from your starting point and see if the destination is the same. This may mean going through multiple ways as each state can go to multiple states. It would be like dealing with a tree.

[Blivrail]

I was thinking something more like this. See if you can use this method.

[saiz66]

To Kjordan:

I am not sure what you are confused by. Is it my diagram and the array of linked lists? The indexes are the Processes. So Process 1 is pointing to Process 2. So there is a linked list of 2 for Index 1. And Index 2 is process 2 which is pointing to 2 processes, 3 and 4 which are shown by the linked lists 3 and 4. And Index 3 has nothing so no linked lists for that. And Process 4 is pointing to 1 and 3 which are shown by the nodes 1 and 3.

To Blivrail:

I would use your method but I am using linked lists of arrays and I have incorporated that into my program so changing it would be difficult. If it is possible to use it with my setup then that would be great.

Basically this is my idea. I go through each node to check where it would be going and checkin if there is a cycle. So from my example graph. I would check Index 1 linked list 2 and then check all the indexes for 2 to see if it goes back to 1. Since none don't I would have to check each node, 3. Then go to 3 where there is nothing. Then I got to check Index 2 and check Index 4.

This is what I got so far:

void checkDeadlock(list<int>* waitFor)
{
	int i, tempIndex, tempNode, startIndex, startNode;

	for (i=0; i<Max; i++)
	{
  
  list<int>::iterator it = waitFor[i].begin();
  
  while (it != waitFor[i].end())
  {

 	 tempIndex = i;
 	 tempNode = *it;

 	 while (it != waitFor[tempNode].end())
 	 {
    if (tempIndex == *it)
   	 cout << "It is a cycle" << endl;
    else 
   	 ++it;

 	 }

 	 // Increment the iterator to the next element
 	 ++it;
  }
	}

}

I know this is not complete. Anybody can help me out?

[Blivrail]

I think your idea will come through, but 'm not sure if your code makes 100% logical sense at the moment. You might want to create a list of list<ints>, as in list< list<int> >... so the outside list would contain a list of list<int>s.