• 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

    • KDE Plasma 6.5 will notify you if your printer's ink is low by David Uzondu This week, the KDE team continued work on the upcoming Plasma 6.5.0 as well as Plasma 6.4's fourth bug fix release, 6.4.4. As usual, both Plasma versions saw several UI tweaks, bug fixes, and performance improvements. The most notable changes are discussed in this article. Let's start with Plasma 6.5. The desktop environment is getting a useful feature that tells you when your printer is low on ink. This works by having the system check the Common Unix Printing System, or CUPS, for marker levels after a print job is created or completed. CUPS stores attributes like marker-levels in its printers.conf file, and once a level is determined to be low, it triggers a marker-supply-low-warning that Plasma will now use to inform you. UI improvements scheduled for 6.5 include disabling key repeat for certain global shortcuts, like toggling Overview, to prevent rapid screen flashing that could be a seizure risk. There is a better "Someone started sharing this screen" notification that now appears only after a connection is fully established. You will also find standard KDE styling with the "Confirm deleting network connection" dialog, and more consistent spacing in the Global Menu widget. As for bug fixes in 6.5, a layout bug that caused visual overflow in the printer setup page has been corrected. An issue that stopped you from using the virtual keyboard in the Application Dashboard search field is fixed, and XDG portal-using apps can now request screencasts of new virtual outputs. Finally, the clipboard configuration window's size and position information has been moved from the state config file to the settings file. Moving on to 6.4.4, the hitboxes for desktop items now correctly match their visual styling. This means no more accidentally selecting an invisible box around a file. And when you mark a notification as low priority, it will now correctly appear in your history if it arrived during Do Not Disturb mode, so it does not just vanish. If you're experiencing a Kwin crash on login, particularly in a QEMU virtual machine, 6.4.4 has a fix for that on the way. Other bug fixes 6.4.4 brings include: A fix for the Global Menu widget's single-button mode for X11 users. The search field in the Wayland version of the Global Menu widget works again. An annoying bug in the Global Shortcuts XDG portal that made apps think they had no shortcuts has been resolved. Plasma Browser Integration's built-in Share feature has been repaired. Plasma 6.4.4 will drop on the 5th of next month. You can find more details on the official KDE Blog.
    • I just remember wondering how she was ever a bridge officer at all with all of her insufferable insecurities. I am sure she's a wonderful person in real life, but the character was poorly written. They even had to dedicate a whole episode to her being forced into taking the responsibility of leading cadets out of a problem of some sort as if to show how she is "growing" into her function. Never bridge officer material and I just rolled my eyes at her scenes and eventually stopped watching the show altogether, but also because of all the lead character's cry/whisper/talking that frustrated me.
    • Didnt know it was coded/decoded so my bad.
    • Why isn't it more widespread then? What about people that like PC gaming and don't want/don't own a console? MMO gaming/professional work with specific software aren't "edge cases".
  • Recent Achievements

    • Week One Done
      Homayoun Hotak earned a badge
      Week One Done
    • Dedicated
      Profit earned a badge
      Dedicated
    • One Month Later
      hhgygy earned a badge
      One Month Later
    • Week One Done
      hhgygy earned a badge
      Week One Done
    • One Year In
      NIKI77 earned a badge
      One Year In
  • Popular Contributors

    1. 1
      +primortal
      642
    2. 2
      ATLien_0
      241
    3. 3
      Xenon
      168
    4. 4
      neufuse
      149
    5. 5
      +FloatingFatMan
      123
  • Tell a friend

    Love Neowin? Tell a friend!