I'm implementing a Graph in Java.

The Graph class uses a LinkedList for the vertices. And each vertex also contains a LinkedList of adjacent vertices.

I'm still working on my methods. I just need a quick clarification with a getVertex() method which accepts a String label and returns a Vertex that matches that label.

public class Graph
{
    private class Vertex
    {
        private String label;
        private LinkedList links; 
        private boolean visited; 
        
        Vertex(String label)
        {
            this.label = label; 
            LinkedList links = new LinkedList(); 
            visited = false; 
        }

        private void addEdge(Vertex vertex)
        {
            links.insertLast(vertex); 
        }

        private String getLabel()
        {
            return label; 
        }

        private LinkedList getAdjacent()
        {
            return links; 
        }

        private boolean isVisited()
        {
            return visited; 
        }

        private void visit()
        {
            visited = true; 
        }
 
        private void unvisit()
        {
            visited = false; 
        }
    }

    /* Classfields for Graph Class */   
    private LinkedList vertices; //Linked List for the vertices in the graph
    private int vCount; 
    private int eCount; 

    public Graph()
    { 
        LinkedList vertices = new LinkedList(); 
        vCount = 0; 
        eCount = 0; 
    } 

    public void addVertex(String label)
    {
        Vertex newVertex = new Vertex(label); 
        vertices.insertLast(newVertex);
        vCount  ; 
    }

    public int getVertexCount()
    {
        return vCount; 
    }

    public Vertex getVertex(String label)
    {
        // what to return? 
    }

It should be very simple, but I can't understand how I'm going to import this label but return a Vertex, working with a LinkedList. Would appreciate any tips!

CodePudding user response：

If you are working on assignment on an assignment, and you are expected to use LinkedList that's fine, but it's the best choice of collection that serves as a storage of all vertices in the graph and also as the adjacency list of vertex

I suggest you addressing these issues:

• Firstly, don't use row types LinkedList links, you should always specify a generic type parameter List<Vertex>.
• Write your code against interfaces, not against implementations. I.e. use List<Vertex> instead of LinkedList<Vertex>. It makes your code more flexible.
• In order to be able to retrieve a particular vertex by label, you can use a Map<String, Vertex> to store all vertices of the graph. With that time complexity of the getVertex() will be reduced to constant time, it's way faster than iterate over the list. And the code is a single line vertexByLabel.get(label).
• Maintaining a variable that hold a count of vertices is redundant because you can check the size of collection of vertices to get this value.
• ArrayList performs than LinkedList and has a better memory consumption. For that reason, it considered to be a general purpose implementation of the List interface and it's a preferred choice if you don't expect use cases like removal of elements by the means of Iterator while iterating over the list (which will be done in constant time, here LinkedList really shines). Also, HashSet might be useful in a role of the collection of adjacencent vertices because it will all you to ensure that there will be no duplicates.

So in regard to getVertex() method, if you'll agree with the suggestion to use map, the code will look like this:

private Map<String, Vertex> vertexByLabel = new HashMap<>(); // it is advisable to initialise collections, if you are not passing argument with collection that holds values to the constructor, but just assigning a new collection

public Vertex getVertex(String label) {
   return vertexByLabel.get(label);
}

I also advise you to make changes to the methods addVertex() and addEdge(). Firstly, I would rather expect to a method called addVertex() inside the Vertex class (we are adding a new vertex to the adjacency list of this vertex) and a method addEdge() inside the Graph (we are connecting vertices inside the graph).

And if order to connect the vertices method addEdge() of the graph will expect a vertex label as its first argument, and labes of the adjacent vertices as a variable arity argument (varargs).

In case if you have a strong requirement to utilize LinkedLinked exclusively and not allowed to use generic types. But frankly spiking, it doesn't seem a bright idea to disallow student to use generics. It doesn't reduce complexity a lot because instead you have to deal with manual down-casts, and it's a very bad practice.

Your method might look like this:

public Vertex getVertex(String label) {
    Vertex result = null;
    for (Object next: vertices) { // all elements in the collection of row type a treated by the compiler as being of type Object
        Vertex vertex = (Vertex) next; // you need to cast the element into the Vertex type in order to be able to access its field `label`
        if (vertex.label.equals(label)) {
            result = vertex;
            break;
        }
    }
    return result;
}