package edu.desu.graphs;

import java.util.Arrays;

import java.util.LinkedList;

public class DSUGraph $\{$

$//$ No$.$ of vertices

private final int vertices;

private final int$[][]$ adjacencyMatrix;

$//$ adjacencyList

private final LinkedList$[]$ adjacencyList;

public boolean isConnected$()\{$

return isConnected;

$\}$

public boolean isDirected$()\{$

return isDirected;

$\}$

private final boolean isConnected;

private final boolean isDirected;

$//$ Constructor, for every node in the graph, create a list to represent adjacent nodes

@SuppressWarnings$("$unchecked$")$

DSUGraph$($int numOfVertices, boolean connected, boolean directed$)\{$

isDirected $=$ directed;

isConnected $=$ connected;

vertices $=$ numOfVertices $+1$;

adjacencyList $=$ new LinkedList$[$vertices$]$;

for $($int i $=0$; i $<$ vertices; $++$i$)$

adjacencyList$[$i$]=$ new LinkedList$<>()$;

adjacencyMatrix $=$ new int$[$vertices$][$vertices$]$;

for $($int i $=0$; i $<$ vertices; i$++)\{$

for $($int j $=0$; j $<$ vertices; j$++)\{$

adjacencyMatrix$[$i$][$j$]=0$;

$\}$

$\}$

$\}$

$//$ Function to add an edge into the graph

public void addEdge$($int source, int destination$)\{$

$//$Add edge for Adjacency list

adjacencyList$[$source$].$add$($destination$)$;

$//$Add Edge for Matrix

adjacencyMatrix$[$source$][$destination$]=1$;

if$(!$isDirected$)\{$

adjacencyList$[$destination$].$add$($source$)$;

adjacencyMatrix$[$destination$][$source$]=1$;

$\}$

$\}$

$/*$

Hack method because the indexes are not aligned with the actual value in the array

$*/$

public int rowSum$($int$[]$ arr, int n$)$

$\{$

$//$ base or terminating condition

if $($n $<=0)\{$

return $0$;

$\}$

$//$ Calling method recursively

return rowSum$($arr$,$ n $-1)+$ arr$[$n $-1]$;

$\}$

public void print$()\{$

$//$ Loop through Matrix and print all rows

System.out.println$("*****************$ MATRIX $**************************")$;

for $($int$[]$ row : adjacencyMatrix$)\{$

final int value $=$ rowSum$($row$,$ row.length$)$;

if$($value $>0)\{$

$//$ converting each row as string and then printing in a separate line

System.out.println$($Arrays$.$toString$($row$))$;

$\}$

$\}$

System.out.println$("$

$")$;

System.out.println$("*****************$ LIST $**************************")$;

$//$ Loop through List and Print values

for $($int i $=0$; i $<$ vertices; i$++)\{$

if$(!$adjacencyList$[$i$].$isEmpty$())\{$

System.out.print$($i$+"->")$;

for $($int x : adjacencyList$[$i$])\{$

System.out.print$($x$+"")$;

$\}$

$\}$

System.out.println$()$;

$\}$

$\}$

public int getVertices$()\{$

return vertices;

$\}$

public int$[][]$ getAdjacencyMatrix$()\{$

return adjacencyMatrix;

$\}$

public LinkedList$[]$ getAdjacencyList$()\{$

return adjacencyList;

$\}$

public int inDegree$($int i$)\{$

$//$YOU MUST IMPLEMENT THIS METHOD

return $0$;

$\}$

public int outDegree$($int i$)\{$

$//$YOU MUST IMPLEMENT THIS METHOD

return $0$;

$\}$

$\}$