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

Question

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);
    }
}

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...