Ben A. February 2016

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 size 5
  • Does such an algorithm already exist? If not, what would be your approach to solving this problem? In detail, the following parameters are given:

    1. the number of vertices (e.g., 15)
    2. the number of components (e.g., 2)
    3. the cycles that have to be in the graph (e.g, {3-cycle, 3-cycle, 5-cycle})
  • I only found several algorithms (e.g., Tarjan) that can detect cycles in existing graphs. Do you think it is possible to also use cycle detection algorithms to generate graphs with a specific amount of cycles?

Answers


IVlad February 2016

A greedy algorithm that might fail on some cases, needs peer review.

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

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

We can make another cycle of the same length by introducing a single 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 by always introducing a new node and connecting it to two other nodes in an initial, big enough, cycle.

So, if you can afford an infinite number of nodes, just do this, starting from the largest cycle you need.

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

Start with the largest cycle again:

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

By not adding any more nodes, we can obtain from this the following:

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

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

  3. In general, k - p + 1 length p cycles.

None of these will generate additional cycles. So the whole algorithm will be:

  1. Build your largest requested cycle.

    1.1. If more than one largest, build more by adding a single new node for each. Note that this affects the procedure described for building smaller cycles out of a big one by not adding any new nodes, because you get a new cycle of a certain size. There will be some overlap, so you c

Post Status

Asked in February 2016
Viewed 3,602 times
Voted 12
Answered 1 times

Search




Leave an answer