I need to check if a graph is edge-weighted while maintaining good performance.
This should be an easy task, but it is not. It is a good example of why it is so terribly frustrating to work with graphs in Mathematica.
Here are three test graphs: a vertex-weighted one, an edge-weighted one, and a non-weighted graph.
vwg = Graph[{1, 2, 3}, {1 <-> 2}, VertexWeight -> {1, 2, 3}];
ewg = Graph[{1, 2, 3}, {1 <-> 2}, EdgeWeight -> {2}];
nwg = Graph[{1, 2, 3}, {1 <-> 2}];
You'd think that WeightedGraphQ
works, but it returns True
for vertex weighted graphs as well. (I reported this shortcoming long ago, but it's still not fixed.)
WeightedGraphQ /@ {vwg, ewg, nwg}
(* {True, True, False} *)
How about the following?
weightedGraphQ1[graph_?GraphQ] :=
MemberQ[PropertyList[graph], EdgeWeight]
Not, it doesn't work correctly:
weightedGraphQ1 /@ {vwg, ewg, nwg}
(* {True, True, False} *)
The only solution I found so far is
weightedGraphQ2[graph_?GraphQ] :=
WeightedGraphQ[graph] && PropertyValue[graph, EdgeWeight] =!= Automatic
This works:
weightedGraphQ2 /@ {vwg, ewg, nwg}
(* {False, True, False} *)
But it is awfully slow:
g = ExampleData[{"NetworkGraph", "CondensedMatterCollaborations2005"}];
weightedGraphQ2[g] // RepeatedTiming
(* {0.13, True} *)
There is no reason why it should be so slow:
WeightedAdjacencyMatrix[g]; // RepeatedTiming
(* {0.013, Null} *)
weightedGraphQ1[g]; // RepeatedTiming
(* {4.51*10^-6, Null} *)
WeightedGraphQ[g]; // RepeatedTiming
(* {3.91*10^-7, Null} *)
Is there any fast way to check if a graph is edge-weighted?
Failed ideas:
- Try to get it from
Options[g]
. It is just as slow asPropertyValue
. The timing is about the same as converting an atomic graph to a compound expression (e.g. sending it through MathLink), so I assume this is what is happening. - Use
WeightedAdjacencyMatrix
somehow. But then I can't distinguish between a graph which is unweighted and one in which all edge weights are 1. - I found the potentially useful undocumented functions
GraphComputation`WeightValues
andGraphComputation`WeightVector
, which return the edge and vertex weights, respectively. These functions will return the default weight value (i.e. 1) for unweighted graphs, thus they also can't be used to distinguish between weighted and unweighted graphs.
This is the best-performing solution I could come up with so far:
weightedGraphQ =
WeightedGraphQ[#] &&
With[{weights = GraphComputation`WeightValues[#]},
If[First[weights] === 1 && SameQ @@ weights,
PropertyValue[#, EdgeWeight] =!= Automatic,
True
]
]&
This function performs multiple tests, in the order of increasing timing, and stops as soon as it can prove that the graph is edge weighted.
This is awfully hackish, but it should perform well in most practical cases.
It is risky though because I am relying on the fact that the default value for unspecified edge weights is precisely 1
. Note that for custom properties it is possible set our own default value, e.g. by Properties -> {"DefaultEdgeProperties" -> {"foo" -> 5}}
. This does not work for EdgeWeight
, but it is not clear if that is by design or if it is an oversight.
MinMax @ weights === {1, 1}
orMinMax @ Developer
ToPackedArray @ weights === {1, 1}` should be faster thanSameQ @@ weights
. $\endgroup$AbsoluteOptions
. It comes down to a call toGraphComputation`GraphDeveloperDump`absoluteOptions
. For your specific case ofEdgeWeight
, it seems simplyOptions
is called. For your large graph,Options[g,EdgeWeight]
is still faster thanPropertyValue
. If we acknowledge that your minmax-weights test only needs 7*^-6 seconds, it is indeed 3500x faster :) $\endgroup$