Skip to content
A data structure, written in Java, for storing a set of keys, each with a set of links; keeping in memory whether those links have been visited to from their parent key. Because this is a Map, it does not retain the order in which keys and links are added. If retaining the order is necessary, you may be more interested in the VisitorList.
Find file
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
README.md
VisitorMap.java

README.md

VisitorMap Data Structure

A data structure for storing a set of keys, each with a set of links; keeping in memory whether those links have been visited to by their parent key. Because this is a Map, it does not retain the order in which keys and links are added.

Description

I designed this data structure initially when I needed something to help me deal with the triangulation of polygons. At first I used the VisitorList, but it worked ineffeciently in O(n). I then realised that I did not need to retain ordering, so I created this VisitorMap which works in O(1).

The basic idea is this: we have some key, and that key points to a set of links which store in memory whether they have been visited to from the parent key or not. For example, say we have 3 vertices: v1, v2 and v3.

v1 is the key, which points to two links: v2 and v3. Both of which have initially not been visited to by their parent key, v1. So, the data structure initially looks like the following:

Keys            Links           Visited?
v1      -->     v2      -->     false
        -->     v3      -->     false

Afterwards, we may traverse to v2 from v1, in which case we then declare v2 as been visited to from its parent v1. So now the structure looks like this:

Keys            Links           Visited?
v1      -->     v2      -->     true
        -->     v3      -->     false

Now, let us say we have another key-links set, say: v2 links to v1 and v3:

Keys            Links           Visited?
v1      -->     v2      -->     true
        -->     v3      -->     false

v2      -->     v1      -->     false
        -->     v3      -->     false

Here, you will notice that the link between v2 and v1 is marked as false. This is correct, as v1 has not been visited to from its parent key of v2, even though v2 has been visited to from v1.

Usage

To create and initialise a new VisitorMap, we use:

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

as we would with any List, Map or Set within Java. Once the VisitorMap has been created, we can give the visitormap a new key to store links by:

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

and this will add vertex1 to the list of keys contained within the visitormap. It will also initialise an empty Set of Links and visitation information. If we wish to add a new key, with an initial link and set its visitation details, we use:

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

So here, we create a new key of vertex1 with an initial link to vertex2, and we state that vertex2 has not yet been visited to by vertex1 with a boolean value of false.

In most cases, it will be vital to get the first non-visited link from some key. Therefore, assuming we have the VisitorList created just above, we can use:

int nextVertex = visitormap.getNext(vertex1);

This will return vertex2, because vertex2 has not yet been visited to by vertex1. If we wish to change the visitation details of a specific link from non-visited to visited, we can use:

visitormap.setVisited(vertex1, vertex2, true);

Which will set the visitation details of vertex2 to have now been visited to from vertex1.

Adding a new link for some key is also simple, we can just use:

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

Now, we still have one key within the visitormap; namely, vertex1. But now, this key has two links: vertex2 and vertex3. Except, vertex2 has already been visited to by vertex1, yet vertex3 has not. Therefore, if we were to call,

int nextVertex = visitormap.getNext(vertex1);

again on vertex1, this time around we would yield the link of vertex3. Now let us say that vertex3 has already been visited to. If we call getNext(vertex1) again then a value of null is returned as all links for vertex1 have been visited to by it.

Obviously, we have a problem will int = null, therefore, if this is ever the case, you could use either:

if (visitormap.getNext(vertex1) != null) {
    nextVertex = visitormap.getNext(vertex1);
}

or

if (!visitormap.allVisited(vertex1)) {
    nextVertex = visitormap.getNext(vertex1);
}

These are only two possible workarounds, but of course, there are others. Another could be:

Object obj = visitormap.getNext(vertex1);
if (obj != null) {
    nextVertex = (Integer)obj;
}

It should also be clear as to what it is allVisited(vertex1) is doing. This method returns true if every link for the key vertex1 has been visited to from it, false otherwise.

Improvements

Something went wrong with that request. Please try again.