Undirected graph implementation in java

Question

Here is my code which implements a undirected graph in java. I'm fairly new to java(I come from C) and I am not sure if this is a good implementation. Here are a few things i worry about -

1. Did I use encapsulation in the correct way? Did I overuse/underuse it?
2. Is this a good way of implementing a graph given that i want to write some more classes for BFS and DFS?
3. In the Vertex class should the ArrayList be of 'Vertex' or is Integer fine?
4. Right now, the iteration mechanism that I am using for the Graph feels sloppy. Is there a better design?
5. Other issues with the code, not mentioned above.

---

UndirGraph.java

package graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.StringTokenizer;

/**
 *
 * @author aneesh
 */
public class UndirGraph implements Graph{
    /**
     * Number of vertices in the graph.
     */
    private int v;

    /**
     * Number of edges in the graph.
     */
    private int e;

    /**
     * The graph is a mapping from the 'vertex number ' to a instance 
     * of the class 'Vertex'.
     * The Vertex is a collection of 'vertex numbers ' of vertices
     * adjacent to itself.
     */
    private Map<Integer, Vertex> adjMap;

    /**
     * Construct a new undirected graph with 'n' vertices.
     * @param n The number of vertices.
     */
    public UndirGraph(int n){
        this.v = n;
        this.adjMap = new HashMap<>();
        for(int i = 1; i <= v; ++i){
            adjMap.put(i, new Vertex());
        }
    }

    /**
     * Construct a graph as a copy of another graph.
     * @param rhs The graph to copy.
     */
    public UndirGraph(UndirGraph rhs){
        this.v = rhs.v;
        this.e = rhs.e;
        this.adjMap = new HashMap<>();
        for(Map.Entry<Integer, Vertex> entry: rhs.adjMap.entrySet()){
            this.adjMap.put(entry.getKey(), new Vertex(entry.getValue()));
        }
    }

    /**
     * Construct a graph from a Scanner.
     * @param sc The scanner.
     */
    public UndirGraph(java.util.Scanner sc){
        //Scan the number of vertices in the graph
        this.v = sc.nextInt();
        this.adjMap = new HashMap<>();
        System.out.print(sc.nextLine());  //Set the scanner to the next line.

        while(sc.hasNext()){
            String input = sc.nextLine();
            StringTokenizer strToken = new StringTokenizer(input);
            int count = strToken.countTokens();

            //DEBUG
            //System.out.println(input + " " + count);

            int[] arr = new int[count];
            for(int i = 0; i < count; ++i){
                arr[i] = Integer.parseInt(strToken.nextToken());
            }

            //arr[0] is the number of the vertex
            adjMap.put(arr[0], new Vertex());
            for(int i = 1; i < count; ++i){
                adjMap.get(arr[0]).addNeighbour(arr[i]);
                //System.out.println(arr[i]);
            }
        }
        e = edges();
    }

    /**
     * Custom Exception type which flags exceptions due to
     * improper use of 'vertex numbers '.
     */
    class NoSuchVertexException extends RuntimeException{
        public NoSuchVertexException(String no_such_vertex) {
            super(no_such_vertex);
        }
    }

    /**
     * Custom exception type which flags exception due to 
     * bad edge specifications.
     */
    class BadEdgeException extends RuntimeException{
        public BadEdgeException(String bad_edge){
            super(bad_edge);
        }
    }

    /**
     * Add a edge between Vertex v1 and Vertex v2.
     * @param v1
     * @param v2 
     */
    @Override
    public void addEdge(int v1, int v2){
        if(!hasVertex(v1) || !hasVertex(v2))
            throw new NoSuchVertexException("No such vertex!");
        adjMap.get(v1).addNeighbour(v2);
        adjMap.get(v2).addNeighbour(v1);
    }

    /**
     * Remove a edge between Vertex v1 and Vertex v2.
     * @param v1
     * @param v2 
     */
    @Override
    public void removeEdge(int v1, int v2){
        if(!edgeExists(v1, v2))
            throw new BadEdgeException("Such an edge does not exist!");
        else{
            adjMap.get(v1).removeNeighbour(v2);
            adjMap.get(v2).removeNeighbour(v1);
        }
    }

    /**
     * Count the total number of edges.
     * @return Integer specifying the total number of edges in the graph.
     */
    private int edges(){
        int total = 0;
        for(Vertex v : adjMap.values()){
            total += v.noOfNeighbours();
        }
        return total / 2;
    }

    /**
     * The number of edges in the graph.
     * @return 'e' which denotes |E| of the graph.
     */
    @Override
    public int numberOfEdges(){
        return e;
    }

    /**
     * The number of vertices in the graph.
     * @return 'v' which denotes |V| of the graph.
     */
    @Override
    public int size(){
        return v;
    }

    /**
     * Determines if a edge exists between Vertex v1 and Vertex v2.
     * @param v1    First Vertex.
     * @param v2    Second Vertex.
     * @return true/false.
     */
    @Override
    public boolean edgeExists(int v1, int v2){
        return adjMap.containsKey(v1) && adjMap.containsKey(v2) &&
                adjMap.get(v1).isNeighbour(v2) && 
                adjMap.get(v2).isNeighbour(v1);
    }

    /**
     * Determines if 'v' is a valid vertex number.
     * @param v
     * @return true/false.
     */
    @Override
    public boolean hasVertex(int v){
        return adjMap.containsKey(v);
    }

    /**
     * Contract the edge between Vertex v1 and Vertex v2.
     * Removes Vertex v2 from the graph.
     * @param v1    First Vertex.
     * @param v2    Second Vertex.
     */
    private void contractEdge(int v1, int v2){
        //System.out.println(v1 + " " + v2);
        if(!hasVertex(v1) || !hasVertex(v2))
            throw new NoSuchVertexException("Invalid vertex!");
        else if(!edgeExists(v1, v2))
            throw new BadEdgeException("Such an edge does not exist!");
        else{
            //remove all v1 from v2 and all v2 from v1.
            adjMap.get(v1).removeAll(v2);
            adjMap.get(v2).removeAll(v1);

            //append list of v2 to v1.
            adjMap.get(v1).append(adjMap.get(v2));

            //remove v2 from the map.
            adjMap.remove(v2);

            //replace all occurences of v2 with v1 in the graph.
            for(Vertex vr : adjMap.values()){
                vr.replaceAll(v1, v2);
            }

            //update v and e
            v = adjMap.size();
            e = edges();
        }
    }

    /**
     * Determine a random cut of the graph.
     * @return The number of crossing edges in the random cut.
     */
    public int Cut(){
        UndirGraph copy = new UndirGraph(this);
        while(copy.size() > 2){
            int v1, v2;
            do{
                ArrayList<Integer> keys = new ArrayList<>(copy.adjMap.keySet());
                Random r = new Random();
                v1 = keys.get(r.nextInt(copy.size()));
                v2 = keys.get(r.nextInt(copy.size()));
            }
            while(!copy.edgeExists(v1, v2));

            copy.contractEdge(v1, v2);
        }
        return copy.numberOfEdges();
    }

    /**
     * Determine the minimum cut of the graph using Karger's algorithm.
     * @return The number of crossing edges in the minimum cut.
     */
    public int minCut(){
        int answer = this.numberOfEdges();
        System.out.println(this.size());
        for(int i = 0; i < this.size() * this.size() * 2; ++i)
            answer = Math.min(answer, this.Cut());
        return answer;
    }

    /**
     * Print the graph.
     */
    @Override
    public void print(){
        System.out.println("The Graph:- ");
        for(Map.Entry<Integer, Vertex> entry : adjMap.entrySet()){
            System.out.print(entry.getKey() + " -> ");
            for(Integer i : entry.getValue())
                System.out.print(i + " ");
            System.out.println("\n");
        }
    }
}

---

Graph.java

package graphs;

/**
 *
 * @author aneesh
 */
public interface Graph {
    int numberOfEdges();
    int size();
    boolean edgeExists(int a, int b);
    boolean hasVertex(int v);
    void removeEdge(int a, int b);
    void addEdge(int a, int b);
    void print();
}

---

Vertex.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package graphs;

import java.util.ArrayList;
import java.util.Iterator;

/**
 *
 * @author aneesh
 */
class Vertex implements Iterable<Integer>{
    /**
     * Used for search algorithms.
     */
    private boolean visited;

    /**
     * List of vertices adjacent to this vertex.
     */
    private ArrayList<Integer> neighbours;

    /**
     * No parameter constructor.
     */
    public Vertex(){
        this.visited = false;
        this.neighbours = new ArrayList<>();
    }

    /**
     * Copy a vertex.(Deep copy)
     * @param rhs The vertex to copy from.
     */
    public Vertex(Vertex rhs){
        this.visited = rhs.visited;
        this.neighbours = new ArrayList<>(rhs.neighbours);
    }

    /**
     * Check to see if the vertex is marked as visited.
     * @return true/false
     */
    public boolean isVisited(){
        return visited;
    }

    /**
     * Remove a vertex from the list of neighbor.
     * @param v The vertex to remove.
     */
    public void removeNeighbour(int v){
        this.neighbours.remove(v);
    }

    /**
     * 
     * @return The number of neighbors to this vertex.
     */
    public int noOfNeighbours(){
        return this.neighbours.size();
    }

    /**
     * Checks if 'v' is a neighbor of this vertex.
     * @param v The vertex in question.
     * @return true/false
     */
    public boolean isNeighbour(int v){
        return this.neighbours.contains(v);
    }

    /**
     * Adds a new neighbor.
     * @param v The vertex to be added.
     */
    public void addNeighbour(int v){
        this.neighbours.add(v);
    }

    /**
     * Become neighbors with all the neighbors of 'other'
     * @param other The vertex in question.
     */
    public void append(Vertex other){
        for(int i : other){
            this.neighbours.add(i);
        }
    }

    /**
     * Remove all edges with 'v'.
     * @param v
     */
    public void removeAll(int v){
        this.neighbours.removeIf(x -> x == v);
    }

    /**
     * Replace all 'v2' with 'v1'.
     * @param v1    The substitute vertex.
     * @param v2    The vertex to be substituted.
     */
    public void replaceAll(int v1, int v2){
        this.neighbours.replaceAll(x -> { if(x == v2) return v1; else return x; });
    }

    /**
     * Mark the vertex as visited.
     * @param b 
     */
    public void setVisited(boolean b){
        this.visited = b;
    }

    @Override
    public Iterator<Integer> iterator(){
        return this.neighbours.iterator();
    }
}

Answer 1

I'll just go from top to bottom and comment on everything that I see that smells fishy:

---

package graph;

It's customary to declare packages as "reverse URLs". I for example use de.vogel612 for all my projects before putting in the project name and then building a package structure.

---

public class UndirGraph implements Graph {

Why shorten the name? In this day and age characters of code are literally the cheapest thing you can find in programming. Don't try to bargain on identifier-length. UndirectedGraph is significantly better.

---

/**
 * Number of vertices in the graph.
 */
private int v;

Same applies here (and for edges as well). Just wrute the name out. Interestingly the comment becomes completely obsolete then.

private int vertices;
private int edges;
private Map<Integer, Vertex> adjacencyMap;

---

Eagerly initialize your fields (and mark them final) where possible. Especially for the adjacencyMap that's useful. You can declare:

private final Map<Integer, Vertex> adjacencyMap = new HashMap<>();

just fine and use just as you do now.

---

While we're at that Map. Since your graph is undirected you could formally define an Edge as a Tuple of Vertices or written in short notation:

Let \$V\$ be the vertices of an undirected graph. Then the edges of a Graph are \$E \subseteq V \times V\$ where equality is defined as \$e_1 = e_2 \Leftrightarrow e_1 = (v_1, v_2) \cap e_2 = (v_2, v_1) \forall v_1, v_2 \in V\$

You could accordingly define edges as:

• Tuples (implementing an equality as above)
• Sets of two elements (since they ignore ordering for equality)

You are making it a bit more complicated on yourself by having edges be a property of vertices. That requires maintaining an edge in each direction and is generally considered ... tedious.

Aside from that, you're misusing the HashMap as an Array. For all intents and purposes your code could just as well use Vertex[] adjacencyLists.
Do note that this would require you to either resize that array as needed when you add vertices (which you don't support) or necessitate knowing the number of vertices before constructing the graph.

This would simplify initialization for the first two constructors:

public UndirectedGraph(int n) {
    this.vertices = n;
    this.edges = 0;
    this.adjacencyLists = new Vertex[n];
    for (int i = 0; i < adjacencyLists.length; i++) {
        adjacencyLists[i] = new Vertex();
    }
}

public UndirectedGraph(UndirectedGraph rhs) {
    this.vertices = rhs.vertices;
    this.edges = rhs.edges;
    this.adjacencyLists = new Vertex[rhs.vertices];
    System.arraycopy(rhs.adjacencyLists, 0, this.adjacencyLists, 0, vertices);
}

Sidenote: Should you decide against using an array, the copy-constructor can be simplified by using putAll like so:

this.adjMap.putAll(rhs.adjMap);

---

public UndirGraph(java.util.Scanner sc){

~shiver. It's really really really bad to do I/O inside a constructor. There's so incredibly many things that can go wrong. In general you're better off not having the I/O inside the constructor, but doing it somewhere else and then use the results to create the instance of the class.

As such I will just state that and ignore this for the rest of the review :)

---

/**
 * Custom Exception type which flags exceptions due to
 * improper use of 'vertex numbers '.
 */
class NoSuchVertexException extends RuntimeException{

This is just an ArrayIndexOutOfBoundsException in disguise. When you rewrite your code to use an array, you will actually get that one and don't have to roll that yourself.

---

/**
 * Custom exception type which flags exception due to 
 * bad edge specifications.
 */
class BadEdgeException extends RuntimeException{

You use this exception only when the user tries to remove edges that are not there. That's not an exceptional case. The Java standard library usually ignores requests to remove inexistant elements. The only exceptions to that (that I know off the top of my head) are Iterator and Stack. For an Iterator you'd get an IllegalStateException when you already removed a certain element. A Stack will throw an EmptyStackException when you try to pop or peek off an empty Stack.

In summary this exception goes against how a Java-developer would expect a remove to behave.

---

I think this is sufficient to get you busy for a while and I strongly suggest you post a follow-up question after incorporating the changes I suggested :)