Why does WeightedAdjacencyMatrix take the weight for absent edges to be zero?

Question

According to Wolfram documentation, WeightedAdjacencyGraph[wmat] gives the graph with weighted adjacency matrix wmat, while WeightedAdjacencyMatrix[g] supposedly does the reverse, giving the adjacency matrix of edge weights of the graph g. Yet WeightedAdjacencyGraph takes Infinity to be the absence of an edge, while WeightedAdjacencyMatrix takes the weight of an absent edge to be zero.

This wouldn’t be so bad if completing the round trip were simply a matter of replacing zero with Infinity, but zero is a legitimate weight in a WeightedAdjacencyGraph, meaning an edge of weight zero, not an absent edge. Therefore, there is no way to decide from a WeightedAdjacencyMatrix which zeros mean zero-weighted edges and which zeros mean no edges.

I’m looking both for an explanation of this unexpected behavior and for suggestions on how to work around it. It’s easy enough to write my own version of WeightedAdjacencyMatrix that takes the weight of an absent edge to be Infinity, but I doubt I could match the performance of the built-in function. Besides, I half expected to find an Option in the existing version for this choice, so I’m holding out some hope that I just couldn’t find it.

Answer 1

Here is a workaround: this is a graph with some zero-weight edges:

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 1, 4 <-> 5, 1 <-> 5, 
    2 <-> 5, 3 <-> 5},
   EdgeWeight -> {1, 1, 1, 1, 1, 0, 0, 2}, VertexLabels -> "Name"];
HighlightGraph[g, PathGraph[FindShortestPath[g, 1, 3]]]

WeightedAdjacencyMatrix shows zeros for the missing edges and the actual zero weight edges, however the un-weighted adjacency matrix has only zeros for absent edges, so we can use that:

WeightedAdjacencyMatrix[g] // MatrixForm
AdjacencyMatrix[g] // MatrixForm
MatrixForm[
 Normal[( Normal@WeightedAdjacencyMatrix[g]  /. 0 -> "zw") AdjacencyMatrix[g] +
     "zw" IdentityMatrix[Length@VertexList[g]]]
       /. {0 -> Infinity, "zw" -> 0}]

If you want Infinity on the diagonal, which is what WeightedAdjacencyGraph want:

MatrixForm[
 wam = Normal[( 
      Normal@WeightedAdjacencyMatrix[g] /. 0 -> "zw") AdjacencyMatrix[g]] /. 
        {0 -> Infinity, "zw" -> 0}]

then WeightedAdjacencyGraph[wam] returns the original.

in case you want to put that back to SparseArray form:

  SparseArray[wam, ConstantArray[Length@VertexList[g], 2], Infinity]

Another approach may be to note the SparseArray has explicit zeros for the actual zero weight positions, so in principle you can switch the SparseArray default value. I cant see how to do that except by manually editing the FullForm

Answer 2

Concerning your statement:

Therefore, there is no way to decide from a WeightedAdjacencyMatrix which zeros mean zero-weighted edges and which zeros mean no edges.

This is not true. The SparseArray representation that is used for the WeightedAdjacencyMatrix uses explicit zeros and background zeros. The explicit zeros represent the zero-weighted edges, and the background zeros mean that there is no edge. Now, the FullForm of a SparseArray object is something like:

$$\operatorname{SparseArray}[\operatorname{Automatic},\operatorname{\ dimensions},\operatorname{background},\{\operatorname{index},\operatorname{\ location},\operatorname{values}\}]$$

Here the background is 0, representing the background zeros, and the values field lists the explicit values, and can include an explicit zero as well.

So, as @george2079 alluded to, the way to convert non-edge zeros into Infinity is to just replace the background 0 with Infinity, while leaving the explicit zeros in the values field alone.

Here is a way to do so:

setBackground[Verbatim[SparseArray][a_,b_,_,c__], new_] := SparseArray[a, b, new, c]

Using @george2079's example:

wam = WeightedAdjacencyMatrix[g];
wam //MatrixForm //TeXForm

$\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 2 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 & 0 \\ \end{array} \right)$

Using setBackground:

setBackground[wam, Infinity] //MatrixForm //TeXForm

$\left( \begin{array}{ccccc} \infty & 1 & \infty & 1 & 0 \\ 1 & \infty & 1 & \infty & 0 \\ \infty & 1 & \infty & 1 & 2 \\ 1 & \infty & 1 & \infty & 1 \\ 0 & 0 & 2 & 1 & \infty \\ \end{array} \right)$

Answer 3

WeightedAdjacencyGraph takes Infinity (not 0!) to represent absent connections.

The IGraph/M package provides the IGWeightedAdjacencyGraph and IGWeightedAdjacencyMatrix functions, both of which let you specify which element should represent absent connections. By default, zero is used in both.

---

Here's a function that is analogous to WeightedAdjacencyMatrix, but also allows specifying the element that represents absent connections.

Options[weightedAdjacencyMatrix] = Options[WeightedAdjacencyMatrix];
weightedAdjacencyMatrix[graph_?GraphQ, unconnected : Except[_?OptionQ] : 0, opt : OptionsPattern[]] :=     
With[{sa = WeightedAdjacencyMatrix[graph, opt]},
  SparseArray[sa["NonzeroPositions"] -> sa["NonzeroValues"], Dimensions[sa], unconnected]
]

(But Carl's is probably faster.)

---

Since IGWeightedAdjacencyGraph is implemented purely in Mathematica, I will copy here its current implementation (Feb 2018). It relies on an undocumented syntax of Graph where edges are given in terms of vertex indices (not vertex names).

Example: Graph[{a,b,c}, {{1,2}, {1,3}}] gives the same graph as Graph[{a,b,c}, {a<->b, a<->c}]. Since the index-based edge list may be a packed array, operations on it can be very fast. This implementation of IGWeightedAdjacencyGraph is typically slightly faster than WeightedAdjacencyGraph—I believe for this reason.

IGWeightedAdjacencyGraph[wam_?SquareMatrixQ, unconnected : Except[_?OptionQ] : 0, opt : OptionsPattern[Graph]] :=
    IGWeightedAdjacencyGraph[Range@Length[wam], wam, unconnected, opt]

IGWeightedAdjacencyGraph[vertices_List, wam_?SquareMatrixQ, unconnected : Except[_?OptionQ] : 0, opt : OptionsPattern[Graph]] :=
    Module[{sa = SparseArray[wam, Automatic, unconnected], directedEdges = OptionValue[DirectedEdges]},
      If[Length[vertices] != Length[sa],
        Message[IGWeightedAdjacencyGraph::ndims, vertices, wam];
        Return[$Failed]
      ];
      If[directedEdges === Automatic,
        directedEdges = Not@SymmetricMatrixQ[sa]
      ];
      If[Not[directedEdges],
        sa = UpperTriangularize[sa]
      ];
      Graph[vertices, sa["NonzeroPositions"], EdgeWeight -> sa["NonzeroValues"], DirectedEdges -> directedEdges, opt]
    ]

The key parts of the code are:

• Re-build the sparse matrix with the desired background element: sa = SparseArray[wam, Automatic, unconnected]. Note that this does not change the matrix (like in Carl's answer). It simply changes what is stored explicitly.

• Extract the non-zero positions and values to build the weighted graph: Graph[vertices, sa["NonzeroPositions"], EdgeWeight -> sa["NonzeroValues"]

The rest is just for handling directed/undirected graphs and error checking.