# Determining on whether topology is a tree or a hypercube

Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to reach terminal state TREE if G is a tree, terminal state HYPERCUBE if instead it is a hypercube. Let n be the number of nodes and m the number of edges, you would like to exchange O(m) messages in the worst case.

I will use DFS until I either:

• reach a leaf or
• a node that has been visited before.

In the first case it is a tree and in the second one it is a hypercube. How does this sound?

In the below code, I assume every the graph is tree. But If I see cycle, I change the STATE to HYPERCube. This happens when a node gets the token twice.

Sample Pseudocode

Initiator
Spontaneously
begin
Unvisited:= N(x);
initiator:= true;
VISIT;
end

IDLE
Receving(T)
begin
entry = sender;
unvisited:= N(x) - {sender};
VISIT;
STATE = "TREE";
end

VISITED
Receiving(T)
begin
STATE = "HYPERCUBE"
end

Receiving(R)
begin
VISIT;
end

Procedure VISIT
begin
if Unvisited =! 0 then
next = Unvisited
send(T) to next;
become VISITED
else
if not (initiator) then send(Return) to entry endif
become DONE;
endif
end

• Certainly, hypercubes have cycles but no leaves and trees have leaves but no cycles. But how is this related to message passing? Aren't you supposed to be making a distributed computation? – David Richerby Sep 22 '14 at 0:00
• I just want to change STATE of the node or leaf according to topology. I am doing something wrong? – real1 Sep 22 '14 at 0:03