Skip to content

Poor performance of Graph.replace_vertex/2 for large graphs #85

Open
@stevensonmt

Description

@stevensonmt

Similar to #80 with likely similar fix. ~25x speedup for graph with 1M vertices/edges in iex for:

g = (Graph.new() |> Graph.add_edges(Enum.map(1..1_000_000, fn i -> {i, 1_000_000 - i} end)))
:timer.tc(fn -> Graph.replace_vertex(g, Enum.random(1..1_000_000), 1_000_001) end, :millisecond)
# {56, #Graph<type: directed, num_vertices: 999897, num_edges: 1000000>}
:timer.tc(fn -> Graph.replace_vertex_old(g, Enum.random(1..1_000_000), 1_000_001) end, :millisecond)
# {1399, #Graph<type: directed, num_vertices: 999897, num_edges: 1000000>}

Will add to PR #84 as related issues. Would like someone to double check that I haven't mixed up the in-edges and out-edges definitions.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions