I’m trying to solve a algorithmic contest’s problem. I have a matrix 2000×2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices creation took more than 2s! Just think of it – I’ll need to create Adjacency matrix + run BFS/DFS + do some business logic so time will be increased more! Here is my attempt to create Graph vertices:
Map<Integer, Vertex> allVertices = new HashMap<>();
final long b = System.currentTimeMillis();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
final int id = i * m + j + 1;
Vertex v = allVertices.get(id);
if (v == null)
{
v = new Vertex(id);
allVertices.put(id, v);
}
}
}
final long a = System.currentTimeMillis();
final long d = a - b;
System.out.println(String.format("took <%s> ms", d));
class Vertex
{
Color color;
final int id;
public Vertex(final int id)
{
this.id = id;
}
}
I wonder is this common practice to use OOP to represent big graph’s vertices or I need to use arrays only?
3
First of all, when you’re creating your initial map, you can be confident each vertex isn’t already present in it. You’re wasting a lot of time checking for that.
Second, in algorithm contests with that large of input and relatively small time constraints, the best solution usually only requires you to store one row of input at a time, plus some sort of cumulative result around the size of a row. You should look for those kinds of solutions first.
Only because you want to do things OO does not mean that you must create the graph made out of nodes and vertices. It is absolutely fine to capture the full graph in a single object, and to create a nice, well contracted OO interface on top of it.
A classic idea that I have used is the concept of a cursor that works on top of a graph. That cursor knows about the internal representation, and can sit either on top of nodes and travel along vertices to other nodes, or it could sit even on vertices – its all a matter of design choice really.
The nice thing about such an interface is that it stays reasonably efficient, even if you are hiding to the user if the internal implementation of the graph is using adjacency matrix or adjacency lists.