Undirected graph implementation in java

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 -

• Did I use encapsulation in the correct way? Did I overuse/underuse it?

• Is this a good way of implementing a graph given that i want to write some more classes for BFS and DFS?

• In the Vertex class should the ArrayList be of 'Vertex' or is Integer fine?

• Right now, the iteration mechanism that I am using for the Graph feels sloppy. Is there a better design?

• 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 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 ();
for(Map.Entry 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()){
S

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 adjacencyMap;

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

private final Map 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 :)

StackExchange Code Review Q#134505, answer score: 4