private void updateMap(Map<Vertex<T>,Vertex<T>> cloneMap, Vertex<T> cloneVertex, Vertex<T> adjVertex, Edge<T> edge){
        if(cloneMap.containsKey(adjVertex)){
            Vertex<T> adjVertexClone = cloneMap.get(adjVertex);
            Edge<T> newEdge = new Edge<T>(cloneVertex, adjVertexClone, edge.isDirected(), edge.getWeight());
            cloneVertex.addAdjacentVertex(newEdge, adjVertexClone);
        }else{
            Vertex<T> adjVertexClone = new Vertex<T>(adjVertex.getId());
            cloneMap.put(adjVertex, adjVertexClone);
            Edge<T> newEdge = new Edge<T>(cloneVertex, adjVertexClone, edge.isDirected(), edge.getWeight());
            cloneVertex.addAdjacentVertex(newEdge, adjVertexClone);
        }
    }
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