vendredi 29 janvier 2021

How to generate a random event-graph?

Require

There is a need for me to implement an eventGroup generator. eventGroup means one event must happen after collection A but can be concurrent happen with some others. Let's say generate graph with N ( N < 1000) events.

For example

    e1 --- e2 ---- e4 --- e5
        \-- e3 --/   \--- e6

Means that, e2 happen after e1, e3 after e1, e4 happen after both e2 and e3, e5/e6 happen after e4. So e2 and e3 (e5 and e6) can be concurrent.

Go playground

This is part of my working code, and you can test your algorithm here.

https://play.golang.org/p/xuoz1XrMH1l

My solution

Step1

generate N/2 level and tag event with level

Step2

For each event of each level, generate happen after relation, which 'big level after small level'. Generate this relation randomly.

Questions

  1. Is there a classic algorithm to do this job?
  2. Does my solution have a bug?
  3. Can you provide a better solution? (code or pseudo will be OK)



Aucun commentaire:

Enregistrer un commentaire