TheAlgorithms/C-Sharp · error · ArgumentException

Graph must be undirected!

Error message

Graph must be undirected!

What it means

When Krkal's MST solver is given an adjacency list (Dictionary<int, Dictionary<int, float>>), ValidateGraph verifies that the graph is undirected: for every edge i -> j with weight w, there must be a reverse edge j -> i with the same weight (within 1e-6). Solve calls this validation and throws ArgumentException when a reverse edge is missing or has a different weight. Without this check the algorithm would traverse an edge in only one direction and produce an incorrect spanning tree.

Solutions

1. Mirror every edge when building the dictionary: whenever you set adj[i][j] = w, also set adj[j][i] = w.
2. Write a symmetrization step that walks all (i,j,w) pairs and inserts or overwrites the reverse entry adj[j][i] = w before calling Solve.
3. If the reverse edge exists but has a different weight, decide the correct value (usually min or max of the two) and make both directions consistent.
4. Verify keys exist both ways before calling Solve; a missing reverse key is the most common variant of this error.

Example fix

// before
adj[0][1] = 4f;

// after
adj[0][1] = 4f;
if (!adj.TryGetValue(1, out var rev)) { rev = new Dictionary<int, float>(); adj[1] = rev; }
rev[0] = 4f; // mirror the edge

static bool IsUndirected(Dictionary<int, Dictionary<int, float>> adj)
{
    foreach (var (i, edges) in adj)
        foreach (var (j, w) in edges)
            if (!adj.TryGetValue(j, out var rev) || !rev.TryGetValue(i, out var rw) || Math.Abs(w - rw) > 1e-6)
                return false;
    return true;
}
if (!IsUndirected(adj)) throw new ArgumentException("adjacency list is not undirected");

static bool IsUndirectedAdjacencyList(Dictionary<int, Dictionary<int, float>> adj) => IsUndirected(adj);

try
{
    var mst = kruskal.Solve(adj);
}
catch (ArgumentException ex) when (ex.Message == "Graph must be undirected!")
{
    // add missing/mismatched reverse edges, then retry
}

When it happens

Trigger: Calling Kruskal.Solve with an adjacency-list dictionary where some edge entry adj[i] contains key j but adj[j] either does not contain key i (missing reverse edge) or maps it to a weight differing by more than 1e-6.

Common situations: Building the dictionary from a directed edge list and only adding adj[i][j]; merging edge data where one direction got a different weight; editing one side of an edge during preprocessing; deserializing edge lists that deduplicated by source only.

Understand the failure class

Background: "Must be a positive integer", "Invalid value", "Unsupported": the invalid-argument-value error family, when a library rejects the value you pass — this error's family across 35 libraries.

Related errors

• Matrix must be symmetric!
• Adjacency matrix must be square!
• Adjacency matrix must be symmetric!
• Graph must be connected!
• The length of key should be divisible by 16

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/f2741e95649371d2. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/Graph/MinimumSpanningTree/Kruskal.cs:158

                    throw new ArgumentException("Matrix must be symmetric!");
                }
            }
        }
    }

    /// <summary>
    ///     Ensure that the given graph is undirected.
    /// </summary>
    /// <param name="adj">Adjacency list of graph to check.</param>
    private static void ValidateGraph(Dictionary<int, float>[] adj)
    {
        for (var i = 0; i < adj.Length; i++)
        {
            foreach (var edge in adj[i])
            {
                if (!adj[edge.Key].ContainsKey(i) || Math.Abs(edge.Value - adj[edge.Key][i]) > 1e-6)
                {
                    throw new ArgumentException("Graph must be undirected!");
                }
            }
        }
    }

    /// <summary>
    ///     Determine the minimum spanning tree/forest.
    /// </summary>
    /// <param name="set">Disjoint set needed for set operations.</param>
    /// <param name="nodes">List of nodes in disjoint set associated with each node.</param>
    /// <param name="edgeWeights">Weights of each edge.</param>
    /// <param name="connections">Nodes associated with each item in the <paramref name="edgeWeights"/> parameter.</param>
    /// <returns>Array of edges in the minimum spanning tree/forest.</returns>
    private static (int, int)[] Solve(DisjointSet<int> set, Node<int>[] nodes, float[] edgeWeights, (int, int)[] connections)
    {
        var edges = new List<(int, int)>();

        Array.Sort(edgeWeights, connections);

View on GitHub (pinned to 96e2905cab)