transpose of a directed graph
Carl Forsman
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/graphIntro.htm
It gives the algorithm to compute the Transpose of a directed graph -
Algorithm for computing GT from G in representation of graph G is
ALGORITHM MATRIX TRANSPOSE (G, GT)
For i = 0 to i < V[G]
For j = 0 to j V[G]
GT (j, i) = G(i, j)
j = j + 1;
i = i + 1
To see why it works notice that if GT(i, j) is equal to G(j, i), the
same thing is achieved. The time complexity is clearly O(V2).
1) I think it loop all Nodes in the graph twice?
2) It swap the GT(j,i) = G(i,j), what it really doing? It swap the V
and E?
3) the complexity is O(V^2) that means number of vertices ^2 ?
davec...@gmail.com
> Fromhttp://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphA...
>
> It gives the algorithm to compute the Transpose of a directed graph -
>
> Algorithm for computing GT from G in representation of graph G is
>
> ALGORITHM MATRIX TRANSPOSE (G, GT)
>
> For i = 0 to i < V[G]
> For j = 0 to j V[G]
> GT (j, i) = G(i, j)
> j = j + 1;
> i = i + 1
>
> To see why it works notice that if GT(i, j) is equal to G(j, i), the
> same thing is achieved. The time complexity is clearly O(V2).
>
> 1) I think it loop all Nodes in the graph twice?
> 2) It swap the GT(j,i) = G(i,j), what it really doing? It swap the V
> and E?
> 3) the complexity is O(V^2) that means number of vertices ^2 ?
yeah ok, so you need to bear in mind here that the (adjacency) matrix
representation G for a directed graph on V vertices is an N x N
matrix with a 1 in position G(i,j) precisely when there is a directed
arc from vertex i ---> vertex j in the directed graph, and which
otherwise has a 0 in position G(i,j). The point of this commentary is
just noticing that if you reverse the direction of all of the arcs in
the digraph, then the new digraph so formed has a matrix
representation which is the transpose of the matrix representation of
the original digraph. To address 1), the algorithm considers each pair
of vertices {i,j} (for i != j) precisely twice, because it considers
them in the order (i,j) and in the order (j,i). It says, reversing
the arrows amounts to making i ---> j an arc of GT iff j ---> i is an
arc of G AND making j ---> i an arc of GT iff i ---> j is an arc of G.
To address 2), hopefully from the above it is clear that no, we are
not swapping the vertex set with the edge set, although there are some
interesting results along these lines, see "Line Graphs" and "Graph
Duality". To address 3), yes, a computer program which was running
these looped lines of lines of code to take the transpose of the
matrix representation would run the innermost line "GT (j, i) = G(i,
j)" exactly V^2 times. This algorithm is using a somewhat simplifed
concept of digraph which does not permit multiple arcs in the same
direction between the same pair of vertices. It is also not optimal,
because it wastes V steps inverting the directions of arrows G(i,i)
which do not exist in the context of the paper you link to, and which,
if they did exist, would not be changed by such an inversion anyhow.
Hope this helps.
davec...@gmail.com
umm, i write N above where i mean V, sorry.
LudovicoVan
>
> On Feb 24, 1:30 am, Carl Forsman <fatwallet...@yahoo.com> wrote:
> > From
> > http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphA...
> > It gives the algorithm to compute the Transpose of a directed graph -
> > Algorithm for computing GT from G in representation of graph G is
>
[snip]
> To address 1), the algorithm considers each pair
> of vertices {i,j} (for i != j) precisely twice, because it considers
> them in the order (i,j) and in the order (j,i). It says, reversing
> the arrows amounts to making i ---> j an arc of GT iff j ---> i is an
> arc of G AND making j ---> i an arc of GT iff i ---> j is an arc of G.
This is incorrect and quite messed-up.
In any case, this question was already answered here:
http://groups.google.co.uk/group/sci.math/msg/5a5ae6b654118486?hl=en
This guy is used to multi-posting.
-LV