How can I remove edge weights from a graph, or change all edge weights in one go, with good performance, while preserving edge ordering?
Consider this weight vector and unweighted graph:
weights = RandomReal[1, 5000];
g = RandomGraph[{1000, 5000}];
Adding the weights to the graph is very fast:
wg = Graph[g, EdgeWeight -> weights]; // RepeatedTiming
(* {0.000010, Null} *)
The only way I know to either remove all these weights, or to change the entire edge-weight vector, is to re-build the graph. This is much too slow for my purposes.
g2 = Graph[VertexList[wg], EdgeList[wg]]; // RepeatedTiming
(* {0.0027, Null} *)
wg2 = Graph[VertexList[wg], EdgeList[wg], EdgeWeight -> 2 weights]; // RepeatedTiming
(* {0.0028, Null} *)
Is there a much faster way? I am looking for something comparable in performance to setting the initial weights.
Update:
Originally I neglected to say that I strongly prefer a solution that maintains edges ordering. Consider for example the task of computing the EdgeBetwennessCentrality
of a weighted and unweighted version of a graph. The result of this function depends on edge ordering.
Carl's original answer based on Nucleus
does maintain edge ordering. The solution based on adjacency matrices is much faster, but it does not maintain edge ordering.
Finally, the performance of these solutions depends on the kind of graph we use. Here's a better benchmark:
g1 = ExampleData[{"NetworkGraph", "CondensedMatterCollaborations"}];
g2 = RandomGraph[{VertexCount[g1], EdgeCount[g1]}, EdgeWeight -> RandomReal[1, EdgeCount[g1]]];
Let us preserve all graph options except edge weights. Re-building the graph from vertices and edges is actually slightly faster than re-building it with Nucleus
for g1
:
wg = g1;
ug = Activate[Nucleus[wg] /. Rule[EdgeWeight, _] -> Sequence[]]; // RepeatedTiming
(* {0.22, Null} *)
ug = Graph[VertexList[wg], EdgeList[wg], FilterRules[Options[wg], Except[EdgeWeight]]]; // RepeatedTiming
(* {0.15, Null} *)
For g2
, the timings are 0.011
and 0.056
, i.e. Nucleus
is significantly faster than the straightforward re-building.
Thus overall Nucleus
is still a significant win for performance. But I am still hoping for further improvement, or at least a solution which is never slower than the naïve rebuild.
I believe that the overhead of Nucleus
comes from re-evaluating all the graph options (3rd Graph
argument), and may be possible to eliminate with an appropriately placed Unevaluated
.
The implementation I settled on for the moment is a variation of Carl's Nucleus
idea:
$graphLink::usage = "$graphLink is a loopback link used to convert atomic graphs to a compound form.";
transformGraphOptions::usage = "transformGraphOptions[fun][graph] applies fun to the list of options stored in graph.";
transformGraphOptions[fun_][g_?GraphQ] :=
(
If[Not@MemberQ[Links[], $graphLink],
$graphLink = LinkCreate[LinkMode -> Loopback];
];
With[
{
expr = AbortProtect[
LinkWrite[$graphLink, g];
LinkRead[$graphLink, Hold]
]
},
Replace[expr, Hold@Graph[v_, e_, opt : _ : {}, rest___] :> Graph[v, e, fun[opt], rest]]
]
)
IGUnweighted[g_?IGEdgeWeightedQ] := transformGraphOptions[ FilterRules[#, Except[EdgeWeight]]& ][g]
IGUnweighted[g_?GraphQ] := g
For g1
above it runs in about 0.18-0.19 seconds on my machine.
g
is already edge-weighted, neither of those affects the existing edge weights. Screenshot. $\endgroup$Graph[v_, e_, opt : _List : {}]
? In other words, it always has at least two arguments, and if the third argument exists, it is a list of options. I feel that I'm walking on thin ice here. $\endgroup$AdjacencyMatrix
approach without affecting edge ordering. $\endgroup$