Questions tagged [cycle-detection]
The cycle-detection tag has no usage guidance.
42
questions
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):
...
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 ...
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: '...
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/...
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 ...
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?
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 ...
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 ...
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 ...
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. ...
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:
(...
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 ...
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-...
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 ...
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 ...
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 ...
-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 ...
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($...
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 ...
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 ...
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 ...
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(...
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 ...
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 ...
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 ...
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"
...
-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 ...
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]
...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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" =&...
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....