* Topological Sort Help @ 2007-02-04 19:54 isaac2004 2007-02-04 21:45 ` Ludovic Brenta 2007-02-10 8:37 ` s053914 0 siblings, 2 replies; 20+ messages in thread From: isaac2004 @ 2007-02-04 19:54 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-04 19:54 Topological Sort Help isaac2004 @ 2007-02-04 21:45 ` Ludovic Brenta 2007-02-05 20:30 ` isaac2004 2007-02-10 8:37 ` s053914 1 sibling, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-04 21:45 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-04 21:45 ` Ludovic Brenta @ 2007-02-05 20:30 ` isaac2004 2007-02-05 20:39 ` Ludovic Brenta 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-05 20:30 UTC (permalink / raw) On Feb 4, 1:45 pm, Ludovic Brenta <ludo...@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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-05 20:30 ` isaac2004 @ 2007-02-05 20:39 ` Ludovic Brenta 2007-02-06 2:18 ` isaac2004 0 siblings, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-05 20:39 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-05 20:39 ` Ludovic Brenta @ 2007-02-06 2:18 ` isaac2004 2007-02-06 9:06 ` Ludovic Brenta 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-06 2:18 UTC (permalink / raw) "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...@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. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-06 2:18 ` isaac2004 @ 2007-02-06 9:06 ` Ludovic Brenta 2007-02-08 1:19 ` isaac2004 0 siblings, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-06 9:06 UTC (permalink / raw) On Feb 6, 3:18 am, "isaac2004" wrote: > "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 It is my policy not to do students' assignments for them. That would be a disservice, as the purpose of assignments is to make students think and work; that's the only real way of learning. So far, apart from searching "online" and asking questions here, you have not shown evidence of doing any actual work. I will help you with specific questions when you post your program and explain the part you don't understand. In the mean time, you would be better advised to ask your teacher - it's their job to help you understand the basics. If you are not a student, my apologies. -- Ludovic Brenta. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-06 9:06 ` Ludovic Brenta @ 2007-02-08 1:19 ` isaac2004 2007-02-08 9:25 ` Ludovic Brenta 2007-02-08 18:38 ` Jeffrey R. Carter 0 siblings, 2 replies; 20+ messages in thread From: isaac2004 @ 2007-02-08 1:19 UTC (permalink / raw) the topological sort that i am trying to accomplish from this structure will follow the algorithm that i have created from others(its pretty much the same) the problem is im having trouble setting up the while loop to traverse the array of digraph information PROCEDURE Topological_Sort ( G : IN Digraph; Result : OUT Stackpointer; Hascycle : OUT Boolean) IS S : Set; BEGIN -- WHILE IsEmpty(G) /= False DO -- S := set of all vertices in V who have no sucessors -- if S is empty -- hascycle := true; -- return hascycle -- end if -- take the greatest element e in S -- push e onto a stack -- remove all edge in E that have e as a destination -- remove e from v -- end loop this is the algorithm i have, the while loop makes sure the graph is not a cycle(if it does that kicks out) if there is no cycle it takes the vertes with no sucessors and adds it to a stack. is this setup possible, if so setting up the if statement nested for loops is throwing me off, i have functions like FUNCTION IsStronglyConnected ( G : Digraph) RETURN Boolean IS EdgeSet : Set; VertexSet : Set; BEGIN FOR I IN G'RANGE LOOP VertexSet := VertexSet + Character(I); FOR J IN G'RANGE LOOP IF G(I,J) = True AND I /= J THEN EdgeSet := EdgeSet + Character(J); END IF; END LOOP; END LOOP; IF VertexSet <= EdgeSet THEN RETURN True; ELSE RETURN False; END IF; END IsStronglyConnected; that checks connectivity of the graph and this is the style i have been using. can i get any help with the top sort. thanks so much any advice would be great On Feb 6, 1:06 am, "Ludovic Brenta" <ludo...@ludovic-brenta.org> wrote: > On Feb 6, 3:18 am, "isaac2004" wrote: > > > "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 > > It is my policy not to do students' assignments for them. That would > be a disservice, as the purpose of assignments is to make students > think and work; that's the only real way of learning. So far, apart > from searching "online" and asking questions here, you have not shown > evidence of doing any actual work. I will help you with specific > questions when you post your program and explain the part you don't > understand. In the mean time, you would be better advised to ask your > teacher - it's their job to help you understand the basics. > > If you are not a student, my apologies. > > -- > Ludovic Brenta. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 1:19 ` isaac2004 @ 2007-02-08 9:25 ` Ludovic Brenta 2007-02-08 18:14 ` isaac2004 2007-02-08 18:38 ` Jeffrey R. Carter 1 sibling, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-08 9:25 UTC (permalink / raw) isaac2004 writes: > the topological sort that i am trying to accomplish from this > structure will follow the algorithm that i have created from > others(its pretty much the same) the problem is im having trouble > setting up the while loop to traverse the array of digraph > information OK, at this point it would make more sense if you would post your entire program. Without the type definitions for Set, Digraph, and Stackpointer, there is little anyone can do. Also we'd need the definitions of operations on those types. So, post your entire program. > PROCEDURE Topological_Sort ( > G : IN Digraph; > Result : OUT Stackpointer; > Hascycle : OUT Boolean) IS > > S : Set; > BEGIN > -- WHILE IsEmpty(G) /= False DO You should simply write 'while not IsEmpty (G) do'. > -- S := set of all vertices in V who have > no sucessors What is V? > -- if S is empty > -- hascycle := true; > -- return hascycle Jusr "return". This is a procedure, not a function. > -- end if > -- take the greatest element e in S Which assumes an ordering relationship between elements of S. Please define function "<" (Left, Right : in Element) whatever Element is (presumably Vertex?). > -- push e onto a stack I see you already have a type Set which looks like a stack, so I assume that's the type you want to use here? > -- remove all edge in E that have e as a destination What is E? The stack? > -- remove e from v > -- end loop > > this is the algorithm i have, the while loop makes sure the graph is > not a cycle(if it does that kicks out) if there is no cycle it takes > the vertes with no sucessors and adds it to a stack. is this setup > possible, if so setting up the if statement nested for loops is > throwing me off, i have functions like > > FUNCTION IsStronglyConnected ( > G : Digraph) > RETURN Boolean IS > EdgeSet : Set; > VertexSet : Set; > BEGIN > FOR I IN G'RANGE LOOP > VertexSet := VertexSet + Character(I); Why do you convert I to a Character? Do you think that a node is a Character? Also, there appears to be a function "+" (Left : in Set; Right : in Character) return Set; which we know nothing about. Please post your entire program. > FOR J IN G'RANGE LOOP > IF G(I,J) = True AND I /= J THEN Better write 'if G (I, J) and I /= J then' > EdgeSet := EdgeSet + Character(J); > END IF; > END LOOP; > END LOOP; > IF VertexSet <= EdgeSet THEN > RETURN True; > ELSE > RETURN False; > END IF; Better write 'return VertexSet <= EdgeSet'. Also, there appears to be a function "<=" (Left, Right : in Set) return Boolean; which is not defined. Please post your entire program. > END IsStronglyConnected; > > that checks connectivity of the graph and this is the style i have > been using. can i get any help with the top sort. thanks so much any > advice would be great -- Ludovic Brenta. Because it's messing up the reading order. >Why? >>Please stop top-posting. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 9:25 ` Ludovic Brenta @ 2007-02-08 18:14 ` isaac2004 2007-02-08 18:24 ` Ludovic Brenta 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-08 18:14 UTC (permalink / raw) ok there is a lot of code here because i am using generic packages from an ADA book that i purchased so here goes. the first program is the digraph .adb that contains functions to show properties of a graph PACKAGE BODY Digraphs IS -- non-exported helper routines 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; -----------------------------helper functions FUNCTION IsAdjacent ( G : Digraph; A, B : Vertices) RETURN Boolean IS BEGIN RETURN G(A,B); END IsAdjacent; PROCEDURE Cycle ( G : IN Digraph; E : IN OUT Digraph; Visited : IN OUT Set; Row : IN OUT Vertices; Value : OUT Boolean) IS BEGIN IF IsIn (Visited,Row) THEN Value := True; END IF; FOR Col IN G'RANGE LOOP IF IsAdjacent(G,Row,Col) THEN IF IsIn(Visited, Row) = False THEN Visited := Visited + Row; END IF; DeleteEdge(E,Row,Col); Row := Col; Cycle(G,E,Visited,Row,Value); END IF; END LOOP; FOR I IN Row..G'Last LOOP FOR Col IN G'RANGE LOOP IF IsAdjacent(G,Row,Col) THEN IF IsIn(Visited, Row) = False THEN Visited := Visited + Row; END IF; DeleteEdge(E,Row,Col); Row := Col; Cycle(G,E,Visited,Row,Value); END IF; END LOOP; END LOOP; END Cycle; FUNCTION IsEmpty ( G : Digraph) RETURN Boolean IS BEGIN FOR I IN G'RANGE LOOP FOR J IN G'RANGE LOOP IF G(I,J) = True THEN RETURN False; END IF; END LOOP; END LOOP; RETURN True; END IsEmpty; ---------------------------------- -- modifiers PROCEDURE AddEdge ( G : IN OUT Digraph; Source, Destination : IN Vertices) IS BEGIN G(Source, Destination) := True; END AddEdge; PROCEDURE DeleteEdge ( G : IN OUT Digraph; Source, Destination : IN Vertices) IS BEGIN G(Source, Destination) := False; END DeleteEdge; -- accessors FUNCTION IsReflexive ( G : Digraph) RETURN Boolean IS BEGIN FOR I IN G'RANGE LOOP IF G(I,I)= False THEN RETURN False; END IF; END LOOP; RETURN True; END IsReflexive; FUNCTION IsIrreflexive ( G : Digraph) RETURN Boolean IS BEGIN -- stub FOR I IN G'RANGE LOOP IF G(I,I) = True THEN RETURN False; END IF; END LOOP; RETURN True; END IsIrreflexive; FUNCTION IsSymmetric ( G : Digraph) RETURN Boolean IS BEGIN FOR I IN G'RANGE LOOP FOR J IN G'RANGE LOOP IF G(I,J) = True THEN IF G(J,I) /= True THEN RETURN False; END IF; END IF; END LOOP; END LOOP; RETURN True; END IsSymmetric; FUNCTION IsAntisymmetric ( G : Digraph) RETURN Boolean IS BEGIN FOR I IN G'RANGE LOOP FOR J IN G'RANGE LOOP IF G(I,J) = True THEN IF G(J,I) = True AND I /= J THEN RETURN False; END IF; END IF; END LOOP; END LOOP; RETURN True; END IsAntisymmetric; FUNCTION Istransitive ( G : Digraph) RETURN Boolean IS BEGIN -- stub FOR I IN G'RANGE LOOP FOR J IN G'RANGE LOOP FOR K IN G'RANGE LOOP IF G(K,J) /= (G(K,J) AND (G(K,I) AND G(I,J))) THEN RETURN False; END IF; END LOOP; END LOOP; END LOOP; RETURN True; END Istransitive; FUNCTION Isconnected ( G : IN Digraph) RETURN Boolean IS EdgeSet : Set; VertexSet : Set; BEGIN FOR I IN G'RANGE LOOP VertexSet := VertexSet + Character(I); FOR J IN G'RANGE LOOP IF G(I,J) = True AND I /= J THEN EdgeSet := EdgeSet + Character(J); END IF; END LOOP; END LOOP; IF VertexSet = EdgeSet THEN RETURN True; ELSE RETURN False; END IF; END Isconnected; FUNCTION IsStronglyConnected ( G : Digraph) RETURN Boolean IS EdgeSet : Set; VertexSet : Set; BEGIN FOR I IN G'RANGE LOOP VertexSet := VertexSet + Character(I); FOR J IN G'RANGE LOOP IF G(I,J) = True AND I /= J THEN EdgeSet := EdgeSet + Character(J); END IF; END LOOP; END LOOP; IF VertexSet <= EdgeSet THEN RETURN True; ELSE RETURN False; END IF; END IsStronglyConnected; FUNCTION HasCycle ( G : Digraph) RETURN Boolean IS Value : Boolean := False; E : Digraph := G; Visited : Set; Row : Character := 'A'; BEGIN FOR I IN G'RANGE LOOP FOR J IN G'RANGE LOOP IF I = J AND IsAdjacent(G,I,J) THEN RETURN True; END IF; END LOOP; END LOOP; Cycle(G,E,Visited,Row,Value); IF Value = True THEN RETURN True; ELSE RETURN False; END IF; END Hascycle; PROCEDURE Dfs_Spanningtree ( G : IN Digraph; Startnode : IN Vertices; D : OUT Digraphpointer; Visited : OUT Set) IS -- V1 Source : Vertices; -- Q : Vertex_Queue.Queue BEGIN -- stub D:= NEW Digraph'(Buildmatrix(G'Length)); Source := Startnode; Visited := Visited + Source; FOR Dest IN G'RANGE LOOP IF Isadjacent (G, Source, Dest) AND NOT Isin(Visited, Dest) THEN Visited := Visited + Dest; Addedge(D.All, Source, Dest); Dfs_Spanningtree(G,Dest,D,Visited); END IF; end loop; END Dfs_Spanningtree; PROCEDURE Bfs_Spanningtree ( G : IN Digraph; Startnode : IN Vertices; B : OUT Digraphpointer; Visited : OUT Set) IS V1, S : Vertices; Q : Vertex_Queue.Queue(Capacity => Vertices'Pos(Vertices'Last) - Vertices'Pos(Vertices'First) + 1); BEGIN -- stub B := NEW Digraph'(Buildmatrix(G'Length)); Makeempty(Q); V1 := Startnode; Visited := Visited + V1; Enqueue(Q, V1); WHILE NOT Isempty (Q) loop S:= First(Q); Dequeue(Q); FOR I IN G'Range LOOP IF Isadjacent (G, S, I) AND NOT IsIN (Visited, I) THEN Addedge(B.All, S, I); Visited := Visited + I; enqueue(Q, I); END IF; END LOOP; END LOOP; -- NULL; END Bfs_Spanningtree; --PROCEDURE AddToEnd ( -- L : IN OUT List; -- Word : IN WordType ) IS -- Temp : List; -- BEGIN -- Temp := NEW ListNode; -- Temp.Word := Word; -- Temp.Next := L; -- Temp.Prev := L.Prev; -- Temp.Next.Prev := Temp; -- Temp.Prev.Next := Temp; -- END AddToEnd; -- PROCEDURE Topological_Sort ( G : IN Digraph; Result : OUT Stackpointer; Hascycle : OUT Boolean) IS S : Set; BEGIN -- WHILE IsEmpty(G) /= False DO -- S := set of all vertices in V who have no sucessors -- if S is empty -- hascycle := true; -- return hascycle -- end if -- take the greatest element e in S -- push e onto a stack -- remove all edge in E that have e as a destination -- remove e from v -- end loop NULL; END Topological_Sort; -- actions PROCEDURE Displaygraph ( G : Digraph; Present : Set := - Phi) IS BEGIN Put(" "); FOR J IN G'RANGE(2) LOOP Put(Character(J)); END LOOP; New_Line; FOR I IN G'RANGE(1) LOOP Put(Character(I)); Put(" "); FOR J IN G'RANGE(2) LOOP IF Isin(Present,I) AND Isin(Present,J) THEN IF G(I,J) = True THEN Put("T"); ELSE Put("F"); END IF; ELSE Put(" "); END IF; END LOOP; New_Line; END LOOP; END Displaygraph; END Digraphs; there is a sets generic package that i implement PACKAGE BODY Sets_Generic IS FUNCTION "+" (S : Set; E: Universe) RETURN Set IS Result : Set := S; BEGIN Result.Store(E) := True; RETURN Result; END "+"; FUNCTION "-" (S : Set; E: Universe) RETURN Set IS Result : Set := S; BEGIN Result.Store(E) := False; RETURN Result; END "-"; FUNCTION Single ton (E: Universe) RETURN Set IS BEGIN RETURN Phi + E; END Singleton; FUNCTION "+" (E1, E2: Universe) RETURN Set IS BEGIN RETURN Phi + E1 + E2; END "+"; FUNCTION "+" (S, T : Set) RETURN Set IS Result : Set; BEGIN FOR E IN Universe LOOP Result.Store(E) := S.Store(E) OR T.Store(E); END LOOP; RETURN Result; END "+"; FUNCTION "*" (S, T : Set) RETURN Set IS Result : Set; BEGIN FOR E IN Universe LOOP Result.Store(E) := S.Store(E) AND T.Store(E); END LOOP; RETURN Result; END "*"; FUNCTION "-" (S, T : Set) RETURN Set IS Result : Set; BEGIN FOR E IN Universe LOOP Result.Store(E) := S.Store(E) AND NOT T.Store(E); END LOOP; RETURN Result; END "-"; FUNCTION "-" (S : Set) RETURN Set IS Result : Set; BEGIN FOR E IN Universe LOOP Result.Store(E) := NOT S.Store(E); END LOOP; RETURN Result; END "-"; -- selectors FUNCTION IsIn (S: Set; E: Universe) RETURN Boolean IS BEGIN RETURN S.Store(E); END IsIn; FUNCTION IsEmpty (S: Set) RETURN Boolean IS BEGIN RETURN S = Phi; END IsEmpty; FUNCTION SizeOf (S: Set) RETURN Natural IS Result : Natural := 0; BEGIN FOR E IN Universe LOOP IF S.Store(E) THEN Result := Result + 1; END IF; END LOOP; RETURN Result; END SizeOf; FUNCTION "<=" (S, T : Set) RETURN Boolean IS BEGIN FOR E IN Universe LOOP IF S.Store(E) AND NOT T.Store(E) THEN RETURN False; END IF; END LOOP; RETURN True; END "<="; FUNCTION "<" (S, T : Set) RETURN Boolean IS BEGIN RETURN S /= T AND THEN S <= T; END "<"; END Sets_Generic; also there is a stacks generic package that is used PACKAGE BODY Stacks_Generic IS PROCEDURE MakeEmpty (S : IN OUT Stack) IS BEGIN S.latest := 0; END MakeEmpty; FUNCTION IsEmpty (S : IN Stack) RETURN Boolean IS BEGIN RETURN S.Latest = 0; END IsEmpty; FUNCTION IsFull (S : IN Stack) RETURN Boolean IS BEGIN RETURN S.Latest = S.Capacity; END IsFull; PROCEDURE Push (S : IN OUT Stack; E : IN Element) IS BEGIN IF IsFull (S) THEN RAISE StackFull; ELSE S.Latest := S.Latest + 1; S.Store (S.Latest) := E; END IF; END Push; PROCEDURE Pop (S : IN OUT Stack) IS BEGIN IF IsEmpty (S) THEN RAISE StackEmpty; ELSE S.Latest := S.Latest - 1; END IF; END Pop; FUNCTION Top (S : IN Stack) RETURN Element IS BEGIN IF IsEmpty (S) THEN RAISE StackEmpty; ELSE RETURN S.Store (S.Latest); END IF; END Top; END Stacks_Generic; and that are all the packages that need to be used for the top sort function the algorithm in the function body is a psuedo code algorithm because i am unfamiliar how to implement it in ada. thanks for all the help ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 18:14 ` isaac2004 @ 2007-02-08 18:24 ` Ludovic Brenta 2007-02-08 18:29 ` isaac2004 0 siblings, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-08 18:24 UTC (permalink / raw) You seem to have forgotten to send the specs (package X is...), you just sent the bodies. -- Ludovic Brenta. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 18:24 ` Ludovic Brenta @ 2007-02-08 18:29 ` isaac2004 2007-02-08 18:54 ` Ludovic Brenta 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-08 18:29 UTC (permalink / raw) On Feb 8, 10:24 am, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote: > You seem to have forgotten to send the specs (package X is...), you > just sent the bodies. > > -- > Ludovic Brenta. sorry even more code here it goes here is the sec for digraphs WITH Ada.Text_IO; USE Ada.Text_IO; WITH Ada.Integer_Text_IO; USE Ada.Integer_Text_IO; WITH Sets_Generic; WITH Stacks_Generic; WITH Queues_Generic; WITH Ada.Unchecked_Deallocation; PACKAGE Digraphs IS SUBTYPE Vertices IS Character RANGE 'A' .. 'Z'; TYPE Digraph IS ARRAY (Vertices RANGE <>, Vertices RANGE <>) OF Boolean; PACKAGE Vertex_Text_IO IS NEW Enumeration_IO(Vertices); PACKAGE Vertex_Set IS NEW Sets_Generic(Vertices); USE Vertex_Set; PACKAGE Vertex_Stack IS NEW Stacks_Generic(Vertices); USE Vertex_Stack; PACKAGE Vertex_Queue IS NEW Queues_Generic(Vertices); USE Vertex_Queue; TYPE DigraphPointer IS ACCESS Digraph; TYPE StackPointer IS ACCESS Stack; -- constructor FUNCTION CreateGraph (InputFile : String) RETURN DigraphPointer; -- Pre: InputFile is the name of graph file to be loaded -- Post: Returns a pointer to digraph dynamically created according -- to the specification in InputFile -- (see assignment description for details) -- destructors PROCEDURE Dispose IS NEW Ada.Unchecked_Deallocation(Digraph,DigraphPointer); PROCEDURE Dispose IS NEW Ada.Unchecked_Deallocation(Stack,StackPointer); -- Call: Dispose(X) -- Pre: X points to a dynamically allocated digraph / stack, respectively -- Post: X's memory is release back to the pool -- modifiers PROCEDURE AddEdge (G: IN OUT Digraph; Source, Destination: IN Vertices); PROCEDURE DeleteEdge (G: IN OUT Digraph; Source, Destination: IN Vertices); -- Pre: G, Source, and Destination are defined -- Post: returns G with the edge <Source, Destination> added or -- deleted respectively; AddEdge has no effect if the edge is -- already in G; DeleteEdge has no effect if the edge is not in G -- accessors FUNCTION IsReflexive (G : Digraph) RETURN Boolean; FUNCTION IsIrreflexive (G : Digraph) RETURN Boolean; FUNCTION IsSymmetric (G : Digraph) RETURN Boolean; FUNCTION IsAntisymmetric (G : Digraph) RETURN Boolean; FUNCTION IsTransitive (G : Digraph) RETURN Boolean; FUNCTION IsConnected (G : Digraph) RETURN Boolean; FUNCTION IsStronglyConnected (G : Digraph) RETURN Boolean; FUNCTION HasCycle(G : Digraph) RETURN Boolean; -- Pre: G is defined -- Post: returns True iff G has the property PROCEDURE DFS_SpanningTree (G : IN Digraph; StartNode : IN Vertices; D : OUT DigraphPointer; Visited : OUT Set); PROCEDURE BFS_SpanningTree (G : IN Digraph; StartNode : IN Vertices; B : OUT DigraphPointer; Visited : OUT Set); -- Pre: G, V are defined -- Post: Allocates a new digraph that holds the depth/breadth-first -- search minimum spanning trees, respectively, returning a pointer in D/B -- Returns the (sub)set of vertices present in this digraph in Visited PROCEDURE Topological_Sort (G: IN Digraph; Result : OUT StackPointer; HasCycle : OUT Boolean); -- Pre: G is defined -- Post: Either -- a) finds a directed cycle, and sets HasCycle to True or -- b) topologically sorts the vertices of G, storing them in a -- stack such that nodes will be popped in sorted order -- the "first" or "smallest" unordered node must come first (e.g. C before E) -- (see assignment description for details) -- actions PROCEDURE DisplayGraph (G: Digraph; Present : Set := -Phi ); -- Pre: G is defined, Set optionally defined -- Post: displays G in matrix form using T or F -- for presence or absence of edge -- for all vertices in Set (allows you to print subgraphs) -- by default, Set is all vertices (complement of empty set) -- and so the entire graph is printed END Digraphs; spec for stacks_generic GENERIC TYPE Element IS PRIVATE; PACKAGE Stacks_Generic IS -------------------------------------------------------------------------------- --| Specification for Generic Stacks Package, Array Implementation --| Author: Micahel B. Feldman, The George Washington University --| Last Modified: October 1995 -------------------------------------------------------------------------------- -- type definition TYPE Stack (Capacity : Positive) IS LIMITED PRIVATE; -- exported exceptions StackFull : EXCEPTION; StackEmpty : EXCEPTION; PROCEDURE MakeEmpty (S : IN OUT Stack); -- Pre: S is defined -- Post: S is empty PROCEDURE Push (S : IN OUT Stack; E : IN Element); -- Pre: S and E are defined -- Post: S is returned with E as the top element -- Raises: StackFull if S already contains Capacity elements PROCEDURE Pop (S : IN OUT Stack ); -- Pre: S is defined -- Post: S is returned with the top element discarded -- Raises: StackEmpty if S contains no elements -- selector FUNCTION Top (S : IN Stack) RETURN Element; -- Pre: S is defined -- Post: The top element of S is returned -- Raises: StackEmpty if S contains no elements -- inquiry operations FUNCTION IsEmpty ( S : IN Stack) RETURN Boolean; -- Pre: S is defined -- Post: returns True if S is empty, False otherwise FUNCTION IsFull ( S : IN Stack) RETURN Boolean; -- Pre: S is defined -- Post: returns True if S is full, False otherwise PRIVATE TYPE List IS ARRAY (Positive RANGE <>) OF Element; TYPE Stack (Capacity : Positive) IS RECORD Latest : Natural := 0; Store : List(1 .. Capacity); END RECORD; END Stacks_Generic; spec for sets_generic GENERIC TYPE Universe IS (<>); -- discrete type PACKAGE Sets_Generic IS -------------------------------------------------------------------------------- --| Specification for sets over discrete universes --| Author: Micahel B. Feldman, The George Washington University --| Last Modified: October 1995 -------------------------------------------------------------------------------- TYPE Set is PRIVATE; Phi: CONSTANT Set; -- empty set -- constructors FUNCTION "+" (S: Set; E: Universe) RETURN Set; FUNCTION "-" (S: Set; E: Universe) RETURN Set; -- Pre: S and E are defined -- Post: returns S with E inserted or deleted respectively FUNCTION Singleton (E: Universe) RETURN Set; FUNCTION "+" (E1, E2: Universe) RETURN Set; -- Pre: E, E1, and E2 are defined -- Post: returns a set made from one or two elements FUNCTION "+" (S, T: Set) RETURN Set; FUNCTION "*" (S, T: Set) RETURN Set; FUNCTION "-" (S, T: Set) RETURN Set; -- Pre: S and T are defined -- Post: Returns the union, intersection and difference of -- S and T, respectively FUNCTION "-" (S : Set) RETURN Set; -- Pre: S is defined -- Post: returns the complement of S -- selectors FUNCTION IsIn (S: Set; E: Universe) RETURN Boolean; -- Pre: S and E are defined -- Post: returns True iff E is a member of S FUNCTION IsEmpty (S: Set) RETURN Boolean; -- Pre: S is defined -- Post: returns True iff S is empty FUNCTION SizeOf (S: Set) RETURN Natural; -- Pre: S is defined -- Post: returns the number of members in S FUNCTION "<=" (S, T: Set) RETURN Boolean; FUNCTION "<" (S, T: Set) RETURN Boolean; -- Pre: S and T are defined -- Post: returns True iff if S is -- an improper or proper subset of T, respectively PRIVATE TYPE SetArray IS ARRAY (Universe) OF Boolean; TYPE Set IS RECORD Store: SetArray := (OTHERS => False); END RECORD; Phi: CONSTANT Set := (Store => (OTHERS => False)); END Sets_Generic; if there is anyhting else you need, please tell me ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 18:29 ` isaac2004 @ 2007-02-08 18:54 ` Ludovic Brenta 2007-02-08 19:14 ` isaac2004 0 siblings, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-08 18:54 UTC (permalink / raw) isaac2004 writes: > FUNCTION CreateGraph (InputFile : String) RETURN DigraphPointer; > -- Pre: InputFile is the name of graph file to be loaded > -- Post: Returns a pointer to digraph dynamically created according > -- to the specification in InputFile > -- (see assignment description for details) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ So I was correct, and this is really an assignment. Your teacher may very well be reading this newsgroup. > PROCEDURE Topological_Sort (G: IN Digraph; Result : OUT StackPointer; > HasCycle : OUT Boolean); > -- Pre: G is defined > -- Post: Either > -- a) finds a directed cycle, and sets HasCycle to True or > -- b) topologically sorts the vertices of G, storing them in a > -- stack such that nodes will be popped in sorted order > -- the "first" or "smallest" unordered node must come first (e.g. C > before E) > -- (see assignment description for details) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Ditto. Now I can see the data structures you use, and I understand at last the confusion between vertices and characters; it is because of: SUBTYPE Vertices IS Character RANGE 'A' .. 'Z'; OK. Now, please post your new implementation of Topological_Sort after taking into account my earlier comments: - what is V? - what is E? The other questions have their answers in the specs you just posted. I repeat that I will not do your assignment for you; but I may answer precise questions on particular points of your code. However, here is a small hint: procedure Topological_Sort (G : in Digraph; Result : out Stackpointer; HasCycle : out Boolean) is Sorted_Vertices := new Vertex_Stack.Stack (Capacity => G'Length (1)); -- Allocate a stack of N vertices, N being the number of vertices in G. begin Do_The_Sort: loop ... if there_is_a_cycle then HasCycle := True; -- do not touch Result else HasCycle := False; Result := Sorted_Vertices; return; end if; end loop Do_The_Sort; end Topological_Sort; I think I've already said too much. -- Ludovic Brenta. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 18:54 ` Ludovic Brenta @ 2007-02-08 19:14 ` isaac2004 2007-02-08 19:27 ` Ludovic Brenta 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-08 19:14 UTC (permalink / raw) On Feb 8, 10:54 am, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote: > isaac2004 writes: > > FUNCTION CreateGraph (InputFile : String) RETURN DigraphPointer; > > -- Pre: InputFile is the name of graph file to be loaded > > -- Post: Returns a pointer to digraph dynamically created according > > -- to the specification in InputFile > > -- (see assignment description for details) > > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > > So I was correct, and this is really an assignment. Your teacher may > very well be reading this newsgroup. > > > PROCEDURE Topological_Sort (G: IN Digraph; Result : OUT StackPointer; > > HasCycle : OUT Boolean); > > -- Pre: G is defined > > -- Post: Either > > -- a) finds a directed cycle, and sets HasCycle to True or > > -- b) topologically sorts the vertices of G, storing them in a > > -- stack such that nodes will be popped in sorted order > > -- the "first" or "smallest" unordered node must come first (e.g. C > > before E) > > -- (see assignment description for details) > > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > > Ditto. > > Now I can see the data structures you use, and I understand at last > the confusion between vertices and characters; it is because of: > > SUBTYPE Vertices IS Character RANGE 'A' .. 'Z'; > > OK. Now, please post your new implementation of Topological_Sort > after taking into account my earlier comments: > > - what is V? > - what is E? > > The other questions have their answers in the specs you just posted. > > I repeat that I will not do your assignment for you; but I may answer > precise questions on particular points of your code. However, here is > a small hint: > > procedure Topological_Sort (G : in Digraph; > Result : out Stackpointer; > HasCycle : out Boolean) is > > Sorted_Vertices := new Vertex_Stack.Stack (Capacity => G'Length (1)); > -- Allocate a stack of N vertices, N being the number of vertices in G. > begin > Do_The_Sort: loop > ... > if there_is_a_cycle then > HasCycle := True; > -- do not touch Result > else > HasCycle := False; > Result := Sorted_Vertices; > return; > end if; > end loop Do_The_Sort; > end Topological_Sort; > > I think I've already said too much. > > -- > Ludovic Brenta. thank you very much i understand i am not asking for code, just help with my implementation, V and E are psuedo variables for an edge and a vertex of a graph, how the algorithm is supposed to work is by parsing through the entire matrix, and checking for any vertex(V) that has no sucessors(ie no children) when one is found, it is thrown onto a stack that holds the order of the verrtexs with least successors. this loop then continues through until all vertex are put on the stack, having a topological sort. a conditional is set if there are no vertexes with successors (a cycle) and that is the algorithm, thanks for all the, now i juts need to set up a looping conditional setup that checks if there are no out edges from a vertex. does this sound right? ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 19:14 ` isaac2004 @ 2007-02-08 19:27 ` Ludovic Brenta 2007-02-08 20:22 ` isaac2004 0 siblings, 1 reply; 20+ messages in thread From: Ludovic Brenta @ 2007-02-08 19:27 UTC (permalink / raw) isaac2004 writes: > thank you very much i understand i am not asking for code, just help > with my implementation, V and E are psuedo variables for an edge and > a vertex of a graph, how the algorithm is supposed to work is by > parsing through the entire matrix, and checking for any vertex(V) > that has no sucessors(ie no children) when one is found, it is > thrown onto a stack that holds the order of the verrtexs with least > successors. this loop then continues through until all vertex are > put on the stack, having a topological sort. a conditional is set if > there are no vertexes with successors (a cycle) and that is the > algorithm, thanks for all the, now i juts need to set up a looping > conditional setup that checks if there are no out edges from a > vertex. does this sound right? Yes, that seems about right. Now, consider how the graph is represented: G (I, J) is True if and only if there is an edge from I to J. Now, write function Has_Successors (V : in Vertices; In_Graph : in Digraph) return Boolean; and use it within Topological_Sort. -- Ludovic Brenta. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 19:27 ` Ludovic Brenta @ 2007-02-08 20:22 ` isaac2004 2007-02-09 2:04 ` isaac2004 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-08 20:22 UTC (permalink / raw) On Feb 8, 11:27 am, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote: > isaac2004 writes: > > thank you very much i understand i am not asking for code, just help > > with my implementation, V and E are psuedo variables for an edge and > > a vertex of a graph, how the algorithm is supposed to work is by > > parsing through the entire matrix, and checking for any vertex(V) > > that has no sucessors(ie no children) when one is found, it is > > thrown onto a stack that holds the order of the verrtexs with least > > successors. this loop then continues through until all vertex are > > put on the stack, having a topological sort. a conditional is set if > > there are no vertexes with successors (a cycle) and that is the > > algorithm, thanks for all the, now i juts need to set up a looping > > conditional setup that checks if there are no out edges from a > > vertex. does this sound right? > > Yes, that seems about right. Now, consider how the graph is > represented: G (I, J) is True if and only if there is an edge from I > to J. Now, write > > function Has_Successors (V : in Vertices; In_Graph : in Digraph) > return Boolean; > > and use it within Topological_Sort. > > -- > Ludovic Brenta. a call to another function that is a good idea, my question now is, should this function go through the whole matrix or just one cell in a time and the call just be put in a loop ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 20:22 ` isaac2004 @ 2007-02-09 2:04 ` isaac2004 0 siblings, 0 replies; 20+ messages in thread From: isaac2004 @ 2007-02-09 2:04 UTC (permalink / raw) i created this procedure and it is not working for all possible inputs, can i get some advice on how to change it. notice i havent implemented has cycle yet because i am getting stuck on where to put that PROCEDURE Topological_Sort ( G : IN Digraph; Result : OUT Stackpointer; Hascycle : OUT Boolean) IS B : Digraphpointer; Sucessor : Boolean; V : Set; No_Successors : Set; Bigger_One : Vertices; BEGIN Result := NEW Vertex_Stack.Stack (Capacity => Vertices'Pos (Vertices'Last) - Vertices'Pos (Vertices'First) + 1); B := NEW Digraph'(Buildmatrix(G'Length)); FOR I IN G'RANGE LOOP FOR J IN G'RANGE LOOP IF G(I,J) THEN Addedge(B.All, I, J); END IF; END LOOP; END LOOP; FOR A IN G'RANGE LOOP V := V + A; END LOOP; WHILE NOT Isempty(V) LOOP FOR I IN G'RANGE LOOP Sucessor := False; FOR J IN G'RANGE LOOP IF J /= I THEN IF G(I,J) THEN Sucessor := True; EXIT; END IF; END IF; END LOOP; IF NOT Sucessor THEN No_Successors := No_Successors + I; END IF; END LOOP; FOR L IN REVERSE B'RANGE LOOP IF Isin(No_Successors,L) THEN Bigger_One := L; EXIT; END IF; END LOOP; Push(Result.All, Bigger_One); V := V - Bigger_One; FOR R IN G'RANGE LOOP Deleteedge(B.All, Bigger_One, R); END LOOP; END LOOP; Hascycle := False; END Topological_Sort; thank you so much for the help so far ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 1:19 ` isaac2004 2007-02-08 9:25 ` Ludovic Brenta @ 2007-02-08 18:38 ` Jeffrey R. Carter 2007-02-08 18:53 ` isaac2004 1 sibling, 1 reply; 20+ messages in thread From: Jeffrey R. Carter @ 2007-02-08 18:38 UTC (permalink / raw) isaac2004 wrote: > the topological sort that i am trying to accomplish from this > structure will follow the algorithm that i have created from > others(its pretty much the same) the problem is im having trouble > setting up the while loop to traverse the array of digraph information An easy way to avoid confusing while loops is not to use them. Instead of Name : while Unintuitive_Negative_Logic_For_Loop_Continuation loop use Name : loop exit Name when Intuitive_Positive_Logic_For_Loop_Exit; While loops, with their continuation condition, are generally better if you're doing correctness proofs, but if you're not, using exit conditions is usually clearer and more intuitive. -- Jeff Carter "What I wouldn't give for a large sock with horse manure in it." Annie Hall 42 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 18:38 ` Jeffrey R. Carter @ 2007-02-08 18:53 ` isaac2004 2007-02-09 4:57 ` Jeffrey R. Carter 0 siblings, 1 reply; 20+ messages in thread From: isaac2004 @ 2007-02-08 18:53 UTC (permalink / raw) an exit when makes no sense in this situation because there is no finite stopping condition, if you look at the algorithm provided, i see it harder top implement an exit when loop WHILE IsEmpty(G) /= False DO -- S := set of all vertices in V who have no sucessors -- if S is empty -- hascycle := true; -- return hascycle -- end if -- take the greatest element e in S -- push e onto a stack -- remove all edge in E that have e as a destination -- remove e from v -- end loop if i am wrong please show me an algorithm that would work, thanks On Feb 8, 10:38 am, "Jeffrey R. Carter" <jrcar...@acm.org> wrote: > isaac2004 wrote: > > the topological sort that i am trying to accomplish from this > > structure will follow the algorithm that i have created from > > others(its pretty much the same) the problem is im having trouble > > setting up the while loop to traverse the array of digraph information > > An easy way to avoid confusing while loops is not to use them. Instead of > > Name : while Unintuitive_Negative_Logic_For_Loop_Continuation loop > > use > > Name : loop > exit Name when Intuitive_Positive_Logic_For_Loop_Exit; > > While loops, with their continuation condition, are generally better if > you're doing correctness proofs, but if you're not, using exit > conditions is usually clearer and more intuitive. > > -- > Jeff Carter > "What I wouldn't give for a large sock with horse manure in it." > Annie Hall > 42 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-08 18:53 ` isaac2004 @ 2007-02-09 4:57 ` Jeffrey R. Carter 0 siblings, 0 replies; 20+ messages in thread From: Jeffrey R. Carter @ 2007-02-09 4:57 UTC (permalink / raw) isaac2004 wrote: > an exit when makes no sense in this situation because there is no > finite stopping condition, if you look at the algorithm provided, i > see it harder top implement an exit when loop > > WHILE IsEmpty(G) /= False DO This kind of construct generally indicates the coder doesn't understand the concept of Booleans. There's always an "exit when" equivalent to a while loop. Your loop is equivalent to while Isempty (G) loop which is equivalent to loop exit when not Isempty (G); Note that I'm not dealing with your algorithm here; I'm merely suggesting that if you're having trouble with the condition for continuing the loop, you might find it easier to think in terms of the condition for exiting the loop. -- Jeff Carter "What I wouldn't give for a large sock with horse manure in it." Annie Hall 42 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help 2007-02-04 19:54 Topological Sort Help isaac2004 2007-02-04 21:45 ` Ludovic Brenta @ 2007-02-10 8:37 ` s053914 1 sibling, 0 replies; 20+ messages in thread From: s053914 @ 2007-02-10 8:37 UTC (permalink / raw) yryhrfyhfhygv "isaac2004" <isaac_2004@yahoo.com> ???????:1170618852.885855.258390@j27g2000cwj.googlegroups.com... > 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 > ^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2007-02-10 8:37 UTC | newest] Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2007-02-04 19:54 Topological Sort Help isaac2004 2007-02-04 21:45 ` Ludovic Brenta 2007-02-05 20:30 ` isaac2004 2007-02-05 20:39 ` Ludovic Brenta 2007-02-06 2:18 ` isaac2004 2007-02-06 9:06 ` Ludovic Brenta 2007-02-08 1:19 ` isaac2004 2007-02-08 9:25 ` Ludovic Brenta 2007-02-08 18:14 ` isaac2004 2007-02-08 18:24 ` Ludovic Brenta 2007-02-08 18:29 ` isaac2004 2007-02-08 18:54 ` Ludovic Brenta 2007-02-08 19:14 ` isaac2004 2007-02-08 19:27 ` Ludovic Brenta 2007-02-08 20:22 ` isaac2004 2007-02-09 2:04 ` isaac2004 2007-02-08 18:38 ` Jeffrey R. Carter 2007-02-08 18:53 ` isaac2004 2007-02-09 4:57 ` Jeffrey R. Carter 2007-02-10 8:37 ` s053914
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox