Topological Sort Help
in [ADA]
|
From: isaac2004 on 4 Feb 2007 14:54 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 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
From: Ludovic Brenta on 4 Feb 2007 16:45 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.
From: isaac2004 on 5 Feb 2007 15:30 On Feb 4, 1:45 pm, Ludovic Brenta <ludo...(a)ludovic-brenta.org> wrote: > 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. well i have this data structure i found online that builds a matrix from a input file and then creates a graph from the matrix. my goal is to add and delete edges from this structure, that way i can use the top search to just direct pointers. here is the algorithm for the matrix and graph builder FUNCTION BuildMatrix ( Size : Natural ) RETURN Digraph IS G : Digraph( Vertices'First .. Vertices'Val(Vertices'Pos(Vertices'First) + Size - 1), Vertices'First .. Vertices'Val(Vertices'Pos(Vertices'First) + Size - 1)) := (OTHERS => (OTHERS => False)); BEGIN RETURN G; END BuildMatrix; -- constructor FUNCTION CreateGraph (InputFile : String) RETURN DigraphPointer IS Input : File_Type; NumVertices : Natural; G : DigraphPointer; A, B : Vertices; Ac,Bc : Character; BEGIN Open(Input,In_File,InputFile); Get(Input,NumVertices); G := NEW Digraph'(BuildMatrix(NumVertices)); WHILE NOT End_Of_File(Input) LOOP Get(Input,Ac); -- read source node Get(Input,Bc); -- read in space Get(Input,Bc); -- now read destination node A := Vertices(Ac); B := Vertices(Bc); G.all(A,B) := True; END LOOP; Close(Input); RETURN G; END CreateGraph; how would i set up a function to add or delete items from the data structure. thanks
From: Ludovic Brenta on 5 Feb 2007 15:39 isaac2004 writes: > well i have this data structure i found online that builds a matrix > from a input file and then creates a graph from the matrix. my goal is > to add and delete edges from this structure, that way i can use the > top search to just direct pointers. here is the algorithm for the > matrix and graph builder The matrix you "found online" is exactly the naive representation that I described. Knowing that it should be easy for you to understand how to add or remove edges, yes? -- Ludovic Brenta.
From: isaac2004 on 5 Feb 2007 21:18
"fpund online" is right i know the basics of how it works but implementing anything into it is the part im getting stuck at. any help On Feb 5, 12:39 pm, Ludovic Brenta <ludo...(a)ludovic-brenta.org> wrote: > isaac2004 writes: > > well i have this data structure i found online that builds a matrix > > from a input file and then creates a graph from the matrix. my goal is > > to add and delete edges from this structure, that way i can use the > > top search to just direct pointers. here is the algorithm for the > > matrix and graph builder > > The matrix you "found online" is exactly the naive representation that > I described. Knowing that it should be easy for you to understand how > to add or remove edges, yes? > > -- > Ludovic Brenta. |