Создание всех возможных направленных ациклических графов

Question

Я пытаюсь перечислить все возможные DAG с n вершинами. Я знаю, что их много, и я предполагаю, что n очень маленький (от 3 до 5). Мне было интересно, есть ли способ их перечислить. Мое начальное решение - создать их по количеству ребер m. Рассматривая структуры с 0 ребрами, то те с 1 ... и т. Д. Случаи m=0 или m=n(n-1)/2 являются исследованиями скважин (1 и n! соответственно). Однако мне непонятно, сколько DAG существует с краями 1<m<n(n-1)/2.

Обновление: Как некоторые пользователи считают это широкой темой, я попытаюсь сузить ее до создания неориентированных графов. Поскольку для заданного ненаправленного графа G с границами m существуют 2^|m| ориентации, и я применил метод для этого, проверяя ацикличность. Вопрос по-другому: Как сгенерировать все возможные неориентированные графики для n вершин?

Answer 1

Там должен быть решением ДФСА к задаче создания графики, что-то вроде:

graph(g) { // g is current graph; start with an empty graph 
    find set V of vertices in g 
    if V is not empty 
    emit g 
    for every v in V { 
    find set V' of vertices not in g 
    for every v' in V' { 
     g' = g with new edge from v to v' 
     graph(g') 
    } 
    } 
} 

Answer 2

Потому что неориентированные графов праведного множества ребер, если я вас понимаю второй вопрос, вы просите код, который генерирует все возможные наборы ребер. Это правильно?

void getAllEdgeSets(List<Edge> currentEdges, List<Edge> remainingEdges) { 
    if (remainingEdges.isEmpty()) { 
     processSet(currentEdges); 
    } else { 
     Edge edge = remainingEdges.remove(0); 
     getAllEdgeSets(currentEdges, remainingEdges); 
     currentEdges.add(edge); 
     getAllEdgeSets(currentEdges, remainingEdges); 
     currentEdges.remove(edge); 
    } 
} 

это называется с пустым списком, чтобы начать с:

getAllEdgeSets(Collections.EMPTY_LIST, edges); 

Вы также можете превратить это в источник для потока, так что вы можете обрабатывать, как вы идете (потенциально параллельно):

streamAllGraphs(5).filter(Graph::isAcyclic).forEach(...);