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 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!news3.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local01.nntp.dca.giganews.com!nntp.scarlet.biz!news.scarlet.biz.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 08 Feb 2007 12:54:23 -0600
From: Ludovic Brenta <ludovic@ludovic-brenta.org>
Newsgroups: comp.lang.ada
Subject: Re: Topological Sort Help
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>
Date: Thu, 08 Feb 2007 19:54:22 +0100
Message-ID: <87ejp0cwf5.fsf@ludovic-brenta.org>
User-Agent: Gnus/5.110006 (No Gnus v0.6) Emacs/21.4 (gnu/linux)
Cancel-Lock: sha1:ra3lmDvkBR+myI1mgjq7+yvfsag=
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
NNTP-Posting-Host: 62.235.236.165
X-Trace: 
 sv3-nAM2A9YMgfEgrN2v9HPP5PfZeCJPmZEEQovsTURgJ6F69JX5ZtXGP6jEBss2stImDLBQ02uQWWm4GL/!ZRoPYk133pHROtlQ9zrYwErKysGGwcq5D6zfTqCWc2VWvFylhM32lo2K1d2jJNN7lA1QXmKxXVQ=
X-Complaints-To: abuse@scarlet.be
X-DMCA-Complaints-To: abuse@scarlet.biz
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint
 properly
X-Postfilter: 1.3.32
Xref: g2news2.google.com comp.lang.ada:9158
Date: 2007-02-08T19:54:22+01:00
List-Id: <comp.lang.ada>

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.