search

waynebhayes / SANA

Simulating Annealing Network Aligner
25 stars 39 forks source link

SPC measure does not work with SANA method #109

Open TIXFeniks opened 4 years ago

TIXFeniks commented 4 years ago

Hello! I am trying to use the tool with the SPC measure, but the incremental methods are not implemented in SANA.cpp. Is there a way to maximize the SPC measure without changing the source code? There was also an assert(false) in the distance matrix computation in Graph.cpp but i found a way around that (By implementing Dijkstra as the comment suggested and using openmp to speed it up).

waynebhayes commented 4 years ago

Short answer: no, the code needs to change.

Long answer: To operate efficiently, SANA needs a way to "incrementally" update the value of the objective function whenever we randomly change the alignment. If you've pre-computed all-pairs shortest paths on the two input networks, then the question is: when we re-align one (or two) nodes from G1 to new places in G2, how does the shortest path difference change? We couldn't figure out how to do it efficiently, so we left it undone. If you can figure out a way in pseudo-code to update the shortest path difference for both the Change and Swap operations, I can probably find a student to implement it. But it would take time, and we'd probably need to talk through it by voice.