Re: Topological Sort Help

[Ludovic Brenta <ludovic@ludovic-brenta.org>]

isaac2004 writes:
> hello i am trying to further my knowledge of graphs and i keep running
> into this function called topological sort. i read the definition and
> somewhat understand it as a function that does the following
>
> 1. searches for a directed cycle
> 2. sorts vertices of a graph in order onto a stack or array of some
> type so the nodes can be popped in order
>
> so my questions are
>
> are these reasonable thoughts on this algorithm

Have you read [1] http://en.wikipedia.org/wiki/Topological_sort ?

The first algorithm explained works the other way: it sorts the nodes
first, and removes edges from the graph as it goes.  If there are
edges remaining after the sort, then the graph has a cycle and cannot
be sorted.

In fact, how are you going to find cycles in a graph without doing a
topological sort? :)

> how would i write up an algorithm of this nature, would it be just
> like traversing down a list and adding elements to a stack. thanks
> for any help

The first step is to devise a representation of the graph as a data
structure.  In a directed graph, there are nodes and edges; each edge
links two nodes and has a direction. One naive way of representing
such a graph is with a two-dimensional array of Booleans, where
Graph(X, Y) is True iff there is an edge from X to Y.  But that
representation does not scale well to many nodes, so you may have to
create a more memory-efficient data structure if your problem warrants
that.

I suggest you start with the naive representation first, write your
algorithm, and then change the data structure if you run into memory
problems.

HTH

-- 
Ludovic Brenta.