Java - Which is the best implementation structure for Graph?

Question

The graph is very large but undirected. Edges are unweighted..

In my implementation, I have to find the vertex with max degree and do deletion on both vertexes and edges...

Linked list? ArrayList? Map?

Which one is better for my implementation?

Answer 1

From the above suggested the answer would be

Map with LinkedList...

Your datastructure could be like this(varies according to your requirement)...

Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>

Basically, Graphs are best implemented with the help of HASHING and the above datastructure helps a lot in that..

Answer 2

You could also have a look at specifically-designed libraries, like JUNG

Answer 3

If your algorithm requires looking up on max degree, then you want a data structure ordered by degree, something like a PriorityQueue would be good.

Then you need to store the graph itself. For deletion quickly I'd recommend something like a Sparse Array structure. If you have to use java.util data structures, then a HashMap from vertexes to the list of connected vertexes offers O(1) deletion.

If you could use 3rd party libraries, then there are a list of answers here of which JGraph and JUNG seem most popular.

Answer 4

The two fundamental data structures for representing graphs are the adjacency list and the adjacency matrix, see http://en.wikipedia.org/wiki/Adjacency%5Flist and http://en.wikipedia.org/wiki/Adjacency%5Fmatrix The articles also discuss the pros and cons of those two structures.

Answer 5

Depends on what other requirements you have. A naive, simple approach could be

class Node
{
  List<Node> edges;
  int id;
}

where you'd have a List of all the nodes in the graph. The problem is this can become inconsistent; e.g. node A might be in node B's edges list, but node B might not be in node A's list. To get around this, you could model it as such:

class Edge
{
  Node incidentA;
  Node incidentB;
}

class Node
{
  int id;
}

Again, you'd have List and List of all the edges and nodes in the system. Of course analyzing this data structure would be done in a very different way than in the other approach.

Answer 6

My suggestion would be to store the vertexes in a priority queue. That way you can have very fast access to the vertex with the highest degree. As for how to implement the vertexes, I would store each neighboring vertex in some kind of set data-structure such as a HashSet or a TreeSet to be able to remove stuff efficiently. I wouldn't represent the edges explicitly, it's not needed.

Code, something along the lines of:

class Graph {

  PriorityQueue<Node> vertexes;

  public Graph() {
    vertexes = new PriorityQueue<Vertex>(10,new Vertex());
  }

  public Vertex maxDegreeVertex() {
    return vertexes.peek();
  }

  ...

}

class Vertex implements Comparator<Vertex> {
  HashSet<Vertex> edges;

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

  public compare(Vertex v1, Vertex v2) {
    v2.edges.size().compareTo(v1.edges.size());
  }

  ...

}

Hope this helps.