#### Matrix Graphs

d
package com.thealgorithms.datastructures.graphs;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
* Implementation of a graph in a matrix form Also known as an adjacency matrix
*
* @author Unknown
*/
public final class MatrixGraphs {
private MatrixGraphs() {
}

public static void main(String[] args) {
System.out.println("The graph matrix:");
System.out.println(graph);
System.out.println("Depth first order beginning at node '1':");
System.out.println(graph.depthFirstOrder(1));
System.out.println("Breadth first order beginning at node '1':");
}
}

/**
*/

/**
* The number of vertices in the graph
*/
private int _numberOfVertices;

/**
* The number of edges in the graph
*/
private int _numberOfEdges;

/**
* The adjacency matrix for the graph
*/

/**
* Static variables to define whether or not an edge exists in the adjacency
* matrix
*/
static final int EDGE_EXIST = 1;
static final int EDGE_NONE = 0;

/**
* Constructor
*/
this.setNumberOfVertices(givenNumberOfVertices);
this.setNumberOfEdges(0);
for (int i = 0; i < givenNumberOfVertices; i++) {
for (int j = 0; j < givenNumberOfVertices; j++) {
}
}
}

/**
* Updates the number of vertices in the graph
*
* @param newNumberOfVertices the new number of vertices
*/
private void setNumberOfVertices(int newNumberOfVertices) {
this._numberOfVertices = newNumberOfVertices;
}

/**
* Getter for `this._numberOfVertices`
*
* @return the number of vertices in the graph
*/
public int numberOfVertices() {
return this._numberOfVertices;
}

/**
* Updates the number of edges in the graph
*
* @param newNumberOfEdges
*
*/
private void setNumberOfEdges(int newNumberOfEdges) {
this._numberOfEdges = newNumberOfEdges;
}

/**
* Getter for `this._numberOfEdges`
*
* @return the number of edges
*/
public int numberOfEdges() {
return this._numberOfEdges;
}

/**
* Sets a new matrix as the adjacency matrix
*
*/
}

/**
* Getter for the adjacency matrix
*
*/
}

/**
* Checks if two vertices are connected by an edge
*
* @param from the parent vertex to check for adjacency
* @param to the child vertex to check for adjacency
* @return whether or not the vertices are adjancent
*/
private boolean adjacencyOfEdgeDoesExist(int from, int to) {
}

/**
* Checks if a particular vertex exists in a graph
*
* @param aVertex the vertex to check for existence
* @return whether or not the vertex exists
*/
public boolean vertexDoesExist(int aVertex) {
return aVertex >= 0 && aVertex < this.numberOfVertices();
}

/**
* Checks if two vertices are connected by an edge
*
* @param from the parent vertex to check for adjacency
* @param to the child vertex to check for adjacency
* @return whether or not the vertices are adjancent
*/
public boolean edgeDoesExist(int from, int to) {
if (this.vertexDoesExist(from) && this.vertexDoesExist(to)) {
}

return false;
}

/**
* This method adds an edge to the graph between two specified vertices
*
* @param from the data of the vertex the edge is from
* @param to the data of the vertex the edge is going to
* @return returns true if the edge did not exist, return false if it
*/
public boolean addEdge(int from, int to) {
if (this.vertexDoesExist(from) && this.vertexDoesExist(to)) {
this.setNumberOfEdges(this.numberOfEdges() + 1);
return true;
}
}

return false;
}

/**
* this method removes an edge from the graph between two specified vertices
*
* @param from the data of the vertex the edge is from
* @param to the data of the vertex the edge is going to
* @return returns false if the edge doesn't exist, returns true if the edge
* exists and is removed
*/
public boolean removeEdge(int from, int to) {
if (!this.vertexDoesExist(from) || !this.vertexDoesExist(to)) {
this.setNumberOfEdges(this.numberOfEdges() - 1);
return true;
}
}
return false;
}

/**
* This method returns a list of the vertices in a depth first order
* beginning with the specified vertex
*
* @param startVertex the vertex to begin the traversal
* @return the list of the ordered vertices
*/
public List<Integer> depthFirstOrder(int startVertex) {
// If the startVertex is invalid, return an empty list
if (startVertex >= _numberOfVertices || startVertex < 0) {
return new ArrayList<Integer>();
}

// Create an array to track the visited vertices
boolean[] visited = new boolean[_numberOfVertices];

// Create a list to keep track of the order of our traversal
ArrayList<Integer> orderList = new ArrayList<Integer>();

// Perform our DFS algorithm
depthFirstOrder(startVertex, visited, orderList);

return orderList;
}

/**
* Helper method for public depthFirstOrder(int) that will perform a depth
* first traversal recursively on the graph
*
* @param currentVertex the currently exploring vertex
* @param visited the array of values denoting whether or not that vertex
* has been visited
* @param orderList the list to add vertices to as they are visited
*/
private void depthFirstOrder(int currentVertex, boolean[] visited, List<Integer> orderList) {
// If this vertex has already been visited, do nothing and return
if (visited[currentVertex]) {
return;
}

// Visit the currentVertex by marking it as visited and adding it
// to the orderList
visited[currentVertex] = true;

// Get the adjacency array for this vertex
for (int i = 0; i < adjacent.length; i++) { // we are considering exploring, recurse on it // If an edge exists between the
// currentVertex and the vertex
depthFirstOrder(i, visited, orderList);
}
}
}

/**
* This method returns a list of the vertices in a breadth first order
* beginning with the specified vertex
*
* @param startVertex the vertext to begin the traversal
* @return the list of the ordered vertices
*/
// If the specified startVertex is invalid, return an empty list
if (startVertex >= _numberOfVertices || startVertex < 0) {
return new ArrayList<Integer>();
}

// Create an array to keep track of the visited vertices
boolean[] visited = new boolean[_numberOfVertices];

// Create a list to keep track of the ordered vertices
ArrayList<Integer> orderList = new ArrayList<Integer>();

// Create a queue for our BFS algorithm and add the startVertex
// to the queue

// Continue until the queue is empty
while (!queue.isEmpty()) {
// Remove the first vertex in the queue
int currentVertex = queue.poll();

// If we've visited this vertex, skip it
if (visited[currentVertex]) {
continue;
}

// We now visit this vertex by adding it to the orderList and
// marking it as visited
visited[currentVertex] = true;

// Get the adjacency array for the currentVertex and
// check each node
for (int vertex = 0; vertex < adjacent.length; vertex++) { // vertex we are considering exploring, we add it to the queue // If an
// edge exists between the current vertex and the
}
}
}

return orderList;
}

/**
* this gives a list of vertices in the graph and their adjacencies
*
* @return returns a string describing this graph
*/
public String toString() {
String s = "    ";
for (int i = 0; i < this.numberOfVertices(); i++) {
s = s + i + " ";
}
s = s + " \n";

for (int i = 0; i < this.numberOfVertices(); i++) {
s = s + i + " : ";
for (int j = 0; j < this.numberOfVertices(); j++) {
s = s + this._adjacency[i][j] + " ";
}
s = s + "\n";
}
return s;
}
}