algorithm - Generate a directed graph with n cycles -

i want generate directed graph contains specified amount of cycles respective length. example, graph should contain:

 2 cycles of size 3  1 cycle of size 5 

• does such algorithm exist? if not, approach solving problem? in detail, following parameters given:

  1. the number of vertices (e.g., 15)
  2. the number of components (e.g., 2)
  3. the cycles have in graph (e.g, {3-cycle, 3-cycle, 5-cycle})

• i found several algorithms (e.g., tarjan) can detect cycles in existing graphs. think possible use cycle detection algorithms generate graphs specific amount of cycles?

a greedy algorithm might fail on cases, needs peer review.

note that, if have cycle of length k:

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

we can make cycle of same length introducing single other node:

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

or cycle of same length - 1:

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

this can go on forever introducing new node , connecting 2 other nodes in initial, big enough, cycle.

so, if can afford infinite number of nodes, this, starting largest cycle need.

if must work fixed number of nodes, should strive minimize number of nodes used constructing requested cycles. leftover nodes can added not form cycles.

start largest cycle again:

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

by not adding more nodes, can obtain 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 generate additional cycles. whole algorithm be:

1. build largest requested cycle.

   1.1. if more 1 largest, build more adding single new node each. note affects procedure described building smaller cycles out of big 1 not adding new nodes, because new cycle of size. there overlap, can't double number of solutions. far can tell, increases number 1.

2. build lesser cycles not adding new nodes.

3. if not done building needed cycles:

   3.1. if have nodes left, use them.

   3.2. if don't have nodes left, output no solution.

4. if done building cycles:

   4.1. if have nodes left, add them linked list somewhere won't bother you.

   4.2. if no nodes left, you're done.