Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

redundant linear indexing #52

Closed
hexaeder opened this issue Nov 4, 2020 · 0 comments
Closed

redundant linear indexing #52

hexaeder opened this issue Nov 4, 2020 · 0 comments

Comments

@hexaeder
Copy link
Member

hexaeder commented Nov 4, 2020

I found the offset/index stuff rather confusing and redundant. I think this could be reorganized a bit in order to make it more straight forward. Right now the index information is stored as pairs of offset+lenght as well as ranges in GraphStruct and again decentralized in the EdgeData/VertexData. Here are some ideas:

Each vortex and (in contrast to LighGraphs) each edge is identified by a unique index. Since the GraphStruct should not depend on the concrete underlying data structure. It should only allow quick access to

  • index of src and dst vertex for given edge
  • indices of all outgoing/incomming edges for given vertex
struct GraphStruct
    v_dims::Vector{Int}
    e_dims::Vector{Int}
    v_syms::Vector{Symbol}
    e_syms::Vector{Symbol}
    _e_src_vert::Vector{Int}
    _e_dst_vert::Vector{Int}
    _v_out_edges::Vector{Vector{Int}}
    _v_in_edges::Vector{Vector{Int}}
end

During the initialisation of GraphData all of the offsets could be calculated explicitly very cheap like

@inline function linear_vert_idx(g::GraphStruct, i)
    offset = i==1 ? 0 : sum(@view g.v_dims[1:i-1])
    @inbounds last = offset + g.v_dims[i]
    offset+1:last
end

... and once the 'views' aka EdgeData/VertexData are constructed they are cached there.

# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant