* Topological Sort Help
@ 2007-02-04 19:54 isaac2004
2007-02-04 21:45 ` Ludovic Brenta
2007-02-10 8:37 ` s053914
0 siblings, 2 replies; 20+ messages in thread
From: isaac2004 @ 2007-02-04 19:54 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-04 19:54 Topological Sort Help isaac2004
@ 2007-02-04 21:45 ` Ludovic Brenta
2007-02-05 20:30 ` isaac2004
2007-02-10 8:37 ` s053914
1 sibling, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-04 21:45 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-04 21:45 ` Ludovic Brenta
@ 2007-02-05 20:30 ` isaac2004
2007-02-05 20:39 ` Ludovic Brenta
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-05 20:30 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-05 20:30 ` isaac2004
@ 2007-02-05 20:39 ` Ludovic Brenta
2007-02-06 2:18 ` isaac2004
0 siblings, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-05 20:39 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-05 20:39 ` Ludovic Brenta
@ 2007-02-06 2:18 ` isaac2004
2007-02-06 9:06 ` Ludovic Brenta
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-06 2:18 UTC (permalink / raw)
"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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-06 2:18 ` isaac2004
@ 2007-02-06 9:06 ` Ludovic Brenta
2007-02-08 1:19 ` isaac2004
0 siblings, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-06 9:06 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-06 9:06 ` Ludovic Brenta
@ 2007-02-08 1:19 ` isaac2004
2007-02-08 9:25 ` Ludovic Brenta
2007-02-08 18:38 ` Jeffrey R. Carter
0 siblings, 2 replies; 20+ messages in thread
From: isaac2004 @ 2007-02-08 1:19 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 1:19 ` isaac2004
@ 2007-02-08 9:25 ` Ludovic Brenta
2007-02-08 18:14 ` isaac2004
2007-02-08 18:38 ` Jeffrey R. Carter
1 sibling, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-08 9:25 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 9:25 ` Ludovic Brenta
@ 2007-02-08 18:14 ` isaac2004
2007-02-08 18:24 ` Ludovic Brenta
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-08 18:14 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 18:14 ` isaac2004
@ 2007-02-08 18:24 ` Ludovic Brenta
2007-02-08 18:29 ` isaac2004
0 siblings, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-08 18:24 UTC (permalink / raw)
You seem to have forgotten to send the specs (package X is...), you
just sent the bodies.
--
Ludovic Brenta.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 18:24 ` Ludovic Brenta
@ 2007-02-08 18:29 ` isaac2004
2007-02-08 18:54 ` Ludovic Brenta
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-08 18:29 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 1:19 ` isaac2004
2007-02-08 9:25 ` Ludovic Brenta
@ 2007-02-08 18:38 ` Jeffrey R. Carter
2007-02-08 18:53 ` isaac2004
1 sibling, 1 reply; 20+ messages in thread
From: Jeffrey R. Carter @ 2007-02-08 18:38 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 18:38 ` Jeffrey R. Carter
@ 2007-02-08 18:53 ` isaac2004
2007-02-09 4:57 ` Jeffrey R. Carter
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-08 18:53 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 18:29 ` isaac2004
@ 2007-02-08 18:54 ` Ludovic Brenta
2007-02-08 19:14 ` isaac2004
0 siblings, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-08 18:54 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 18:54 ` Ludovic Brenta
@ 2007-02-08 19:14 ` isaac2004
2007-02-08 19:27 ` Ludovic Brenta
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-08 19:14 UTC (permalink / raw)
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?
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 19:14 ` isaac2004
@ 2007-02-08 19:27 ` Ludovic Brenta
2007-02-08 20:22 ` isaac2004
0 siblings, 1 reply; 20+ messages in thread
From: Ludovic Brenta @ 2007-02-08 19:27 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 19:27 ` Ludovic Brenta
@ 2007-02-08 20:22 ` isaac2004
2007-02-09 2:04 ` isaac2004
0 siblings, 1 reply; 20+ messages in thread
From: isaac2004 @ 2007-02-08 20:22 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 20:22 ` isaac2004
@ 2007-02-09 2:04 ` isaac2004
0 siblings, 0 replies; 20+ messages in thread
From: isaac2004 @ 2007-02-09 2:04 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-08 18:53 ` isaac2004
@ 2007-02-09 4:57 ` Jeffrey R. Carter
0 siblings, 0 replies; 20+ messages in thread
From: Jeffrey R. Carter @ 2007-02-09 4:57 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Topological Sort Help
2007-02-04 19:54 Topological Sort Help isaac2004
2007-02-04 21:45 ` Ludovic Brenta
@ 2007-02-10 8:37 ` s053914
1 sibling, 0 replies; 20+ messages in thread
From: s053914 @ 2007-02-10 8:37 UTC (permalink / raw)
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
>
^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2007-02-10 8:37 UTC | newest]
Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-02-04 19:54 Topological Sort Help isaac2004
2007-02-04 21:45 ` Ludovic Brenta
2007-02-05 20:30 ` isaac2004
2007-02-05 20:39 ` Ludovic Brenta
2007-02-06 2:18 ` isaac2004
2007-02-06 9:06 ` Ludovic Brenta
2007-02-08 1:19 ` isaac2004
2007-02-08 9:25 ` Ludovic Brenta
2007-02-08 18:14 ` isaac2004
2007-02-08 18:24 ` Ludovic Brenta
2007-02-08 18:29 ` isaac2004
2007-02-08 18:54 ` Ludovic Brenta
2007-02-08 19:14 ` isaac2004
2007-02-08 19:27 ` Ludovic Brenta
2007-02-08 20:22 ` isaac2004
2007-02-09 2:04 ` isaac2004
2007-02-08 18:38 ` Jeffrey R. Carter
2007-02-08 18:53 ` isaac2004
2007-02-09 4:57 ` Jeffrey R. Carter
2007-02-10 8:37 ` s053914
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox