Manipulate directed acyclic graphs
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
languages/ada/asr/abstractions/dag:
File Name Size
--------- ----
dag.zip 10,348
Totals
============== ==============
1 Files 10,348
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.
DATE VERSION AUTHOR HISTORY 03/85 1.0 Bill Toscano Initial Release
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
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.