Generieren eines zufälligen DAG

Um also zu versuchen, all diese vernünftigen Antworten zusammenzufassen:

(Im Folgenden habe ich V für die Anzahl der Scheitelpunkte im generierten Graphen und E für die Anzahl der Kanten verwendet, und wir nehmen an, dass E ≤ V(V-1)/2.)

Ich persönlich denke, die nützlichste Antwort ist ein Kommentar von Flavius, der auf den Code hinweist http://condor.depaul.edu/rjohnson/source/graph_ge.c. Dieser Code ist wirklich einfach und wird bequem durch einen Kommentar beschrieben, den ich reproduziere:

To generate a directed acyclic graph, we first
generate a random permutation dag[0],...,dag[v-1].
(v = number of vertices.)
This random permutation serves as a topological
sort of the graph. We then generate random edges of the
form (dag[i],dag[j]) with i < j.

Tatsächlich generiert der Code die Anforderungsanzahl von Kanten, indem er wiederholt Folgendes ausführt:

1. Generieren Sie zwei Zahlen im Bereich [0, V);
2. reject them if they’re equal;
3. swap them if the first is larger;
4. reject them if it has generated them before.

The problem with this solution is that as E gets closes to the maximum number of edges V(V-1)/2, then the algorithm becomes slower and slower, because it has to reject more and more edges. A better solution would be to make a vector of all V(V-1)/2 possible edges; randomly shuffle it; and select the first (requested edges) edges in the shuffled list.

The reservoir sampling algorithm lets us do this in space O(E), since we can deduce the endpoints of the k^th edge from the value of k. Consequently, we don’t actually have to create the source vector. However, it still requires O(V²) time.

Alternatively, one can do a Fisher-Yates shuffle (or Knuth shuffle, if you prefer), stopping after E iterations. In the version of the FY shuffle presented in Wikipedia, this will produce the trailing entries, but the algorithm works just as well backwards:

// At the end of this snippet, a consists of a random sample of the
// integers in the half-open range [0, V(V-1)/2). (They still need to be
// converted to pairs of endpoints).
vector<int> a;
int N = V * (V - 1) / 2;
for (int i = 0; i < N; ++i) a.push_back(i);
for (int i = 0; i < E; ++i) {
  int j = i + rand(N - i);
  swap(a[i]a[j]);  a.resize(E);

Dies erfordert nur O(E) Zeit, aber es erfordert O(N).²) Platz. Tatsächlich kann dies mit einigen Tricks zum O(E)-Raum verbessert werden, aber ein SO-Code-Snippet ist zu klein, um das Ergebnis zu enthalten, also werde ich einen einfacheren im O(E)-Raum und O(E log E) bereitstellen ) Zeit. Ich gehe davon aus, dass es eine Klasse DAG mit mindestens:

class DAG {
  // Construct an empty DAG with v vertices
  explicit DAG(int v);

  // Add the directed edge i->j, where 0 <= i, j < v
  void add(int i, int j);
};

Jetzt geht es hier:

// Return a randomly-constructed DAG with V vertices and and E edges.
// It's required that 0 < E < V(V-1)/2.
template<typename PRNG>
DAG RandomDAG(int V, int E, PRNG& prng) {
  using dist = std::uniform_int_distribution<int>;
  // Make a random sample of size E
  std::vector<int> sample;
  sample.reserve(E);
  int N = V * (V - 1) / 2;
  dist d(0, N - E);  // uniform_int_distribution is closed range
  // Random vector of integers in [0, N-E]
  for (int i = 0; i < E; ++i) sample.push_back(dist(prng));
  // Sort them, and make them unique
  std::sort(sample.begin(), sample.end());
  for (int i = 1; i < E; ++i) sample[i] += i;
  // Now it's a unique sorted list of integers in [0, N-E+E-1]
  // Randomly shuffle the endpoints, so the topological sort
  // is different, too.
  std::vector<int> endpoints;
  endpoints.reserve(V);
  for (i = 0; i < V; ++i) endpoints.push_back(i);
  std::shuffle(endpoints.begin(), endpoints.end(), prng);
  // Finally, create the dag
  DAG rv;
  for (auto& v : sample) {
    int tail = int(0.5 + sqrt((v + 1) * 2));
    int head = v - tail * (tail - 1) / 2;
    rv.add(head, tail);
  }
  return rv;
}

Sie könnten einen zufälligen gerichteten Graphen erzeugen und dann eine Tiefensuche nach Zyklen durchführen. Wenn Sie einen Zyklus finden, unterbrechen Sie ihn, indem Sie eine Kante löschen.

Ich denke, das ist der schlimmste Fall O (VE). Jede DFS nimmt O (V) und jede entfernt mindestens eine Kante (also max E)

Wenn Sie den gerichteten Graphen generieren, indem Sie alle möglichen V ^ 2-Kanten gleichmäßig zufällig auswählen und DFS in zufälliger Reihenfolge ausführen und eine zufällige Kante löschen, erhalten Sie eine gleichmäßige Verteilung (oder zumindest eine nahe daran) über alle möglichen Dags.

Ein ganz einfacher Ansatz ist:

1. Weisen Sie Kanten zufällig zu, indem Sie über die Indizes einer unteren diagonalen Matrix iterieren (wie durch einen Link oben vorgeschlagen: https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs)

2. Dadurch erhalten Sie einen DAG mit möglicherweise mehr als einer Komponente. Sie können eine disjunkte Datenstruktur verwenden, um Ihnen die Komponenten zu geben, die dann zusammengeführt werden können, indem Sie Kanten zwischen den Komponenten erstellen.

Disjunkte Mengen werden hier beschrieben: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Bearbeiten: Ich habe diesen Beitrag ursprünglich gefunden, als ich mit einem Planungsproblem namens Flexible Job Shop Scheduling Problem mit Sequenzierungsflexibilität arbeitete, bei dem Jobs (die Reihenfolge, in der Operationen verarbeitet werden) durch gerichtete azyklische Graphen definiert werden. Die Idee war, einen Algorithmus zu verwenden, um mehrere zufällige gerichtete Graphen (Jobs) zu generieren und Instanzen des Scheduling-Problems zu erstellen, um meine Algorithmen zu testen. Der Code am Ende dieses Beitrags ist eine Basisversion des Codes, den ich zum Generieren der Instanzen verwendet habe. Der Instanzgenerator ist zu finden hier.

Ich habe nach Python übersetzt und einige Funktionalitäten integriert, um einen transitiven Satz des zufälligen DAG zu erstellen. Auf diese Weise hat der erzeugte Graph die minimale Anzahl von Kanten bei gleicher Erreichbarkeit.

Der transitive Graph kann unter visualisiert werden http://dagitty.net/dags.html indem Sie die Ausgabe einfügen Modellnummer (rechts).

Python-Version des Algorithmus

import random

class Graph:
    nodes = []
    edges = []
    removed_edges = []

    def remove_edge(self, x, y):
        e = (x,y)
        try:
            self.edges.remove(e)
            # print("Removed edge %s" % str(e))
            self.removed_edges.append(e)
        except:
            return

    def Nodes(self):
        return self.nodes

    # Sample data
    def __init__(self):
        self.nodes = []
        self.edges = []


def get_random_dag():
    MIN_PER_RANK = 1    # Nodes/Rank: How 'fat' the DAG should be
    MAX_PER_RANK = 2
    MIN_RANKS = 6   # Ranks: How 'tall' the DAG should be
    MAX_RANKS = 10
    PERCENT = 0.3  # Chance of having an Edge
    nodes = 0

    ranks = random.randint(MIN_RANKS, MAX_RANKS)

    adjacency = []
    for i in range(ranks):
        # New nodes of 'higher' rank than all nodes generated till now
        new_nodes = random.randint(MIN_PER_RANK, MAX_PER_RANK)

        # Edges from old nodes ('nodes') to new ones ('new_nodes')
        for j in range(nodes):
            for k in range(new_nodes):
                if random.random() < PERCENT:
                    adjacency.append((j, k+nodes))

        nodes += new_nodes

    # Compute transitive graph
    G = Graph()
    # Append nodes
    for i in range(nodes):
        G.nodes.append(i)
    # Append adjacencies
    for i in range(len(adjacency)):
        G.edges.append(adjacency[i])

    N = G.Nodes()
    for x in N:
        for y in N:
            for z in N: 
                if (x, y) != (y, z) and (x, y) != (x, z):
                    if (x, y) in G.edges and (y, z) in G.edges:
                        G.remove_edge(x, z)

    # Print graph
    for i in range(nodes):
        print(i)
    print()
    for value in G.edges:
        print(str(value[0]) + ' ' + str(value[1]))

get_random_dag()

Unten sehen Sie in der Abbildung den zufälligen DAG mit vielen redundanten Kanten, die vom obigen Python-Code generiert wurden.

Ich habe den Code angepasst, um den gleichen Graphen (gleiche Erreichbarkeit) zu generieren, aber mit der geringstmöglichen Anzahl von Kanten. Dies wird auch als transitive Reduktion bezeichnet.

def get_random_dag():
    MIN_PER_RANK = 1    # Nodes/Rank: How 'fat' the DAG should be
    MAX_PER_RANK = 3
    MIN_RANKS = 15   # Ranks: How 'tall' the DAG should be
    MAX_RANKS = 20
    PERCENT = 0.3  # Chance of having an Edge
    nodes = 0
    node_counter = 0

    ranks = random.randint(MIN_RANKS, MAX_RANKS)

    adjacency = []
    rank_list = []
    for i in range(ranks):
        # New nodes of 'higher' rank than all nodes generated till now
        new_nodes = random.randint(MIN_PER_RANK, MAX_PER_RANK)

        list = []
        for j in range(new_nodes):
            list.append(node_counter)
            node_counter += 1
        rank_list.append(list)

        print(rank_list)

        # Edges from old nodes ('nodes') to new ones ('new_nodes')
        if i > 0:
            for j in rank_list[i - 1]:
                for k in range(new_nodes):
                    if random.random() < PERCENT:
                        adjacency.append((j, k+nodes))

        nodes += new_nodes

    for i in range(nodes):
        print(i)
    print()
    for edge in adjacency:
        print(str(edge[0]) + ' ' + str(edge[1]))
    print()
    print()

Ergebnis:

Erstellen Sie ein Diagramm mit n Knoten und eine Kante zwischen jedem Knotenpaar n1 und n2 wenn n1 != n2 und n2 % n1 == 0.