VisitorMap Data Structure

Blog

27 May


During the development of the Sky Engine for Android, I came to a point where I needed to write an algorithm for the triangulation of polygons. In order to do this in O(n), I had to develop a data structure that would remember visitation information.

You may have already seen something like what I'm about to describe, but I wanted to go away and program it for myself. So, here is it: the VisitorMap. (Conversely, there is also a VisitorList, which shall be touched on as well).


Source Code
The Basic Idea The basic idea of the VisitorMap is as follows:

We have some Key, and that Key points to a set of Links which store in memory whether they have been visited to from their parent Key.

For example, let us say we have the following vertices of a triangle: v1, v2, and v3. The positional data of these vertices does not matter to us, as we are using them to show the general idea.

In this case, v1 shall be the Key, which has both the other vertices - v2 and v3 - as Links. Initially, both of these Links have not been visited to from v1, therefore their visitation data is set to false. With this information, our VisitorMap will initially have the following structure:

Keys Links Visitation v1 --> v2 --> false --> v3 --> false

If we start from v1 and traverse across to vertex v2, then v2 will later be declared as have being visited to from its parent of v1. So now, our structure would look like the following:

Keys Links Visitation v1 --> v2 --> true --> v3 --> false

Now, let us say we have added another Key-Link set to our VisitorMap, namely: v2 as the Key, linking to v1 and v3. Our structure would now look as follows:

Keys Links Visitation v1 --> v2 --> true --> v3 --> false v2 --> v1 --> false --> v3 --> false

One thing about the VisitorMap, is that it is not transitive. So as you will notice; even though vertex v2 has been visited to from v1, the vice-versa is not true - v1 has not been marked as visited to from v2.


Usage of the VisitorMap The VisitorMap itself is a generic type class. So when we want to create an instance of it, we must declare the types for the Keys and Links:

public class VisitorMap<K, L> { private HashMap<K, HashMap<L, Boolean>> map; public VisitorMap() { map = new HashMap<K, HashMap<L, Boolean>>; } ... }

Here, K represents the typing for the Keys, and L represents the typing for the Links. You will also notice the Boolean type for the values of the second embedded HashMap. These Booleans represent the visitation data for their associated Links.

To begin with, we need to actually create and initialise a new VisitorMap. We do this like we would with any other Map in Java, using Integers as an example:

VisitorMap<Integer, Integer> visitormap = new VisitorMap<Integer, Integer>();

Once our VisitorMap has been created, we can add a new Key to visitormap with:

int vertex1 = 1; visitormap.add(vertext1);

and this will add the Integer of vertex1 to the set of Keys within our visitormap. Furthermore, it will also initialise the Key with an empty Set of Links and visitation data. Conversely, if we wished to add a new Key with a Link and set its visitation data, we would use:

int vertex1 = 1; int vertex2 = 2; visitormap.add(vertex1, vertex2, false);

Here we create a new Key of vertex1 with a Link to vertex2, and we state that vertex2 has not yet been visited to from vertex1 with the Boolean value of false. We can then add another Link of say vertex3 in the same way:

int vertex3 = 3; visitormap.add(vertex1, vertex3, false);

So that now, vertex1 has two Links: vertex2 and vertex3.

In most cases it will be vital to get the first non-visited Link from some Key. Therefore, assuming we have the VisitorMap we created just above, we can use the following to return just that:

int nextVertex = visitormap.getNext(vertex1);

This will return vertex2, because vertex2 has not yet been visited to from vertex1. Once we have obtained the Link to go to, we can then set the visitation data of vertex2 from being non-visited to visited as follows:

visitormap.setVisited(vertex1, vertex2, true);

A note to remember, vertex2 is only hypothetically being returned. This is, after all, a Map. Therefore, precise ordering is not retained. If we wish to retain the order in which Keys and their Links are added, then we should use the associated VisitorList.

Finally, say we wished to see if all Links from some Key have been visited; then we would use:

boolean visited = visitormap.allVisited(vertex1);

If true is returned, then all Links from vertex1 have been visited to from vertex1, else, we still have Links that need to be visited.




Share this:

Comments


  Allowed tags: <a> <b> <strong> <i> <em> <del> [code] [com]