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$
3
  • $\begingroup$ Make a note here. $\endgroup$
    – yode
    May 8, 2017 at 17:11
  • $\begingroup$ Do you think GraphComputation`GraphAbsoluteOptions[ ExampleData[{"NetworkGraph", "EastAfricaEmbassyAttacks"}]] can help? $\endgroup$
    – yode
    May 9, 2017 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, 2017 at 16:59

1 Answer 1

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$
2
  • $\begingroup$ Great! Small but useful improvement from DeleteDuplicates. Please also see the comments I just posted on W Community. $\endgroup$
    – Szabolcs
    Apr 25, 2017 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$
    – TimRias
    Apr 25, 2017 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.