Questions tagged [cycle-detection]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
34 views

Finding cycles in an undirected graph in [node, node] format returns wrong result

I'm trying to find cycles in an undirected, unweighted graph. In [node, node] format. Here is the code I wrote: def find_cycles(graph): cycles = [] def dfs(node, visited, path): ...
Mani's user avatar
  • 3
1 vote
1 answer
111 views

Cycle Detection in Undirected Graph [closed]

I have this undirected and weighted graph in the above link and I just cannot detect how many cycles are there. I have tried BFS, DFS and Set disjoint method but all of them just goes wrong somewhere ...
Mashrur Kabir Riyan's user avatar
0 votes
1 answer
57 views

Finding cyclic product relations with TypeORM/SQL/NestJS

Currently I have a Product class like so: @Entity() export class Product { @PrimaryGeneratedColumn() id: number; @ManyToMany(() => Product, (product) => product.id, { onDelete: '...
CXY's user avatar
  • 33
0 votes
0 answers
124 views

How to to check the cycles count in time series data using Python

I have a battery voltage data with respect to Datetime, collected data for one month I need to find out the number of cycles of battery hers is my data https://docs.google.com/spreadsheets/d/...
aparna podili's user avatar
2 votes
1 answer
149 views

Getting wrong answer for simple algorithm with cycle detection

I am solving this problem, a part of the problem that is giving me troubles is formulated as follows: a. Start from index i=0; b. Jump to index i=A[i]; c. If the current index i is outside the valid ...
Bart Louwers's user avatar
0 votes
1 answer
63 views

In course schedule II : Leetcode, how can we ensure when there are multiple answers the solution is the one with increasing order of course number?

When there are multiple solutions, I want to return the solution where courses are in ascending order. How can I do that by the topological sort algorithm?
sam's user avatar
  • 21
0 votes
2 answers
1k views

Count number of cycles in a Directed graph

Question: Write a program which gives us the number of cycles in a Directed graph. Approach 1: I know that we can detect cycles in graph using Depth First Search and return the answer in terms of a ...
KSP's user avatar
  • 94
1 vote
1 answer
751 views

Counting the number of cycles in an Undirected Graph

Question Write a JAVA program to count the number of cycles in an Undirected graph. My approach: I tried solving this using Depth First Search. I found a program online that counts the cycles of ...
KSP's user avatar
  • 94
1 vote
1 answer
136 views

Finding the cycle in a directed graph

I was solving a problem to determine whether a graph contains a cycle. I solved it using the coloring method (in the visited array I will mark, 0 if it has never visited, 1 if it is visited, and 2 if ...
anand singh's user avatar
1 vote
0 answers
111 views

How to print all cycles in a linked list with extra pointers?

Given a data structure that resembles a linked list with a pointer pointing to next node and another pointer pointing to any random node, I have to print all the unique cycles that the structure has. ...
shivam agarwal's user avatar
0 votes
1 answer
197 views

Why aren't cyclic lists considered lists in Scheme?

I haven't found any questions regarding this for the Scheme programming language, so I hope this isn't a duplicate. While doing some dabbling in the interpreter I encountered a peculiar occurrence: (...
Snusifer's user avatar
  • 495
0 votes
1 answer
48 views

Different approach to detecting cycle/loop in a linked list

So I know about Floyd's cycle detection algorithm but while going over the problem I came up with another idea to solve it. If we can store the 'nextpointer' of every node in a vector/list while we ...
Manas Tuteja's user avatar
0 votes
2 answers
199 views

Cycle detection in Linked List using address of nodes

I have learned recently that: (typically)heap in memory always grows upward refer to-> https://unix.stackexchange.com/questions/466443/do-memory-mapping-segment-and-heap-grow-until-they-meet-...
Prateek Tewary's user avatar
24 votes
3 answers
11k views

Can we detect cycles in directed graph using Union-Find data structure?

I know that one can detect cycles in direct graphs using DFS and BFS. I want to know whether we can detect cycles in directed graphs using Union-Find or not? If yes, then how? and If we can't, then ...
vinter's user avatar
  • 486
4 votes
1 answer
7k views

Time complexity for detecting a cycle in a graph

I am trying to understand the time complexity of some efficient methods of detecting cycles in a graph. Two approaches for doing this are explained here. I would assume that time complexity is ...
bollock1's user avatar
1 vote
0 answers
92 views

How to detect a cycle in a directed graph using the union-find algorithm [duplicate]

Can I apply the union-find algorithm for the detecting a cycle in a directed graph other than Depth First Search (DFS)? I know that we can apply the union-find algorithm for the detecting cycle in a ...
Vinay Kumar's user avatar
-1 votes
1 answer
58 views

My program stop itself in a part of code. How to fix it?

I am doing a program that verifies a cycle in a tree. It's fine with small data, but when data increasing, it stops. Help me, please. Cromosoma *kruskalModificado(Gen *setGenes, int numGenes, int ...
Sotireus98's user avatar
1 vote
0 answers
44 views

Cycle detection by array reference

I have been searching for tree cycle detection and came by this PHP code: /** * Takes an adjacency list: an array of parent/child relationships * array(array(1,2)); */ function check_for_cycles($...
Ralf's user avatar
  • 41
1 vote
1 answer
519 views

How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List ...
ATK's user avatar
  • 358
1 vote
0 answers
195 views

Brent-Pollard factorization: What are the correct tortoise & hare indices in Brent's cycle finding algorithm?

Some time ago, I ported this Python implementation of the Pollard-Brent algorithm to Clojure. It works, and works fast, too; that's not the problem. And when given identical non-random seed values and ...
tabidots's user avatar
0 votes
1 answer
118 views

Writing a function to detect a cycle in a linked list (Floyd's alg)... Logic looks correct but can't find the bug

I am trying to detect a cycle in a linked list I created (I'm practicing for interviews questions). I understand the logic involved in Floyd's tortoise-hare algorithm but the function is always ...
Jack Surtees's user avatar
2 votes
2 answers
932 views

Cycle detection in java

I'm working on a hackerrank problem and it seems like no matter the variation of the solution I try, I can't get the cycle detection to work. Here's the code I'm using static boolean hasCycle(...
ceckenrode's user avatar
  • 4,583
1 vote
1 answer
1k views

Cycle Detection in a Graph using NetworkX Python

My CSV file has ~2.6 million records of transaction among different people. I am trying to make a graph from this file as: person having unique IDs as nodes and edges representing transaction between ...
Shubham Singh's user avatar
1 vote
2 answers
3k views

Algorithm to order tasks with dependencies

In a private open source project I encounter the following problem: There are a variety of tasks to perform. Some of these tasks will have annotations that they must be performed after one or more ...
Regis May's user avatar
  • 3,130
7 votes
1 answer
3k views

How to detect circular references in JavaScript

For example: $ node > var x = {} undefined > x.x = x { x: [Circular] } Wondering the sort of structures are they using to accomplish this, because it's not encoded directly into what I just ...
Lance's user avatar
  • 76k
6 votes
1 answer
4k views

Most efficient way of finding circular references in list

Given the following list of redirects [ { "old": "a", "target": "b" }, { "old": "b", "target": "c" }, { "old": "c", "target": "d" ...
JOSEFtw's user avatar
  • 9,901
-3 votes
2 answers
76 views

Can we assign address of two nodes as a next of a one LinkedListNode in C#?

I am solving one program from linked list data structure in c#, where I need to check that given linked list is NULL terminated or ends with cycle. I want to check it with different test cases, but ...
Prasad Telkikar's user avatar
1 vote
2 answers
848 views

Why does Floyd's cycle finding algorithm fail for certain pointer increment speeds?

Consider the following linked list: 1->2->3->4->5->6->7->8->9->4->...->9->4..... The above list has a loop as follows: [4->5->6->7->8->9->4] ...
Divij Sehgal's user avatar
2 votes
0 answers
1k views

Efficient gremlin query to find a cycle in a graph

I have a big TinkerGraph (~80.000 vertices, ~160.000 edges) and I need to detect if there is a cycle in it using the Apache TinkerPop/Gremlin query language. If any, I would like to obtain the ...
Federico's user avatar
  • 1,955
2 votes
2 answers
5k views

BFS cycle detection

Could someone provide a step by step pseudocode using BFS to search a cycle in a directed/undirected graph? Can it get O(|V|+|E|) complexity? I have seen only DFS implementation so far.
Turbo's user avatar
  • 75
1 vote
1 answer
55 views

How to experimentally simulate and compare various graph cycle detection algorithms?

I studied about various algorithms for cycle detection algorithm in directed graphs like incremental way search, strongly connected components, BFS, two way search, etc. Now I want to simulate it and ...
user avatar
7 votes
1 answer
845 views

Generate a directed graph with n cycles

I want to generate a directed graph that contains exactly the specified amount of cycles with their respective length. For example, the graph should contain: 2 cycles of the size 3 1 cycle of the ...
derbenoo's user avatar
  • 313
3 votes
3 answers
652 views

Cycle Detection Algorithm: Is there a condition for Tortoise and Hare to enter into cycle?

Recently I attended an interview and came accross the following question which I am not able to figure out. Question-1: As per the proof which I read Tortoise moves 1 step and Hare moves 2 steps at ...
Amarnath's user avatar
  • 8,775
3 votes
3 answers
514 views

What is a rho shaped sequence?

I came across this in the solution presented by Saurabh Kr Vats at this http://www.careercup.com/question?id=14990323 He says: # Finally, the sequence could be "rho-shaped." In this # case, the ...
tanvi's user avatar
  • 947
2 votes
1 answer
135 views

Cycle detection in non-iterated sequence

My understanding is that tortoise-hare like algorithms works on iterated sequences That is, for any x, succ(x) = x0. I would like to implement an algortihm that can detect cycles in both ...
lsund's user avatar
  • 744
6 votes
1 answer
180 views

Finding cycles in a (not quite) Latin square

Given a matrix of size m X n with no repetition of values in rows or columns, is there an efficient method of detecting cycles? For example, here is a sample matrix: 3 5 2 9 7 4 4 3 6 ...
Jim White's user avatar
  • 211
0 votes
1 answer
2k views

Find all vertices in a cycle in a directed graph

I have a directed graph i.e matrix of order n x n. I need to find all the cycles present in it along with the vertices involved in the cycle. Here is an example: A B C D 0 1 1 1 1 0 1 0 ...
user3035457's user avatar
0 votes
1 answer
1k views

ArrayList of ArrayList (for Cycle Detection)

Well this question is more about an efficient algorithm than the implementation, so I won't post code. (won't really help you to understand the question) To introduce you to the question: I'm ...
Christian Luis de Belaustegui's user avatar
3 votes
1 answer
374 views

Tarjan's cycle detection: missing cycles

I have tried out Tarjan's algorithm for cycle detection with the implementation from http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/ . The following graph ...
MarryS's user avatar
  • 175
2 votes
2 answers
3k views

Adjacency Linked List Cycle Detection - Java

I have some problem checking if my adjacency list has a cycle or not. I want to make a function that checks if my adjacency list has existing at least one cycle. Based on my program. First, I have to ...
aldrich19's user avatar
0 votes
2 answers
126 views

Find circular replacement patterns

Suppose I would like to expand a string by replacing placeholders from a dictionary. The replacement strings can also contain placeholders: $pattern = "#a# #b#"; $dict = array("a" => "foo", "b" =&...
chiborg's user avatar
  • 27.2k
36 votes
16 answers
37k views

detecting the start of a loop in a singly linked link list?

Is there any way of finding out the start of a loop in a link list using not more than two pointers? I do not want to visit every node and mark it seen and reporting the first node already been seen....
Biswajyoti Das's user avatar