[BUG] RemoveVertexIf VERY inefficient

[Bouke]

Describe the bug I called RemoveVertexIf to remove 0.3M vertices from a graph containing about 1.3M vertices. This was still running after 12 hours or so. Looking at the code it seems to be very inefficient:

• For each vertex to remove
  • For each vertex in the graph
    • Clone the edge list of that vertex
    • For each edge in that cloned list
      • Remove it from the graph

Expected behaviour Should finish in reasonable time, presumably much less than it takes to create the graph.

[KeRNeLith]

Hello,

Do you have some sample to showcase the issue?

I imagine you're talking about the implementation of the AdjacencyGraph<TVertex, TEdge> right?

[KeRNeLith]

@Bouke I made a branch to put a try for optimizing the vertex removal. I pushed it on optimize_graph_remove_operations for now.

You can test the new version using the snapshot package from MyGet. It should be the result of this build.

Here is a benchmark code I used (using BenchmarkDotNet):

public class RemoveBenchmark
{
    private readonly AdjacencyGraph<int, Edge<int>> _graph;

    public RemoveBenchmark()
    {
        var rand = new Random(1234);
        var graph = new AdjacencyGraph<int, Edge<int>>();
        graph.AddVertexRange(Enumerable.Range(0, 10000));
        for (int i = 0; i < 10000; ++i)
        {
            int v1, v2;
            do
            {
                v1 = rand.Next(0, graph.VertexCount);
                v2 = rand.Next(0, graph.VertexCount);
            } while (graph.ContainsEdge(v1, v2));

            graph.AddEdge(new Edge<int>(v1, v2));
        }

        _graph = graph;
    }

    // Benchmark methods
    [Benchmark(Baseline = true)]
    public void CurrentVersion()
    {
        AdjacencyGraph<int, Edge<int>> graph = _graph.Clone();
        graph.RemoveVertexIfOld(vertex => vertex > 6900);
    }

    [Benchmark]
    public void ReworkedVersion()
    {
        AdjacencyGraph<int, Edge<int>> graph = _graph.Clone();
        graph.RemoveVertexIf(vertex => vertex > 6900);
    }
}

And here are the results I got:	Method	Mean	Error	StdDev	Ratio
CurrentVersion	846.4 ms	16.90 ms	41.78 ms	1.00
ReworkedVersion	121.0 ms	0.49 ms	0.43 ms	0.14

BTW I'm curious to know how much it would help on your use case.