Closed GiggleLiu closed 6 days ago
It might be beneficial if we also wrap on SimpleEdgeIter
type, and haveedges(g)
return an iterator.
The point is that, we can check if an edge exists simply through a has_edge
function without needing to generate all the edges again. c.f. Graphs.jl/
in(e, es::SimpleEdgeIter) = has_edge(es.g, e)
e.g. in the case of UnitDiskGraph, we can use
Graphs.has_edge(g::UnitDiskGraph, s, d) = sum(abs2, g.locations[s] .- g.locations[d]) ≤ g.radius^2
Here are some benchmarks on my device with #34
julia> g = UnitDiskGraph([(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (1.0, 1.0)], 1.2)
UnitDiskGraph{2, Float64}([(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (1.0, 1.0)], 1.2)
julia> e = Graphs.SimpleEdge((3,4))
Edge 3 => 4
julia> @btime e in edges(g);
28.907 ns (1 allocation: 32 bytes)
julia> @btime e in ProblemReductions.all_edges(g);
83.462 ns (2 allocations: 208 bytes)
julia> @btime collect(edges(g));
106.279 ns (4 allocations: 368 bytes)
julia> @btime ProblemReductions.all_edges(g);
65.501 ns (2 allocations: 208 bytes)
For example, we have the same problem defined on planar graph, unit-disk graph, tree graphs et al, instead of the most generic ones.
I suggest we define some wrapper types on the
SimpleGraph
type that defined inGraphs.jl
.Ref: