[Tcllib-devel] Revision 37

[Michał A. <ant...@gm...>]

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.


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

 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?
- it works with graph using edge weights - should I change it to attributes
and assume for further work that all code should be using only attributes?

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?
- when diameter is odd, it just checks, if found solution is better than
previous one
- 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.


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

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

Best Regards,
Michał Antoniewski