Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public boolean contractEdge(V vertex1, V vertex2) {
- //First makes sure that both vertices are in the graph.
- if (!adjList.containsKey(vertex1) || !adjList.containsKey(vertex2))
- return false;
- //Then makes sure there is at least one edge between them.
- if (this.getEdge(vertex1, vertex2) != -1 ||
- this.getEdge(vertex2, vertex1) != -1) {
- //This checks to see which vertex is bigger.
- if (vertex1.compareTo(vertex2) < 0) {
- //The following for each loops handles the outgoing, then the
- //incoming edges for the vertices.
- for (V v : adjList.get(vertex2).keySet()) {
- //This if statement prevents the method from adding a self
- //reference.
- if (v.compareTo(vertex1) != 0) {
- //The next if statement picks the larger of the two
- //edges, if there are two of them present.
- if (this.getEdge(vertex2, v) >
- this.getEdge(vertex1, v)) {
- this.addEdge(vertex1, v, this.getEdge(vertex2, v));
- } else {
- this.addEdge(vertex1, v, this.getEdge(vertex1, v));
- }
- }
- }
- //Incoming block:
- for (V v : adjList.keySet()) {
- //If block to prevent self reference.
- if (adjList.get(v).keySet().contains(vertex2) &&
- v.compareTo(vertex1) != 0) {
- //If statement that checks the edge sizes to find the
- //larger of the two.
- if (this.getEdge(v, vertex2) >
- this.getEdge(v, vertex1)) {
- this.addEdge(v, vertex1, this.getEdge(v, vertex2));
- } else {
- this.addEdge(v, vertex1, this.getEdge(v, vertex1));
- }
- }
- }
- //Removes the smaller of the two parameter vertices and
- //returns true.
- this.removeVertex(vertex2);
- return true;
- } else {
- //These two for each loops handle the vertices if vertex2 is
- //larger than vertex1. It works in exactly the same way as
- //above, except the vertices are switched around.
- for (V v : adjList.get(vertex1).keySet()) {
- if (v.compareTo(vertex2) != 0) {
- if (this.getEdge(vertex1, v) >
- this.getEdge(vertex2, v)) {
- this.addEdge(vertex2, v, this.getEdge(vertex1, v));
- } else {
- this.addEdge(vertex2, v, this.getEdge(vertex2, v));
- }
- }
- }
- for (V v : adjList.keySet()) {
- if (adjList.get(v).keySet().contains(vertex1) &&
- v.compareTo(vertex2) != 0) {
- if (this.getEdge(v, vertex1) >
- this.getEdge(v, vertex2)) {
- this.addEdge(v, vertex2, this.getEdge(v, vertex1));
- } else {
- this.addEdge(v, vertex2, this.getEdge(v, vertex2));
- }
- }
- }
- this.removeVertex(vertex1);
- return true;
- }
- }
- //Final return false statement.
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement