search

tromp / cuckoo

a memory-bound graph-theoretic proof-of-work system
Other
822 stars 173 forks source link

Are cuckroo and cucktoo using the same find cycles' algorithm? #94

Closed FivePeter closed 5 years ago

FivePeter commented 5 years ago

Using DFS, cucktoo needs to store a lot of information. Thanks

tromp commented 5 years ago

yes, cuckoo/src/cucka{r,t}oo/graph.hpp implements the dfs cycle finder Slides 24 and 25 show the space requirements of the cyclebase finder and dfs cycle finder respectively. you can reduce these by doing more trimming beforehand...

FivePeter commented 5 years ago

Can I use the directed cuckoo graph to find cucktoo's cycles？For example， the following figure has two paths, D1->A2, A1->C1。When adding (A1,C2),I don't know its direction, A1->C2 or C2->A1?

A1 A2 B1 B2

C1 C2 D1 D2

Thanks

tromp commented 5 years ago

I don't see how. But note that the cyclebase finder maintains a directed forest, where all edges in a single component tree are directed to its root.