# Graph representation using adjacency list for BFS, DFS, and Karger's algorithm

I want to implement some graph algorithms for learning purposes (e.g BFS, DFS, Karger's min-cut algo) and before diving into them I want to make sure I have got the graph representation right (using an adjacency list). I want to keep things minimum to exactly what I need to implement these algorithms on undirected graphs for the time being.

Here's my Vertex class:

public final class Vertex {
private final int label;
private VertexColor color = VertexColor.WHITE;
private int distance;
private Vertex parent;

public Vertex(int label, int distance, Vertex parent) {
this(label);
this.distance = distance;
this.parent = parent;
}

public Vertex(int label) {
this.label = label;
}

public int getLabel() {
return label;
}

public VertexColor getColor() {
return color;
}

public void setColor(VertexColor color) {
this.color = color;
}

public Vertex getParent() {
return parent;
}

public void setParent(Vertex parent) {
this.parent = parent;
}

public int getDistance() {
return distance;
}

public void setDistance(int distance) {
this.distance = distance;
}

@Override
public String toString() {
return "Vertex{" +
"label=" + label +
", color=" + color +
", distance=" + distance +
", parent=" + parent +
'}';
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Vertex vertex = (Vertex) o;

if (label != vertex.label) return false;
if (distance != vertex.distance) return false;
if (color != vertex.color) return false;
return !(parent != null ? !parent.equals(vertex.parent) : vertex.parent != null);

}

@Override
public int hashCode() {
int result = label;
result = 31 * result + (color != null ? color.hashCode() : 0);
result = 31 * result + distance;
result = 31 * result + (parent != null ? parent.hashCode() : 0);
return result;
}
}


My VertexColor enum:

public enum VertexColor {
WHITE, GREY, BLACK
}


public class SimpleAdjacencyList {
private Map<Integer, List<Vertex>> adjacencyList = new HashMap<>();

/**
* Initializes a new graph from a file.
* @param file format should be:
* 1    2   4
* 2    3   1
* 3    2   4
* 4    3   1
*/
String line;
try {
while ((line = br.readLine()) != null) {
String[] numbers = line.trim().split("(\\s)+");
int key = Integer.parseInt(numbers[0]);
List<Vertex> vertices = new ArrayList<>(numbers.length);
Vertex parent = new Vertex(key);
for(int i = 1; i < numbers.length; i++){
int label = Integer.parseInt(numbers[i]);
}
}
} catch (IOException ex) {
ex.printStackTrace();
}
}

@Override
public String toString() {
'}';
}

}

// TODO: remove this
public static void main(String[] args) {
System.out.println(list);
}
}


In general your code is good. There are some small issues I dislike, and there's an issue with the Adjacency list that's small too. Basically, if this was a real review, I would probably say: fine - but small things to work on next time.

## Constructors

I have no reference for this, but I much prefer convencience constructors to call canonical ones. In your code, you have... hmmm, you don't have an actual canonical constructor - you can't construct with a VertextColor:

public Vertex(int label, int distance, Vertex parent) {
this(label);
this.distance = distance;
this.parent = parent;
}

public Vertex(int label) {
this.label = label;
}


Here, you have a canonical constructor (int, int, Vertex) calling a convenience one (Vertex). I would prefer the opposite, and have code like:

public Vertex(int label, int distance, Vertex parent, VertexColor color) {
this.label = label;
this.distance = distance;
this.parent = parent;
this.color = color;
}

public Vertex(int label, int distance, Vertex parent) {
this(label, distance, parent, VertexColor.WHITE);
}

public Vertex(int label) {
this(label, 0, null, VertexColor.WHITE);
}


This way it makes it obvious what is what, and also, the actual fields are only set in a single constructor too.... Additionally, it opens up an easier way to make the fields final, if you wanted to.

Finally, I don't like code that relies on using the not-supplied default values of declared fields, and the Canonical constructor solves that (what I mean here, is that your current constructor Vertex(int label) does not set any other fields, but relies on the default values for private int distance; and private Vertex parent;.

## toStrings

Your toStrings are using string concatenations. This is not horrible, but I would prefer to see string formatting.

This code:

public String toString() {
return "Vertex{" +
"label=" + label +
", color=" + color +
", distance=" + distance +
", parent=" + parent +
'}';
}


would be better as:

public String toString() {
return String.format("Vertex{label=%d, color=%s, distance=%d, parent=%s}",
label, color, distance, parent);
}


## equals & hashCode

Your two methods appear to follow the equals/hashCode contract, which is great. I would suggest two changes though in each.... in the equals, you have:

public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Vertex vertex = (Vertex) o;

if (label != vertex.label) return false;
if (distance != vertex.distance) return false;
if (color != vertex.color) return false;
return !(parent != null ? !parent.equals(vertex.parent) : vertex.parent != null);

}


You should use instanceof instead of o == null || getClass() != o.getClass(). instanceof will return false for a null value, and, it is more clear what its intent is. Additionally, you should use Objects.equals(a,b). Your code could be:

public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof Vertex)) {
return false;
}

Vertex vertex = (Vertex)o;

return label == vertex.label
&& distance == vertex.distance
&& color == vertex.color
&& Objects.equals(parent, vertex.parent);
}


In the hashCode method, I suspect this is auto-generated code. It's OK, but I thought there would be a way to integrate Objects.deepHashCode(...) but there may not be.

This code looks fine too. The one comment here is that I would prefer to see a more batch-oriented integer conversion of each line.

I would have a method like:

private static int[] lineToInts(String line) {
String[] parts = line.split("\\s+");
int[] numbers = new int[parts.length];
for (int i = 0; i < parts.length; i++) {
numbers[i] = Integer.parseInt(parts[i]);
}
return numbers;
}


If you have Java 8, I would make that:

private static int[] lineToInts(String line) {
return Stream.of(line.split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
}


Then you can simplify the other code...

Also, in this class, use printf for the toString...