package graph;

import java.io.InputStream;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * Created by Paweł Kopeć on 23.12.16.
 *
 * Implementation of graph data structure
 * based on adjacency matrix.
 *
 * TODO
 * 1. Think of data structure for adjacency matrix
 * based on bit operations, not integers.
 * 2. Get rid of redundancies in adjacency matrix
 */
public class MatrixGraph extends Graph {

    private static final boolean CONNECTED = true;
    private static final boolean DISCONNECTED = false;

    private boolean[][] adjacencyMatrix;
    private int[] neighbourNumbers;

    public MatrixGraph() {
        super();
    }

    public MatrixGraph(int verticesNumber) {
        super(verticesNumber);
    }

    public MatrixGraph(InputStream in) {
        super(in);
    }

    public MatrixGraph(String string) {
        super(string);
    }

    @Override
    protected void initContainers(int verticesNumber, int edgesNumber) {
        adjacencyMatrix = new boolean[verticesNumber][verticesNumber];
        neighbourNumbers = new int[verticesNumber];
    }

    @Override
    public void addEdge(int from, int to) {
        validateEdge(from, to);

        adjacencyMatrix[from][to] = CONNECTED;
        neighbourNumbers[from]++;
        adjacencyMatrix[to][from] = CONNECTED;
        neighbourNumbers[to]++;
        edgesNumber++;
    }

    @Override
    public void removeEdge(int from, int to) {
        if(!hasEdge(from, to)) {
            throw new IllegalArgumentException(NO_SUCH_EDGE);
        }
        adjacencyMatrix[from][to] = DISCONNECTED;
        neighbourNumbers[from]--;
        adjacencyMatrix[to][from] = DISCONNECTED;
        neighbourNumbers[to]--;
        edgesNumber--;
    }

    @Override
    public LinkedList<Integer> getNeighbours(int index) {
        validateVertex(index);

        LinkedList<Integer> neighbours = new LinkedList<>();
        for(int i = 0; i < adjacencyMatrix[index].length; i++) {
            if(adjacencyMatrix[index][i] == CONNECTED) {
                neighbours.add(i);
            }
        }
        return neighbours;
    }

    @Override
    public int getNeighboursNumber(int index) {
        validateVertex(index);
        return neighbourNumbers[index];
    }

    @Override
    public boolean hasEdge(int from, int to) {
        validateEdge(from, to);
        return adjacencyMatrix[from][to] == CONNECTED;
    }

    @Override
    public void makeEmpty() {
        for(int i = 0; i < verticesNumber; i++) {
            for(int j = 0; j < verticesNumber; j++) {
                adjacencyMatrix[i][j] = DISCONNECTED;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder("").append(verticesNumber).append(" ");
        str.append(edgesNumber).append(" ");

        for(int i = 0; i < verticesNumber; i++) {
            for(int j = i + 1; j < verticesNumber; j++) {
                if (adjacencyMatrix[i][j] == CONNECTED) {
                    str.append(i).append(" ").append(j).append(" ");
                }
            }
        }

        return str.toString();
    }
}
@@ -54,25 +54,21 @@
 va.util.
-LinkedLis
+BitSe
 t;%0Aimpor
@@ -83,30 +83,18 @@
 til.
-NoSuchElementException
+LinkedList
 ;%0A%0A/
@@ -314,16 +314,49 @@
 tegers.%0A
+ * Update - Java BitSet will do.%0A
  * 2. Ge
@@ -566,19 +566,14 @@
 ate 
-boolean%5B%5D%5B%5D
+BitSet
  adj
@@ -1015,16 +1015,15 @@
 new 
-boolean%5B
+BitSet(
 vert
@@ -1032,18 +1032,17 @@
 esNumber
-%5D%5B
+*
 vertices
@@ -1043,25 +1043,25 @@
 rticesNumber
-%5D
+)
 ;%0A        ne
@@ -1227,65 +1227,99 @@
 trix
-%5Bfrom%5D%5Bto%5D = CONNECTED;%0A        neighbour
+.set(from * verticesNumber + to);%0A        adjacencyMatrix.set(to * vertices
 Number
-s%5B
+ + 
 from
-%5D++;
+);%0A
 %0A   
@@ -1327,45 +1327,32 @@
     
-adjacencyMatrix%5Bto%5D%5Bfrom%5D = CONNECTED
+neighbourNumbers%5Bfrom%5D++
 ;%0A  
@@ -1604,68 +1604,103 @@
 trix
-%5Bfrom%5D%5Bto%5D = DISCONNECTED;%0A        neighbour
+.clear(from * verticesNumber + to);%0A        adjacencyMatrix.clear(to * vertices
 Number
-s%5B
+ + 
 from
-%5D--;
+);%0A
 %0A   
@@ -1708,48 +1708,32 @@
     
-adjacencyMatrix%5Bto%5D%5Bfrom%5D = DISCONNECTED
+neighbourNumbers%5Bfrom%5D--
 ;%0A  
@@ -1988,37 +1988,22 @@
 i %3C 
-adjacencyMatrix%5Bindex%5D.length
+verticesNumber
 ; i+
@@ -2041,31 +2041,41 @@
 trix
-%5Bindex%5D%5Bi%5D == CONNECTED
+.get(index * verticesNumber + i) 
 ) %7B%0A
@@ -2434,31 +2434,40 @@
 trix
-%5Bfrom%5D%5Bto%5D == CONNECTED
+.get(from * verticesNumber + to)
 ;%0A  
@@ -2527,181 +2527,32 @@
     
-for(int i = 0; i %3C verticesNumber; i++) %7B%0A            for(int j = 0; j %3C verticesNumber; j++) %7B%0A                adjacencyMatrix%5Bi%5D%5Bj%5D = DISCONNECTED;%0A            %7D%0A        %7D
+adjacencyMatrix.clear();
 %0A   
@@ -2879,27 +2879,36 @@
 trix
-%5Bi%5D%5Bj%5D == CONNECTED
+.get(i * verticesNumber + j)
 ) %7B%0A

Change implementation of MatrixGraph.