Генерация случайного ориентированного графа

Я написал функцию, которая возвращает ориентированный граф в виде матрицы смежности. Функция требует два аргумента: количество узлов и количество ребер. Сначала узлы размещаются и мгновенно подключаются к графу. Когда все узлы добавлены, создаются случайные ребра, пока не будут размещены все ребра.

Код:

public int[,] GenerateMatrix(int Nodes, int Edges)
    {
        if (Edges < Nodes - 1) throw new Exception("Too few edges");
        if (Edges > Nodes * (Nodes - 1)) throw new Exception("Too many edges");

        int[,] adjacencyMatrix = new int[Nodes, Nodes];

        // Gives every cell a value of zero
        for (int y = 0; y < Nodes; y++)
        {
            for (int x = 0; x < Nodes; x++)
            {
                adjacencyMatrix[x, y] = 0;
            }
        }

        int placedEdges = 0;

        for (int i = 1; i < Nodes; i++)
        {
            // produce edge between rnd(0, amountofnodes) to new node
            int fromVertex = random.Next(0, i);
            int weight = random.Next(1, 10);

            adjacencyMatrix[i, fromVertex] = weight;
            placedEdges++;
        }

        while (placedEdges < Edges)
        {
            int fromVertex = random.Next(0, Nodes);
            int weight = random.Next(1, 10);

            int targetVertex = random.Next(0, Nodes);
            while (targetVertex == fromVertex || adjacencyMatrix[targetVertex, fromVertex] != 0) //|| adjacencyMatrix[fromVertex, targetVertex] != 0)// tredje condition tar bort parallella kanter
            {
                fromVertex = random.Next(0, Nodes);
                targetVertex = random.Next(0, Nodes);
            }

            adjacencyMatrix[targetVertex, fromVertex] = weight;
            placedEdges++;
        }

        return adjacencyMatrix;
    }

2 ответа
2

Вот мои предложения:

  • Nodes, Edges: в большинстве случаев параметры функции не начинаются с большой буквы. nodes и edges более предпочтительны.

  • throw new Exception: Хорошо, что вы делаете предварительные проверки. Обычно предпочтительным типом исключения является ArgumentException (1), чтобы указать, что у вас проблема с параметрами вызова.

  • adjacencyMatrix: Вам не нужно обнулять все записи внутри этой матрицы, потому что по умолчанию их значение будет нулевым. (int это тип значения со значением по умолчанию 0).

    • Если вы хотите очистить массив, потому что вы получили это, например, через параметр, вы можете использовать встроенный Array.Clear (1):
      Array.Clear(adjacencyMatrix, 0, adjacencyMatrix.Length);
  • random.Next(0, i): Альтернатива: random.Next() % i

  • random.Next(1, 10): Альтернатива: new Random().Next() * (10 - 1) + 1 (1)

  • placedEdges++: вместо того, чтобы увеличивать его каждый раз, вы можете инициализировать его правильным значением: int placedEdges = Nodes -1;

  • fromVertex и targetVertex:

    • fromVertex + toVertex
    • ИЛИ ЖЕ sourceVertex и targetVertex было бы

    дать более удобное именование.

  • Почему вы рекомендуете альтернативную рандомизацию? Это быстрее? На мой взгляд random.Next (start, to) более читабелен.

    – Густав Линдер

  • random.Next(start, to) имеет хорошие шансы быть униформой – стройная для random.Next() % i.

    – седобородый

  • Если вы посмотрите исходный код Следующий() и Далее (int minValue, int maxValue) то вы можете видеть, что последний может вызвать InternalSample дважды в некоторых случаях.

    – Питер Чала


  • 1

    В данном конкретном случае он его не назовет, поэтому я могу согласиться с вами, ребята, что вызов random.Next со значениями min и max может быть здесь более удобным.

    – Питер Чала

Вы описываете, что должен выполнять код:
Сделай так в коде, с помощью какого инструмента поддержка вам подходит. MS находится на XML-веселье, доксиген в настоящее время имеет домен .nl.

Опустить присвоение каждой ячейке нулевого значения:

Значения по умолчанию элементов числового массива равны нулю.,
и ссылочные элементы имеют значение null.

Ты используешь узел так же как вершина – Питер Чала уже оценил микширование из и цель.

Для равномерно псевдослучайного неотрицательного числа с точностью до некоторой maxValue вызов int Random.Next(int maxValue).
Каждое ребро от первой петли «указывает вниз», внося неравномерность.

При выборе fromVertex это уже есть Узлы-1 исходящие края, while-loop не прерывается.
Ожидать многие в любом случае срабатывает через этот цикл, когда имеется более чем около Nodes ^ 3/2 ребер.
(третье условие позволяет избежать антипараллельные края)
(При начальной (без комментариев!) Проверке диапазона необходимо учитывать отказ от использования антипараллельных ребер.)

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *