import java.util.$*$;

$//$ Name: Yerim Cho

$/*$

$*$ We will use an Integer type to represent each node's ID$.$

$*/$

public class HW$10$ implements Connectable $\{$

HashMap$>$ nodes;

int numEdge $=0$;

public HW$10()\{$

nodes $=$ new HashMap$>()$;

$\}$

@Override

public Set nodeSet$()\{//$ return the set of nodes

if $($nodes$.$size$()<=0)\{//$ if the graph is empty. no nodes to return.

Set set $=$ new HashSet$<>()$; $//$ just return the empty set.

return set;

$\}$

return nodes.keySet$()$;

$\}$

@Override

public Set getNeighbors$($int node$)\{//$ return the set of neighbors connected to 'node'

if $($nodes$.$containsKey$($node$))\{$

return nodes.get$($node$).$keySet$()$;

$\}$

throw new NoSuchElementException$("$There is no such node."$)$;

$\}$

@Override

public Iterator breadthFirstIterator$($int src$)\{//$ return the iterator on nodes in a breadth$-$first manner

ArrayList result $=$ new ArrayList$()$;

if $($nodes$.$size$()==0)$ return result.iterator$()$;

Iterator itr $=$ nodeSet$().$iterator$()$;

Stack visited $=$ new Stack$()$;

Queue q $=$ new LinkedList$()$;

q$.$add$($nodeSet$().$iterator$().$next$())$;

itr $=$ nodeSet$().$iterator$()$;

while $(!$q$.$isEmpty$())\{$

int element $=$ q$.$poll$()$;

visited.push$($element$)$;

result.add$($element$)$;

Iterator neighbor $=$ getNeighbors$($element$).$iterator$()$;

while $($getNeighbors$($element$)!=$ null$)\{$

while $($neighbor$.$hasNext$())\{$

int neigh $=$ neighbor.next$()$;

if $(!$visited.contains$($neigh$))\{$

visited.push$($neigh$)$;

result.add$($neigh$)$;

$\}$

$\}$

$\}$

$\}$

return result.iterator$()$;

$\}$

@Override

public Iterator depthFirstIterator$($int src$)\{//$ same as above in a depth$-$first manner $//$stack

ArrayList result $=$ new ArrayList$()$;

if $($nodes$.$size$()==0)$ return result.iterator$()$;

Iterator itr $=$ nodeSet$().$iterator$()$;

Stack visited $=$ new Stack$()$;

Stack s $=$ new Stack$()$;

itr $=$ nodeSet$().$iterator$()$;

s$.$push$($itr$.$next$())$;

while $(!$s$.$empty$())\{$

int element $=$ s$.$pop$()$;

visited.push$($element$)$;

result.add$($element$)$;

Iterator neighbor $=$ getNeighbors$($element$).$iterator$()$;

while $($neighbor$.$hasNext$())\{$

int neigh $=$ neighbor.next$()$;

if $(!$visited.contains$($neigh$))\{$

visited.push$($neigh$)$;

result.add$($neigh$)$;

$\}$

$\}$

$\}$

return result.iterator$()$;

$\}$

@Override

public void addNode$($int node$)\{//$ add a new vertex into the current graph.

if $(!$ nodes.containsKey$($node$))\{$

HashMap neighbor $=$ new HashMap$()$;

neighbor.put$($node$,0\mathrm{.}0)$; $//$ make the node. the weight is zero since the node is linked with itself.

nodes.put$($node$,$ neighbor$)$;

$\}$

return;

$\}$

@Override

public boolean addEdge$($int source, int target, double w$)\{//$ add a new edge. also add non$-$existing nodes. return false if edge already exists.

if $(!$isEdge$($source$,$ target$))$ return false;

$//$ check whether the source vertex exits in the HashMap nodes.

else $\{$

numEdge$++$;

Iterator nodeSet $=$ nodeSet$().$iterator$()$;

boolean exist $=$ false;

while $($nodeSet$.$hasNext$())\{$

if $($source $==$ nodeSet.next$())\{$

exist $=$ true;

break;

$\}$

$\}$

if $($exist $==$ false$)$ addNode$($source$)$;

nodeSet $=$ nodeSet$().$iterator$()$;

exist $=$ false;

while $($nodeSet$.$hasNext$())\{$

if $($target $==$ nodeSet.next$())\{$

exist $=$ true;

break;

$\}$

$\}$

if $($exist $==$ false$)$ addNode$($target$)$;

HashMap neighbor $=$ nodes.get$($source$)$;

neighbor.put$($target$,$ w$)$;

nodes.put$($source$,$ neighbor$)$;

neighbor $=$ nodes.get$($target$)$;

neighbor.put$($source$,$ w$)$;

nodes.put$($target$,$ neighbor$)$;

return true;

$\}$

$\}$

@Override

public boolean removeNode$($int node$)\{//$ remove node. return false if node doesn't exist.

boolean exist $=$ false;

Iterator nodeSet $=$ nodeSet$().$iterator$()$;

while $($nodeSet$.$hasNext$())\{$

if $($node $==$ nodeSet.next$())\{$

exist $=$ true;

nodes.remove$($node$)$;

break;