Re: Topological Sort Help

[Ludovic Brenta <ludovic@ludovic-brenta.org>]

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.