[ns] Questions on Dijkstra's algorithm in "ns"

[Suleyman Uludag <suludag@cs.depaul.edu>]

I am trying to understand the Dijkstra's SPF algorithm implementation
in ns. However, I have some questions: 

  1) In RouteLogic::compute_routes() function in route.cc, "size_" seems
to hold
the number of nodes in the network. However, when I print the "size_"
when the control of the program reaches that function, it contains the
square of the number of the nodes in the topology. For example, if the
number of nodes is 4, then the value of size is 16. What is the value of
"size_" supposed to be; the number of nodes or the square of the number
of the nodes. 

  2) I tried to track it down to find out how it is passed to the
compute_routes() function but I couldn't. I guess my programming is very
weak. Could anyone give me some clues as to how "size_" is handled and
passed to the compute_routes()? 

  3) A single dimensional array is used to represent the Incindence
Matrices. The incidence matrices are created with a size of (n * n),
where n is set to size_ at the beginning of the function. Following the
previous example from (1), the arrays would have 256 members for a
network which has only 4 nodes. Is my understanding correct? If not,
what am I missing?

  4) The algorithm seems to compute shortest paths out of only n-1
sources, and it would seem that there are only n-1 vertices in the
graph. But then, for each source, it computes shortest paths to n-1
different sinks, indicating that there are indeed n
vertices in total. Is the total number of vertices (nodes) supposed be n
(size_) or n-1?

  I appreciate any help on the above, rather poorly worded, questions.


\su