What's the meaning of pathcount[] in `cyclebase.hpp`?

tromp / cuckoo

a memory-bound graph-theoretic proof-of-work system

Other

822 stars 173 forks source link

What's the meaning of pathcount[] in `cyclebase.hpp`? #90

Closed xiongyw closed 5 years ago

xiongyw commented 5 years ago

I did not figure out the meaning and usage of it yet...

Many thanks!

tromp commented 5 years ago

Currently, it's only used to determine if a node has an outgoing edge. That is, pathcount[u] != 0 if and only if cuckoo[u] has been set to point to another node. It was introduced to try find more cycles than just a cycle base, but I later realized this was a dead-end approach and instead I ended up implementing the DFS based search in cucka[rt]oo/graph.hpp With the current limited use of pathcount, the above condition is equivalent to cuckoo[u] != -1, so it could easily be eliminated.

xiongyw commented 5 years ago

Got it, thanks a lot.