On Wednesday 18 Jan 2012 19:11:55 Waldek Hebisch wrote: > It looks very interesting. I have the following comments: > > - you provide 'spanningForestNode' which IIUC will give list of > as many trees as there are vertices in the graph. However, > usually one needs a single tree per connected component. > - in description of 'spanningTreeArrow' you say that the > it is expanded up to moment when it is impossible the. > expand it without getting repeated arrow. If this description > is true then the thing is quite different than a tree so > the name is misleading.
OK, I'll look at wiki and so on and try to get a definition we can agree on. At the moment the loop detection uses 'spanningForestNode' as it is. I realise this is very inefficient (in terms of memory and runtime), I want to improve the loop detection and routing algorithms (perhaps use Floyd's algorithm or something line that) and not use spanningForestNode for this purpose. Although I think spanningForestNode should still be provided as it represents an important concept. > - for WeightedGraph it is natural make type of weights into > a type parameter. For path algorithm we would then require > this parameter to come from OrderedAbelianMonoid. I was thinking of switching to doubleFloat as floating point weights seem more common in the literature? > - WeightedGraph associates extra info with arrows. Sometimes > we need extra info at vertices, so that would be another kind > of graph. Yes I agree, an issue is: do we include this in the Rep of every type of graph? If we do then the memory usage goes up a bit but if we don't then we need lots of permutations of domains: Weighted nodes + directed graph Weighted arrows + directed graph Weighted nodes + weighted arrows + directed graph Weighted nodes + undirected graph Weighted arrows + undirected graph Weighted nodes + weighted arrows + undirected graph Weighted nodes + function graph ... and so on There are other types of graph that I would like to experiment with, for instance, what I think of as a multilevel graph which perhaps could be implemented in equivalent ways: * As a graph whose elements are themselves graphs, where the outer graph can see inside (has arrows between the nodes of) the inner graph. * As a set of graphs with mappings between them, where the whole system is treated as a graph. * As a graph which also has arrows between the arrows. I would also like to experiment with the connection between (duality?) this code and the computing framework. That is use graphs to implement finite-state machine, Turing machine, etc. > - AFAICS you consistenly use lists for representation. That is > fine if you want to incrementallu construct graphs. But most > (all ???) efficient graph algorithms assume that vertices > are some interval in integers and represent other info in > arrays. There is plenty of scope to improve the code. I have not tested how well it scales up (in terms of memory usage and runtime) but I suspect not very well at the moment. I think there is a lot of scope of the algorithms used and these issues like using Lists vs. Arrays. If we are thinking about how well this would scale up then I guess: * mutable (using List) would be more efficient for constructing very large graphs. * immutable (using array) would be more efficient for deconstructing/ using the graphs once they have been constructed. I guess it would be nice to have both mutable and immutable graphs but that would add even more permutations of domain types. So there is a lot that I would like to do if I get the time (any help welcome), I think the most important issue to to get an overall architecture which will allow all these options without having to make big changes to the structure later. Martin -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
