• 0

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


Question

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!!!!

post-47-1092177822.gif

Edited by saiz66

20 answers to this question

Recommended Posts

  • 0

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

  • 0

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.

  • 0

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)

  • 0

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!

  • 0

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!

post-47-1092714022.gif

  • 0
  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.

  • 0

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&lt;int&gt;* waitFor)
{
	int i, tempIndex, tempNode, startIndex, startNode;

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

 	 tempIndex = i;
 	 tempNode = *it;

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

 	 }

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

}

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

post-47-1092759058.gif

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • Darwin Mach Kernel/ BSD. Which is both open source.
    • You mean BSD. The UNIX kernel is not open source.
    • I have been on Linux Mint full-time since Jan 2019. while there is a learning curve, it's worth it if you can make the switch, which I can. I mainly browse web, play some games (generally Lutris(Windows games), or through emulators (MAME/Mesen/Flycast etc) etc), and use a small amount of Windows programs (Foobar2000/7-zip/WinRAR/ImgBurn etc) etc. it's nice to dodge the bloat/BS of Windows as you can really feel Linux is all around faster, especially certain things. p.s. recently I enabled NTSync for games since Linux Mint recently offered the 6.14 kernel, which has NTSync support (it's not enabled by default though but you can enable it temporarily for your current boot of the OS through 'sudo modprobe ntsync')
    • A rotten article full of handwaving of anti-consumer practices. Aside from the fact that no, not even close to every piece of major software collects information about its users, ethical developers make such telemetry opt-in and allow it to be completely disabled. To use KDE Plasma as an example, you're shown a greeter upon first boot that gives users the option to send the developers telemetry, with the default being off and 'off' actually meaning off. Windows 10 has never offered that capability - only a promise that Microsoft will slurp up less of your data if you spend time tweaking 50 different privacy settings. There is still absolutely no way to completely opt out of sending Microsoft telemetry in any version of Windows 10 (or 11, naturally). Even using group policy in Enterprise editions only allows you to reduce telemetry to the bare minimum. Home-focused editions don't even get that option. Articles like this dismissing user privacy concerns as "FUD" are a part of the reason Microsoft felt confident enough to go so much further with Windows 11. I guess you get what you deserve in that respect. Personally, I finally made the move to Linux after 15 years or so of dabbling with it, but never really considering a permanent switch. Enjoy your bright, shiny Windows future. You asked for it, after all.
  • Recent Achievements

    • First Post
      smileyhead earned a badge
      First Post
    • One Month Later
      K V earned a badge
      One Month Later
    • Week One Done
      K V earned a badge
      Week One Done
    • Dedicated
      CarlosABC earned a badge
      Dedicated
    • One Month Later
      solidox earned a badge
      One Month Later
  • Popular Contributors

    1. 1
      +primortal
      639
    2. 2
      ATLien_0
      240
    3. 3
      Xenon
      172
    4. 4
      neufuse
      155
    5. 5
      +FloatingFatMan
      122
  • Tell a friend

    Love Neowin? Tell a friend!