Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package exercise3;
- import java.util.ArrayList;
- import java.util.Iterator;
- import java.util.List;
- public class AdjacencyMatrixGraph<V, E> implements Graph<V, E> {
- private List<Vertex<V>> vertices; //the vertices of the graph
- private List<Edge<E>> edges; //the edges of the graph
- private int vertexNo;
- public AdjacencyMatrixGraph() {
- vertices = new ArrayList<Vertex<V>>();
- edges = new ArrayList<Edge<E>>();
- vertexNo = 0;
- }
- @Override
- public Iterator<Vertex<V>> adjacentVertices(Vertex<V> v) {
- Iterator<Edge<E>> it = incidentEdges(v);
- ArrayList<Vertex<V>> vertices = new ArrayList<Vertex<V>>();
- while (it.hasNext()) {
- ELEdge e = (ELEdge) it.next();
- Vertex<V> vertex = e.getEndpoint1().equals((ELVertex) v) ? e.getEndpoint2() : e.getEndpoint1();
- vertices.add(vertex);
- }
- return vertices.iterator();
- }
- @Override
- public boolean areAdjacent(Vertex<V> v, Vertex<V> w) {
- ELVertex v1 = check(v);
- ELVertex v2 = check(w);
- int[] numbers = indexes(v1.getNumber(), v2.getNumber());
- if (edges.get(numbers[1] * (numbers[0] + 1)) != null) {
- return true;
- }
- return false;
- }
- @Override
- public int degree(Vertex<V> v) {
- Iterator<Edge<E>> it = incidentEdges((ELVertex) v);
- int count = 0;
- while (it.hasNext()) {
- it.next();
- count++;
- }
- return count;
- }
- @Override
- public Iterator<Edge<E>> edges() {
- return edges.iterator();
- }
- @Override
- public Vertex<V>[] endVertices(Edge<E> e) {
- Vertex<V>[] vertices = new Vertex[2];
- ELEdge edge = check(e);
- vertices[0] = edge.getEndpoint1();
- vertices[1] = edge.getEndpoint2();
- return vertices;
- }
- @Override
- public Iterator<Edge<E>> incidentEdges(Vertex<V> v) {
- ArrayList<Edge<E>> incidents = new ArrayList<Edge<E>>();
- ELVertex v1 = check(v);
- for (Vertex<V> vertex : vertices) {
- ELVertex v2 = (ELVertex) vertex;
- int[] numbers = indexes(v1.getNumber(), v2.getNumber());
- if (edges.get(numbers[1] * (numbers[0] + 1)) != null) {
- incidents.add(edges.get(numbers[1] * (numbers[0] + 1)));
- }
- }
- return incidents.iterator();
- }
- private int[] indexes(int n1, int n2) {
- int[] out = new int[2];
- if (n1 > n2) {
- out[0] = n2;
- out[1] = n1;
- }
- else if (n1 < n2) {
- out[0] = n1;
- out[1] = n2;
- }
- else {
- out[0] = n1;
- out[1] = n2;
- }
- return out;
- }
- @Override
- public Edge<E> insertEdge(Vertex<V> v, Vertex<V> w, E element) {
- ELVertex v1 = check(v);
- ELVertex v2 = check(w);
- int[] numbers = indexes(v1.getNumber(), v2.getNumber());
- ELEdge edge = new ELEdge(element, v1, v2);
- edges.add(numbers[1] * (numbers[0] + 1), edge);
- v1.incNumIncidentEdges();
- v2.incNumIncidentEdges();
- return edge;
- }
- @Override
- public Vertex<V> insertVertex(V element) {
- ELVertex v = new ELVertex(element);
- vertices.add(v);
- return v;
- }
- @Override
- public int numEdges() {
- return edges.size();
- }
- @Override
- public int numVertices() {
- return vertices.size();
- }
- @Override
- public Vertex<V> opposite(Vertex<V> v, Edge<E> e) {
- ELVertex v1 = check(v);
- ELEdge edge = check(e);
- return edge.getEndpoint1().equals(v1) ? check(edge.getEndpoint2()) : check(edge.getEndpoint1());
- }
- @Override
- public void removeEdge(Edge<E> e) {
- edges.remove(e);
- }
- @Override
- public void removeVertex(Vertex<V> v) {
- vertices.remove(v);
- }
- @Override
- public Iterator<Vertex<V>> vertices() {
- return vertices.iterator();
- }
- private ELVertex check(Vertex<V> v)
- {
- if (v == null)
- throw new RuntimeException("Vertex can't be null.");
- else if (!(v instanceof AdjacencyMatrixGraph.ELVertex))
- throw new RuntimeException("Vertex is not of the right type.");
- return (ELVertex) v;
- }
- private ELEdge check(Edge<E> e)
- {
- if (e == null)
- throw new RuntimeException("Edge can't be null.");
- else if (!(e instanceof AdjacencyMatrixGraph.ELEdge))
- throw new RuntimeException("Edge is not of the right type.");
- return (ELEdge) e;
- }
- private class ELEdge implements Edge<E> {
- private E element;
- private ELVertex endPoint1; //the vertex at one end of the edge
- private ELVertex endPoint2; //the vertex at the other end of the edge
- public ELEdge(E element, ELVertex v1, ELVertex v2)
- {
- this.element = element;
- endPoint1 = v1;
- endPoint2 = v2;
- }
- @Override
- public E element()
- {
- return element;
- }
- public ELVertex getEndpoint1()
- {
- return endPoint1;
- }
- public ELVertex getEndpoint2()
- {
- return endPoint2;
- }
- }
- private class ELVertex implements Vertex<V>
- {
- private V element;
- private int numIncidentEdges; //count of edges incident to this vertex
- int number;
- public ELVertex(V element)
- {
- this.element = element;
- numIncidentEdges = 0;
- number = vertexNo;
- vertexNo++;
- }
- @Override
- public V element()
- {
- return element;
- }
- public int getNumber() {
- return number;
- }
- public int getNumIncidentEdges()
- {
- return numIncidentEdges;
- }
- public void incNumIncidentEdges()
- {
- numIncidentEdges++;
- }
- public void decNumIncidentEdges()
- {
- numIncidentEdges--;
- }
- @Override
- public String toString()
- {
- return element.toString();
- }
- }
- }
Add Comment
Please, Sign In to add comment