search

thi-ng / umbrella

⛱ Broadly scoped ecosystem & mono-repository of 199 TypeScript projects (and ~180 examples) for general purpose, functional, data driven development
https://thi.ng
Apache License 2.0
3.38k stars 150 forks source link

hasVertex for adjacency list #398

Closed dearlordylord closed 1 year ago

dearlordylord commented 1 year ago

It has hasEdge but I found that I need hasVertex as well and that it's missing it...

postspectacular commented 1 year ago

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...

Would you feel comfortable making these additions yourself and update this PR? Let me know pls! Thanks

dearlordylord commented 1 year ago

Thank you for a detailed response @postspectacular , and yes I'd actually love to assist with this, although probably not earlier than the next week. I'm going to look into it and update the PR. Thank for your directions, it seems they are going to be very helpful.

dearlordylord commented 1 year ago

moved to https://github.com/thi-ng/umbrella/pull/400