I'm looking for code-review, optimization and best practices. Also verifying complexity to be O(E) time and O(V+E) space complexity.
final class NodeClone<T> {
private final T item;
NodeClone(T item) {
this.item = item;
}
public T getItem() {
return item;
}
}
final class EdgeClone<T> {
private final NodeClone<T> node1;
private final NodeClone<T> node2;
EdgeClone (NodeClone<T> node1, NodeClone<T> node2) {
this.node1 = node1;
this.node2 = node2;
}
public NodeClone<T> getNode1() {
return node1;
}
public NodeClone<T> getNode2() {
return node2;
}
}
public class CloneGraph<T> implements Iterable<NodeClone<T>> {
/*
* A map from nodes in the graph to list of outgoing edges.
*/
private final Map<NodeClone<T>, List<EdgeClone<T>>> graph;
public CloneGraph() {
graph = new HashMap<NodeClone<T>, List<EdgeClone<T>>>();
}
public CloneGraph(Map<NodeClone<T>, List<EdgeClone<T>>> graph) {
this.graph = graph;
}
/**
* Adds a new node to the graph. If the node already exists then its a
* no-op.
*
* @param node Adds to a graph. If node is null then this is a no-op.
* @return true if node is added, false otherwise.
*/
public boolean addNode(NodeClone<T> node) {
if (node == null) {
throw new NullPointerException("The input node cannot be null.");
}
if (graph.containsKey(node)) return false;
graph.put(node, new ArrayList<EdgeClone<T>>());
return true;
}
/**
* Given the two nodes it would add an arc from source
* to destination node.
*
* @param node1 the node1 node.
* @param node2 the node2 node.
* @param length if length if string
* @throws NullPointerException if node1 or nod2 is null.
* @throws NoSuchElementException if either node1 or node2 does not exists.
*/
public void addEdge (NodeClone<T> node1, NodeClone<T> node2) {
if (node1 == null || node2 == null) {
throw new NullPointerException("node1 and node2, both should be non-null.");
}
if (!graph.containsKey(node1) || !graph.containsKey(node2)) {
throw new NoSuchElementException("node1 and node2, both should be part of graph");
}
final EdgeClone<T> edgeClone = new EdgeClone<T>(node1, node2);
graph.get(node1).add(edgeClone);
graph.get(node2).add(edgeClone);
}
/**
* Removes an edge from the graph.
*
* @param node1 If the first node.
* @param node2 If the second node.
* @throws NullPointerException if either node1 or node2 specified is null
* @throws NoSuchElementException if graph does not contain either node1 or node2
*/
public void removeEdge (NodeClone<T> node1, NodeClone<T> node2) {
if (node1 == null || node2 == null) {
throw new NullPointerException("node1 and node2, both should be non-null.");
}
if (!graph.containsKey(node1) || !graph.containsKey(node2)) {
throw new NoSuchElementException("node1 and node2, both should be part of graph");
}
graph.get(node1).remove(node2);
}
/**
* Given a node, returns the edges going outward that node,
* as an immutable map.
*
* @param node The node whose edges should be queried.
* @return An immutable view of the edges leaving that node.
* @throws NullPointerException If input node is null.
* @throws NoSuchElementException If node is not in graph.
*/
public List<EdgeClone<T>> edgesFrom(NodeClone<T> node) {
if (node == null) {
throw new NullPointerException("The node should not be null.");
}
List<EdgeClone<T>> edges = graph.get(node);
if (edges == null) {
throw new NoSuchElementException("node does not exist.");
}
return Collections.unmodifiableList(edges);
}
@Override
public Iterator<NodeClone<T>> iterator() {
return graph.keySet().iterator();
}
public CloneGraph<T> clone() {
final Map<NodeClone<T>, List<EdgeClone<T>>> clonedGraph = new HashMap<NodeClone<T>, List<EdgeClone<T>>>();
for (Entry<NodeClone<T>, List<EdgeClone<T>>> entry : this.graph.entrySet()) {
final NodeClone<T> node = entry.getKey();
final List<EdgeClone<T>> edgeList = entry.getValue();
clonedGraph.put(new NodeClone<T>(node.getItem()), new ArrayList<EdgeClone<T>>(edgeList));
}
return new CloneGraph<T>(clonedGraph);
}
public static void main(String[] args) {
CloneGraph<Integer> graph = new CloneGraph<Integer>();
NodeClone<Integer> nodeA = new NodeClone<Integer>(1);
NodeClone<Integer> nodeB = new NodeClone<Integer>(2);
NodeClone<Integer> nodeC = new NodeClone<Integer>(3);
graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeA, nodeC);
CloneGraph<Integer> clonedGraph = graph.clone();
Iterator<NodeClone<Integer>> itr = clonedGraph.iterator();
while (itr.hasNext()) {
NodeClone<Integer> node = itr.next();
System.out.println("Item : " + node.getItem());
System.out.println("Edges: ");
for (EdgeClone<Integer> edge : clonedGraph.edgesFrom(node)) {
System.out.println(edge.getNode1().getItem() + " : " + edge.getNode2().getItem());
}
System.out.println();
}
}
}
