freenode/#clasp - IRC Chatlog
Search
19:57:16
drmeister
Hello - I'm back from a bunch of meetings. If I didn't mention this already... the pull requests I accepted yesterday worked fine with Cando.
20:08:03
Bike
did some stuff with value numbering so it actually numbers now, and more importantly i think i worked out a solution to the thinky problem i was having with actually using it for type inference, so i can do that next.
20:33:01
Bike
it's a data structure and algorithms for representing partitions of sets. i could be mistaken about whether it's usable though.
20:33:23
Bike
generally speaking for fastness i need a good implementation of sets. right now i'm using lists, which are not a good implementation of sets
20:34:13
drmeister
Cando's ring finding algorithm uses bitvectors - and it works on very large graphs.
20:36:33
drmeister
On that - I was going to add back a makefile that just does ./waf configure build_dboehm so all people need to do to build clasp is type: make
20:43:03
drmeister
Cando's algorithm is here: https://github.com/drmeister/cando/blob/dev/src/chem/ringFinder.cc#L29
20:43:21
drmeister
There is a reference: Balducci and Pearlman in J. Chem. Inf. Comput. Sci. Vol 34, No. 4, 1994
20:44:16
drmeister
Then each iteration of the algorithm, every node sends every node it's connected to a bitvector message and the bitvectors get updated.
20:44:49
drmeister
I think that's how it works. Don't quote me on it until you've checked out the paper.
20:45:55
drmeister
Another way to find rings is to build a spanning tree from an arbitrary point and then look for edges that aren't part of the tree - they are part of loops.
20:46:29
drmeister
Then generate another spanning tree from one end of the edge, searching for the other end of the edge - those will be the rings.
20:50:31
drmeister
It would tickle me to use the same code for generating optimized code that we use to assign atom types.
20:52:34
Bike
loop detection in a CFG is somewhat more involved, and the graph is directed, but still