Adjacency List- updated

The first [smaller] part of this project will be to implement and use an adjacency list. You'll recall that an adjacency is conceptually a 'list of lists', ie:

A->C->D
C
D
F->K->J
H->K
J
K

After much deliberation, for this project it has been decided that you will implement this structure as a Skiplist of Skiplists. Code re-use is good stuff, and a skiplist is functionally(as far as writing your program) no worse than any of the java API classes that are available. If you don't like your own SkipList you may inherit someone elses from project 1. Note that insertion/deletion from this structure is O(log(n)log(m)), where n is the number of nodes in the graph and m is the degree of the graph (the max number of edges incident to a single vertex). This represents a binary search to find the correct row of the list to find the starting vertex, followed by a a binary search to check for existance of the ending vertex. You are guaranteed that all paths in this project will be bidirectional. This means that you need only store each edge once instead of twice, giving you half the memory usage and half the access time but making your graph less general. This optimization is up to you(it's not much to implement). You'll use the graph to implement shortest path using dijkstra's algorithm. If you have a fibbonacci heap handy the run time of this algorithm is O(V*lg(V)+E) (where E is the number of edges and V is the number of vertices). And a fibonacci heap is what you ask? Well, I have no idea, but those of you who go on to take algorithms classes will no doubt hear about fibonacci heaps again, and I just wanted to be the first to share. Let's just say that they are magical, and that you will probably *never* learn how they work. If you've put this spec on paper, feel free to X is this paragraph to avoid reading it ever again. End digression. So anyway, you will be required to do shortest path in O(ElgV). It would be nice if you understand where this bound comes from, so I will explain it below, but as with the KDTree it suffices that if you implement the algorithm correctly, that is the runtime you will have. Allow me to sketch the algorithm to explain the running time(I'm not trying to teach the algorithm here- see your book/class/newsgroup/google). Every iteration of this algorithm you are guaranteed to find the correct shortest path to exactly one node- so we know right away there will be V iterations. At each state your graph is split in two sections- the 'solved' section, for which you know the correct distances, and the rest, which have some distance values associated with them which may or may not be accurate- this set is stored in some kind of priority queue. An iteration begins by selecting the node (call it 'N') from this queue with the best distance value, adding it to the 'solved' set, and 'relaxing' all it's edges. Relaxing is when for each node adjacent to N we see if it is faster to get to that node through N than it's current best known path. We update distances and back-pointers appropriately (so we know what the shortest path actually is when we finish), and that ends the round. Note that if a node's distance value is changed, its position in the priority queue has to be fixed up somehow. (this is where the magical fibonnaci heap would come into play, it's got an advantage in this 'fix up' step). One way to do this is just to have multiple copies of the same node in the queue and ignore them when they come back up (this is the approach I will use in the explanation), or else to remove the old value before reinserting it. Either works. Now, how long does all this take. There are V rounds, and in every round we have to pull something out of the front of the priority queue- which with a skiplist is an O(1) expected time operation(note that it would be log(E) in a balanced binary tree), so each round takes O(V) time. Rather than try and deal with how many elements are added to and removed from the queue in any single round, it is easier to think about how many such operations can occur in the life of the algorithm. Every single edge in the graph has exactly one opportunity to add a vertex to the queue (during a relax operation), so there are O(E) possible insertions. If we allow duplicates, the size of the queue can grow to O(E), so we may treat each queue operation as O(log(E)). That gives O(ElogE) running time for all queue operations during the life of the algorithm. Together that gives a running time of O(V+ElgE), which since E is bounded by $V^2$, is O(ElgV). And that's the required running time of your search;) Yes, your adjacency list is to be a skiplist of skiplists, and you should go ahead and use your skiplist for the priority queue (you may either use the O(logn) operation to remove the head of the list, or you may implement a 'pop' or 'shift' operation that runs in O(1) expected/amortized time. Why expected? Well, you have update that tower for that node- and the tower may be up to about O(logn) height. Recall though that the *average* height of a node is only 2. You might want to understand this stuff- you might have occasion to want to explain it to someone someday,or something... ;)

Web Accessibility