Kata

A lot of people are leaving their jobs at your workplace. The Human Resources (HR) department has conjured up the new magic trick to keep people from leaving: friendships. They feel that while people know everyone on their team, they don't know people from other departments, even though they may be literally working at neighbouring desks. They also feel that if the workplace was more socially interconnected (= there would be more friendships), especially between different departments, then people would be happier to work there and would be less likely to leave.

So, the HR guys want you to help analyze the data provided by the workplace social network. They will give you a graph of this social network where vertices (nodes) represent people and friendships are edges between vertices. You will be given two departments and you need to analyze the inter-department friendships between them. You will pass the data back to HR and they will decide what to do with the very isolated departments - throw a party for them, most likely.

Before moving on: this Kata is part of the Graph Operations series. Solving previous parts in the series first might be a good way to familiarize yourself with graphs. And who knows, maybe you will be able to use that code again, especially that from part one... ;)

• Part 1: Neighbours of a vertex (hmm, this could be useful...)
• Part 2: Your distance from a colleague (a bit harder, and not necessarily useful for this Kata - but fun! ;) )
• Part 3: This Kata
• Part 4: Is it connected?

More formally, you will receive a Graph object representing the social network of your workplace, and two Sets of Vertex objects representing two departments. Your job is simple: count the connections (Edges) between the two departments (but don't count edges inside a department or edges where an endpoint is not in any of the departments.

Graph, Vertex and Edge will all be preloaded for you and should not be modified. The methods that should interest you in this Kata are the following:

• public Set<Vertex> getVertices() in Graph that returns a set of all vertices of the graph.

• public Set<Edge> getEdges() in Graph that returns a set of all edges of the graph.

• public Vertex getV1() and public Vertex getV2() in Edge that return the Vertex endpoints of an edge.

• Both Vertex and Edge has hashCode and equals implemented.

However, for simpler offline development and better understanding the full code of these classes will be provided in the end of the description.

Please note the following:

• The graph is undirected (you can travel both ways on any edge - if you know someone, he/she knows you as well)
• The graph is unweighted (each edge counts as 1)
• There are no loop edges (edges that have the same vertex as both ends)
• There are no multiple edges (paralell edges between two vertices - you either know someone, or you don't)
• Hashcode-equals implemented for Vertex and Edge as well.
• Two edges are equal if their endpoints are equal regardless of their order

If you are not entirely clear on what to do, please refer to the example test cases, they should clear up all confusion!

Have fun coding, and don't forget to vote and rate this Kata, so it can get out of beta! If you have any feedback, please don't hesitate to leave a comment!

Now, as promised, the full source code of the three classes for easier offline development:

The Graph class:

public class Graph {
    private static int uidCounter = 0;
    Set<Vertex> vertices;
    Set<Edge> edges;

    public Graph(){
        vertices = new HashSet<>();
        edges = new HashSet<>();
    }

    public void addVertex(Vertex vertex){
        vertices.add(vertex);
    }
    
    public void addVertices(Vertex... vertices){
        for(Vertex v: vertices)
            addVertex(v);
    }

    public void addEdge(Vertex v1, Vertex v2){
        addEdge(new Edge(v1, v2));
    }

    public void addEdge(Edge edge){
        vertices.add(edge.v1);
        vertices.add(edge.v2);
        edges.add(edge);
    }

    public void addEdges(Vertex... vertices){
        if(vertices.length%2 != 0)
            throw new IllegalArgumentException();

        for(int i = 0; i< vertices.length; i=i+2){
            addEdge(vertices[i], vertices[i+1]);
        }
    }

    public Set<Vertex> getVertices(){ return vertices; }

    public Set<Edge> getEdges(){ return edges; }

    static int getUidForNode(){ return uidCounter++; }
}

The Vertex class:

class Vertex {
    private final int uid;

    Vertex(){
        uid = Graph.getUidForNode();
    }

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

        Vertex other = (Vertex) o;
        return uid == other.uid;
    }

    @Override
    public int hashCode() { return uid; }
}

The Edge class:

class Edge{
    Vertex v1;
    Vertex v2;

    Edge(Vertex v1, Vertex v2){
        this.v1 = v1;
        this.v2 = v2;
    }

    public Vertex getV1() { return v1; }

    public Vertex getV2() { return v2; }

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

        Edge other = (Edge) o;
        return (v1.equals(other.v1) && v2.equals(other.v2)) || (v1.equals(other.v2) && v2.equals(other.v1));
    }

    @Override
    public int hashCode() {
        return v1.hashCode() + v2.hashCode();
    }
}

Have fun coding! ;)