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
}
My adjacency list implementation:
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
*/
public SimpleAdjacencyList(String file) {
String line;
try {
BufferedReader br = new BufferedReader(new FileReader(file));
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);
vertices.add(parent);
for(int i = 1; i < numbers.length; i++){
int label = Integer.parseInt(numbers[i]);
vertices.add(new Vertex(label, 0, null));
}
adjacencyList.put(key, vertices);
}
} catch (IOException ex) {
ex.printStackTrace();
}
}
@Override
public String toString() {
return "SimpleAdjacencyList{" +
"adjacencyList=" + adjacencyList +
'}';
}
public Map<Integer, List<Vertex>> getAdjacencyList() {
return adjacencyList;
}
// TODO: remove this
public static void main(String[] args) {
SimpleAdjacencyList list = new SimpleAdjacencyList("/Users/orestis/Documents/test.txt");
System.out.println(list);
}
}
1 Answer 1
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.
AdjacencyList
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...