Starting work to implement #18 as well as #54 for some of my own use cases. Looks like some planning work went into these in the past so not sure if there's a more preferred approach.
Ran into a performance use case for multigraphs where to minimize enumeration on traversals for I wanted an index of edge label sets to trade some space for time.
Current approach
A map edge_index: %{edge_index_key => MapSet.t()} to store the sets of of edge keys: edge_key :: {vertex_id, vertex_id}.
Since the trade-off of space for time shouldn't be assumed by default it's optional with Graph.new(multigraph: true) where an override-able edge_indexer: (Edge.t() -> edge_index_key) is invoked during edge addition but only when multigraph is true. The default indexer builds sets of edge_keys by the label. This lets the sets be built off of the weight or other edge properties.
For metadata / edge properties changing the edge value from %{label => edge_weight} to
as well as adding the properties map to the %Edge{} struct.
Finally to use the index - reflection / traversal APIs can be extended for predicates such as Graph.out_edges(graph, :a, :foo) where multigraph: true it returns the subset of edges in the index by the key :foo. Not 100% on the API - something more explicit like Graph.out_edges(graph, :a, label: :foo) might be preferred so it can be used without multigraphs or where a function to filter the edges by can be passed in.
Todos:
[ ] Option to enable multigraphs via edge indexing
[ ] Override-able indexing function defaulting to fn %{label: label} -> label end to return the key
[ ] Traversal APIs with filter predicates to benefit from the indexing
Starting work to implement #18 as well as #54 for some of my own use cases. Looks like some planning work went into these in the past so not sure if there's a more preferred approach.
Ran into a performance use case for multigraphs where to minimize enumeration on traversals for I wanted an index of edge label sets to trade some space for time.
Current approach
A map
edge_index: %{edge_index_key => MapSet.t()}to store the sets of of edge keys:edge_key :: {vertex_id, vertex_id}.Since the trade-off of space for time shouldn't be assumed by default it's optional with
Graph.new(multigraph: true)where an override-ableedge_indexer: (Edge.t() -> edge_index_key)is invoked during edge addition but only whenmultigraphistrue. The default indexer builds sets ofedge_keysby thelabel. This lets the sets be built off of theweightor other edge properties.For metadata / edge properties changing the edge value from
%{label => edge_weight}toas well as adding the
propertiesmap to the%Edge{}struct.Finally to use the index - reflection / traversal APIs can be extended for predicates such as
Graph.out_edges(graph, :a, :foo)wheremultigraph: trueit returns the subset of edges in the index by the key:foo. Not 100% on the API - something more explicit likeGraph.out_edges(graph, :a, label: :foo)might be preferred so it can be used without multigraphs or where a function to filter the edges by can be passed in.Todos:
fn %{label: label} -> label endto return the key