65.9K
CodeProject is changing. Read more.
Home

TopDown Analyze Method with Tree Graphs as Support

Patrice T
starIconstarIconstarIconstarIconstarIcon

5.00/5 (2 votes)

Jul 22, 2023

CPOL

5 min read

viewsIcon

2736

downloadIcon

20

Tree Graphs used as support for Top-Down Analyze method

Contents

  1. Introduction
  2. Background
    1. yEd The Diagram Editor
    2. Stepwise Refinement, Structured Programming, Top-Down Analyze Methods
  3. Translation of typical structures to a tree
  4. A Practical Case : The NQueens Puzzle
    1. Incremental analyze
    2. Translation to Code
  5. Points of Interest
  6. Links
  7. History

Introduction

I am using Tree Graphs as helper with the Top-Down analyze method. Because the sheet of paper is never large enough. Here is how I do it.

Background

yEd The Diagram Editor

yEd is a freeware Graph Editor made by yWorks. yWorks is a company working around a library allowing easy integration of Graphs in tier applications.

yEd exists in two flavors, a Java app or a Live version on your browser.

The main reason I use yEd is the neat feature of Auto-Layout. Every time I make a change in tree, 1 click and the tree is rebuilt according to settings.

Stepwise Refinement, Structured Programming, Top-Down Analyze Methods

Three names for more or less a similar paradigm and the same result: a guideline to translate algorithms to structured programs, and also to help define the algorithm itself.

  • Stepwise Refinement is a general purpose not aimed at programming
  • Structured Programming by Edsger W. Dijkstra and overs
  • Top-Down Analyze Method by Nicklaus Wirth

I am not sticking to one of those methods, but using a mix of the three.

Translation of Typical Structures to a Tree

A programmatic flowchart sticks to a translation of source code into a 2D graph, the problem is that it is of no help to define an algorithm.

With those analyze methods, we start at the level of general idea and then stepwise refinement is done, the tree helps to visualize the algorithm solution at different levels.

The general principle is to start from a single complex problem and to split into a few simpler problems and refine until each small problem is simple enough, so that you can code it without further explanation.

Elements Figures
Bloc
Rectangle
Condition
Diamond
Loop
Rectangle with Round Edges
Patterns Tree Translation
Sequence

Seq A
Seq B
Selection

if Cond A is true
    Seq A
end if
Selection

if Cond A is true
    Seq A
else
    Default Seq
end if
Selection

if Cond A is true
    Seq A
else if Cond B is true
    Seq B
else
    Default Seq
end if
repetition

while Cond A is true
    Seq A
end while
repetition

do
    Seq A
while Cond A is true
repetition

do
    Seq A
until Cond A is true

Feel free to use any shape and pattern to fit your needs, but you will need to explain those if you share the trees.

Patterns Tree Translation
For Next
Start
while End condition
    Seq A
    Step
end while
Counter= Start
while Counter <= End
    Seq A
    Counter= Counter+ Step
end while

You stop going into details when you have enough to translate to code.

A Practical Case: The NQueens Puzzle

The goal is to place 8 Queens on a board of same size. Same problem can be solved with different board sizes.

Solving by hand. Just the great lines of the method.

  • If board is filled, it is a solution.
  • For a new row, search first possible queen position. And go to the next row.
  • For existing queen, search next possible position. And go to the next row.
  • When there is no more possible position on row, go back to previous row and move the queen.

The name of the method is backtracking.

Incremental Analyze

I will use a backtracking version of the solving algorithm. Basically, the solving algorithm looks for all solutions, I will stop it after the first solution is found.

Comments Tree Translation
N Queens Solver
Need Size of board
Need to store position of each queen
Position of Queens is the result

I choose a non recursive backtracking algorithm. It is a large loop with two parts inside, a loop forward, and the backsticking part.

Pattern Tree Translation
While Search non Finished
    Go Forward
    Go Backtrack
End While

 

Comments Tree Translation
Need to keep track of actual Row
if column is on board then try it, else backtrack
To go forward

if position is free,
next Row and column 0,
else next column To go backward
Prev Row
Next column

And now, just have to check if a given cell if free or locked.

Comments Tree Translation
Position is free if
no queen locks the cell
on vertical or diagonals
And finally

Translation to Code

// NQueens Solver
#include <iostream>
using namespace std;

// Persistant Initialisation
const int BSize = 8;
int QPos[BSize + 1];

int IsFree(int Row) {
	for (int Index = 1; Index < Row; Index++) {
		// Check column
		if (QPos[Row] == QPos[Index])
			return 0;
		// Check diag /
		if (QPos[Row] == QPos[Index] + (Row - Index))
			return 0;
		// Check diag \
		if (QPos[Row] == QPos[Index] - (Row - Index))
			return 0;
	}
	return 1;
}

int NQ_Solver() {
	// Local Initialisation
	int Row = 1;
	QPos[Row] = 0;
	// BackTracking Search
	while (Row > 0) {
		if (QPos[Row] < BSize) {
			// Go Forward
			if (IsFree(Row)) {
				// Ok, Solution or Next Row
				if (Row < BSize) {
					Row++;
					QPos[Row] = 0;
				} else {
					//	Solution found, Abort
					return 1;
				}
			} else {
				// Next Column
				QPos[Row]++;
			}
		} else {
			// Go Backward
			Row--;
			QPos[Row]++;
		}
	}
	return 0;
}

int main() {
	cout << "NQueens Solver" << endl;
// Call Solver
	if (NQ_Solver()) {
		// Result
		for (int Index = 1; Index <= BSize; Index++) {
			cout << " " << QPos[Index] + 1;
		}
		cout << endl;
		// Board Solution
		for (int Index = 0; Index < BSize; Index++) {
			for (int Col = 0; Col < BSize; Col++) {
				if (QPos[Col + 1] == Index) {
					cout << " *";
				} else {
					cout << " .";
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << "fini" << endl;
	return 0;
}

NQueens.cpp in TopDown.zip.

Result

NQueens Solver
 1 5 8 6 3 7 2 4
 * . . . . . . .
 . . . . . . * .
 . . . . * . . .
 . . . . . . . *
 . * . . . . . .
 . . . * . . . .
 . . . . . * . .
 . . * . . . . .

fini

Points of Interest

When creating an algorithm, building a tree graph helps me a lot to visualize the idea, but the operation is tedious as the tree shape changes with every addition.

The main interest over flowcharts is that we don't have to stick to programming language syntax, instead this approach organizes a high level description of the algorithm.

The auto-layout feature of yEd eases the tree creation process.

History

  • 11th September, 2022: First draft
  • 22nd July, 2023: First publishing