# Programming Assignment # 3 Implementing and Using General Trees Solution

\$35.00 \$30.80

## Description

• Introduction

The electric power grid is the network infrastructure responsible for the generation and trans-mission of electricity. We have three types of elements in a power grid:

A generator: this is a station that generates electricity. A generator has a power limit that it cannot exceed.

A transmitter: this is a station that transmits electricity. A transmitter can be connected directly to a generator or to another transmitter. A transmitter has a maximum power that can pass through it.

A consumer: this can be a household, a shop, a factory etc. A consumer can only be attached to a transmitter (not directly to a generator), and no element can be attached to it. A consumer has maximum consumption power that it cannot exceed.

For simplicity, we assume that the power grid can be represented as a general (non-binary) tree. The grid contains only one generator located at the root, whereas consumers are located at leaf nodes. See Figure 1 for an example.

We are interested in the following:

1. Finding how much power is generated, transmitted or consumed by an element. This is the total power required by the consumers in the corresponding subtree.

Example 1. In the grid shown in Figure 1: Elements 6 and 9 are consuming 0 power, since there are no consumers attached to them. Element 16 consumes 4, Element 8 consumes 10, and Element 4 consumes 19.

1. Whether there is an overload in the grid. An overload takes place when the power required at an element exceeds its capacity. By de nition, overloads can only happen at the generator or the transmitters (but not consumers).

Example 2. In the grid shown in Figure 1, the only element that has an overload is Element 4, since it consumes 19, and its limit is 18.

In this programming assignment, we will use general trees to represent a power grid.

 CSC 212

id: 3

type: Generator

Power:36

 Figure id: 4 id: 5 id: 7 1: type: Transmitter type: Transmitter type: Transmitter Power:18 Power:18 Power:18 aofExample .gridpower id: 8 id: 6 id: 10 id: 12 id: 16 id: 17 type: Transmitter type: Transmitter type: Consumer type: Consumer type: Consumer type: Consumer Power:12 Power:12 Power:9 Power:4 Power:4 Power:4

 id: 13 id: 11 id: 14 id: 9 type: Consumer type: Consumer type: Consumer type: Transmitter Power:3 Power:3 Power:4 Power:12

 3#PA 2

3

• Implementing a general tree

Write a the class LinkedGT that implements the following interface representing a general tree (There is no limit on the number of children that a node can have. The constructor of your class should not take any parameters.):

p u b l i c i n t e r f a c e  GT <T >  {

• Return true if the tree is empty boolean empty () ;

• Return true if the tree is full boolean full () ;

// Return the data  of  the current node

• retrieve () ;

• Update the data of the current node void update ( T e ) ;

//  If  the tree  is empty  e  is inserted as  root .  If  the tree  is  not  empty

• e is added as a child of the current node . The new node is made current and true is returned .

boolean  insert ( T  e ) ;

// Return the number of children of  the current node .

i n t n b C h i l d r e n () ;

//  Put current on  the  i – th child  of  the current node  ( starting from  0) ,

if  it  exists ,  and return true .  If  the child does not  exist ,  current

is  not changed and the method returns false .

boolean  fi nd Ch i ld ( i n t  i ) ;

• Put current on the parent of the current node . If the parent does not exist , current does not change and false is returned .

boolean  f i n d P a r e n t () ;

• Put current on the root . If the tree is empty nothing happens . void findRoot () ;

• Remove the current subtree . The parent of current , if it exists , becomes the new current .

void  remove () ;

}

• Representing a power grid

We will represent a power grid using a general tree. Elements of the grid are represented by the class PGElem below:

p u b l i c c l a s s PGElem  {

p r i v a t e i n t  id ;

p r i v a t e ElemType type ;

p r i v a t e  double  power ;

p u b l i c  PGElem ( i n t  id ,  ElemType  type ,  double  power )  {

t h i s . id  =  id ;

CSC 212 PA # 3

4

t h i s . type  =  type ;

t h i s . power  =  power ;

}

p u b l i c i n t getId ()  {

return  id ;

}

p u b l i c ElemType getType ()  {

return  type ;

}

p u b l i c  double  getPower ()  {

return  power ;

}

}

The enumeration ElemType is de ned as follows:

p u b l i c  enum  ElemType  {

Generator ,  Transmitter ,  Consumer

}

Using these de nitions, write the class PowerGridUtils:

 p u b l i c  c l a s s  P o w e r G r i d U t i l s  { //  Return  the IDs  of all  elements  in  the power grid  pg  in  pre – order . p u b l i c s t a t i c Queue < Integer >  c o l l e c t P r e o r d e r ( GT < PGElem >  pg ) ; //  Searches the  power grid  pg  for  the  element with  ID  id .  If  found ,  it is made current  and  true  is  returned , ot he rw is e  false  is  returned . p u b l i c s t a t i c boolean find ( GT < PGElem >  pg , i n t id ) ; //  Add  the  ge ne ra to r  element  gen  to  the  power grid  pg .  This  can  only  be done  if the  grid is  empty .  If  successful , the  method  returns  true . If  there  is  already  a  generator ,  or  gen  is  not  of  type  Generator , false  is returned . p u b l i c s t a t i c boolean a d d G e n e r a t o r ( GT < PGElem > pg ,  PGElem  gen ) ;

• Attaches pgn to the element id and returns true if s u c c e s s f u l . Note that a consumer can only be attached to a transmitter , and no element can be be attached to it . The tree must not contain more than one ge ne ra to r located at the root . If id does not exist , or there is already aelement with the same ID as pgn , pgn is not

attached ,  and the method retrurns false .

p u b l i c s t a t i c boolean  attach ( GT < PGElem >  pg ,  PGElem  pgn ,  i n t  id ) ;

// Removes element by  ID ,  all c o r r e s p o n d i n g subtree is removed .  If

removed ,  true  is  returned ,  false  is returned ot he rw is e .

p u b l i c s t a t i c boolean  remove ( GT < PGElem >  pg ,  i n t  id ) ;

// Computes total power that consumed by  a  element  ( and all its subtree

) .  If  id  is  incorrect , -1  is returned .

p u b l i c s t a t i c double  t o t a l P o w e r ( GT < PGElem >  pg ,  i n t  id ) ;

• Checks if the power grid contains an overload . The method returns the ID of the first element preorder that has an overload and -1 if

p u b l i c s t a t i c i n t f i n d O v e r l o a d ( GT < PGElem >  pg ) ;

}

CSC 212 PA # 3

5

• Deliverable and rules

You must deliver:

1. Source code submission to Web-CAT. You have to upload the following class in a zipped le:

PowerGridUtils.java

Notice that you should not upload the interfaces and classes given to you.

1. The speci cation given in the assignment (class and interface names, and method signatures) must not be modi ed. Any change to the speci cation results in compilation errors and consequently the mark zero.

1. All data structures used in this assignment must be implemented by the student. The use of Java collections or any other data structures library is strictly forbidden.

1. This assignment is an individual assignment. Sharing code with other students will result in harsh penalties.

1. Posting the code of the assignment or a link to it on public servers, social platforms or any communication media including but not limited to Facebook, Twitter or WhatsApp will result in disciplinary measures against any involved parties.

1. The submitted software will be evaluated automatically using Web-Cat.

1. All submitted code will be automatically checked for similarity, and if plagiarism is con-rmed penalties will apply.

1. You may be selected for discussing your code with an examiner at the discretion of the teaching team. If the examiner concludes plagiarism has taken place, penalties will apply.

CSC 212 PA # 3