Programming Assignment # 3 Implementing and Using General Trees Solution

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.

2. 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 ;

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

there is no overload .

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 ) ;

}

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:

LinkedGT.java

PowerGridUtils.java

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

The submission deadline is:

You have to read and follow the following rules:

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.

2. 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.

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

4. 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.

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

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

7. 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