graph: consider changing semantics of Len() for graph.Iterator
Created by: kortschak
Background
The graph node and edge iterators free the graph packages from the size limits of []graph.Node
and []graph.Edge
when querying graphs. The freedom to be able to perform graph operations on very large graphs that are backed by disk was one of the reasons for changing to int64
ID values rather than int
although at the time I was envisioning only working on subgraphs that had been pull from those larger backing stores.
With store-agnostic iterators we can conceivably work directly (though slowly) with nodes and edges that are not-memory resident with the exception that the iterator Len
method must have a value to will fit inside an int
. This won't work for 32 bit archs and will also not work for very large graphs. Given that the Len
method is also used to give the user information about potential allocations either directly or via graph.NodesOf
etc. it also doesn't work for very large graphs that may be materialised into a slice.
Proposal
I suggest that we add a minor change to the semantics of the Len
method's returned value.
If the size/order of the graph is either unknown, too costly to calculate or likely to be too large to materialise (all loosely defined) then
Len
may return-1
. The iterator'sNext
loop would however still be able to calculate the number of items.
An alternative to this is to add an ok bool
to Len
method, though it is unclear to me how that will help except in the case of 32 archs, and then we would also need to change the return integer type to int64
which I don't think is tenable.
Potential impact of proposal
The only change to the graph packages would be an addition to the documentation for graph.Iterator
on the Len
method and a defensive check for negative length in graph.NodesOf
, graph.EdgesOf
, graph.WeightedEdgesOf
, graph.LinesOf
and graph.WeightedLinesOf
after the relevant *Slicer
type switch, returning a nil slice if the length is negative panicking with an informative message when the length is negative.
Graphs returning iterators with negative length will not work with a variety of analytical functions in the graph packages; they will fail silently to progress and terminate early. This can be fixed for some routines, but others are expected to never work due due to space constraints.
There are no types in the graph packages that would be affected by any of these changes.
I would do the work.