Topological Sort Help

Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[Ludovic Brenta]

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.

Re: Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[Ludovic Brenta]

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.

Re: Topological Sort Help

[isaac2004]

"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.

Re: Topological Sort Help

[Ludovic Brenta]

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.

Re: Topological Sort Help

[isaac2004]

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.

Re: Topological Sort Help

[Ludovic Brenta]

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.

Re: Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[Ludovic Brenta]

You seem to have forgotten to send the specs (package X is...), you
just sent the bodies.

-- 
Ludovic Brenta.

Re: Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[Jeffrey R. Carter]

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

Re: Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[Ludovic Brenta]

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.

Re: Topological Sort Help

[isaac2004]

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?

Re: Topological Sort Help

[Ludovic Brenta]

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.

Re: Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[isaac2004]

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

Re: Topological Sort Help

[Jeffrey R. Carter]

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

Re: Topological Sort Help

[s053914]

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
>