Create a directed graph with n cycles

Question

I want to create a directed graph that contains exactly the specified number of cycles with their corresponding length. For example, a graph should contain:

  2 cycles of the size 3 
 1 cycle of the size 5

• Does such an algorithm already exist? If not, what will be your approach to solving this problem? The following parameters are given in detail:

  • number of vertices (e.g. 15)
  • number of components (e.g. 2)
  • cycles that should be on the chart (for example, {3-cycle, 3-cycle, 5-cycle})

• I found several algorithms (e.g. Tarjan) that can define loops in existing graphs. Do you think that you can also use cycle detection algorithms to generate graphs with a certain number of cycles?

Answer 1

A greedy algorithm that may fail in some cases needs expert judgment.

Note that if we have a cycle of some length k :

 1 -> 2 -> 3 -> ... -> k -> 1 

We can make another loop of the same length by introducing one other node:

 1 -> 2 -> 3 -> ... -> k -> 1 k' -> 1 -> 2 -> ... -> k - 1 -> k' 

Or a cycle of the same length - 1:

 1 -> 2 -> 3 -> ... -> k -> 1 k' -> 1 -> ... -> k - 2 -> k' 

This can go on forever, always introducing a new node and connecting it to two other nodes in the initial, fairly large loop.

So, if you can afford an infinite number of nodes, just do it starting with the largest loop you need.

If you must work with a fixed number of nodes, we should strive to minimize the number of nodes used to construct the requested cycles. Any remaining nodes can be easily added, so they do not form any cycles.

Start with the biggest loop again:

 1 -> 2 -> ... -> k -> 1 

Without adding more nodes, you can get the following from this:

• k length of 2 cycles: 2 -> 1, 3 -> 2, ... 1 -> k .

• k - 2 length of 3 cycles: 3 -> 1, 4 -> 2, ..., k -> k - 2 .

• In the general case, the cycles k - p + 1 length p .

None of them will generate additional cycles. Thus, the whole algorithm will be:

• Create your biggest requested cycle.

  1.1. If more than one in size, add another new node for each. Please note that this affects the described procedure for building smaller cycles from large ones without adding new nodes, because you get a new cycle of a certain size. There will be some overlap, so you cannot just double the number of solutions. As far as I can tell, it only increases the number by 1.

• Create your smaller loops without adding new nodes.

• If the necessary cycles have not been created:

  3.1. If you have nodes, use them.

  3.2. If you have no nodes, print no solution .

• If build cycles are completed:

  4.1. If you have nodes, add them as a linked list somewhere so that they do not bother you.

  4.2. If there are no nodes left, you are done.