# Big graph traversal with OOP

I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. 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?

• What do the rows and columns of the matrix represent? Is it sparse? What format is it provided in? How is the graph (i.e, adjacency/incidence) determined from the matrix? Apr 5, 2015 at 4:32
• No it is not sparse it is full. Graph is determined as following: each cell has adj list from max 4 elements (up, down, left, right). Hope that helped. Apr 6, 2015 at 10:05
• Hard to give much help because the solution might rely on some kind of Project Euler-esque analytical simplification to get into a state where it's computable within a reasonable time Jun 3, 2015 at 16:44