On Thu, 06 Dec 2007 21:25:25 +0100, Kish Shen <kisshen_at_cisco.com> wrote: > Hi, > > Tias Guns wrote: >> >> >> This is a really powerful visualisation tool, I like it a lot. >> I'm not sure what the double borders and cursive values try to tell, >> they don't seem to add information ? >> What would be really cool is if the graph would be updated >> incrementally (flush a new node and its edges immediately to uDraw when >> it is created). That way, it could be used together with the >> 'Visualisation Client'. You could watch the variables get assigned and >> propagated in the Visualisation Client, and at the same time you could >> see the search tree being traversed in uDraw ! >> > Thanks for your modifications! > > What do you use the search-tree visualisation for? For example, do you > use it for debugging, and/or are you using it to better understand the > execution of your program? I use it to better understand the program indeed. More specifically I'm interested in better understanding at what ratio the solutions are being found using propagation or backtracking, if there are identical subtrees or other duplicate computations, what the effect of different value/variable ordering has on the width and size of the search tree, etc... For measuring the size of the search tree (=number of nodes), I added a getter to the generic_search.ecl file you pointed me too (see attached patch). For a certain model, the model only needs 1 backtrack for each solution, so I needed a different measure to express (in)efficiency. It seemed only possible to put a maximum on the number of nodes in the search, and not to get the number of nodes, so I added an option nodecount(X) in the style of backtrack(X), maybe other people might find this interesting too. > We have been interested in visualising the search process, and I would > like to know how people want to use it Currently we don't have > sufficient resource to develop this, but one reason for open sourcing > ECLiPSe is to allow the user community to contribute, and we would > certainly welcome any contribution in this area! > > While at IC-Parc, a visiting student developed a 3-D visualisation of > the search-tree, which was able to display the search-tree > incrementally. I am not sure if this code was ever distributed, and we > took it out from the source when ECLiPSe was open-sourced, because we > were not sure of the licensing and porting issues (for example the code > uses OpenGL). I took a quick look at the code again today, and it seems > that we should be able to open source the source code itself. > > I think one important issue with visualisation of the search process is > how this will work with large programs, which will have very large > search space that will be impossible to display all at once. I was not > directly involved with the 3-D search-tree visualisation, but I think > one reason that 3-D was used is that it allowed more flexibility for the > display (e.g. you need to worry less about overlapping nodes when you > display them), and it allowed zooming in and out from parts of the > search-tree. I think a 3-D model would be overkill for me. I use the search-tree visualisation in two ways: a) semi-incrementally (together with visualisation client or tracer) to follow the search process step-by-step or b) to visually compare the effect of 2 models on the same problem (eg 2 different search-methods or one model with redundant constraints etc) Having the davinci module work really incremental would benefit `a)', but probably slow down `b)'. About the overlapping nodes: In my previous patch I added the command "da('menu(layout(improve_all))'), % Auto layout search tree", which makes uDraw improve the layout by making all edges non-overlapping and spacing them nicely, and some zooming seems possible to some extend. But as you said, for large problems this doesn't cut it. It would take a very long time before the entire search tree is piped to uDraw, and it would not be overviewable. But that's probably a general problem of drawing large trees : ) I'm just sticking to small instances for the visualisation. > For incremental display of the search-tree with lib(daVinci) and > search/6, you can always modify the search/6 predicate to do this -- the > code for this is in <ECLiPSe>/icparc_solvers/generic_search.ecl. Thanks for the pointer, I addapted it to get the nodecount as explained above. Greetings, Tias > Cheers, > > Kish
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET