CODEWITHSUNDEEP
javagraphequals
Michael
Michael

Reputation: 42110

Edge of undirected graph in Java

Suppose I am writing a Java class to represent an edge of undirected graph. This class Edge contains two vertices to and from. 

class Edge<Vertex> {

  private final Vertex to, from

  public Edge(Vertex to, Vertex from) {
    this.to = to;
    this.from = from;
  } 
  ... // getters, equals, hashCode ...
}

Obviously e1 = new Edge(v1, v2) and e2 = new Edge(v2, v1) are actually the same in an undirected graph. Does it make sense? How would you implement class Edge to meet that requirement?

Upvotes: 0

Views: 4429

Answers (4)

Dan W
Dan W

Reputation: 5782

I actually wouldn't have this logic in my Edge class but rather some sort of over-seeing class such as a Graph class. The reason for this is because an Edge is just an object with 2 vertices. It doesn't know anything about the rest of the edges in the graph.

So, to expand on @noMad's answer, I would actually put his checkIfSameEdge method in my Graph class:

public class Graph {
    private List<Edge> edges;
    ....
    public void addEdge(Edge e) {
        for (Edge edge : edges) {
            if (isSameEdge(edge, e) {
                return; // Edge already in Graph, nothing to do
        }
        edges.add(e);
    }
    private boolean isSameEdge(Edge edge1, Edge edge2) {
        return ((edge1.to.equals(edge2.to) && edge1.from.equals(edge2.from))
             || (edge1.to.equals(edge2.from) && edge1.from.equals(edge2.to)))
    }
}

BTW: I would rename to and from to vertex1 and vertex2 because it is an undirected graph and to and from indicate direction, but that's just my opion.

Upvotes: 2

dbyrne
dbyrne

Reputation: 61101

Perform a sort on the vertices in the constructor based on some unique identifier. This way they are stored consistently regardless of order.

I find this preferable to noMAD's solution because all code interacting with these objects will treat them identically, not just your implementation of equals.

Also, calling your class members to and from is confusing because it sounds like a directed graph. I would rename these to something more generic like vertex1 and vertex2.

  public Edge(Vertex x, Vertex y) {
      if (vertex2.getId() > vertex1.getId()) {
          this.vertex1 = x;
          this.vertex2 = y;
      } else {
          this.vertex1 = y;
          this.vertex2 = x;
      }
  }

Upvotes: 2

symcbean
symcbean

Reputation: 48387

Presumably the nodes contain some sort of scalar values - sort the parameters based on these values (using the compareTo method) and use a factory to create a new instance or return an existing instance.

Upvotes: 1

noMAD
noMAD

Reputation: 7844

Well, of the top of my head, the naivest method would be:

protected boolean checkIfSameEdge(Vertex to, Vertex from) {
  if(to.equals(this.from) && from.equals(this.to) || to.equals(this.to) && from.equals(this.from)) {
    return true;
  return false;
}

Obviously you would have to override equals and hashcode

Upvotes: 1

Related Questions