New to Ada need help implementing Warshall's algorithm

New to Ada need help implementing Warshall's algorithm

[James Brewer]

Hello I hope this is right forum for this question. I have been asked to write a program that implements Warshall's algorithm using Ada. The problem, I have never written an Ada program and I a limited time frame to put this together.
I have have the IDE installed and am in the process of writing some rudimentary programs to familiarize myself with the language but I'm afraid that I may run out of time. 

The input data I have is a series of connections between 7 to 9 entities that would be stored in a file.

examples: A->B  A->D  C->D 
          alice->bob  alice->larry bob -> larry
           1 -> 3  1 -> 5  2 -> 5

Any help you could offer would be greatly appreciated.
Thanks

Re: New to Ada need help implementing Warshall's algorithm

[Shark8]

On Wednesday, September 21, 2016 at 4:05:12 PM UTC-6, James Brewer wrote:
> Hello I hope this is right forum for this question. I have been asked to write a program that implements Warshall's algorithm using Ada. The problem, I have never written an Ada program and I a limited time frame to put this together.
> I have have the IDE installed and am in the process of writing some rudimentary programs to familiarize myself with the language but I'm afraid that I may run out of time. 
> 
> The input data I have is a series of connections between 7 to 9 entities that would be stored in a file.
> 
> examples: A->B  A->D  C->D 
>           alice->bob  alice->larry bob -> larry
>            1 -> 3  1 -> 5  2 -> 5
> 
> Any help you could offer would be greatly appreciated.
> Thanks


This sounds kind of like homework, is it?

In any case, what you could do is use Ada.Containers to handle the problem:
* Create an enumeration for nodes, perhaps Node_01 to Node_10.
* Instantiate Ada.Containers.Indefinite_Vectors with that enumeration as key and element as string. (This is to associate your input-variables w/ the enumeration.)
* Instantiate Ada.Containers.Ordered_Sets with the enumeration; this is to represent node-connections.
* Instantiate Ada.Containers.Indefinite_Ordered_Maps with the Set-type from the above as the element and the enumeration as the key. 

The rest is left to you.

Re: New to Ada need help implementing Warshall's algorithm

[Simon Wright]

Shark8 <onewingedshark@gmail.com> writes:

> On Wednesday, September 21, 2016 at 4:05:12 PM UTC-6, James Brewer wrote:
>> Hello I hope this is right forum for this question. I have been asked
>> to write a program that implements Warshall's algorithm using Ada.

> In any case, what you could do is use Ada.Containers to handle the
> problem:
[...]
> The rest is left to you.

The algorithm, as described in Wikipedia, relies on a 2-D array of
Boolean, which sounds a much more straightforward approach.

OP is likely to have a lot more trouble dealing with the data input,
I'd've thought.

I couldn't tell from the description of the input whether that was three
examples of order-3 problems or one example of an order-9
problem. Whatever, it'd be simpler if the input was in pairs, one per
line, without the => to distract; read the file once to get the
dimensions, create an array of the right size (probably on the heap),
read again to populate the array, Warshall, bob's your uncle.

Re: New to Ada need help implementing Warshall's algorithm

[James Brewer]

On Thursday, September 22, 2016 at 11:31:53 PM UTC-5, Shark8 wrote:
> On Wednesday, September 21, 2016 at 4:05:12 PM UTC-6, James Brewer wrote:
> > Hello I hope this is right forum for this question. I have been asked to write a program that implements Warshall's algorithm using Ada. The problem, I have never written an Ada program and I a limited time frame to put this together.
> > I have have the IDE installed and am in the process of writing some rudimentary programs to familiarize myself with the language but I'm afraid that I may run out of time. 
> > 
> > The input data I have is a series of connections between 7 to 9 entities that would be stored in a file.
> > 
> > examples: A->B  A->D  C->D 
> >           alice->bob  alice->larry bob -> larry
> >            1 -> 3  1 -> 5  2 -> 5
> > 
> > Any help you could offer would be greatly appreciated.
> > Thanks
> 
> 
> This sounds kind of like homework, is it?
> 
> In any case, what you could do is use Ada.Containers to handle the problem:
> * Create an enumeration for nodes, perhaps Node_01 to Node_10.
> * Instantiate Ada.Containers.Indefinite_Vectors with that enumeration as key and element as string. (This is to associate your input-variables w/ the enumeration.)
> * Instantiate Ada.Containers.Ordered_Sets with the enumeration; this is to represent node-connections.
> * Instantiate Ada.Containers.Indefinite_Ordered_Maps with the Set-type from the above as the element and the enumeration as the key. 
> 
> The rest is left to you.

It is a homework of sorts, but not in the way you'd normally think.  The instructor uses Ada when teaching algorithms for the examples but he expects you to teach yourself Ada on your own while trying to learn the algorithms. This is a bit daunting when you don't know what the language can and cannot do.

Thanks for the help, I appreciate it.  

Re: New to Ada need help implementing Warshall's algorithm

[James Brewer]

On Friday, September 23, 2016 at 1:26:22 AM UTC-5, Simon Wright wrote:
> Shark8 <> writes:
> 
> > On Wednesday, September 21, 2016 at 4:05:12 PM UTC-6, James Brewer wrote:
> >> Hello I hope this is right forum for this question. I have been asked
> >> to write a program that implements Warshall's algorithm using Ada.
> 
> > In any case, what you could do is use Ada.Containers to handle the
> > problem:
> [...]
> > The rest is left to you.
> 
> The algorithm, as described in Wikipedia, relies on a 2-D array of
> Boolean, which sounds a much more straightforward approach.
> 
> OP is likely to have a lot more trouble dealing with the data input,
> I'd've thought.
> 
> I couldn't tell from the description of the input whether that was three
> examples of order-3 problems or one example of an order-9
> problem. Whatever, it'd be simpler if the input was in pairs, one per
> line, without the => to distract; read the file once to get the
> dimensions, create an array of the right size (probably on the heap),
> read again to populate the array, Warshall, bob's your uncle.

It is three diffent sets of data. I think I may try to simplify the input data to a 0,1 2d array for each set, read the set in and then process each set writing it to an output file (the last two I will have to figure out).

Thanks for the reponse.

Re: New to Ada need help implementing Warshall's algorithm

[Stephen Leake]

On Friday, September 23, 2016 at 10:07:53 AM UTC-5, James Brewer wrote:
> 
> It is three diffent sets of data. I think I may try to simplify the input data to a 0,1 2d array for each set, read the set in and then process each set writing it to an output file (the last two I will have to figure out).

Here's a working program that does the IO, to get you started. It reads from a file, writes to standard out.

Reading the entire input line from the file, then processing it, simplifies debugging.

with Ada.Command_Line;
with Ada.Text_IO; use Ada.Text_IO;
procedure Warshall
is
   procedure Put_Usage
   is
   begin
      Put_Line ("Usage: warshall <input file name>");
   end Put_Usage;

   File : File_Type;
begin
   Open (File, In_File, Ada.Command_Line.Argument (1));

   loop
      exit when End_Of_File (File);

      declare
         Line : constant String := Get_Line (File);
         --  Each line should have format 'A B' where, A, B => 1 | 0
         A : Boolean;
         B : Boolean;
      begin
         if Line (1) = '0' then
            A := False;
         else
            A := True;
         end if;

         if Line (3) = '0' then
            B := False;
         else
            B := True;
         end if;

         --  FIXME: implement warshall's algorithm

         Put_Line ("A, B: " & Boolean'Image (A) & " " & Boolean'Image (B));
      end;
   end loop;
end Warshall;

given an input file:

0 1
1 0

this produces:

A, B: FALSE TRUE
A, B: TRUE FALSE

I'm happy to hear about an instructor using Ada to teach algorithms!

-- Stephe

Re: New to Ada need help implementing Warshall's algorithm

[James Brewer]

Thought I would clarify my previous post. So here it goes.

Ideally, the input data will look like this (the number of row and columns will vary and there will be more than one set (matrix) of data with different row and column names in the input file.

example:

         ColName1 ColName2 ColName3 ColNameN
RowName1    0        0        0        0
RowName2    1        1        1        1
RowName3    0        1        0        0
RowNameN    0        1        1        0


Here is the code I have so far without the read from file and output to file implementation.


WITH Text_IO; USE Text_IO;      -- This gets the IO facility.
WITH Ada.Integer_Text_IO; USE Ada.Integer_Text_IO; -- This gets the integer IO facility.
--****
-- use zero elements in array to store size 0,0 and row/column names?


-- read size
-- use size to read names of columns
-- store in array


-- use size to read first row of data?
-- as data is read convert from 0/1 to true false and store?

-- if value read = 0 => array2d(n,n) = false
-- if value read = 1 => array2d(n,n) = true


-- * main procedure *
PROCEDURE BooleanTest IS              -- Main, but no special name is needed.BEGIN

   N : Integer := 4; -- max size ** to be read
   OutputConvertion : Integer;
   Array2d: ARRAY (1..N, 1..N) OF boolean;

-- * main procedure starts begins*
BEGIN
   -- read array size and column names

   -- hard coded to be read from file
   
   Array2d(1, 1) := false;
   Array2d(1, 2) := false;
   Array2d(1, 3) := false;
   Array2d(1, 4) := false;

   Array2d(2, 1) := false;
   Array2d(2, 2) := true;
   Array2d(2, 3) := false;
   Array2d(2, 4) := true;

   Array2d(3, 1) := false;
   Array2d(3, 2) := true;
   Array2d(3, 3) := false;
   Array2d(3, 4) := true;

   Array2d(4, 1) := true;
   Array2d(4, 2) := false;
   Array2d(4, 3) := true;
   Array2d(4, 4) := false;

   FOR I IN 1..N LOOP
      FOR J IN 1..N LOOP
         IF Array2d(J,I) = true THEN --true nodes connected
            FOR K IN 1..N LOOP
               Array2d(J,K) := Array2d(J,K) OR Array2d(I,K);
            END LOOP;
         END IF;
      END LOOP;
   END LOOP;

-- *********** output to screen ************

   FOR I IN 1..N LOOP
      FOR J IN 1..N LOOP
         IF Array2d(I,J) = True THEN
            OutputConvertion := 1;
         ELSE 
            OutputConvertion := 0;
         END IF;
         Put( OutputConvertion);
         Put(" ");                
      END LOOP;
      New_Line(1);
   END LOOP;
   

END BooleanTest;
-- * main procedure ends *

Thanks again for all the help.

Re: New to Ada need help implementing Warshall's algorithm

[Stephen Leake]

On Monday, September 26, 2016 at 12:38:16 PM UTC-5, James Brewer wrote:
> example:
> 
>          ColName1 ColName2 ColName3 ColNameN
> RowName1    0        0        0        0
> RowName2    1        1        1        1
> RowName3    0        1        0        0
> RowNameN    0        1        1        0
> 
> 
> WITH Text_IO; USE Text_IO;      -- This gets the IO facility.
> WITH Ada.Integer_Text_IO; USE Ada.Integer_Text_IO; -- This gets the integer IO facility.
> --****
> -- use zero elements in array to store size 0,0 and row/column names?

not necessary.

> -- read size

Read the first line, count the spaces (trim trailing spaces if needed).

use Ada.Strings.Fixed.Index to find the spaces.

> -- use size to read names of columns

split the first line at the spaces.

> -- use size to read first row of data?

Read the whole line, split at spaces.

> -- if value read = 0 => array2d(n,n) = false

can be:

array2d(n, n) := read = 0;

--  Stephe

Re: New to Ada need help implementing Warshall's algorithm

[Simon Wright]

Stephen Leake <stephen_leake@stephe-leake.org> writes:

> On Friday, September 23, 2016 at 10:07:53 AM UTC-5, James Brewer wrote:
>> 
>> It is three diffent sets of data. I think I may try to simplify the
>> input data to a 0,1 2d array for each set, read the set in and then
>> process each set writing it to an output file (the last two I will
>> have to figure out).
>
> Here's a working program that does the IO, to get you started. It
> reads from a file, writes to standard out.

And here's a different one, which works out the size of the matrix by
finding the number of unique names in the input. The structure supports
strings for names, but the implementation only handles single-character
names because I was being lazy.

Input:
e b
a b
b c
b d
d a
d e
c e

Output:
a  3
b  2
c  4
d  5
e  1
01000
00011
01000
10000
10100

Code:
with Ada.Command_Line;
with Ada.Containers.Indefinite_Ordered_Maps;
with Ada.Text_IO; use Ada.Text_IO;

procedure Brewer is

   File : File_Type;

   package Names_To_Indices
     is new Ada.Containers.Indefinite_Ordered_Maps (String, Positive);
   Names : Names_To_Indices.Map;

   procedure Add_If_New (Name : String)
   is
      use type Ada.Containers.Count_Type;
   begin
      if not Names.Contains (Name) then
         Names.Insert (Name, Positive (Names.Length + 1));
      end if;
   end Add_If_New;

begin

   Open (File, In_File, Ada.Command_Line.Argument (1));
   --  each line is to have format Name_1 Name_2, implying there is a
   --  path from Name_1 to Name_2.

   loop
      begin
         declare
            Line : constant String := Get_Line (File);
         begin
            --  I'm being lazy here and assuming single-character Names.
            Add_If_New (Line (1 .. 1));
            Add_If_New (Line (3 .. 3));
         end;
      exception
         when others => exit;
      end;
   end loop;
   Reset (File);

   --  output name-to-index (ordered by name, not index, sorry)
   for J in Names.Iterate loop
      Put_Line (Names_To_Indices.Key (J)
                  & " "
                  & Names_To_Indices.Element (J)'Img);
   end loop;

   --  now we know the size of the matrix
   declare
      Size : constant Positive := Positive (Names.Length);
      Matrix : array (1 .. Size, 1 .. Size) of Boolean
        := (others => (others => False));
   begin
      --  populate the matrix
      loop
         begin
            declare
               Line : constant String   := Get_Line (File);
               From : constant Positive := Names.Element (Line (1 .. 1));
               To   : constant Positive := Names.Element (Line (3 .. 3));
            begin
               Matrix (From, To) := True;
            end;
         exception
            when others => exit;
         end;
      end loop;
      Close (File);

      --  dump the matrix
      for J in Matrix'Range (1) loop
         for K in Matrix'Range (2) loop
            Put (if Matrix (J, K) then '1' else '0');
         end loop;
         New_Line;
      end loop;
   end;

end Brewer;

Re: New to Ada need help implementing Warshall's algorithm

[jre11712]

On Wednesday, September 21, 2016 at 5:05:12 PM UTC-5, James Brewer wrote:
> Hello I hope this is right forum for this question. I have been asked to write a program that implements Warshall's algorithm using Ada. The problem, I have never written an Ada program and I a limited time frame to put this together.
> I have have the IDE installed and am in the process of writing some rudimentary programs to familiarize myself with the language but I'm afraid that I may run out of time. 
> 
> The input data I have is a series of connections between 7 to 9 entities that would be stored in a file.
> 
> examples: A->B  A->D  C->D 
>           alice->bob  alice->larry bob -> larry
>            1 -> 3  1 -> 5  2 -> 5
> 
> Any help you could offer would be greatly appreciated.
> Thanks

THIS GUY WAS HAVING TROUBLE WITH OLE BURRIS!!!!!

Re: New to Ada need help implementing Warshall's algorithm

[Lucretia]

On Friday, 23 September 2016 15:54:14 UTC+1, James Brewer  wrote:
> It is a homework of sorts, but not in the way you'd normally think.  The instructor uses Ada when teaching algorithms for the examples but he expects you to teach yourself Ada on your own while trying to learn the algorithms. This is 

So why haven't you? See https://en.wikibooks.org/wiki/Ada_Programming

> a bit daunting when you don't know what the language can and cannot do.

It can do what other languages can and more.