I'm new to Java and working with graphs. I have a time evolving graph (e.g 5 snapshots of the same graph in different instance of time) and I need to compute some basic network metrics like density, size, centrality, etc on each one of them. I was wondering as to what basic data structures I could use to store and perform computation on each graph. I tried using adjacency matrix, but the node size is too large and dynamic which leads to inefficiency. I came across few libraries notably JgraphT to hold undirected graphs
UndirectedGraph<String, DefaultEdge> G =
new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
But this is for one graph. Is there a way to create an array of these undirected graphs or any other way which I am missing to store time evolving graphs?
A few options:
(1) You can create an array (or a List, or a Set, etc.) of graphs just as you can of any other object. If all the timesteps fit easily into memory (say 100 timesteps of 1000 nodes/edges each) then this should work fine. Here's an example using JUNG:
List<Graph<V, E>> graphList = new ArrayList<>(); // Java 7 syntax
Graph<V, E> graph = new DirectedSparseGraph<V, E>();
// populate 'graph'
graphList.add(graph);
(2) If the nodes in each graph are all the same (i.e., it's just the edges that are changing), store the nodes once, and store a list of sets of edges, one set for each timestep.
(3) If the whole graph is relatively static, you can store the original graph, and then store deltas (added/removed nodes or edges) for each timestep. This can be considerably more space-efficient, but requires that you reconstruct steps 1-n in order to see the state at time n+1.
(4) Finally, you can use a single graph, annotate each node/edge with the interval(s) at which it is present, and apply a filter any time you want to apply an algorithm to the graph.