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$

2 Answers 2

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$
2
  • $\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, 2017 at 17:44
  • $\begingroup$ @Szabolcs OK will do. $\endgroup$
    – M.R.
    Apr 14, 2017 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$
13
  • $\begingroup$ h = PetersenGraph[]; setVertexPropSemiImperative[h, "foo", Range[10]] fails for me $\endgroup$
    – M.R.
    Apr 14, 2017 at 17:18
  • $\begingroup$ @M.R. Yes, for me too. Strange... I am investigating. $\endgroup$
    – WReach
    Apr 14, 2017 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, 2017 at 17:46
  • 1
    $\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, 2017 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, 2017 at 17:50

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .