From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,cd5005cccfba0311 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!postnews.google.com!v33g2000cwv.googlegroups.com!not-for-mail From: "isaac2004" Newsgroups: comp.lang.ada Subject: Re: Topological Sort Help Date: 8 Feb 2007 11:14:09 -0800 Organization: http://groups.google.com Message-ID: <1170962049.091400.130220@v33g2000cwv.googlegroups.com> References: <1170618852.885855.258390@j27g2000cwj.googlegroups.com> <87sldllhpt.fsf@ludovic-brenta.org> <1170707421.136089.281290@l53g2000cwa.googlegroups.com> <87y7ncjq4y.fsf@ludovic-brenta.org> <1170728294.194370.133540@k78g2000cwa.googlegroups.com> <1170752808.678318.252960@l53g2000cwa.googlegroups.com> <1170897552.495666.223180@v33g2000cwv.googlegroups.com> <87ps8ldmrw.fsf@ludovic-brenta.org> <1170958478.093428.155250@j27g2000cwj.googlegroups.com> <87wt2scxt0.fsf@ludovic-brenta.org> <1170959388.358591.91380@s48g2000cws.googlegroups.com> <87ejp0cwf5.fsf@ludovic-brenta.org> NNTP-Posting-Host: 140.160.105.171 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-Trace: posting.google.com 1170962054 2521 127.0.0.1 (8 Feb 2007 19:14:14 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Thu, 8 Feb 2007 19:14:14 +0000 (UTC) In-Reply-To: <87ejp0cwf5.fsf@ludovic-brenta.org> User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322; InfoPath.1; .NET CLR 2.0.50727),gzip(gfe),gzip(gfe) Complaints-To: groups-abuse@google.com Injection-Info: v33g2000cwv.googlegroups.com; posting-host=140.160.105.171; posting-account=bWy1LAwAAAAtVkasDCH0ykMCBMNd-FcL Xref: g2news2.google.com comp.lang.ada:9159 Date: 2007-02-08T11:14:09-08:00 List-Id: On Feb 8, 10:54 am, Ludovic Brenta 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?