On Mon, Jan 11, 2010 at 07:53:28AM +0000, Nick Atty scratched on the wall: > I store all the data for my waterways route planner in SQLite, but I > load it into memory for running Dijkstra's algorithm on it to find the > shortest (when weighted) paths. It's at canalplan.eu if anyone wants a > play. > > One problem you rapidly run into when storing graphs in SQL, in my > limited and non-expert experience, is that - as in this example - you > end up with edge records each of which refers to two vertices. My > database maintenance and update code is riddled with: > > SELECT ... FROM link WHERE place1=x AND place2=y OR place1=y AND place2=x; > > and similar. Apart from imposing a condition (such as always having v1 > < v2 in the example code) is there any sensible way round this?
Put in A->B and B->A as two different edges. Yes, the database is going to get a bit bigger, but most graph algorithms use directed edges anyways-- having "two way" edges is usually just a generalization. Using directed edges also allows you to easily designate one-way routes, or routes with asymmetric weights (river with a strong current?). It also simplifies the SQL quite a bit, which will likely make index utilization better. Of course, storage and maintenance goes up, but such are trade-offs. -j -- Jay A. Kreibich < J A Y @ K R E I B I.C H > "Our opponent is an alien starship packed with atomic bombs. We have a protractor." "I'll go home and see if I can scrounge up a ruler and a piece of string." --from Anathem by Neal Stephenson _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
