10
$\begingroup$

I am looking for a way to either get or set a vertex property for all vertices of the graph at once. The two functions will be:

getVertexProp[g_?GraphQ, prop_] := ...
setVertexProp[g_?GraphQ, prop_, values_] := ...

getVertexProp must return a list of values. Each value corresponds to the respective vertex in VertexList[g]. When one particular vertex does not have this property, the list must contain Missing["Nonexistent"].

setVertexProp must set a property when given a similar list.

Requirements

The functions must work with any property, either built-in or custom. getVertexProperty should work even if a property is set only for some of the vertices.

I suggest testing the implementation at least with:

  • Properties VertexWeight, VertexStyle, and "foo".
  • The two graphs g1 = RandomGraph[{10,20}] and g2 = Graph[VertexList[g1], EdgeList[g1]].
  • Setting the same property twice on both graphs above (to test overwriting).

Example implementation

getVertexProp[g_?GraphQ, prop_] := 
 Replace[PropertyValue[{g, #}, prop], $Failed -> Missing["Nonexistent"]] & /@ VertexList[g]

setVertexProp[g_?GraphQ, prop_, values_] :=
 If[
  Length[values] =!= VertexCount[g],
  $Failed,
  Fold[SetProperty[{#1, #2[[1]]}, prop -> #2[[2]]] &, g, Transpose[{VertexList[g], values}]]
 ]

I am looking for an implementation that performs better than these.

Benchmark:

g = ExampleData[{"NetworkGraph", "BipartiteDiseasomeNetwork"}];

values = getVertexProp[g, "Type"]; // RepeatedTiming
(* {0.0080, Null} *)

setVertexProp[g, "Foo", values]; // AbsoluteTiming
(* {15.3572, Null} *)

getVertexProp is fine, but there is a potential for speedup. Compare these two methods of retrieving edge properties:

rg = RandomGraph[{1000, 10000}, EdgeCapacity -> RandomReal[1, 10000]];

PropertyValue[{rg, #}, EdgeWeight -> EdgeCapacity] & /@ EdgeList[rg]; // RepeatedTiming
(* {0.040, Null} *)

WeightedAdjacencyMatrix[rg]["NonzeroValues"]; // RepeatedTiming
(* {0.0000189, Null} *)

Unfortunately, this implementation of setVertexProp is unusably slow.

A different implementation could special-case each type of graph property, but this is ugly and error-prone.

$\endgroup$
8
$\begingroup$

Pardon the rant, but IMO graph related property value infrastructure was poorly designed. The Graph[] api was created before the advent of Associations, and I don't think it has changed since version 8.0.

Anyway, PropertyValue is typically faster than SetProperty according to the docs, maybe this works for you:

ClearAll@setVertexProp;
setVertexProp[g_, prop_, vals_] := Module[{h=g, vl=VertexList@g},
    Do[PropertyValue[{h, vl[[i]]}, prop] = vals[[i]], {i,Length@vl}];
    Return @ h
]

And the timings:

g=ExampleData[{"NetworkGraph","BipartiteDiseasomeNetwork"}];
values = getVertexProp[g, "Type"]; 
res=test1[g,"Foo",values];//AbsoluteTiming
res===g

(* 
   {0.0307, Null}
   False
*)
$\endgroup$
  • $\begingroup$ The function should return a new graph object though, and leave the old one unmodified. Can you fix this (make a copy at the beginning)? $\endgroup$ – Szabolcs Apr 14 '17 at 17:44
  • $\begingroup$ @Szabolcs OK will do. $\endgroup$ – M.R. Apr 14 '17 at 17:56
3
$\begingroup$

I haven't run this through all of the use cases, but just to get the creative juices flowing:

setVertexPropSemiImperative[g_?GraphQ, prop_, values_List] :=
  Module[{vertices = VertexList[g] // Developer`FromPackedArray, i = 0}
  , If[Length[values] =!= Length[vertices]
    , $Failed
    , SetProperty[{g, vertices}, prop :> values[[++i]]]
    ]
  ]

Timings, on my machine:

setVertexProp[g, "Foo", values]; // AbsoluteTiming
(* 33.4833 *)

setVertexPropSemiImperative[g, "Foo", values]; // AbsoluteTiming
(* 0.0413123 *)

Notes

Developer`FromPackedArray? is used here because it has been empirically shown that SetProperty will not accept a packed array of indices (in version 11.1 at least):

SetProperty[{WheelGraph[3], {1, 2, 3}}, "foo" -> 999]
(* ... a graph ... *)

SetProperty[{WheelGraph[3], {1, 2, 3} // Developer`ToPackedArray}, "foo" -> 999]
(* $Failed *)

The VertexList of the graph in the question is not a packed array. But some graph types have a packed vertex list, e.g.

PetersenGraph[] // VertexList // Developer`PackedArrayQ
(* True *)
$\endgroup$
  • $\begingroup$ h = PetersenGraph[]; setVertexPropSemiImperative[h, "foo", Range[10]] fails for me $\endgroup$ – M.R. Apr 14 '17 at 17:18
  • $\begingroup$ @M.R. Yes, for me too. Strange... I am investigating. $\endgroup$ – WReach Apr 14 '17 at 17:25
  • $\begingroup$ I do not fully understand why this should work. I don't think v can be a list of vertices in SetProperty[{g, v}, ...]. At least that did not work in any examples I tried. $\endgroup$ – Szabolcs Apr 14 '17 at 17:46
  • $\begingroup$ @M.R. It fails because SetProperty[{PetersenGraph[], Range[10]}, "foo" -> 999] fails. Yet SetProperty[{PetersenGraph[], {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}, "foo" -> 999] works. It is as if SetProperty was HoldAll, but it isn't. It is a kernel function though, so there appears to be some black magic (emphasis on "black"). $\endgroup$ – WReach Apr 14 '17 at 17:48
  • $\begingroup$ @Szabolcs The documentation claims that a list of vertices is "typically" valid, as is All and a pattern. However, I could not get the latter two to work. And, as @M.R. points out, indexes do not always work either. $\endgroup$ – WReach Apr 14 '17 at 17:50

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.