Блог

Главная - Вопросы по программированию - Javascript, генерирующий случайный ориентированный ациклический граф (DAG)

Javascript, генерирующий случайный ориентированный ациклический граф (DAG)

#javascript #data-structures #graph #graph-theory #cytoscape.js

#javascript #структуры данных #График #теория графов #cytoscape.js

Вопрос:

Я пытаюсь написать функцию для генерации случайного ориентированного ациклического графа (DAG) с n узлами. Я написал эту функцию для генерации узлов, теперь мне нужно сгенерировать ребра, но, похоже, я не могу обмозговать это. У меня есть некоторые ограничения, граф ациклический, и узел может иметь максимум 3 родителя.

 var colors = ["#FF0000","#00FF00","#0000FF"]
var alpahbet = "abcdefghijklmnopqrstuvwxyz"

var intializeNodes = function (numOfNodes){
    for(i = 0; i< numOfNodes; i  ){
        nodes.push({
            group: 'nodes',
            data: {id: alpahbet.charAt(i), color: colors[Math.floor(Math.random() * colors.length)]},
        });
        nodes.push()
    }
}

Спасибо за помощь!

Комментарии:

1. Итак, вы создали несколько узлов. Что вы пробовали в создании краев?

2. Я не думаю, что это так же просто, как добавить все узлы сразу, а затем добавить несколько ребер. Вы должны предотвратить изолированные узлы и поддерживать максимальное количество дочерних узлов. Кажется, я читал статью о генерации DAG с помощью цепи Маркова. Если вы можете, ознакомьтесь с текущими подходами к реализации случайной генерации DAG, я нашел несколько интересных статей.

3. В зависимости от требуемого размера, может быть достаточно просто случайным образом добавлять ребра, проверяя для каждого, что граф остается ациклическим, и на цели не более максимального количества входящих узлов. Вероятно, это станет проблематичным, если количество ребер будет слишком близко к максимально возможному, но если мы не близки к этому, это, вероятно, самый простой метод. Поочередно добавляйте все потенциальные ребра и повторно удаляйте случайные, пока не будут выполнены критерии.

4. Eeeh, случайный означает, что могут быть довольно ожидаемые результаты. Если вы хотите убедиться, что соответствуете критериям, я не думаю, что это так просто, как просто добавить несколько ребер и надеяться, что удаление некоторых сделает граф ациклическим. Уже есть 26 узлов с, по крайней мере, вероятно, от 2 до 5 исходящих ребер.