2

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? – user2313838 Apr 5 '15 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. – Michael Z Apr 6 '15 at 10:05
  • 1
    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 – Ben Aaronson Jun 3 '15 at 16:44
1

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.