Re: [Tcllib-devel] Revision 37

[Andreas K. <and...@ac...>]

Michał Antoniewski wrote:
> Hello.
>  
> Regarding previous ping mail, promised description.
>  
>  
> 1. BFS.
>  
> After some attempts and different organisations of code I decided to 
> divide that BFS procedure into 2 procedures - one for shortests paths 
> finding (ShortestPathsByBFS) and standard BFS (BFS).
>  
> Why and some notes about them:
> - creating one procedure for both, makes code quite complex
> - as both procedures can return dictionaries, trees and graphs, there 
> would be a lot of repeated code or a lot of statements like if which 
> make code doesn't look good ( I just wasn't satisfied at all when I 
> looked at it )
> - dividing into 2 procedures, lets us give easily some improvement to 
> path finding : e.g. if node wasn't in queue yet, it's added at the end 
> of the queue, but when it was added before and erased also from the 
> queue, we add it at the beginning of the queue - it helps a lot cause a 
> lot of not needed computation is omitted.
> - I just see it like 1000 times clearer, when there is such division - 
> both, more intuitive and also considering implementation.

I'll have a closer look at this then.


> Shortests path finding by BFS vs Dijkstra:
> - BFS can work with negative weights ( but negative cycles are of course 
> unwelcome )
> - it's quicker for not sparse graphs, with big amount of nodes
> - it also finds (like Dijkstra) paths from one node to others, so we 
> don't have to use e.g Bellman's Ford, when negative weights are there.

> Path finding by BFS returns us:
> - dictionary containing distances between start node s and each other 
> vertice
> - or dictionary containing paths between start node and each other vertice

Like dijkstra then.

> Notes to BFS path finding:
> - it's weighted, so to get unweighted version we just give at input 
> graph with all weights set to 1.... it's allright or should there be 
> considered unweighted option?

No need for the unweighted option, IMHO.

> - it works with graph using edge weights - should I change it to 
> attributes

Does it make sense for upcoming algorithms ?

 > and assume for further work that all code should be using
> only attributes?

Yes, IMHO.

> Standards BFS returns:
> - BFS tree found by algorithm (struct::tree)
> - BFS graph found by algorithm


> 2. MDST - Minimum diameter spanning tree
>  
> Firstly, how algorithm works:
> - it searches for each node it's BFS tree - so, for each node there is 
> found a tree, with root in that node

> - if, that tree has odd diameter, it's optimal solution

(*)

> - if not.... there can be better solution. For diameter d (diameter of 
> the tree found by BFS), OPT can be "d" or "d-1"

> - now to find, if there is better solution, we do a little trick:
>         a) we search for the deepest subtree of current BFS tree, 
> considering only children of root node as roots of that subtree [*]
>         b) for each subtree found, we do such operation: we add a node 
> between root node of subtree and root node of BFS tree and run BFS again 
> with the start node in a new node we have just added. If the depth of 
> the tree won't change the better solution is found.

> - from all the trees that BFS found, we choose the one with the smallest 
> diameter.

> [*] I've got one concern about that step. My resources say two things: 
> one that we find as I wrote above - the deepest subtree, but also I 
> found that we search for subtree, which height ( the greatest level in a 
> tree -> depth + 1 ) is equal to diameter ( BFS Tree )/2 - 1 (lets call 
> it X for further investigation). So, know I have an issue, if I can just 
> put that equality with X or not, cause I found an example of tree that 
> have even diameter and has bigger value of height than X. On the other 
> hand, that example didn't force the improvement of solution....so, it's 
> possible that this X value can bound the set of proper trees well....but 
> as I'm not completely sure I've put in the code "height >= X" and will 
> investigate it further.
>  
> Implementation:
> - it uses both : graph found with BFS and tree found by BFS.
> - graph is used for diameter counting and other issues, tree is better 
> for handling descendants and finding the greatest tree.
> - it forces adding struct::tree package require to graph ops....is that ok?

Yes.

> - when diameter is odd, it just checks, if found solution is better than 
> previous one

Ah, so what you say at (*) above means 'optimal solution for that specific 
node', not 'optimal solution for the entire graph'.

> - when diameter is even, it does those operations I described above. It 
> creates additional graph for it - tempGraph. If tempGraph has better 
> diameter after providing those changes - the better solution is set.
>  
>  
> 3. Flow problems
>  
> Now both Flow Problems use BFS pathfinding procedure.
>  
> I wrote a little about it in previous mails but to remind:
> - negative arcs - BFS can handle them
> - for not sparse networks BFS is better than Dijkstra - like I noted above.
> - Dijkstra after adding those "must-have" improvements, does a lot more 
> computations. So generally, for typical flow problems BFS will get 
> shorter times of computations -
> even for complete networks ( it's proven ).

> - as BFS has some pathological cases, when reaches exponential increase 
> of amount of operations, but those networks won't occur in practise.

Can you describe the pathological cases ?
This would make a good thing to note in the docs.

> I hope I remebered to write about everything. Just tell me what you 
> think about such organisation.

Review of rev 37+38 will be done sometime today.

> Tests are not full yet, so I will supplement the lacking ones.

Andreas.