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!s48g2000cws.googlegroups.com!not-for-mail From: "isaac2004" Newsgroups: comp.lang.ada Subject: Re: Topological Sort Help Date: 8 Feb 2007 10:29:48 -0800 Organization: http://groups.google.com Message-ID: <1170959388.358591.91380@s48g2000cws.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> NNTP-Posting-Host: 140.160.105.171 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-Trace: posting.google.com 1170959395 28299 127.0.0.1 (8 Feb 2007 18:29:55 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Thu, 8 Feb 2007 18:29:55 +0000 (UTC) In-Reply-To: <87wt2scxt0.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: s48g2000cws.googlegroups.com; posting-host=140.160.105.171; posting-account=bWy1LAwAAAAtVkasDCH0ykMCBMNd-FcL Xref: g2news2.google.com comp.lang.ada:9152 Date: 2007-02-08T10:29:48-08:00 List-Id: On Feb 8, 10:24 am, Ludovic Brenta 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 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