Metadata lost when a vertex is removed.

[my-little-repository]

In the following snippet, I create a graph with 5 nodes each labeled from "1" to "5". I then delete the node labeled "1" (which happens to be the first node) using the rem_vertex! function. As a result, the label "5" is lost. Is it the intended behavior?

  let g = MetaGraph(Graph(5))
    for v in vertices(g)
      set_prop!(g, v, :name, string(v))
    end
    for v in vertices(g)
      if get_prop(g, v, :name) == "1"
        rem_vertex!(g, v)  
      end
    end
    map(v -> (v, get_prop(g, v, :name)), filter_vertices(g, :name))
  end
  
  julia> 3-element Array{Tuple{Int64,String},1}:
   (2, "2")
   (3, "3")
   (4, "4")

I understand why it is so (removing a vertex swaps it with the last vertex without copying the associated metadata) but that makes the metadata quite brittle.

[sbromberger]

Actually, I think the problem is a bit different:

julia> g = MetaGraph(Graph(5))
{5, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> for v in vertices(g)
             set_prop!(g, v, :name, string(v))
           end

julia> get_prop(g,1,:name)
"1"

julia> rem_vertex!(g,1)
true

julia> get_prop(g,5,:name)
"5"

julia> get_prop(g,4,:name)
"4"

julia> get_prop(g,3,:name)
"3"

julia> get_prop(g,2,:name)
"2"

julia> get_prop(g,1,:name)
ERROR: KeyError: key :name not found
Stacktrace:
 [1] getindex at ./dict.jl:474 [inlined]
 [2] get_prop(::MetaGraphs.MetaGraph{Int64,Float64}, ::Int64, ::Symbol) at /Users/bromberger1/.julia/v0.6/MetaGraphs/src/MetaGraphs.jl:138

julia> g
{4, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

[sbromberger]

@my-little-repository this should now perform properly (that is,

    mga = MetaGraph(Graph(5))
    for v in vertices(mga)
        set_prop!(mga, v, :name, string(v))
    end
    @test get_prop(mga, 1, :name) == "1"
    @test get_prop(mga, 5, :name) == "5"
    @test rem_vertex!(mga, 1)
    @test get_prop(mga, 1, :name) == "5"
    @test isempty(props(mga, 5))

). Let me know if you continue to see issues.

[my-little-repository]

Note that the code in my first post in this thread now returns an error.

  let g = MetaGraph(Graph(5))
    for v in vertices(g)
      set_prop!(g, v, :name, string(v))
    end
    for v in vertices(g)
      println("vertex ", v, " under scrutiny")
      if get_prop(g, v, :name) == "1"
        rem_vertex!(g, v)
        println("vertex ", v, " removed")
      end
    end
    map(v -> (v, get_prop(g, v, :name)), filter_vertices(g, :name))
  end
  
  vertex 1 under scrutiny
  vertex 1 removed
  vertex 2 under scrutiny
  vertex 3 under scrutiny
  vertex 4 under scrutiny
  vertex 5 under scrutiny
  ERROR: KeyError: key :name not found
  Stacktrace:
   [1] getindex at ./dict.jl:474 [inlined]
   [2] get_prop(::MetaGraphs.MetaGraph{Int64,Float64}, ::Int64, ::Symbol) at /home/yves/.julia/v0.6/MetaGraphs/src/MetaGraphs.jl:142
   [3] anonymous at ./<missing>:7

It seems that it is an error to erase a non-existent vertex. In LightGraphs, rem_vertex! does not return an error if the vertex is not there but instead returns false.

  let g = Graph(5), labels = Dict()
    for v in vertices(g)
      labels[v] = string(v)
    end
    for v in vertices(g)
      println("vertex ", v, " under scrutiny")
      if labels[v] == "1"
        rem_vertex!(g, v)
        labels[v] = labels[end]
        println("vertex ", v, " removed")
      end
    end
    map(v -> (v, labels[v]) , vertices(g))
  end
  
  vertex 1 under scrutiny
  vertex 1 removed
  vertex 2 under scrutiny
  vertex 3 under scrutiny
  vertex 4 under scrutiny
  vertex 5 under scrutiny
  4-element Array{Tuple{Int64,String},1}:
   (1, "5")
   (2, "2")
   (3, "3")
   (4, "4")

Finally note that rem_vertex! does not play well with iterators such as filter_vertices.

[sbromberger]

Note that the code in my first post in this thread now returns an error.
...
Finally note that rem_vertex! does not play well with iterators such as filter_vertices.

You cannot iterate over vertices (or edges, or neighbors, or...) while modifying the graph in a loop. This is true for all graph types since we make no guarantees as to how the modification is performed. Any modification of the graph invalidates the loop variable.

One solution is to use an iterator to gather a list of vertices you want to keep (or remove), and then use induced_subgraph to create a new graph with the vertices you want to keep. induced_subgraph will return a vector that maps the new vertices to their original ones:

julia> mga = MetaGraph(Graph(5))
{5, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> for v in vertices(mga)
               set_prop!(mga, v, :name, string(v))
           end

julia> z = induced_subgraph(mga, [1,3,5])
({3, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0), [1, 3, 5])

julia> g = z[1]
{3, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> props(g, 1)
Dict{Symbol,Any} with 1 entry:
  :name => "1"

julia> props(g, 2)
Dict{Symbol,Any} with 1 entry:
  :name => "3"

julia> props(g, 3)
Dict{Symbol,Any} with 1 entry:
  :name => "5"

It seems that it is an error to erase a non-existent vertex.

This is, strictly speaking, not true:

julia> mga = MetaGraph(Graph(5))

{5, 0} undirected Int64 metagraph with Float64 weights defined by :weight (default weight 1.0)

julia> for v in vertices(mga)
               set_prop!(mga, v, :name, string(v))
           end

julia> rem_vertex!(mga,1)
true

julia> rem_vertex!(mga,6)
false