| 1 | /* |
| 2 | �*�$Id:�AdjacencyList.java�5865�2005-10-25�21:02:06Z�dfs�$ |
| 3 | �* |
| 4 | �*�Copyright�2004�Daniel�F.�Savarese |
| 5 | �*�Copyright�2005�Savarese�Software�Research |
| 6 | �* |
| 7 | �*�Licensed�under�the�Apache�License,�Version�2.0�(the�"License"); |
| 8 | �*�you�may�not�use�this�file�except�in�compliance�with�the�License. |
| 9 | �*�You�may�obtain�a�copy�of�the�License�at |
| 10 | �* |
| 11 | �*�����https://www.savarese.com/software/ApacheLicense-2.0 |
| 12 | �* |
| 13 | �*�Unless�required�by�applicable�law�or�agreed�to�in�writing,�software |
| 14 | �*�distributed�under�the�License�is�distributed�on�an�"AS�IS"�BASIS, |
| 15 | �*�WITHOUT�WARRANTIES�OR�CONDITIONS�OF�ANY�KIND,�either�express�or�implied. |
| 16 | �*�See�the�License�for�the�specific�language�governing�permissions�and |
| 17 | �*�limitations�under�the�License. |
| 18 | �*/ |
| 19 | � |
| 20 | package�com.savarese.algorithms.graph; |
| 21 | � |
| 22 | import�java.util.*; |
| 23 | � |
| 24 | /** |
| 25 | �*�An�AdjacencyList�represents�a�graph�by�mapping�a�set�of�vertices�to |
| 26 | �*�the�set�of�{@link�Edge�edges}�emanating�from�each�vertex. |
| 27 | �* |
| 28 | �*�@author�<a�href="https://www.savarese.com/">Daniel�F.�Savarese</a> |
| 29 | �*/ |
| 30 | � |
| 31 | public�class�AdjacencyList<V,�E�extends�Edge<V,�?>> |
| 32 | ��implements�Graph<V,�E> |
| 33 | { |
| 34 | � |
| 35 | ��private�HashMap<V,�HashSet<E>>�__map; |
| 36 | � |
| 37 | ��/** |
| 38 | ���*�Creates�an�empty�adjacency�list. |
| 39 | ���*/ |
| 40 | ��public�AdjacencyList()�{ |
| 41 | ����__map�=�new�HashMap<V,�HashSet<E>>(); |
| 42 | ��} |
| 43 | � |
| 44 | � |
| 45 | ��/** |
| 46 | ���*�Adds�a�vertex�to�the�graph�if�the�vertex�is�not�already |
| 47 | ���*�contained�in�the�graph.��If�it�is�not�in�the�graph,�an |
| 48 | ���*�empty�edge�set�is�initialized. |
| 49 | ���* |
| 50 | ���*�@param�vertex�The�vertex�to�add. |
| 51 | ���*�@return�The�set�of�edges�emanating�from�the�vertex. |
| 52 | ���*/ |
| 53 | ��private�Set<E>�__addVertex(V�vertex)�{ |
| 54 | ����HashSet<E>�edges�=�__map.get(vertex); |
| 55 | � |
| 56 | ����if(edges�==�null)�{ |
| 57 | ������edges�=�new�HashSet<E>(); |
| 58 | ������__map.put(vertex,�edges); |
| 59 | ����} |
| 60 | � |
| 61 | ����return�edges; |
| 62 | ��} |
| 63 | � |
| 64 | � |
| 65 | ��public�void�add(E�edge)�{ |
| 66 | ����__addVertex(edge.getSource()).add(edge); |
| 67 | ����addVertex(edge.getDestination()); |
| 68 | ��} |
| 69 | � |
| 70 | � |
| 71 | ��public�void�addVertex(V�vertex)�{ |
| 72 | ����__addVertex(vertex); |
| 73 | ��} |
| 74 | � |
| 75 | � |
| 76 | ��public�void�clear()�{ |
| 77 | ����__map.clear(); |
| 78 | ��} |
| 79 | � |
| 80 | � |
| 81 | ��public�Set<E>�edgeSet(V�v)�{ |
| 82 | ����Set<E>�edges�=�__map.get(v); |
| 83 | � |
| 84 | ����if(edges�==�null) |
| 85 | ������return�null; |
| 86 | � |
| 87 | ����return�edges; |
| 88 | ��} |
| 89 | � |
| 90 | � |
| 91 | ��public�int�size()�{ |
| 92 | ����return�__map.size(); |
| 93 | ��} |
| 94 | � |
| 95 | � |
| 96 | ��public�Set<V>�vertexSet()�{ |
| 97 | ����return�__map.keySet(); |
| 98 | ��} |
| 99 | } |
