Welcome to yEd Q&A!
Here you can ask questions and receive answers from other members of the community and yEd developers. And you can tell us your most wanted feature requests.

Categories

Is it possible to detect directed cycles on a completed graph?

0 votes
in Help by

1 Answer

0 votes
 
Best answer
There is no tool for that in yEd.

In a complete graph, each node belongs to a directed cycle, because for each set of nodes {v1, ..., vk} the edges {(v1,v2), (v2,v3), ..., (vk,v1)} exist. In other words, this is a trivial problem. However, the number of cycles rises exponentially with the number of nodes. Because the graph is complete, all permutations of a subset form cycles. Moreover, in a graph with n nodes, there are 2^(n-1)-1 subsets with at least two nodes. I.e. there is no efficient way to find/enumerate all cycles. (Which is one reason there is no such tool in yEd.)
by [yWorks] (160k points)
selected by
Legal Disclosure | Privacy Policy
...