2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.