Как генерировать случайные графики?

Question

Я хочу, чтобы генерировать случайные, неориентированные и связанные графики в Java. Кроме того, я хочу иметь возможность контролировать максимальное количество вершин на графике. Я не уверен, что было бы лучшим способом подойти к этой проблеме, но вот несколько из них можно придумать:

(1) Создайте число между 0 и n и пусть это будет число вершин. Затем, случайно связав вершины вместе (возможно, создайте случайное число на вершину и пусть это будет число ребер, выходящих из указанной вершины). Поверните график, начиная с произвольной вершины (скажем, с помощью Breadth-First-Search), и пусть наш случайный граф G будет всем посещенным узлом (таким образом мы убеждаемся, что G подключен).

(2) Создание случайного квадратную матрицу (из 0 х и 1 'S) с длиной стороны между 0 и n (так или иначе). Это была бы матрица смежности для нашего графика (диагональ матрицы должен быть либо все 1, либо все 0). Создайте структуру данных из графика и пересечь график с любого узла, чтобы получить список подключенных узлов, и назовем его графиком G.

Любые другие способы генерации достаточно случайного графа приветствуются. Примечание: Мне не нужен чисто случайный граф, т. Е. Создаваемый граф не должен иметь каких-либо специальных математических свойств (например, однородности). Мне просто нужно много и много графиков для тестирования чего-то другого.

Вот класс Java Node Я использую:

public class Node<T> { 
    T data; 
    ArrayList<Node> children= new ArrayList<Node>(); 
    ...} 

Вот Graph класса я использую (вы можете сказать, почему я заинтересован только в связных графах на данный момент):

public class Graph { 
    Node mainNode; 
    ArrayList<Node> V= new ArrayList<Node>(); 

    public Graph(Node node){ 
     mainNode= node; 
    } 
    ...} 

в качестве примера, это то, как я делаю графики для целей тестирования прямо сейчас:

//The following makes a "kite" graph G (with "a" as the main node). 
    /*  a-b 
      |/| 
      c-d 
    */ 
    Node<String> a= new Node("a"); 
    Node<String> b= new Node("b"); 
    Node<String> c= new Node("c"); 
    Node<String> d= new Node("d"); 
    a.addChild(b); 
    a.addChild(c); 
    b.addChild(a); 
    b.addChild(c); 
    b.addChild(d); 
    c.addChild(a); 
    c.addChild(b); 
    c.addChild(d); 
    d.addChild(c); 
    d.addChild(b); 
    Graph G1= new Graph(a); 

Answer 1

Независимо от того, что вы хотите сделать с вашим графиком, я думаю, его плотность также является важным параметром. В противном случае вы просто создадите набор небольших кликов (полные графики) с использованием случайных размеров, а затем соедините их случайным образом.

Если я прав, я бы посоветовал вам использовать Erdős-Rényi model: это просто, недалеко от того, что вы изначально предложили, и позволяет вам контролировать плотность графа (так, в основном: количество ссылок).

Вот краткое описание этой модели:

1. Определить значение вероятности р (чем выше р и более плотного график: 0 = нет, 1 ссылку = полностью подключен графом);
2. Создайте свои n узлов (как объекты, как матрицу смежности, или что-нибудь, что вам подходит);
3. Каждая пара узлов связана с (независимой) вероятностью p. Итак, вы должны решить, существует ли связь между ними, используя эту вероятность p. Например, я предполагаю, что вы могли бы нарисовать значение q между 0 и 1 и создать ссылку iff q < p. Затем сделайте то же самое для каждой возможной пары узлов в графе.

С этой моделью, если ваш p ​​достаточно большой, то очень вероятно, что ваш график подключен (см. Ссылку в Википедии). В любом случае, если у вас есть несколько компонентов, вы также можете заставить его подключаться, создавая связи между узлами отдельных компонентов. Во-первых, вы должны идентифицировать каждый компонент, выполнив поиск по ширине (по одному для каждого компонента). Затем вы выбираете пары узлов в двух разных компонентах, создаете связь между ними и считаете оба компонента объединенными. Вы повторяете этот процесс, пока не останется один компонент.

Answer 2

Единственная сложная задача - обеспечить соединение последнего графика. Для этого вы можете использовать disjoint set data structure. Следите за количеством компонентов, изначально n. Неоднократно выбирают пары случайных вершин u и v, добавляя ребро (u, v) к графу и структуре непересекающихся множеств и уменьшая счетчик компонентов, когда эта структура сообщает вам, что u и v принадлежат к разным компонентам. Остановитесь, когда количество компонентов достигнет 1. (Обратите внимание, что использование матрицы смежности упрощает управление случаем, когда край (u, v) уже присутствует в графике: в этом случае adj [u] [v] будет установлен в 1 второй раз, который по желанию не имеет эффекта.)

Если вы обнаружите, что это создает слишком плотные (или слишком разреженные) графики, то вы можете использовать другое случайное число, чтобы добавить ребра только в k% времени, когда конечные точки уже являются частью одного и того же компонента (или когда они являются частью разных компонентов), для некоторого k.