CODEWITHSUNDEEP
javaalgorithmgraph
padawan
padawan

Reputation: 1315

Best Way to Implement an Edge Weighted Graph in Java

First of all, I'm dealing with graphs more than 1000 edges and I'm traversing adjacency lists, as well as vertices more than 100 times per second. Therefore, I really need an efficient implementation that fits my goals.

My vertices are integers and my edges are undirected, weighted.

I've seen this code.
However, it models the adjacency lists using edge objects. Which means I have to spend O(|adj|) of time when I'd like to get the adjacents of a vertex, where |adj| is the cardinality of its adjacents.

On the other hand, I'm considering to model my adjacency lists using Map<Integer, Double>[] adj.
By using this method, I would just use adj[v], v being the vertex, and get the adjacents of the vertex to iterate over.

The other method requires something like:

public Set<Integer> adj(int v) 
{
    Set<Integer> adjacents = new HashSet<>();
    for(Edge e: adj[v])
        adjacents.add(e.other(v));
    return adjacents;
}

My goals are:

Upvotes: 2

Views: 6191

Answers (1)

Jacob Bartel
Jacob Bartel

Reputation: 76

I've used th JGrapht for a library for a variety of my own graph representations. They have a weighted graph implementation here: http://jgrapht.org/javadoc/org/jgrapht/graph/SimpleWeightedGraph.html

That seems to handle a lot of what you are looking for, and I've used it to represent graphs with up to around 2000 vertices, and it handles reasonably well for my needs, though I don't remember my access rate.

Upvotes: 1

Related Questions