7
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Well, no one here know why it was done like this. Only Wolfram does. I strongly suggest that you write to Wolfram Support and ask about this. I find this implementation very annoying and have complained about it to Wolfram on more than one occasion. It was stated more than once here that issues which are reported by more people are taken more seriously, so please report it. $\endgroup$ – Szabolcs Nov 22 '16 at 19:24
  • $\begingroup$ @Szabolcs Will do. Thanks for the quick response. $\endgroup$ – RRas Nov 22 '16 at 19:34
  • $\begingroup$ It is probably an oversight from having written the WeightedAdjacencyMatrix function for a shortest path algorithm that works with matrices instead of a more efficient graph representation. In that representation it is convenient to represent missing edges by infinity. $\endgroup$ – Hbar Sep 29 '18 at 14:52
4
$\begingroup$

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]]]

enter image description here

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

enter image description here

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

enter image description here

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

$\endgroup$
  • $\begingroup$ That’s clever. Thanks. $\endgroup$ – RRas Nov 22 '16 at 23:09
2
$\begingroup$

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

IGraph/M provides the IGWeightedAdjacencyGraph function, which lets you specify which element should represent absent connections. By default, zero is used.


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.

$\endgroup$
2
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ @Szabolcs I don't understand. The point was that explicitly stored elements shouldn't change, only the background, and that's what my function does. I especially don't want to rebuild the sparse array because then explicitly stored elements that are the same as the background get dropped. $\endgroup$ – Carl Woll Feb 4 '18 at 19:54
  • $\begingroup$ Sorry, you are correct. $\endgroup$ – Szabolcs Feb 4 '18 at 20:11

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.