16
$\begingroup$

Bug introduced in 8.0 and fixed in 12.2.

How can I remove EdgeWeights from a Graph without affecting any other properties of the graph?

Let's construct a graph with weights:

g = RandomGraph[{10, 20}, EdgeWeight -> ConstantArray[1, 20]]

Based on the documentation I would expect the following to return Automatic (the same thing it returns for a graph that has no edge weights):

PropertyValue[RemoveProperty[g, EdgeWeight], EdgeWeight]

(* ==> {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} *)

However, it returns the weights that were originally set.

The following seems to work, but it removes other properties as well

PropertyValue[RemoveProperty[g], EdgeWeight]

(* ==> Automatic *)

Extracting the edges and vertices, then re-building the graph will discard other properties as well. Graph objects are atomic, and they don't have a Mathematica-expression form, so trying to modify them at the expression level is not a possibility either.

How can one then remove EdgeWeights from a Graph without modifying any other properties of the Graph?

Update: It turns out WeightedGraphQ@RemoveProperty[g] still returns True. So even though the weight values are removed, the system still considers the graph to be weighted.

Improve this question
$\endgroup$
3
  • 10
    $\begingroup$ I think we are witnessing here one of the (probably many) consequences of the design decision which seems a departure from the general Mathematica design based on symbolic programming paradigm. I particularly like, and agree with this post of @WReach, in this regard. I make this comment irrespective of whether or not your particular question has a (simple) solution. $\endgroup$
    – Leonid Shifrin
    May 16, 2012 at 10:02
  • 2
    $\begingroup$ @Leonid I completely agree. BTW this question was triggered by some bugs/crashes in FindShortestPath. I think these types of crashes/problems would be less likely to occur if Graph weren't designed this way. There are several problems which I think are related to the Graph data structure becoming corrupted internally. $\endgroup$
    – Szabolcs
    May 16, 2012 at 10:48
  • $\begingroup$ Yes, I agree. And, I am not surprised. It is the impedance mismatch between mutability and idiomatic Mathematica, which makes the design particularly hard in cases when mutability is needed. Choosing an easy route just brings this impedance mismatch to the user. This is not an easy problem, of course. $\endgroup$
    – Leonid Shifrin
    May 16, 2012 at 11:25

5 Answers 5

Reset to default
9
$\begingroup$

This has to be a bug. I think Graph never really associates EdgeWeight with corresponding edges.

Here is a simplified example.

g = Graph[{1, 2, 3}, {
                Property[1 <-> 2, EdgeWeight -> x],
                         1 <-> 3,
                Property[2 <-> 3, EdgeWeight -> y]
                }];

gNew = RemoveProperty[{g, 1 <-> 2}, EdgeWeight];
gNew2 = SetProperty[{g, 1 <-> 2}, EdgeWeight -> Missing["Nonexistent"]];


Outer[
            PropertyValue[{#1, #2}, EdgeWeight] &,
            {g, gNew, gNew2},
            {1 <-> 2, 1 <-> 3, 2 <-> 3}
            ] // TableForm[#, 
                TableHeadings -> {{"g", "gNew", "gNew2"},
                 {1 <-> 2, 1 <-> 3, 2 <-> 3}}] & // Quiet

comparison of EdgeWeight list after removing

Notice the gNew row, how EdgeWeights are mis-aligned when the preceding one (i.e. x) deleted. And the 3rd column gives us a clue how PropertyValue extracts EdgeWeight -- that is, by Part.

I would definitely call this a bug.

The workaround I can come up with are two ways. The easy way is as I did for gNew2 -- instead of removing it, replacing it with a placeholder. While the hard way is to permute the to-be-delete edge to the end of edge-list before performing the delete:

myRemoveEdgeWeight[g_, e_] :=
    Module[{vl = VertexList[g], el = EdgeList[g], pos, ewl, ew},
        pos = Position[el, e];
        el = Insert[Delete[el, pos], e, -1];
        ewl = PropertyValue[g, EdgeWeight];
        ew = Extract[ewl, pos][[1]];
        ewl = Insert[Delete[ewl, pos], ew, -1];
        Graph[vl, el, EdgeWeight -> ewl] //
            RemoveProperty[{#, e}, EdgeWeight] &
        ]

PropertyValue[{myRemoveEdgeWeight[g, 1 <-> 2], #}, EdgeWeight] & /@
 {1 <-> 2, 1 <-> 3, 2 <-> 3}

{{1, y}[[3]], 1, y}
Improve this answer
$\endgroup$
5
$\begingroup$

I should post this as a comment, but it is too long. Perhaps I'll delete it later.

There is also some nuisance with RandomGraph[]. Compare the following equivalent graphs:

n = 6;
g = CompleteGraph[n, EdgeWeight -> Range[n (n - 1)/2]]
WeightedAdjacencyMatrix[g] // MatrixForm
g1 = RandomGraph[{n, n (n - 1) /2}, EdgeWeight -> Range[n (n - 1)/2]]
WeightedAdjacencyMatrix[g1] // MatrixForm

Edit

Answering Szabolcs's comment:

n = 6;
g = CompleteGraph[n, EdgeWeight -> Range[n (n - 1)/2]];
w = WeightedAdjacencyMatrix[g] // MatrixForm;
g1 = RandomGraph[{n, n (n - 1) /2}, EdgeWeight -> Range[n (n - 1)/2]];
w1 = WeightedAdjacencyMatrix[g1] // MatrixForm;
Row[{w, w1}]

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is consistent if we take into account the different order of edges in EdgeList[g] and EdgeList[g1]. $\endgroup$
    – Szabolcs
    May 16, 2012 at 12:35
  • $\begingroup$ What I mean is that the edge weights are set assuming the ordering in EdgeList. Since this is different for the two graphs, the weights are given to different edges in the two graphs. Also, the adjacency matrix will generally depend on the vertex ordering returned by VertexList (your example is a bit special because a complete graph is symmetric to the exchange of any two vertices) Becaise of this symmetry, in your example it should be possible to permute the rows/columns of one adjacency matrix to obtain the other one. $\endgroup$
    – Szabolcs
    May 16, 2012 at 12:46
  • $\begingroup$ @Szabolcs See edit please ... something nastier is going on $\endgroup$
    – Dr. belisarius
    May 16, 2012 at 13:05
  • $\begingroup$ @Szabolcs What you are explaining is what I expected :) $\endgroup$
    – Dr. belisarius
    May 16, 2012 at 13:14
4
$\begingroup$

IGUnweighted in IGraph/M can do this.

A possible implementation is

Graph[ VertexList[g], EdgeList[g], FilterRules[Options[g], Except[EdgeWeight]] ]

However, this is not as fast as it could be. The current implementation IGraph/M uses is similar to how Carl Woll's Nucleus function works.

Improve this answer
$\endgroup$
2
$\begingroup$

The bug appears to have been fixed in V13.0.0 or earlier

bugfixed

Improve this answer
$\endgroup$
0
$\begingroup$

You can use simple loop.

Before

bridge

For[i = 1, i <= Length@EdgeList@bridge, i++,
  bridge = RemoveProperty[{bridge, EdgeList[bridge][[i]]}, EdgeLabels]]; 
bridge

After

now

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This does not answer the posed question. The code does not even mention EdgeWeight. $\endgroup$
    – Szabolcs
    Oct 16, 2018 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.