transpose graph

Question

how can i write program in java to find the transpose of the graph G, where the input and the output of the program are represented as adjacency list structure. for example:
input:
1>2>3>4>1
outout:
1>4>3>2>

Answer 1

Let's say given a graph G, and a vertex V in Vertices(G), G[V] is the adjacency list of V.

In pseudocode:

FUNCTION transpose(Graph G) : Graph
   INIT Graph GT

   FOR EVERY Vertex U IN Vertices(G) DO
      FOR EVERY Vertex V IN G[U] DO
          append(GT[V], U)

   RETURN GT

This is O(|V|+|E|).

---

Java implementation

The following implementation closely follows the pseudocode. The only thing added is the null check for append. Vertex labels are String, and a graph is represented as a Map<String,List<String>>

import java.util.*;
public class Transpose {
    public static void main(String[] args) {
        Map<String,List<String>> g = new HashMap<String,List<String>>();
        g.put("A", Arrays.asList("B", "C"));
        g.put("B", Arrays.asList("A", "D"));
        g.put("C", Arrays.asList("D"));

        System.out.println(g);
        // prints "{A=[B, C], B=[A, D], C=[D]}"
        //
        // .--- A <--> B --> D <--.
        // |                      |
        // '---------> C ---------'

        Map<String,List<String>> gT = new HashMap<String,List<String>>();
        for (String u : g.keySet()) {
            for (String v : g.get(u)) {
                List<String> gTv = gT.get(v);
                if (gTv == null) {
                    gT.put(v, gTv = new ArrayList<String>());
                }
                gTv.add(u);
            }
        }
        System.out.println(gT);
        // prints "{D=[B, C], A=[B], B=[A], C=[A]}"
        //
        // .--> A <--> B <-- D ---.
        // |                      |
        // '---------- C <--------'     
    }
}

Caveat: this core algorithm doesn't keep vertices with neither in-bound nor out-bound edge(s), but that requires only a trivial processing.