Graph - Square of a directed graph
Yes, this will be a homework (I am self-learning not for university) question but I am not asking for solution. Instead, I am hoping to clarify the question itself.
In CLRS 3rd edition, page 593, excise 22.1-5,
The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that (u,v) ∈ E2 if and only if G contains a path with at most two edges between u and v. Describe efficient algorithms for computing G2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
However, in CLRS 2nd edition (I can't find the book link any more), page 530, the same exercise but with slightly different description:
The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that (u,w) ∈ E2 if and only if for some v ∈ V, both (u,v) ∈ E and (v,w) ∈ E. That is, G2 contains an edge between u and w whenever G contains a path with exactly two edges between u and w. Describe efficient algorithms for computing G2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
For the old exercise with "exactly two edges", I can understand and can solve it. For example, for adjacency-list, I just do v->neighbour->neighbour.neighbour, then add (v, neighbour.neighbour) to the new E2.
But for the new exercise with "at most two edges", I am confused.
What does "if and only if G contains a path with at most two edges between u and v" mean?
Since one edge can meet the condition "at most two edges", if u and v has only one path which contains only one edge, should I add (u, v) to E2?
What if u and v has a path with 2 edges, but also has another path with 3 edges, can I add (u, v) to E2?
Answer
Yes, that's exactly what it means. E^2 should contain (u,v) iff E contains (u,v) or there is w in V, such that E contains both (u,w) and (w,v).
In other words, E^2 according to the new definition is the union of E and E^2 according to the old definition.
Regarding to your last question: it doesn't matter what other paths between u and v exist (if they do). So, if there are two paths between u and v, one with 2 edges and one with 3 edges, then (u,v) should be in E^2 (according to both definitions).