Message Boards Message Boards

6
|
4458 Views
|
2 Replies
|
8 Total Likes
View groups...
Share
Share this post:

[FEATURE] Test if a graph is edge-weighted

Posted 7 years ago

It would be very useful to have a reliable function to check if a graph has edge weights.

One might naïvely think that WeightedGraphQ does this:

enter image description here

But that is not quite so. It will return True both when there are EdgeWeights or VertexWeights. I am not quite sure what is the use of this function, as I have not yet come across a situation where I would want to use WeightedGraphQ without also checking if the weights belong to edges or vertices.

If you used WeightedGraphQ before and thought that it tested only for edge weights, upvote this post!

How can we check if there are edge weights then? The best I could come up with is

 PropertyValue[wg, EdgeWeight] =!= Automatic

But:

  • Is this reliable? Given Mathematica's extremely flaky graph property handling, I am just not confident about it.
  • If I have to use this, then what is the point of WeightedGraphQ? In what application do people care if the graph is weighted but not care if the weights belong to edges or vertices?

To show some of that flakiness, take a look at the documentation of all the property handling functions, then see if you can make sense of any of this:

Could you have guessed that there are so many different types of properties with different behaviours and that custom properties are yet again different?

Now let's set some edge weights:

g = RandomGraph[{10, 20}];
wg = RandomGraph[{10, 20}, EdgeWeight -> Range[20]];

In[82]:= PropertyValue[g, EdgeWeight]
PropertyValue[wg, EdgeWeight]

Out[82]= Automatic
Out[83]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

So far so good. But this is an edge property, so this should work too:

PropertyValue[{g, First@EdgeList[g]}, EdgeWeight]
PropertyValue[{wg, First@EdgeList[wg]}, EdgeWeight]

The results are $Failed and 1, again it makes sense.

Now let's set weights:

PropertyValue[
 SetProperty[g, EdgeWeight -> {}],
 EdgeWeight
 ]
(* Automatic *)

How does this make sense? {} should not be allowed. But when I use it, it is silently ignored, and does not change anything, either in g or wg.

Let's try to put some numbers in that list:

SetProperty[g, EdgeWeight -> {1, 2, 3}]

It returns unevaluated now. Why the difference from {}? Neither make sense here.

Let's try the weighted graph:

PropertyValue[
 SetProperty[wg, EdgeWeight -> {1, 2, 3}],
 EdgeWeight
 ]

(* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, \
20} *)

Now it is silently ignored again. This is totally inconsistent.

Let's try giving EdgeCount[g] weights, as that should make sense.

In[96]:= PropertyValue[
 SetProperty[g, EdgeWeight -> Reverse@Range[20]],
 EdgeWeight
 ]

Out[96]= {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, \
4, 3, 2, 1}

Good, it works.

Now try the weighted graph:

SetProperty[wg, EdgeWeight -> Reverse@Range[20]]

This returns unevaluated. What is going on?

OK, maybe you'll say that I need to set weights edge by edge instead of in bulk. And that indeed works. But if PropertyValue supports querying this property for the whole graph, then why doesn't SetProperty support setting it this way? Setting it edge by edge is not only terribly cumbersome, it is also very slow. How should I set it for all edges?

I guess I could use

weights = Reverse@Range[20];
Fold[SetProperty[{#1, First[#2]}, EdgeWeight -> Last[#2]] &, g, Transpose[{EdgeList[g], weights}]]

but is this seriously considered convenient or usable (even if we ignore performance)?

Also notice that when I used syntax which is arguably incorrect, there was never a single error or warning message. Sometimes there was no evaluation, which should usually trigger some problems further down the processing pipeline, but in other cases the weights were just silently ignored.

After seeing all this, are you still confident about your results when using graph properties? Either a tiny mistake you made, or some weird quirk of property handling could have introduced an error into your results.

If this were happening in version 8 (when Graph) was introduced or version 9, I could understand it. But the fact that 7 years after the introduction of Graph (and many bug reports sent to support) it is still like this sends a very discouraging message about whether people should use Mathematica for their network analysis (especially if they plan to publish results).

POSTED BY: Szabolcs Horvát
2 Replies

The solution above suffers from bad performance, unfortunately. Here's a faster, but complicated version:

https://mathematica.stackexchange.com/a/163247/12

edgeWeightedQ[g_?EmptyGraphQ] := False (* avoid error with First if graph has no edges but is vertex weighted *)
edgeWeightedQ[g_] :=
    WeightedGraphQ[g] &&
    With[{weights = Developer`ToPackedArray@GraphComputation`WeightValues[g]},
      If[First[weights] === 1 && MinMax[weights] === {1, 1},
        PropertyValue[g, EdgeWeight] =!= Automatic,
        True
      ]
    ]

A similar implementation is included in IGraph/M as IGEdgeWeightedQ.

POSTED BY: Szabolcs Horvát

Originally I wrote that the best I could come up with was

 PropertyValue[wg, EdgeWeight] =!= Automatic

but I was not confident that this would work in every situation.

Perpahs some thought that this was nitpicking. It wasn't:

g = Graph[{}, {}];

PropertyValue[g, EdgeWeight]
(* $Failed *)

It does not work on the null graph.

So in case someone else wants to test if a graph is edge-weighted, let me rewise that to

WeightedGraphQ[wg] &&  PropertyValue[wg, EdgeWeight] =!= Automatic

(keeping in mind that && is short circuiting)

If anyone finds a problem with this variant, let me know.

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract