Java assignment to use Dijkstras search method, breath-first and depth first

Question

Hello StackOverflow community, need your help. I have a final for my java class and its asking for: Generate a graph with 100,000 nodes, where each node randomly has between 1 and 5 connections to other nodes. Each node should contain within it a random value between 1 and 300,000. (So generally about 1 in 3 searches will yield a query match). Allow the user to enter a number to search for, and implement each of the following three types of searching algorithms. Breadth-First. (30 points) Depth-First. (30 points) Dijkstra's Algorithm. (40 points)

Do not allow back-tracking in your searches. (Mark nodes that you already searched as complete, and do not re-visit them in the same search). Each search should return the following: The Success/Failure of your search. The length of the shortest path to the found node. The total number of nodes examined during the search. Optionally you may return the exhaustive display of the shortest path, for testing and verification.

For some reason, my IDE shows that BFS and Dijkstras has "duplicated code fragment 17 lines long" can someone look at tell me how to fix it or maybe a better way to implement it? Also, if i try to do nodesNum > 30k in "Driver Class" i get a memory leak.

Here is the code:

Class Graph:

import java.util.*;
import javax.swing.JOptionPane;

class Graph
{
    private Listing[] vertex;
    private int[][] edge;
    private int max;
    private int numberOfVertices;
    private int nodeCheck = 0;
    private int selectNum = 0;

    Graph(int g)
    {
        vertex = new Listing[g];
        edge = new int[g][g];
        max = g;
        numberOfVertices = 0;
    }
    private void depthFirstSearch(int firstVertex)
    {
        int v;
        Stack<Integer> nodeStack = new Stack<>();

        for(int i = 0; i<numberOfVertices; i++)
        {
            if (vertex[i] != null) {
                vertex[i].setPushed(false);
            }
        }
        nodeStack.push(firstVertex);
        vertex[firstVertex].setPushed(true);

        while (!nodeStack.empty())
        {
            v = nodeStack.pop();
            vertex[v].visit();
            nodeCheck++;
            for (int column = 0; column < numberOfVertices; column++)
            {

                if(edge[v][column] == 1 && vertex[column].getPushed())
                {
                    nodeStack.push(column);
                    vertex[column].setPushed(true);
                }
            }
        }
    }
    private void breathFirstSearch(int firstVertex)
    {
        int V;
        Queue<Integer> nodeQueue = new LinkedList<>();

        for(int i = 0; i < numberOfVertices; i++)
        {
            if(vertex[i] != null)
                vertex[i].setPushed(false);
        }
        nodeQueue.add(firstVertex);
        vertex[firstVertex].setPushed(true);

        while(!nodeQueue.isEmpty())
        {
            V = nodeQueue.remove();
            vertex[V].visit();
            nodeCheck++;
            for(int column = 0; column < numberOfVertices; column++)
            {
                if(edge[V][column] == 1 && vertex[column].getPushed())
                {
                    nodeQueue.add(column);
                    vertex[column].setPushed(true);
                }
            }
        }
    }

    private void Dijkstra(int firstVertex)
    {
        int v;
        LinkedList<Integer> nodeQueue = new LinkedList<>();

        int i = 0;
        while (i < numberOfVertices)
        {
            if(vertex[i] != null)
                vertex[i].setPushed(false);
            i++;
        }
        nodeQueue.add(firstVertex);
        vertex[firstVertex].setPushed(true);

        while(!nodeQueue.isEmpty())
        {
            v = nodeQueue.remove();
            vertex[v].visit();
            nodeCheck++;
            for(int column = 0; column < numberOfVertices; column++)
            {
                if(edge[v][column] == 1 && vertex[column].getPushed())
                {
                    nodeQueue.add(column);
                    vertex[column].setPushed(true);
                }
            }
        }
    }

    private void insertVertex(int vertexNumber, Listing newListing)
    {
        if(vertexNumber >= max)
        {
            return;
        }
        vertex[vertexNumber] = newListing.deepCopy();
        numberOfVertices++;
    }

    private void insertEdge(int fromVertex, int toVertex)
    {
        if(vertex[fromVertex] == null || vertex[toVertex] == null)
            return;
        edge[fromVertex][toVertex] = 1;
    }

    void showVertex(int vertexNumber)
    {
        System.out.print(vertex[vertexNumber]);
    }

    void showEdges(int vertexNumber)
    {
        for(int column = 0; column < numberOfVertices; column++)
        {
            if(edge[vertexNumber][column] == 1)
            {
                System.out.println(vertexNumber + "," + column);
            }
        }
        System.out.println();
    }

    void InitializeNodes(Graph G, int nodesNum)
    {
        Random random = new Random();
        for (int i = 0; i < nodesNum; i++ )
        {
            Listing v = new Listing(random.nextInt(300000) + 1);
            G.insertVertex(i, v);
        }

        int vertexListNumber = G.vertex.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nodesNum; i++ )
        {
            list.add(i);
        }
        Collections.shuffle(list);
        for (int i = 0; i < vertexListNumber; i++ )
        {
            int randnum = random.nextInt(5);
            for (int j = 0; j < randnum; j++ )
            {
                int rand = random.nextInt(5);
                G.insertEdge(i, list.get(rand));
            }
        }

    }

    int Search()
    {
        String search = JOptionPane.showInputDialog("Enter Node to search:");
        try
        {
            if(search != null)
            {
                selectNum = Integer.parseInt(search);
            }
        }
        catch (NumberFormatException e)
        {
            selectNum = 0;
        }
        return selectNum;
    }

    private int SelectPane()
    {
        String paneSelect = JOptionPane.showInputDialog("Choose a search method:" +
                "\n\t1: Use Depth-First Search" +
                "\n\t2: Use Breadth-First Search" +
                "\n\t3: Use Dijkstra's Search" +
                "\n\t4: Close  Program");
        int selectNum = 0;

        try{
            if(paneSelect != null)
            {
                selectNum = Integer.parseInt(paneSelect);
            }
        }
        catch (NumberFormatException ignored)
        {
        }
        return selectNum;
    }

    void algorithmChoice(Graph graph, int vertexStart)
    {
        int paneNum = 0;
        while (paneNum != 4)
        {
            paneNum = SelectPane();
            switch (paneNum)
            {
                case 1:
                    graph.depthFirstSearch(vertexStart);
                    System.out.println("Nodes counted were: " + nodeCheck);
                    System.out.println("------------------------------------");
                    break;
                case 2:
                    graph.breathFirstSearch(vertexStart);
                    System.out.println("Nodes counted were: " + nodeCheck);
                    System.out.println("------------------------------------");
                    break;
                case 3:
                    graph.Dijkstra(vertexStart);
                    System.out.println("Nodes counted were: " + nodeCheck);
                    System.out.println("------------------------------------");
                    break;
                case 4:
                    break;
                default:
                    JOptionPane.showMessageDialog(null, "Enter 4 to quit.");
                    break;
            }
        }
    }


}

Class Listing:

public class Listing
{
    private int value;
    private boolean pushed;

    Listing(int v)
    {
        value = v;
    }
    public String toString()
    {
        return ("Vertex: " + value + "\n" );
    }

    Listing deepCopy()
    {
        return new Listing(value);
    }
    boolean getPushed()
    {
        return !pushed;
    }
    void setPushed(boolean value)
    {
        pushed = value;
    }
    void visit()
    {
        System.out.println(this);
    }
}

Class Driver:

public class Driver
{
    public static void main(String[] args)
    {
        int nodesNum = 30000; //Can go up to 30k nodes, otherwise causes memory leak.
        Graph graph = new Graph(nodesNum);
        graph.InitializeNodes(graph, nodesNum);

        for(int i = 0; i<5; i++)
        {
            System.out.print("Node " + i + "\'s ");
            graph.showVertex(i);
            System.out.print("Its routes are:\n");
            graph.showEdges(i);
        }

        int select = graph.Search();
        graph.algorithmChoice(graph, select);
    }
}

Thanks alot for your help!

Answer 1

The error you get is due to exceeding max heap size when creating a edge = new int[g][g]; where g can be as high as 100,000 in your case.
I would suggest avoiding the use of such huge matrix.
Instead introduce an Edge object :

class Edge{

    private final int fromVertex, toVertex;

    Edge(int fromVertex, int toVertex){
        this.fromVertex = fromVertex;
        this.toVertex = toVertex;
    }

    @Override
    public boolean equals(Object obj) {
        if( ! (obj instanceof Edge)) return false;
        Edge other = (Edge)obj;
        return connects(other.fromVertex, other.toVertex);
    }

    boolean connects(int fromVertex, int toVertex){
        return fromVertex == this.fromVertex && toVertex == this.toVertex ||
                    fromVertex == this.toVertex && toVertex == this.fromVertex;
    }
 }

and use it in Graph.
Instead of private int[][] edge; use a collection of Edges:
private final Set<Edge> edges = new HashSet<>(); Change insertEdge to:

private void insertEdge(int fromVertex, int toVertex)
{
    if(vertex[fromVertex] == null || vertex[toVertex] == null)
        return;
    edges.add(new Edge(fromVertex, toVertex));
}

and add a method to check if there is an edge between two vertices:

private boolean isEdgeBetween(int fromVertex, int toVertex)
{
    for(Edge edge : edges){
        if(edge.connects(fromVertex, toVertex)) return true;
    }

    return false;
}

Usage : if( isEdgeBetween(v,column) && vertex[column].getPushed())
instead of: if(edge[v][column] == 1 && vertex[column].getPushed())