PAL CARD CATALOG ENTRY

SHORT DESCRIPTION

Manipulate directed acyclic graphs


MOVEMENT WITHIN THE PAL CARD CATALOG
Move to top-level taxonomy
Move to keyword list

ASSET PROFILE

UNIT NAME
Abstractions/DAG (A1DAG)
VERSION
1.0
REVIEW CODE
C1 1.0 B
INET ADDRESS
Not documented in PAL database
AUTHOR
Bill Toscano, Michael Gordon
Intermetrics, Inc,
733 Concord Ave
Cambridge, MA 02138
Contact: Lt. Colonel Falgiano
ESD/SCW
Hanscom AFB, MA 01731
RIGHTS
PUBLIC DOMAIN
COPYRIGHT
(c) 1985 Intermetrics, Inc.
DATE CREATED
15 October 1985
DATE RELEASED
18 March 1985
DATE LAST UPDATED
17 March 1985
LOCATION
ASR
C2MUG
PC-BLUE
ENVIRONMENT
VAX/VMS, DEC Ada
LIMITATIONS
Not documented in PAL database
CERTIFICATION
Ada System Certifier_1 1.0
Date/Time of Processing: Tuesday   24 May       1994 12:53:46Pm
Overall Assessment of System: OK
Classification of System: B
Basis of Classification --
Syntax Errors                               PASS
Completeness                                PASS
Independence from External Libraries        FAIL
Independence from a Specific Ada Compiler   PASS

Explanations for failures --
System withs non-standard library units that are not provided

Number of ...
Files               2
Library Units       2
Lines            1761
Statements        500
Comments          581

Unidentified Withed Units --
3 unidentified withed units

FILE LISTING

Directory Display


languages/ada/asr/abstractions/dag:
  File Name                 Size
  ---------                 ----
  dag.zip                 10,348


Totals
  ==============  ==============
    1 Files               10,348

ABSTRACT

	This generic package provides the DAG, or Directed Acyclic
Graph, abstract data type.  A directed graph is a set of nodes and a
set of directed edges connecting pairs of nodes.  A directed graph, G,
is acyclic iff for each node, N, in G, there is no sequence of edges in
G that leads to N.  This package maintains acyclicity.
	The nodes consist of labels and their associated values.  Both
types are generic formals.  There are no explicit bounds on the size
of DAGs, as they are implemented on the heap.
	A DAG is denoted by a labels/edges pair.
	The following is a list of operations:

Constructors:
	Create: Create an empty DAG
	Add_Node, Add_Edge: Add a node or an edge to a DAG
	Set_Value: Set the value of a label of a DAG
	Copy: Make a copy of a DAG
Query Operations:
	Is_Empty: Return TRUE if a DAG has not been initialized (Create)
	Is_Root, Is_Leaf: Return TRUE if there is no edge in a DAG such
		that equal(1,12) or equal(1,11)
	Is_Successor, Is_Descendent: Return TRUE if (11,12) is an edge
		or if there is a sequence of edges beginning at 11 and
		ending at 12
	Get_Value: Return the value of a label
	Root_Count, Node_Count, Edge_Count, Pred_Count, Succ_Count: Counts
	Put_Image: Output a literal form of a DAG into a file
Iterators:
	Make_Nodes_Iter, More, Next (2)
	Make_Edges_Iter, More, Next
	Make_Roots_Iter, More, Next (2)
	Make_Leaves_Iter, More, Next (2)
	Make_Preds_Iter, More, Next (2)
	Make_Succs_Iter, More, Next (2)
	Make_Preorder_Iter (2), More, Next (2)
	Make_Postorder_Iter (2), More, Next (2)
Heap Management:
	Destroy_DAG
	Destroy_DAG_and_Labels
	Destroy_DAG_and_Values
	Destroy_DAG_and_Nodes

        ABSTRACTIONS  is  used  by NOSC/WIS tools 5.1.1, 5.1.2, 6.1.2,
and 6.2.  See also NEW_ABSTRACTIONS.


REVISION HISTORY

DATE         VERSION AUTHOR                  HISTORY 
03/85        1.0  Bill Toscano               Initial Release 


RELEASE NOTICE

This prologue must be included in all copies of this software.

This software is copyright by the author.

This software is released to the Ada community.
This software is released to the Public Domain (note:
  software released to the Public Domain is not subject
  to copyright protection).
Restrictions on use or distribution:  NONE


DISCLAIMER

	This software and its documentation are provided "AS IS" and
without any expressed or implied warranties whatsoever.  No warranties
as to performance, merchantability, or fitness for a particular
purpose exist.
	The user is advised to test the software thoroughly before
relying on it.  The user must assume the entire risk and liability of
using this software.  In no event shall any person or organization of
people be held responsible for any direct, indirect, consequential or
inconsequential damages or lost profits.