private void clone(Vertex<T> origVertex,Map<Vertex<T>,Vertex<T>> cloneMap){
        Vertex<T> cloneVertex = null;
        if(cloneMap.containsKey(origVertex)){
            cloneVertex = cloneMap.get(origVertex);
        }else{
            cloneVertex = new Vertex<T>(origVertex.getId()*10);
            cloneMap.put(origVertex, cloneVertex);
        }
        for(Edge<T> edge : origVertex.getEdges()){
            if(edge.getVertex1().equals(origVertex)){
                Vertex<T> adjVertex = edge.getVertex2();
                updateMap(cloneMap,cloneVertex,adjVertex,edge);
            }else{
                Vertex<T> adjVertex = edge.getVertex1();
                updateMap(cloneMap,cloneVertex,adjVertex,edge);
            }
        }
    }
Given a directed graph clone it in O(n) time where n is total number of edges
Test cases
Graph is directed/non directed
Graph has 0 edges
Graph has cycle
Graph is linear
Graph is dense
Graph is sparse
src/com/interview/graph/CloneDirectedGraph.java