4
\$\begingroup\$

I am learning graph theory and I have implemented a Directed Graph with weights in Java. My next objective with this class is to learn more about algorithms like Dijkstra, Bellman-Ford, etc. I have split the implementation into two classes - GraphNode and DirectedGraphWithWeights.

GraphNode.java

public class GraphNode {
    private int nodeValue;
    private Integer weight = Integer.MAX_VALUE;

    GraphNode(int nodeValue) {
        this.nodeValue = nodeValue;
    }

    public int getNodeValue() {
        return this.nodeValue;
    }

    public Integer getWeight() {
        return this.weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public int hashCode() {
        return new Integer(this.nodeValue).hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        GraphNode other = (GraphNode) obj;
        if(nodeValue != other.getNodeValue()) return false;
        return true;
    }
}

DirectedGraphWithWeights.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class DirectedGraphWithWeights {

    private HashMap<GraphNode, LinkedList<GraphNode>> adjacentVerticesByVertex;
    private Set<GraphNode> allNodesSet;

    /**
     * Constructor
     */
    DirectedGraphWithWeights() {
        adjacentVerticesByVertex = new HashMap<>();
        allNodesSet = new HashSet<>();
    }

    /**
     * Returns the number of vertices in the Graph
     * @return Returns the number of vertices
     */
    public int getNumberOfVertices() {
        return this.allNodesSet.size();
    }

    /**
     * Returns if the graph is directed
     * @return
     */
    public boolean isDirected() {
        return true;
    }

    /**
     * Returns the number of edges
     * @return Returns the number of edges
     */
    public int getNumberOfEdges() {
        int numberOfEdges = 0;
        for(var vertices : this.adjacentVerticesByVertex.values()) {
            numberOfEdges += vertices.size();
        }
        return numberOfEdges;
    }

    /**
     * Adds a node to the graph. VertexA -> VertexB, adding a node creates an
     * edge between VertexA and VertexB with the specified weight
     * @param vertexA Vertex A
     * @param vertexB Vertex B
     * @param weight Weight of the edge
     */
    public void addNode(int vertexA, int vertexB, int weight) {
        GraphNode vertexANode = new GraphNode(vertexA);
        GraphNode vertexBNode = new GraphNode(vertexB);
        allNodesSet.add(vertexANode);
        allNodesSet.add(vertexBNode);
        if(!adjacentVerticesByVertex.containsKey(vertexANode))
            adjacentVerticesByVertex.put(vertexANode,
                    new LinkedList<GraphNode>());
        vertexBNode.setWeight(weight);
        adjacentVerticesByVertex.get(vertexANode).add(vertexBNode);
    }

    /**
     * Returns all the vertices of the graph
     * @return All the vertices of the graph
     */
    public Iterable<Integer> getAllVertices() {
        Set<Integer> vertices = new HashSet<>();
        for(var key : adjacentVerticesByVertex.keySet()) {
            vertices.add(key.getNodeValue());
        }
        return vertices;
    }

    /**
     * Returns all the adjacent nodes
     * @param source Source node
     * @return Returns all the adjacent nodes
     */
    public Iterable<GraphNode> getAdjacentVertices(int source) {
        GraphNode tempNode = new GraphNode(source);
        return adjacentVerticesByVertex.get(tempNode);
    }

    public void printAllVertices() {
        for(GraphNode it : adjacentVerticesByVertex.keySet()) {
            System.out.print(it.getNodeValue() + " -> ");
            for(var node : getAdjacentVertices(it.getNodeValue())) {
                System.out.print("value: " + node.getNodeValue() +
                        "; weight: " + node.getWeight() + " -> ");
            }
            System.out.println();
        }
    }
}

I would highly appreciate feedback on my idea of implementation.

\$\endgroup\$
  • \$\begingroup\$ hashCode() use default, why? its tried and tested (unless you have different case) \$\endgroup\$ – emotionlessbananas Mar 13 at 10:02
  • \$\begingroup\$ Sorry I did not understand. Can you please re-phrase? \$\endgroup\$ – Rahul Wadhwani Mar 13 at 11:10
1
\$\begingroup\$

My computer theory classes have been a couple of decades ago, so I may be wrong, but you seem to be confusing the terms "node", "vertex", "edge" and some more.

Unless I'm mistaken "node" and "vertex" are the same thing, so I'd suggest to use one or the other, but not both. You also seem to sometimes call the value assigned to a vertex "node". Use a consistent term such as "value" instead.

Also nodes (usually) don't have weights, vertices do.

Then the method addNode actually adds an edge, so it should be named accordingly.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, RoToRa! I have changed the names for the variables and the functions. In terms of functionality of the class, do you think it is constructed fine? \$\endgroup\$ – Rahul Wadhwani Mar 13 at 17:35
  • \$\begingroup\$ As I wrote: Edges have weights, not nodes, so this code can't work, espeically since the way it is written, the "weight" of the node is overwritten and lost if two edges go to same node. \$\endgroup\$ – RoToRa Mar 16 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.