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

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

Код:

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;
    }

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

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

  • Также рассмотрите возможность ограничения возможный диапазон этих переменных. uint или даже меньше как ushort может лучше подойти для вашего варианта использования.

• 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 было бы

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

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

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

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

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

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

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