freenode/#clasp - IRC Chatlog
Search
8:14:36
phoe
I'm a lurker on #clasp for the time being. I enjoy reading the conversations that happen in here.
15:15:17
drmeister
I'm trying to improve cando's subgraph isomorphism matching - has anyone done anything like that before
15:18:24
drmeister
On the other hand I have a partial implementation of the algorithm that bails out after the first hit and I need it to find all the solutions.
15:19:08
Bike
it's the same problem, though there might be some practical improvements possible by relying on the peculiar graph structure of molecules
15:21:03
beach
In the article "Beyond worst-case analysis" in this month's CACM, the author thinks that many problem that are known to be intractable (in the CS sense of the word) are hard only for instances that don't matter.
15:23:13
Bike
it says a subgraph G0 has all vertices that are vertices of the greater graph, and edges that are all edges of the greater graph between vertices that are in the subgraph
15:24:07
Bike
then the rest of the paragraph defines the subgraph isomorphism problem as finding bijections between the search graph's and the subgraph's vertices and edges.
15:25:06
drmeister
Bike - you know our smarts code? Well, it's not ready for smirnoff because it doesn't enumerate all the solutions when you search from a particular atom.
15:26:34
drmeister
The smarts code is reduced to a decision tree that you test by starting on a particular atom.
15:30:31
Bike
smarts is probably a slightly harder problem because you also care about what elements the atoms are and so on.
15:30:42
Bike
though maybe that actually makes it easier since you can rule out possibilities faster.
15:33:46
Bike
maybe i could work on it? i have enough CS education to read the math and enough chemistry to read that.
15:34:39
drmeister
My problem is it doesn't iterate through all solutions, it finds the first match and returns.
15:36:11
drmeister
If you start it on N2 it will bail out immediately because the head of Chain(C,...) is a C and not an N.
15:37:33
drmeister
Right - Chain(head,tail) . head is an atom test. tail is a Chain or a Branch or NIL
15:44:04
drmeister
The current code does a search with backtracking - it's fine for saying - yes - this atom is in a subgraph that matches the pattern - that's fine for atom type assignment.
15:44:59
drmeister
I need to change the way the search goes so that I can iterate through the solutions...
15:46:27
drmeister
Hmm, right now the contains the state of the search. I need to get the state of the search into a vector that stores the values that are currently on the stack.
15:55:29
drmeister
So test #2 starting on N2 should return N2C4C5, N2C6C7 and N2C8C9 and starting on N3 return N3C2C3 and everything else should fail
15:56:21
drmeister
Right now, test#2 on N3 will return N3C2C3 and on N2 will arbitrarily return one of the solutions N2C4C5, N2C6C7 or N2C8C9 and false starting on any other atom.
15:58:07
drmeister
Not that you need to look at it but the code that does this is in chemInfo.cc https://github.com/drmeister/cando/blob/dev/src/chem/chemInfo.cc#L1558 and https://github.com/drmeister/cando/blob/dev/src/chem/chemInfo.cc#L1621
15:58:37
drmeister
Then I have these papers that sound like gobbledy gook and I can't make sense of their algorithms.