http://www.microsoft.com/college/
while not done if the graph is empty, then we're done (exit the loop) pick a node with no predecessors if no such node exists , then the graph is cyclic (exit the loop) output that node (number that node) delete that node from the graph end while
/**
* Output the nodes in the current acyclic directed graph so that
* when there is a path from A to B, A is output before B.
* pre: The graph is acyclic
* post: The graph may be modified
* post: All nodes in the graph are output
* post: The output order follows the dependencies of the graph.
*
* @exception CyclicException if the graph is cyclic.
*/
void topologicalSort() throws CyclicException {
// If the graph is empty, then we're done
if empty() return;
// Find a node with no predecessors
Node small = fewestPredecessors();
// If no such node exists, the graph is cyclic
if (small.predCount() != 0) {
throw new CyclicException("Can't toposort cyclic graphs");
}
// Output that node
System.out.print(small.contents());
// Delete it from the graph
delete(small);
// And go on
topologicalSort();
} // topologicalSort
/** See description above. */
public void topologicalSort() {
// Variables
Dictionary adjacencies = new Dictionary();
// Adjacency lists
Dictionary pred_count = new Dictionary();
// Predecessor count of each node
Linear no_pred = new Linear();
// Nodes with no predecessors
Edge e; // The next edge to deal with
Object source; // Source of directed edge
Object sink; // Sink of directed edge
// Fill in the adjacency list
for(Enumeration edges = this.edges(); edges.hasMoreElements();) {
e = edges.nextElement();
source = e.source();
sink = e.sink();
// If the source or sink isn't in the dictionaries, add it
if (!adjacencies.contains(source)) {
adjacencies.put(source, new Linear());
pred_count.put(source, new Counter());
}
if (!adjacencies.contains(sink)) {
adjacencies.put(sink, new Linear());
pred_count.put(sink, new Counter());
}
// Update adjacency list for source
adjacencies.get(source).add(sink);
// Update predecessor count for sink (not real Java)
((Counter) pred_count.get(source)).increment();
} // for
// Identify all nodes with no predecessors
for(Enumeration nodes = pred_count.keys(); nodes.hasMoreElements(); ) {
source = nodes.nextElement();
if (((Counter) pred_count.get(source)).isZero()) {
no_pred.add(source);
}
} // for
// As long as there are nodes with no predecessors, output and
// "delete" them
while (!no_pred.empty()) {
source = no_pred.next();
source.output();
for (Enumeration neighbors = adjacencies.get(source);
neighbors.hasMoreElements(); ) {
sink = neighbors.nextElement();
((Counter) pred_count.get(sink)).decrement();
if ((Counter.pred_count.get(sink)).isZero()) {
no_pred.add(sink);
}
} // for
} // while
// Are there nodes remaining? If so, it was a cyclic graph.
for(Enumeration nodes = pred_count.keys(); nodes.hasMoreElements(); ) {
source = nodes.nextElement();
if (!pred_count.get(source).isZero()) {
throw new CyclicException();
}
} // for
} // topologicalSort()
Counter class that we can use
to count references. It should be trivial to implement that counter.
Use mnemonic input and output. Make input easy to prepare (and to prepare correctly). Echo the input and any defaults onto the output; make the output self-explanatory.
At the heart of the method of simulated annealing is an analogy with thermodynamics, specifically with the way that liquids freeze and crystalize, or metals cool and anneal. At hight temperatures, the molecules of a liquid move freely with respect to one another. If the liquid is cooled slowly, thermal mobility is lost. The atoms are often able to line themselves up and form a pure crystal that is completely ordered over a discance up to billions of times the size of an individual atom in all directions. This crystal is in a state of minimum energy for this system. The amazin fact is that, for slowly cooled systems, nature is able to find this minimum energy state. In fact, if a liquid metal is colled quickly of "quenched," it does not reach this state but rather ends up in a polycrystalline or amorphous state having somewhat higher energy.
So the essence of the process is slow cooling, allowing ample time for redistribution of the atoms as they lose mobility. This is the technical definition of annealing, and it is essential for ensuring that a low energy state is achieved.
Although the analogy is not perfect, there is a sense in which [many algorithms] correspond to rapid cooling or quencying. In all cases, we have gone greedily for the quick, nearby solution: from the starting point, go immediately downhill as far as you can go. This, as often remarked above, leads to a local, but not necessarily a global, minimum.
delete() and
fewestPredecessors() n times, where n
is the number of nodes in the graph.
delete() is likely to take time proportional to the
number of edges incident to the deleted node.
fewestPredecessors() is likely to take O(n) time
in a graph structure not optimized for this operation.
delete()s will then be O(m),
where m is the number of edges in the graph.
fewestPredecessors() will then be
O(n^2).
fewestPredecessors()
take less time by using a heap, it turns out that this isn't as good
a solution as it might seem because we need to update the predecessor
count of a number of nodes each time we delete a node.
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
Source text last modified Wed Dec 3 13:10:38 1997.
This page generated on Wed Dec 3 13:12:24 1997 by SiteWeaver.
Contact our webmaster at rebelsky@math.grin.edu