Teamex4/Graph.java at master · RainerYuan/Teamex4 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
///////////////////////////////////////////////////////////////////////////////
// assignment name: p4
// Author: Bowen Zhang
// Partner: Griff Zhang, Jichen Zhang, Junge Zhang, Tianyuan(Rainer) Yuan
// Email : bzhang296@wisc.edu
// due date: April 15th 2018
// CS Login: bowenz
// Credits: none
// known bugs: none
//////////////////////////////////////////////////////////////////////////////
import java.util.*;


/**
 * Undirected and unweighted graph implementation
 *
 * @param <E> type of a vertex
 *
 * @author sapan (sapan@cs.wisc.edu)
 *
 */
public class Graph<E> implements GraphADT<E> {

    /**
     * Instance variables and constructors
     */


	private HashMap<E,ArrayList<E>>dictionary;

	/**
	  * constructor for graph class
	  */
	public Graph() {
		dictionary=new HashMap<>();
	}


    /**
     * add vertex
     * parameter  E vertex
     * return null if duplicate or add null
     * otherwise add to arraylist
     */
    @Override
    public E addVertex(E vertex) {
        if (vertex == null || dictionary.containsKey(vertex)) {
            return null;
        } else {
            dictionary.put(vertex, new ArrayList<>());
            return vertex;
        }
    }

    /**
     * remove vertex
     * parameter E vertex
     * return null if vertex is null or arraylist does not have this vertex
     * else remove vertex from array list
     */
    @Override
    public E removeVertex(E vertex) {
        if (vertex == null || !dictionary.containsKey(vertex)) {
            return null;
        } else {
            for (E opposite : getNeighbors(vertex)) {
                dictionary.get(opposite).remove(vertex);
            }
            dictionary.remove(vertex);
            return vertex;
        }
    }

    /**
     * add Edge
     * parameter E vertex1,  E vertex2
     * return true if both vertices exist and are in array list
     * else return false
     */
    @Override
    public boolean addEdge(E vertex1, E vertex2) {
        if (vertex1 != null
                && vertex2 != null
                && vertex1 != vertex2
                && dictionary.containsKey(vertex1)
                && dictionary.containsKey(vertex2)) {
            dictionary.get(vertex1).add(vertex2);
            dictionary.get(vertex2).add(vertex1);
            return true;
        } else {
            return false;
        }
    }

    /**
     * remove edge
     * parameter E vertex1  E vertex2
     * return true if both vertices exist and are in the array list
     * and there is an edge between two vertices
     * else return false
     */
    @Override
    public boolean removeEdge(E vertex1, E vertex2) {
        if (vertex1 != null
                && vertex2 != null
                && vertex1 != vertex2
                && dictionary.containsKey(vertex1)
                && dictionary.containsKey(vertex2)
                && dictionary.get(vertex1).contains(vertex2)
                && dictionary.get(vertex2).contains(vertex1)) {
            dictionary.get(vertex1).remove(vertex2);
            dictionary.get(vertex2).remove(vertex1);
            return true;
        } else {
            return false;
        }

    }

    /**
     * Check whether the two vertices are adjacent
     * parameter vertex1  vertex2
     * return true if both the vertices have an edge with each other, else return false
     * if vertex1 and vertex2 are not connected (also if valid conditions are violated)
     */
    @Override
    public boolean isAdjacent(E vertex1, E vertex2) {
        if (vertex1 != null
                && vertex2 != null
                && vertex1 != vertex2
                && dictionary.containsKey(vertex1)
                && dictionary.containsKey(vertex2)) {
            return dictionary.get(vertex1).contains(vertex2) && dictionary.get(vertex2).contains(vertex1);
        } else {
            return false;
        }
    }

    /**
     * Get all the neighbor vertices of a vertex
     * parameter vertex
     * return  an iterable for all the immediate connected neighbor vertices
     */
    @Override
    public Iterable<E> getNeighbors(E vertex) {
        if (vertex != null && dictionary.containsKey(vertex)) {
            return dictionary.get(vertex);
        } else {
            return null;
        }
    }

    /**
     * Get all the vertices in the graph
     * @return an iterable for all the vertices
     */
    @Override
    public Iterable<E> getAllVertices() {
        return dictionary.keySet();
    }
}