8
$\begingroup$

Cross posted on W Community.


I am looking for a fast way to retrieve the vertex and edge property names present in a graph, for use in IGraph/M. There should be two functions:

vertexPropertyList
edgePropertyList

which will each return a list of property names. They should work on any graph. They should return properties which are present on only some of the vertices or edges.

Naïve and slow implementations:

vertexPropertyList[g_?GraphQ] := 
 Union @@ (PropertyList[{g, #}] & /@ VertexList[g])
edgePropertyList[g_?GraphQ] := 
 Union @@ (PropertyList[{g, #}] & /@ EdgeList[g])

g1 = ExampleData[{"NetworkGraph", 
    "CondensedMatterCollaborations2005"}];

g2 = ExampleData[{"NetworkGraph", "HighEnergyTheoryCollaborations"}];

g3 = RandomGraph[BernoulliGraphDistribution[50000, 0.005]];

{AbsoluteTiming@vertexPropertyList[#], AbsoluteTiming@edgePropertyList[#]} & /@ {g1, g2, g3} // Column

Mathematica graphics


Bounty update

Current best solution, based partly on @kglr's answer below:

This is the one to beat for the bounty:

hasCustomProp[g_] := OptionValue[Options[g, Properties], Properties] =!= {}

standardVertexProperties = {
  VertexCoordinates,
  VertexShape, VertexShapeFunction, VertexSize, VertexStyle,
  VertexLabels, VertexLabelStyle,
  VertexWeight, VertexCapacity
};

ClearAll[vertexPropertyList]
vertexPropertyList[g_ /; VertexCount[g] == 0] = {};
vertexPropertyList[g_ /; GraphQ[g] && hasCustomProp[g]] := Sort@DeleteDuplicates[Join @@ PropertyList[{g, VertexList[g]}]]
vertexPropertyList[g_ /; GraphQ[g]] := Intersection[PropertyList[g], standardVertexProperties]

Things I already tried:

To save people time, here I will show approaches that I tried and that did not prove fruitful.

We can get the custom properties and their values like this:

Options[g, Properties]

We could try to extract the property names from this structure. The problem is that edge and vertex properties must be separated. So we start with filtering vertices:

vertexProps = Lookup[
   Association@OptionValue[Options[g1, Properties], Properties],
   VertexList[g1]
   ]; // AbsoluteTiming

(* {0.160342, Null} *)

This in itself takes longer than

PropertyList[{g1, VertexList[g1]}]; // AbsoluteTiming
(* {0.093381, Null} *)

So at least this implementation is not going to be fast enough. It does not mean that there isn't another way to use Options[g, Properties].

$\endgroup$
  • $\begingroup$ Make a note here. $\endgroup$ – yode May 8 '17 at 17:11
  • $\begingroup$ Do you think GraphComputation`GraphAbsoluteOptions[ ExampleData[{"NetworkGraph", "EastAfricaEmbassyAttacks"}]] can help? $\endgroup$ – yode May 9 '17 at 14:31
  • $\begingroup$ you could also define hasCustomProp for edge and vertex separately. For example, hasVCustomProp[g_] := MemberQ[OptionValue[Options[g, Properties], Properties][[All, 1]], x_ /; VertexQ[g, x]] hasECustomProp[g_] := MemberQ[OptionValue[Options[g, Properties], Properties][[All, 1]], _DirectedEdge | _UndirectedEdge] $\endgroup$ – halmir May 15 '17 at 16:59
5
$\begingroup$

Also naive but faster:

ClearAll[vertexPList, edgePList]
vertexPList[g_?GraphQ] := DeleteDuplicates[Join @@ PropertyList[{g, VertexList[g]}]]
edgePList[g_?GraphQ] := DeleteDuplicates[Join @@ PropertyList[{g, EdgeList[g]}]]

{AbsoluteTiming@vertexPList[#], 
    AbsoluteTiming@edgePList[#]} & /@ {g1, g2, g3} // Column

Mathematica graphics

versus

{AbsoluteTiming@vertexPropertyList[#], 
    AbsoluteTiming@edgePropertyList[#]} & /@ {g1, g2, g3} // Column

Mathematica graphics

$\endgroup$
  • $\begingroup$ Great! Small but useful improvement from DeleteDuplicates. Please also see the comments I just posted on W Community. $\endgroup$ – Szabolcs Apr 25 '17 at 10:15
  • $\begingroup$ You can make a further slight improvement by putting another DeleteDuplicates before the join. (This mostly helps if there are many edges/vertices with the same set of properties.) $\endgroup$ – mmeent Apr 25 '17 at 15:15

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.