Question 1:
===========

Consider the following class dictionary and an
object and sentence which are both legal with respect to
the class dictionary.
Find the UNKNOWNS.

// An application consists of a list of modules which use
// a library.
Application = "*application*"
  <modules> List(Module) 
  "*using*" <using> List(AdaptiveSoftwareLibrary).
// an adaptive software library consists of a list
// of adaptive behavioral components (ABCs) and
// a list of customizing class dictionaries.
AdaptiveSoftwareLibrary =
  <abcs> List(ABC_Exp)
  <cds> List(CdExp).
// A module is a list of ABCs customized by a class dictionary.
Module = "*module*" <abcs> List(ABC_Exp) <customizer> CdExp.
// A class dictionary may be given explicitly, or by an evolutionary
// transformation which extends an existing cd or by a directive
// which restricts an existing cd.
CdExp : Cd | ExtendedCd | RestrictedCd.
Cd = "*cd*".
ExtendedCd = "*extended-cd*".
RestrictedCd = "*restricted-cd*" Directive CdExp.
Directive : SimpleDirective | DirectiveName.
SimpleDirective = "*from*" <from> Vertex "*to*" <to> Vertex.
ABC_Exp : ABC | ExtendedABC | CompoundABC. 
ExtendedABC = "*extended-abc*".
CompoundABC = <abcs> List(ABC).
// Adaptive Behavioral Component
ABC = 
  // customization parameters
    [<customization_parameters> List (CParam)]
  // provided function
    ProvidedSignature 
  // named directives
    ["*directives*" <directives> List(DirectiveDef)]
  // variables local to ABC; used to "transport" objects
    ["*var*" <var> List(VarDef)]
  // additional classes and parts needed by ABC
    ["*cd-extensions*" <cd_extensions> List(Extension)]
  // calls to other ABCs prefixed by a traversal -> elastic connections
    ["*connections*"<connections>  List(Connection)]
  [  <traversal> Traversal ]
  [ "*instantiated*" <instantiate> List(ABC_Exp)]
  [ "*called*" <call> List(ABC_Exp)]
  .
CParam = "*cparam*".
DirectiveDef = DirectiveName "=" Directive.
DirectiveName = <n> DemIdent.
ProvidedSignature =  // ABC provided, if return type is not void, can view
	     // it as new edge in extended class graph (derived edge).
"*operation*" <type_spec> Type_spec <name>  ABC_Name
"(" [ <parameter_decls> CommaList(ParamDecl) ] ")"
[ "*init*" <init> Block ] .
Type_spec = <n> DemIdent.
ParamDecl = <param_type_spec> Vertex
	    <param_name> Param_name.
Param_name             =  <name> DemIdent.
VarDef = "*var*".
Extension = "*cd-extension*".
Connection = Directive ABC_Name.
Traversal = "*traverse*"
  [<collaborators> Collaborators]
  Directive 
  ["*conditions*" <conditions> List(Condition)]
  [ "*prelude*" <prelude> Block]
  <wrappers> List(Wrapper)
  [ "postlude*" <postlude> Block].
Collaborators = "*collaborators*"
  // behavioral types
    <typ> List(TypeDef) 
  // represent other ABCs which participate in traversal
    <behavioralObjects> List(BehObject).
TypeDef = "*type*".
BehObject = "*behavioral-object*".
Wrapper = "*wrapper*".
Condition : VertexCond | EdgeCond.
VertexCond = "*vertex-if*" <condition> Block Vertex.
EdgeCond   = "*edge-if*"   <condition> Block Edge.
Vertex = <n> DemIdent.
ABC_Name = <n> DemIdent.
Block = <t> DemText.
Edge = "*edge*".

List(S) ~ "(" {S} ")".
CommaList(S) ~ S {"," S} .

=================================================== object

: Application ( 
   < modules > : Module_List { 
      : Module ( 
         < abcs > : ABC_Exp_List { } 
         < customizer > : Cd ( ) ) , 
      : Module ( 
         < abcs > : ABC_Exp_List { 
            : ABC ( 
               < providedsignature > : ProvidedSignature ( 
                  < type_spec > : Type_spec ( 
                     < n > : DemIdent "A" ) 
                  < name > : ABC_Name ( 
                     < n > : DemIdent "f" ) ) 
               < directives > : DirectiveDef_List { 
                  : DirectiveDef ( 
                     < directivename > : DirectiveName ( 
                        < n > : DemIdent "X" ) 
                     < directive > : SimpleDirective ( 
                        < from > : Vertex ( 
                           < n > : DemIdent "Q" ) 
                        < to > : Vertex ( 
                           < n > : DemIdent "R" ) ) ) , 
                  : DirectiveDef ( 
                     < directivename > : DirectiveName ( 
                        < n > : DemIdent "Y" ) 
                     < directive > : SimpleDirective ( 
                        < from > : Vertex ( 
                           < n > : DemIdent "S" ) 
                        < to > : Vertex ( 
                           < n > : DemIdent "T" ) ) ) } 
               < var > : VarDef_List { 
                  : VarDef ( ) , 
                  : VarDef ( ) } 
               < cd_extensions > : Extension_List { 
                  : Extension ( ) } 
               < connections > : Connection_List { 
                  : Connection ( 
                     < directive > : DirectiveName ( 
                        < n > : DemIdent "X" ) 
                     < abc_name > : ABC_Name ( 
                        < n > : DemIdent "f" ) ) , 
                  : Connection ( 
                     < directive > : DirectiveName ( 
                        < n > : DemIdent "Y" ) 
                     < abc_name > : ABC_Name ( 
                        < n > : DemIdent "g" ) ) } 
               < traversal > : Traversal ( 
                  < collaborators > : Collaborators ( 
                     < typ > : TypeDef_List { } 
                     < behavioralObjects > : BehObject_List { } ) 
                  < directive > : SimpleDirective ( 
                     < from > : Vertex ( 
                        < n > : DemIdent "A" ) 
                     < to > : Vertex ( 
                        < n > : DemIdent "B" ) ) 
                  < wrappers > : Wrapper_List { 
                     : Wrapper ( ) } ) ) } 
         < customizer > : Cd ( ) ) } 
   < using > : AdaptiveSoftwareLibrary_List { } ) 


================================================== sentence

*application*
  (
  *module* () *cd*
  *module* 
    ( 
    *operation* A f()
      *directives* 
	(X = *from* Q *to* R
	 Y = *from* S *to* T)
      *var* (*var* *var*)
      *cd-extensions* (*cd-extension*)
      *connections* (X f Y g)
      *traverse*
        *collaborators* () ()
        *from* A *to* B (*wrapper*) )
  *cd*)
*using* ()
Consider the following class dictionary, propagation patterns
and the call in main.C.

Find the UNKNOWNS so that the program matches the documentation.
The purpose of the program is to translate from one
graph representation to another.

For example, the graph representation


Class Dictionary Graph

Vertex List

  ConstVertex  Basket name_pos "{183 50}"
		vertex_pos "{200 66}"
   AltVertex   Fruit name_pos "{183 133}"
                vertex_pos "{200 150}"
  ConstVertex  Apple name_pos "{133 183}"
		vertex_pos "{150 200}"
  ConstVertex  Orange name_pos "{233 183}"
		vertex_pos "{250 200}"
  ConstVertex  Weight name_pos "{283 133}"
		vertex_pos "{300 150}"
  ConstVertex  DemNumber name_pos "{333 183}"
		vertex_pos "{400 150}"

Edge List
   ConstEdge fruit name_pos "{205 108}"
	 from
 	 ConstVertex  Basket
   	 to
	 AltVertex   Fruit

   AltEdge    
	from
	AltVertex   Fruit
	to
  	ConstVertex  Apple 
   AltEdge
	from
	AltVertex   Fruit
	Bendpoints "{{500 4} {20 90}}"
	to
 	ConstVertex  Orange

   ConstEdge  weight name_pos "{250 145}"
	from
	AltVertex   Fruit
	Bendpoints "{{250 400} {500 500}}"
	to
  	ConstVertex  Weight
   ConstEdge  n  name_pos "{350 145}"
	from
  	ConstVertex  Weight
	to
  	ConstVertex  DemNumber


is translated into:


Basket = < fruit > Fruit . 
Fruit : Apple | Orange *common* < weight > Weight . 
Apple = . 
Orange = . 
Weight = < n > DemNumber . 
DemNumber = . 

by propagation pattern cppCreCDGraph at the end of the pp list below.

The following code is from the DemDraw COM1205 undergraduate project.
========================================================== class dictionary

Graph = "Class Dictionary Graph"
           < vertices > Vertex_List
           < edges > Edge_List 

//    made the following optional so we wouldn't need to change the 
//    demeter-input file, but would create using the cppInit.pp 

	   [ "defaultConstVertex" < defaultConstVertex > ConstVertex]
	   [ "defaultAltVertex" < defaultAltVertex > AltVertex]
	   [ "defaultConstEdge" < defaultConstEdge > ConstEdge]
	   [ "defaultAltEdge" < defaultAltEdge > AltEdge] .

Edge :   AltEdge
        | ConstEdge
        *common*
	  "from"     < from > Vertex
	  [ "Bendpoints" < middlepoints > Coordinates ]
	  "to"    < to > Vertex .

Edge_List ~ "Edge" "List" { Edge } .

Vertex_List ~ "Vertex" "List" {  Vertex } .

Vertex :  AltVertex
        | ConstVertex
	| Term
        *common*
          < vertexname > VertexName
          [ "vertex_pos" < position > Coordinates ] .

AltEdge = "AltEdge" .

ConstEdge = "ConstEdge"
            < edgename > EdgeName .

ConstVertex = "ConstVertex" .

AltVertex =  "AltVertex" .

Coordinates = <coords> DemString.

VertexName =  < name > DemIdent
              [ "name_pos" < vn_offset > Coordinates ] .

EdgeName =    < name > DemIdent 
	      "name_pos" < en_offset > Coordinates .

Term =    "TermVertex" .


// New classes for creating a Class Dictionary Graph object

Cd_Graph = < adjacencies > Cd_Adj_List .

Cd_Adj_List ~ { Cd_Adjacency } .

Cd_Adjacency = < source > Cd_Vertex < ns > Cd_Neighbors "." .

Cd_Neighbors :  Cd_Construct | Cd_Alternat 
                *common* < construct_ns > Cd_LV_List .

Cd_Construct = "=" .

Cd_Alternat = ":" < alternat_ns > Cd_V_BarList "*common*" .

Cd_LV_List ~ { Cd_LVertex } .

Cd_V_BarList ~ Cd_Vertex { "|" Cd_Vertex } .

Cd_LVertex = "<" < label_name > DemIdent ">" < vertex > Cd_Vertex .

Cd_Vertex = < vertex_name > DemIdent .

===================================================== propagation patterns

// This pp will return a DemIdent* that points to the DemIdent that holds the
// name of the ConstEdge object on which the function is called.

*operation* DemIdent* GetCEName()
  *traverse* *from* ConstEdge
  *to* EdgeName
  *wrapper* EdgeName
  (@ return_val = this->get_name(); @)


// This pp will return a DemIdent* that points to the DemIdent that holds the
// name of the Vertex object on which the function is called.

*operation* DemIdent* GetVName()
  *traverse* *from* Vertex
  *to* VertexName
  *wrapper* VertexName
  (@ return_val = this->get_name(); @)


// Find the Cd_V_BarList-object of Adjacency with source SrcVert
// and add DesVert to Cd_V_BarList-object.

// If the source SrcVert is a 
// construction vertex, the command has no effect.

*operation* void cdgAddANeighbor(DemIdent* SrcVert,
                                 DemIdent* DesVert)
   *traverse*
      *from* Cd_Graph
      *to*   Cd_V_BarList

   *carry* *in* Cd_Vertex* S_Chk_Vert = (@ this -> get_source() @)
      *along* *from* Cd_Adjacency
              *to*   Cd_V_BarList

   *wrapper* Cd_V_BarList
      (@
         if (SrcVert->g_equal(S_Chk_Vert->get_vertex_name())) {

            this->append(new Cd_Vertex((DemIdent*)DesVert->g_copy()));
         }
      @)
      

// Find the Cd_LV_List-object of Adjacency with source SrcVert
// and add DesVert to Cd_LV_List-object.

// For instance, if the source is an alternation vertex, the
// destination vertex should be added to the "common" list.


*operation* void cdgAddCNeighbor(DemIdent* SrcVert,
                                 DemIdent* Name,
                                 DemIdent* DesVert)
   *traverse*
      *from* Cd_Graph
      *to*   Cd_LV_List

   *carry* *in* Cd_Vertex* S_Chk_Vert = (@ this -> get_source() @)
      *along* *from* Cd_Adjacency
              *to*   Cd_LV_List

   *wrapper* Cd_LV_List
      (@
         if (SrcVert->g_equal(S_Chk_Vert->get_vertex_name())) {

            Cd_LVertex* new_LVertex = new Cd_LVertex();

            new_LVertex->set_vertex(new Cd_Vertex((DemIdent*)DesVert->g_copy()));
            new_LVertex->set_label_name((DemIdent*)Name->g_copy());

            this->append(new_LVertex);
         }
      @)


// Create a new adjacency with a source vertex of the given name
// and an empty neighbor list of type Cd_Alternat.  Add it to 
// the current Cd_Adj_List.

*operation* void cdgAddSourceAVertex(DemIdent* name)
  *traverse* *from* Cd_Graph *to* Cd_Adj_List
   *wrapper* Cd_Adj_List
      (@
         Cd_Adjacency* NewAdj = new Cd_Adjacency();
         Cd_Vertex* NewVertex = new Cd_Vertex(name);
         Cd_Alternat *NewAlternat = new Cd_Alternat(new Cd_V_BarList());

         NewAlternat->set_construct_ns(new Cd_LV_List());

         NewAdj->set_source(NewVertex);
         NewAdj->set_ns(NewAlternat);                                                  
         this->append(NewAdj);
      @)


// Create a new adjacency with a source vertex of the given name
// and an empty neighbor list of type Cd_Construct.  Add it to 
// the current Cd_Adj_List.

*operation* void cdgAddSourceCVertex(DemIdent* name)
*traverse* *from* Cd_Graph *to* Cd_Adj_List
   *wrapper* Cd_Adj_List
      (@
         Cd_Adjacency* NewAdj = new Cd_Adjacency();
         Cd_Vertex* NewVertex = new Cd_Vertex(name);
         Cd_Construct *NewConstruct = new Cd_Construct();

         NewConstruct->set_construct_ns(new Cd_LV_List());

         NewAdj->set_source(NewVertex);
         NewAdj->set_ns(NewConstruct);

	cout << "Before the append" << endl;
         this->append(NewAdj);
      @)


// Iterate through the edge list, adding each as a neighbor to the list of
// adjacencies in the CDG object. The actual function call used depends on
// the edge type. Just pass the vertex name and leave it up to the CDG 
// object to implement the addition.

// This must be done after to cppAddSourceVertices.

*operation* void cppAddNeighbors(Cd_Graph* cdg)
   *traverse*
      *from* Graph
      *through* -> *,edges,*
      *to* { ConstEdge, AltEdge }
   *wrapper* ConstEdge
      (@
         cdg->cdgAddCNeighbor(this->get_from()->GetVName(),
                              this->GetCEName(), 
                              this->get_to()->GetVName());
      @)
   *wrapper* AltEdge
      (@
         cdg->cdgAddANeighbor(this->get_from()->GetVName(),
                              this->get_to()->GetVName());
      @)


// Iterate through the vertex list, adding each as a source vertex
// to the list of adjacencies in the CDG object.  The actual function call 
// used depends on the vertex type. Just pass the vertex name and leave it
// up to the CDG object to implement the addition.

// This must be done prior to cppAddNeighbors.

*operation* void cppAddSourceVertices(Cd_Graph* cdg)
   *traverse*
      *from* Graph
      *through* -> *,vertices,*
      *to* { ConstVertex, AltVertex }
   *wrapper* ConstVertex
      (@ cdg->cdgAddSourceCVertex(this->GetVName()); @)
   *wrapper* AltVertex
      (@ cdg->cdgAddSourceAVertex(this->GetVName()); @)



// Add all vertices as source vertices to the CDG object.
// Add all edges as neighbors to the CDG object.

*operation* Cd_Graph* cppCreCDGraph()
   *init* (@ new Cd_Graph(new Cd_Adj_List()) @)
   *wrapper* Graph
      (@
	 cout << "Before cppAddSourceVertices" << endl;	
         this->cppAddSourceVertices(return_val);
	 cout << "After/Before cppAddNeighbors" << endl;
         this->cppAddNeighbors(return_val);
	 cout << "Final After Add Neighbors" << endl;
      @)

===================================================== call in main.C

cout << " the cd " << iGraph -> cppCreCDGraph() << endl;
Considert the following cd:

A = B C D.
// B : R | S | T | U | V | W | X *common* <g> G.
B :                           C | D *common* <g> G.
C : R |     T |     V |     X *common* <h> H.
D :     S |     U |     W *common* <i> I.

R = .
S = .
T = .
U = .
V = .
W = .
X = .

G = .
H = .
I = .

Does it have the tree-property?  Answer: UNKNOWN
Is it object-equivalent to a single
inheritance class dictionary? If so, replace one class
definition or give answer "NO" in UNKNOWN.