Stack Overflow
Stack Overflow

Questions tagged [cyclic-graph]

55 questions
40
votes
5 answers

How to detect if adding an edge to a directed graph results in a cycle?

I came upon wait-for graphs and I wonder, are there any efficient algorithms for detecting if adding an edge to a directed graph results in a cycle? The graphs in question are mutable (they can have nodes and edges added or removed). And we're not…
Petr
  • 62,528
  • 13
  • 153
  • 317
27
votes
6 answers

How to detect if a directed graph is cyclic?

How can we detect if a directed graph is cyclic? I thought using breadth first search, but I'm not sure. Any ideas?
iva123
  • 3,395
  • 10
  • 47
  • 68
15
votes
1 answer

How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' acyclic. More formal: The desired…
mtsz
  • 2,725
  • 7
  • 28
  • 41
12
votes
4 answers

How to initialize and "modify" a cyclic persistent data structure in Scala?

I have searched and found some info on this topic but the answers are either confusing or not applicable. I have something like this: class Thing (val name:String, val refs:IndexedSeq[Ref]) class Ref (val name:String, val thing:Thing) Now, I want…
mentics
  • 6,852
  • 5
  • 39
  • 93
12
votes
7 answers

Finding the longest road in a Settlers of Catan game algorithmically

I'm writing a Settlers of Catan clone for a class. One of the extra credit features is automatically determining which player has the longest road. I've thought about it, and it seems like some slight variation on depth-first search could work, but…
Jay
  • 510
  • 6
  • 17
11
votes
1 answer

How do find the longest path in a cyclic Graph between two nodes?

I already solved most the questions posted here, all but the longest path one. I've read the Wikipedia article about longest paths and it seems any easy problem if the graph was acyclic, which mine is not. How do I solve the problem then? Brute…
rfgamaral
  • 16,546
  • 57
  • 163
  • 275
9
votes
1 answer

convert cyclic to acyclic graph

I want to convert a cyclic graph into an acyclic graph. Is there an pseudocode that can do this? I did try to search but most of them returned where mathematical based on markov chain or research articles. I want to write a program to do it and any…
Dexters
  • 2,419
  • 6
  • 37
  • 57
9
votes
3 answers

How to detect if the given graph has a cycle containing all of its nodes? Does the suggested algorithm have any flaws?

I have a connected, non-directed, graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph, which has 3 nodes and 3 edges. Every node added onto the graph and has 2 connections with the existing…
Varaquilex
  • 3,447
  • 7
  • 40
  • 60
8
votes
3 answers

How to hash and check for equality of objects with circular references

I have a cyclic graph-like structure that is represented by Node objects. A Node is either a scalar value (leaf) or a list of n>=1 Nodes (inner node). Because of the possible circular references, I cannot simply use a recursive HashCode() function,…
mfya
  • 352
  • 4
  • 9
7
votes
3 answers

Generating immutable cyclic data structures

Suppose I have this simple class: public class Pair { public readonly object first; public readonly object second; public Pair(object first, object second) { this.first = first; this.second = second; } } It would be…
configurator
  • 40,828
  • 14
  • 81
  • 115
6
votes
3 answers

How to override println behavior for reference types

I have a cyclic graph I created using dosync and ref-set. When I pass this to println I get a java.lang.StackOverflowError as I would expect, because it's effectively trying to print an infinitely-nested structure. I found that if I do (str…
Sonicsmooth
  • 2,673
  • 2
  • 22
  • 35
5
votes
0 answers

Python Networkx Implementing Cyclic Directed Graph

I’m trying to find all paths through the following cyclic directed graph. I would like to be able to include the paths which pass through the cycles once, but not include the possibility of infinitely cycling through one path. Start -> [1]; 1 ->…
M. Morgan
  • 93
  • 7
5
votes
3 answers

How to represent directed cyclic graph in Prolog with direct access to neighbour verticies

I need to construct directed graph (at runtime) with cycles in Prolog and I am not sure know how to represent it. My requirement is that I need to get from one vertex to his neigbour in a constant time. Is it possible to represent it as a tree,…
Ondřej Kunc
  • 1,087
  • 9
  • 17
4
votes
1 answer

Find cyclic dependency without using graph in Map of array

I have an object like following: var myMap = { v1: ['v2', 'v4', 'v5'], v2: ['x', 'v4', 'y'], v3: ['v2', 'v4', 'v5'], v4: ['e', 'v1', 'v5'], v5: ['v2', 'v4', 'v3'], }; I have to find map of entities cyclic without converting it…
Akhilesh Kumar
  • 9,085
  • 13
  • 57
  • 95
4
votes
1 answer

Finding all cycles in a directed graph using recursive backtracking

I am working on finding cycles in directed graph using recursive backtracking. There is a suggested pseudocode for this here, which is here: dfs(adj,node,visited): if (visited[node]): if (node == start): "found a path" …
brain storm
  • 30,124
  • 69
  • 225
  • 393
1
2 3 4