dearlordylord
commented
1 year ago Initial comment of @postspectacular
https://github.com/thi-ng/umbrella/pull/398#issuecomment-1531584361
Thanks, @Firfi - this seems like an easy enough fix, but the main reason that method didn't exist so far is that I wasn't quite clear myself yet how to handle this in the general case of the IGraph interface, which should be the common API for all three implementations provided by this package. For the AdjacencyList impl, the mere presence of an entry for a vertex ID is proof the vertex exists, but for AdjacencyBitMatrix and AdjacencyMatrix this isn't the case and there we can currently only infer if a vertex exists iff there are also any incoming/outgoing edges associated with it. One my ideas to overcome this was adding another bitfield for keeping track of explicitly or implicitly declared vertices and then add addVertex(id) and hasVertex(id) methods to the IGraph interface. The only other thing to consider there is the additional memory overhead (122KB per million vertices), but maybe that's not too bad...
postspectacular
predecessor: https://github.com/thi-ng/umbrella/pull/398
I thought a bit about addVertex:
for Adjacency Matrix, it seems it doesn't fit the adjacency matrix model since it contradicts its definition; IF we are to store vertices info in it, it'll become not just BitField but BitMatrix (since we need n^2 booleans to keep the number of edges); which effectively becomes BitMatrix
for BitMatrix, I haven't added addVertex yet and haven't considered it diligently yet, since it doesn't fit the initial idea of "Grapg Interface" anymore (no "addVertex" because of the AdjacencyList consideration above)
Note that BitField doesn't seem to be enough to track Vertices because it loses the info about "how many are there"
Therefore I'm isolating this PR to hasVertex only:
still, there is no BitMatrix (or BitField) used for AdjacencyList because of the considerations above (it seems it becomes AdjacencyBitMatrix, effectively, and we already have that), therefore edge presence implemented through
degreefor AdjacencyBitMatrix, BitMatrix is already there, however O(n) scans needed to determine the presence of a bit to know a vertice is present
nothing new for AdjacencyList
Added some tests, including a bit unrelated bitFIeld test (it is a side effect of me figuring it out 😆 )