Delete multiple edges with specific property in a metagraph

Specific Domains Graphs
,
1

Hello everyone,

I want to delete multiple edges in a metagraph that have a specific property, here is my mwe:

using MetaGraphs, Graphs
g = erdos_renyi(1000,5000)
mg = MetaGraph(g)
for i in 1:nv(mg) #give all edges specific property
    for j in neighbors(mg, i)
        set_prop!(mg, Edge(i, j), :age, 5)
    end
end

for i in 1:nv(mg) #remove edges with specific property
    for j in neighbors(mg, i)    
        if get_prop(mg, i, j, :age) <= 5
            rem_edge!(mg, i, j)  
        end
    end
end
ne(mg)

This returns around 1000 edges and I always need to repeat the second for-loop 2 times to remove all edges.
What am I missing?
Thanks in advance

2

Are you visiting each edge two times, or (i, j) is distinct from (j, i)? This is the only strange thing I see.

3

Adding rem_edge!(mg, j, i) in addition to rem_edge!(mg, i, j) to the for-loop doesn’t change anything, if this is what you mean

4

No, it shouldn’t. You are already visiting both (i, j) and (j, i), because you visit all nodes, and from every node you visit all neighbors, so you visit (1, 3) when your node is 1 and (3, 1) when your node is 3. This is what I was meaning.

5

Truly baffling.

using MetaGraphs, Graphs

let
g = erdos_renyi(1000,5000)#; is_directed = true, seed = 1)

mg = MetaGraph(g)
for i in 1:nv(mg) #give all edges specific property
    for j in neighbors(mg, i)
        set_prop!(mg, Edge(i, j), :age, 5)
    end
end
@show nv(mg)
@show ne(mg)

qt_removed = 0
for i in 1:nv(mg) #remove edges with specific property
    for j in neighbors(mg, i)
        if get_prop(mg, i, j, :age) <= 5
						qt_removed += 1
            rem_edge!(mg, i, j)
        end
    end
end

@show nv(mg)
@show ne(mg)
@show qt_removed
@show ne(mg) + qt_removed

for i in 1:nv(mg) #remove edges with specific property
    for j in neighbors(mg, i)
        if get_prop(mg, i, j, :age) <= 5
						qt_removed += 1
            rem_edge!(mg, i, j)
        end
    end
end

@show nv(mg)
@show ne(mg)
@show qt_removed
@show ne(mg) + qt_removed
end

outputs

nv(mg) = 1000
ne(mg) = 5000
nv(mg) = 1000
ne(mg) = 1020
qt_removed = 3980
ne(mg) + qt_removed = 5000
nv(mg) = 1000
ne(mg) = 81
qt_removed = 4919
ne(mg) + qt_removed = 5000
5000
1 Like
6

Weird, you should report an issue…

7

Or maybe this is due to modifying the graph while iterating through neighbors…
Edit: Yep, this is it, you can maybe store the edges you want to delete in each pass through a neighborhood, then delete all the edges at once.

2 Likes
8

Yes, I think this is the best line of investigation. I do not know how the graph is stored, my basic mental model of representation did not have this problem, but maybe if it is highly optimized it does not support this.

9

That does the trick. If I store all edges with the specific property in an edgelist and then remove all edges of that list, it only takes a single for-loop and works as expected.

Thank you both for your fast replies!