deleting a node does not update keys in edge_data

[cecileane]

After deleting a vertex, the order of the codes for the other vertices can be reshuffled, such that the "standard" arrangement of vertex labels to identify undirected edges is modified. Yet, the keys of the edge data still follow the previous arrangement of vertex labels. Here is a minimal example.

julia> using Graphs, MetaGraphsNext

julia> g = MetaGraph(Graph{Int8}(0), Symbol, Int8, Int8, :trial, x -> x, zero(Int8));

julia> add_vertex!(g, :l1, 1); add_vertex!(g, :l2, 2);

julia> add_vertex!(g, :l3, 3); add_vertex!(g, :l4, 4);

julia> code_for(g, :l4) # 4
4

julia> add_edge!(g, :l2, :l1, 10);

julia> g.edge_data
Dict{Tuple{Symbol, Symbol}, Int8} with 1 entry:
  (:l1, :l2) => 10

We want to merge :l4 with :l1. First: connect :l4 to :l1's neighbors, second: delete :l1.

julia> add_edge!(g, :l2, :l4, 10); # connect l4 to l1's only neighbor

julia> g.edge_data
Dict{Tuple{Symbol, Symbol}, Int8} with 2 entries:
  (:l2, :l4) => 10
  (:l1, :l2) => 10

julia> MetaGraphsNext.arrange(g, :l4, :l2)
(:l2, :l4)

julia> g.edge_data[MetaGraphsNext.arrange(g, :l4, :l2)] # edge data is found
10

julia> delete!(g, :l1) # now delete l1 (and its incident edges)

julia> code_for(g, :l4) # 1: has changed. now smaller than the code for l1
1

julia> MetaGraphsNext.arrange(g, :l4, :l2) # different order: because new code for l4
(:l4, :l2)

julia> g.edge_data[MetaGraphsNext.arrange(g, :l4, :l2)] # edge data not found
ERROR: KeyError: key (:l4, :l2) not found
Stacktrace:
 [1] getindex(h::Dict{Tuple{Symbol, Symbol}, Int8}, key::Tuple{Symbol, Symbol})
   @ Base ./dict.jl:484
 [2] top-level scope
   @ REPL[166]:1

julia> for (lab1, lab2) in keys(g.edge_data)
           l1, l2 = MetaGraphsNext.arrange(g, lab1, lab2)
           if lab1 != l1 || lab2 != l2
               @error "labels in edge_data keys = $lab1, $lab2 yet arranged labels = $l1, $l2"
           end
       end
┌ Error: labels in edge_data keys = l2, l4 yet arranged labels = l4, l2
└ @ Main REPL[167]:4

[gdalle]

Wow that is indeed a big bug. And I'm not sure we can fix it within MetaGraphsNext.jl because this behavior is an implementation detail of the SimpleGraph type from Graphs.jl. And if you use another graph type as basis (from VertexSafeGraphs.jl by example) things will be different.
Do you have any suggestion on how to proceed? Perhaps preventing deletion on a meta graph is better?

[cecileane]

Preventing deletion would be too bad! I can think of various options.

But the current code seems to make the following assumption: If the vertex being removed is not the "last" one, in the sense of having the last code, then the "last" vertex (initially with the last code) had its code changed to the deleted vertex's code. In my example above, deleting vertex :l1 deleted the vertex with code 1, so vertices 2 and 3 remained unchanged and the "last" vertex with code 4, labelled :l4, was re-assigned code 1. This assumption seems to be behind the current version of _rem_vertex! on lines 222-227, for the purpose of adjusting the vertex_labels and vertex_properties, to adjust the data of the former "last" vertex.

Is this assumption valid for all graph types, not just SimpleGraphs?
If so, then it should be easy to make a similar adjustment to edge_data.

[bramtayl]

Most likely my bad. The original code was inherited from the original metagraphs, which made that assumption I think, no idea if it holds in general. I wonder if the best solution is just to update MetaGraphs.arrange to sort the based on the labels, not the codes? I guess that would require the labels to have a total order though.

[cecileane]

Indeed, arranging the order of node labels based on the node labels themselves would be best!

Ah but yes, that would require a total order on the labels, and no duplicate labels --which may already be required perhaps, anyway. Personally, I think it's fair to ask for labels that can be ordered, as vertices also have data. The biggest issues might be:

• adjust all places that might be affected: perhaps that's easy, but I'm not familiar with the package
• handle a breaking change (for users who are currently using labels without a total order): communication and all.

[gdalle]

I'm not sure why arrange is the key, if memory serves it's only used to sort two vertices within an edge?
I don't think there is a general solution because different underlying graphs will deal with indices differently, and the Graphs interface does not prescribe anything

[bramtayl]

I think changing this line https://github.com/JuliaGraphs/MetaGraphsNext.jl/blob/5eb369b473fd50c665dec95cb0c9c5b591aa68de/src/directedness.jl#L27C11-L27C11 to label_1 < label_2 would probably be fine for now. < works with symbols and strings, which I'm guessing are the most common label types. We can worry about the deletion issue later. @cecileane can you make a PR with a test? And maybe a note in the docs that labels need to support <?