*From*: Ingo Weinhold <bonefish@xxxxxxxxxxxxxxx>*To*: haiku-appserver@xxxxxxxxxxxxx*Date*: Wed, 20 Apr 2005 15:21:20 +0200 (MEST)

On Wed, 20 Apr 2005, Stephan Assmus wrote: [...] > As for doing the in-place copy of all the rects in a BRegion in the > correct order, I have already contacted Stefano in privat (because he > wrote BRegion). If anybody else has an idea for a fast topological > sorting algorithm, feel free to speak up! :-) To learn more about the > problem, read the extensive comment above src/servers/app/drawing/ > DisplayDriverPainter::CopyRegionList(). I probably don't have a perfect solution, but it strikes me that this problem looks similar to topologically sorting directed acyclic graphs (DAGs), for which a beautiful solution by Tarjan exists. For those not familar with graphs, a directed graph consists of a set of nodes (aka vertices) and directed edges (aka arcs or arrows) between the nodes. If there's no cycle in the graph (i.e. no path along the edges that ends where is started), it's a DAG. Topologically sorting the nodes of a DAG means to enumerate the nodes such that for any two nodes one may be enumerated before the other if and only if there is no path along the edges from the latter to the former. Or formulated differently, if you remove the nodes one after the other in the order they are enumerated (and the incident edges with them) you would always only remove a node that has no ingoing edges. This is pretty much already the idea of Tarjan's algorithm. The representation of the graph should be a set per node containing the nodes the node has outgoing edges to. First the algorithm counts the number of ingoing edges for each node (aka indegree). It maintains a set (a list or stack is sufficient) of nodes with indegree 0. It picks one of those nodes and removes it from the graph, decrementing the indegrees of adjacent nodes, putting those whose indegree dropped to 0 into the set. This goes on until the 0 indegree set is empty, which in case of a DAG only happens, when all nodes have been removed. If there are still nodes, the remaining subgraph(s) is/are cyclic. Back to the problem of topologically sorting non-overlapping rectangles: If you consider the rectangles nodes and add edges respective to their horizontal and vertical relationship, topologically sorting the nodes sorts the rectangles as required. In case of left->right, top->bottom moving for any pair of nodes you would add an edge when one rect is to the right or to the bottom of the other. If both is the case, but with opposite directions (as for A and B in your example) neither edge is added (the order between the two rects shouldn't matter). Unfortunately the complexity is O(n^2) here, but I actually think we can't do faster, anyway. At least not when considering the dimensions separately. Maybe one can use the fact that the rectangles don't overlap to reduce the complexity, but I don't see how. CU, Ingo

**References**:**[haiku-appserver] Re: Going "back" & clipping***From:*Stephan Assmus

- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping
- » [haiku-appserver] Re: Going "back" & clipping