0
\$\begingroup\$

I wrote a function that returns a directed graph as an adjacency matrix. The function requires two arguments: the amount of nodes and the amount of edges. At first, nodes are placed and instantly connected to the graph. When all nodes are added, random edges are created until all edges are placed.

Code:

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;
    }
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Welcome to CodeReview@SE. I think the difference in code indentation between the method head and the braces around its body unusual: please state, in comment or question body, whether it is intentional or not. If it is against your intentions, please heed What should I [not] do when someone answers my question?. \$\endgroup\$ – greybeard Jan 18 at 12:59
  • \$\begingroup\$ When picking a fromVertex that already has Nodes-1 outgoing edges, the while-loop won't terminate. \$\endgroup\$ – greybeard Jan 18 at 12:59
3
\$\begingroup\$

Here are my suggestions:

  • Nodes, Edges: most of the time the function's parameters don't start with big letter. nodes and edges are more preferable.

  • throw new Exception: It is good that you do preliminary checks. Usually the preferred Exception type is ArgumentException (1) to indicate that you have a problem with the calling parameters.

  • adjacencyMatrix: You don't need to zero all of the entries inside this matrix because by default their value will be zero. (int is a value type with a default value 0).

    • If you wish to clean the array, because you have received that for example via a parameter then you can use the built-in Array.Clear (1):
      Array.Clear(adjacencyMatrix, 0, adjacencyMatrix.Length);
  • random.Next(0, i): Alternative: random.Next() % i

  • random.Next(1, 10): Alternative: new Random().Next() * (10 - 1) + 1 (1)

  • placedEdges++: instead of increasing it every time you could initialize it with the proper value: int placedEdges = Nodes -1;

  • fromVertex and targetVertex:

    • fromVertex + toVertex
    • OR sourceVertex and targetVertex would

    give more convenient naming.

\$\endgroup\$
4
  • \$\begingroup\$ Why do you recommend the alternative randomization? Is it faster? According to me random.Next(start, to) is more readable. \$\endgroup\$ – Gustaf Linder Jan 18 at 11:25
  • \$\begingroup\$ random.Next(start, to) has a good chance to be uniform - slim for random.Next() % i. \$\endgroup\$ – greybeard Jan 18 at 11:31
  • \$\begingroup\$ If you look at the source code of Next() and Next(int minValue, int maxValue) then you can see that the latter might call the InternalSample twice in some cases. \$\endgroup\$ – Peter Csala Jan 18 at 11:35
  • 1
    \$\begingroup\$ In this particular case it won't call it, so I can agree with you guys that calling random.Next with min and max values might be more convenient here. \$\endgroup\$ – Peter Csala Jan 18 at 11:37
2
\$\begingroup\$

You describe what the code is to accomplish:
do so in the code, using what tool support works for you. MS is on an XML spree, doxygen currently has a .nl domain.

Omit giving every cell a value of zero:

The default values of numeric array elements are set to zero,
and reference elements are set to null.

You use node as well as vertex - Peter Csala already assessed mixing from and target.

For a uniformly pseudo-random non-negative number up to some maxValue call int Random.Next(int maxValue).
Each and every edge from the first loop "points down", introducing a non-uniformity.

When picking a fromVertex that already has Nodes-1 outgoing edges, the while-loop won't terminate.
Expect many trips though this loop when there are more than about Nodes^3/2 edges, anyway.
(tredje villkoret undviker antiparallella kanter)
(Not using anti-parallel edges would need to be taken into account in the initial (uncommented!) range check.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.