public Graph<T> clone(Graph<T> graph){
        if(graph == null){
            return null;
        }
        if(!graph.isDirected){
            throw new IllegalArgumentException("Cloning non directed graph");
        }
        if(graph.getAllVertex().size() == 0){
            throw new IllegalArgumentException("No vertex in the graph");
        }
        Map<Vertex<T>,Vertex<T>> cloneMap = new HashMap<Vertex<T>,Vertex<T>>();
        for(Vertex<T> vertex : graph.getAllVertex()){
            clone(vertex,cloneMap);
        }
        Graph<T> clonedGraph = new Graph<>(true);
        for(Vertex<T> vertex : cloneMap.values()){
            clonedGraph.addVertex(vertex);
        }
        return clonedGraph;
    }
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