Greedy algorithm python – Coin change problem

A greedy python algorithm (greedy algorithm python) greedily selects the best choice at every step. He hopes that these choices lead to the optimal overall solution to the problem. So, a greedy algorithm does not always give the best solution. However in many problems this is the case.

A greedy python algorithm (greedy algorithm python) greedily selects the best choice at every step. He hopes that these choices lead to the optimal overall solution to the problem. So, a greedy algorithm does not always give the best solution. However in many problems this is the case.

Greedy Algorithm: Introduction

The problem of giving change is formulated as follows. How to return a given sum with a minimum of coins and banknotes?

Here is an example in python of the resolution of the problem:

If we consider the Euro monetary system without the cents we have the whole

EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Greedy algorithm python : Coin change problem

Now, to give change to an x ​​value of using these coins and banknotes, then we will check the first element in the array. And if it’s greater than x, we move on to the next element. Otherwise let’s keep it. Now, after taking a valuable coin or bill from the array of coinAndBill [i], the total value x we ​​need to do will become x – coinAndBill [i].

Here is the associated greedy python algorithm:

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(33)#Exemple sur 33 euros

The output for 33 euro is then:

20
10
2
1

Another example with 55 euro of greedy python algorithm:

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(55)#Exemple sur 55 euros

Output :

50
5

Conclusion

The problem of giving change is NP-difficult relative to the number of coins and notes of the monetary system considered (euro in this example). To go further, we can demonstrate that for certain so-called canonical money systems, the use of a greedy algorithm is optimal. A monetary system is said to be canonical if for any sum s the greedy algorithm leads to a minimal decomposition.

NP difficulty is the defining property of a class of problems informally “at least as difficult as the most difficult NP problems”.

A simple example of an NP-hard problem is the sum of subset problem. If P is different from NP then it is unlikely to find a polynomial time algorithm that exactly solves this problem.

External links :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Internal links python greedy algorithm :

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/non-classe/

Levenshtein Python Algo implementation Wagner & Fischer

Here is the levenshtein python implementation of the Wagner & Fischer algorithm (Wagner-Fischer). It allows to calculate the distance of Levenshtein (distance between two strings of characters).

Here is the python implementation of the Wagner & Fischer algorithm (Wagner-Fischer). It allows to calculate the distance of Levenshtein (distance between two strings of characters).

First, the goal of the algorithm is to find the minimum cost. Minimal cost to transform one channel into another. Then a recursive function allows to return the minimum number of transformation. And to transform a substring of A with n characters into a substring of B with the same number of characters. The solution is given. We must calculate the distance between the 2 letters at the same position in the chain A and B. Then Either the letters and the previous letter are identical. Either there is a difference and in this case we calculate 3 costs. So the first is to delete a letter from the chain A. And insert a letter in the chain A to substitute a letter from the chain A. Then we can then find the minimum cost.

Example of levenshtein python implementation :

import numpy as np

def levenshtein(chaine1, chaine2):
    taille_chaine1 = len(chaine1) + 1
    taille_chaine2 = len(chaine2) + 1
    levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
    for x in range(taille_chaine1):
        levenshtein_matrix [x, 0] = x
    for y in range(taille_chaine2):
        levenshtein_matrix [0, y] = y

    for x in range(1, taille_chaine1):
        for y in range(1, taille_chaine2):
            if chaine1[x-1] == chaine2[y-1]:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1, y] + 1,
                    levenshtein_matrix[x-1, y-1],
                    levenshtein_matrix[x, y-1] + 1
                )
            else:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1,y] + 1,
                    levenshtein_matrix[x-1,y-1] + 1,
                    levenshtein_matrix[x,y-1] + 1
                )
    return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])

print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))

To calculate the Levenshtein distance with a non-recursive algorithm. We use a matrix which contains the Levenshtein distances. Then These are the distances between all the prefixes of the first string and all the prefixes of the second string.

Also we can dynamically calculate the values ​​in this matrix. The last calculated value will be the Levenshtein distance between the two whole chains.

Finally there are many use cases of the Levenshtein distance. Levenshtein distance is used in domains. Computational linguistics, molecular biology. And again bioinformatics, machine learning. Also deep learning, DNA analysis. In addition, a program that does spell checking uses, for example, the Levenshtein distance.

Links on the Wagner & Fischer algorithm (Wagner-Fischer) and the Levenshtein python distance or other language:

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Internal links on algorithms

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

PyTorch how to load a pre-trained model?

There are several approaches to recording (serializing) and loading (deserialize) patterns for inference in PyTorch.

For example you may need to load a model that is already trained and back up that comes from the internet. More recently I answered this question on a discussion forum https://discuss.pytorch.org/t/i-want-to-do-machine-learning-with-android/98753. I take advantage of this article to give some details.

SAVE AND LOAD OF A PRE-TRAINED MODE with load_state_dict

In PyTorch you can save a model by storing in its file its state_dict these are Python dictionaries, they can be easily recorded, updated, modified and restored, adding great modularity to PyTorch models and optimizers.

In my example:

ESPNet is backed up with this method

https://github.com/sacmehta/ESPNet/tree/master/pretrained/encoder

I managed to load the encoder model using the ESPNet class that makes a load_state_dict

import torch
model = ESPNet(20,encoderFile="espnet_p_2_q_8.pth", p=2, q=8)
example = torch.rand(1, 3, 224, 224)
traced_script_module = torch.jit.trace(model, example)
traced_script_module.save("model.pt")

The exit is

Encode loaded!

Note that ESPNet uses the default GPU and that an adaptation in Model.py in https://github.com/sacmehta/ESPNet/tree/master/train was required by replacing:

self.encoder.load_state_dict(torch.load(encoderFile)

By:

self.encoder.load_state_dict(torch.load(encoderFile,map_location='cpu'))

Otherwise if you don’t make this adjustment don’t have the ability to launch on a GPU you’ll get the following error:

RuntimeError: Attempting to deserialize object on a CUDA device but torch.cuda.is_available() is False. If you are running on a CPU-only machine, please use torch.load with map_location-torch.device ('cpu') to map your storages to the CPU.
PYTORCH TORCHSCRIPT

BACKUP AND LOAD BY PYTORCH SCRIPT

https://pytorch.org/docs/stable/jit.html

TorchScript is a way to create models that can be made that can be optimized from the PyTorch code.

Any TorchScript program can be saved from a Python process and loaded into a process where there is no Python dependency.

The code below allows you to save the pre-trained ESPNet model that was backed up by the classic torch.save method via the use of TorchScript.

import torch


model = ESPNet(20,encoderFile="espnet_p_2_q_8.pth", p=2, q=8)
example = torch.rand(1, 3, 224, 224)
traced_script_module = torch.jit.trace(model, example)
#Exemple de save avec TorchScript
torch.jit.save(traced_script_module, "scriptmodel.pth")

An example for loader via TorchScript below:

import torch
model = torch.jit.load("scriptmodel.pth")

RESOURCES ON THE SUBJECT

https://pytorch.org/docs/stable/jit.html

https://pytorch.org/tutorials/beginner/Intro_to_TorchScript_tutorial.html

https://stackoverflow.com/questions/53900396/what-are-torch-scripts-in-pytorch

Algorithm the problem of the backpack (Knapsack problem) in more than 128 words

The problem of the algorithmic backpack is interesting and is part of the first digital science and computer science program.

This problem illustrates the gluttonous algorithms that list all the possibilities of solving a problem to find the best solution.

The problem of the backpack is a problem of optimization, i.e. a function that must be maximized or minimized and constraints that must be met.

The problem of the backpack

For a backpack of maximum capacity of P and N items each with its own weight and a set value, throw the items inside the backpack so that the final contents have maximum value.

Example of a statement:

  • Maximum backpack capacity: 11 units
  • Item number: 5
  • Object Values: $10.50,20,30.60
  • Weight of Objects: '1,5,3,2,4'

What is the maximum value that can be put in the backpack considering the maximum capacity constraint of the bag which is 11?

Gluttonous algorithm

An effective solution is to use a gluttonous algorithm. The idea is to calculate the value/weight ratio for each object and sort the object based on this calculated ratio.

You take the object with the highest ratio and add until you can't add any more.

In fractional version it is possible to add fractions of item to the backpack.

Implementation of the problem in non-fractional version

Here is an implementation of the problem in a non-fractional version, i.e. you can't add a fraction of an object to the bag. Only whole objects can be added.

itemsac class: 
    def __init__ (self, weight, value, index): 
        self.index - index         
        self.weight - weight 
        self.value
        self.report - value // weight 
  #Fonction for comparison between two ObjectsSac
  #On compares the ratio calculated to sort them
    def __lt__ (self, other): 
        return self.report< other.rapport 
  

def getValeurMax (weights, values, ability): 
        TableTrie[] 
        for i in range: 
            tableTrie.append (ObjectSac (weigh[i]ts, value[i]s, i)) 
  
        #Trier the elements of the bag by their report
        tableTrie.sort (reverse - True) 
  
        MeterValeur - 0
        for object in tableauTrie: 
            WeightCourant - int (object.weight) 
            ValueCourante - int (object.value) 
            if capacity - weightsCourant '0: 
                #on adds the object to the bag
                #On subtracts capacity
                capacity - weightsCourant 
                MeterValeur - ValueCourante
                #On adds value to the bag 
        return counterValeur 


Weights[1,5,3,2,4] 
Values[10,50,20,30,60] 
capacity - 11
Maximum value - getValeurMax (weight, values, capacity) 
print ("Maximum value in the backpack," ValueMax) 

The result is as follows:

py sacados.py 
Maximum value in backpack - 120

Implementation of the problem in fractional version

In a fractional version of the backpack problem you can add fractions of object to the backpack.

itemsac class: 
    def __init__ (self, weight, value, index): 
        self.index - index         
        self.weight - weight 
        self.value
        self.report - value // weight 
  #Fonction for comparison between two ObjectsSac
  #On compares the ratio calculated to sort them
    def __lt__ (self, other): 
        return self.report< other.rapport 
  

def getValeurMax (weights, values, ability): 
        TableTrie[] 
        for i in range: 
            tableTrie.append (ObjectSac (weigh[i]ts, value[i]s, i)) 
  
        #Trier the elements of the bag by their report
        tableTrie.sort (reverse - True) 
  
        MeterValeur - 0
        for object in tableauTrie: 
            WeightCourant - int (object.weight) 
            ValueCourante - int (object.value) 
            if capacity - weightsCourant '0: 
                #on adds the object to the bag
                #On subtracts capacity
                capacity - weightsCourant 
                MeterValeur - ValueCourante
                #On adds value to the bag 
            else 
                fraction - capacity / weightCouring 
                MeterValeur -Courante value - fraction 
                capacity - int (capacity - (weightsCourant - fraction)) 
                Break
        return counterValeur 


Weights[1,5,3,2,4] 
Values[10,50,20,30,60] 
capacity - 11
Maximum value - getValeurMax (weight, values, capacity) 
print ("Maximum value in the backpack," ValueMax) 

The result is as follows:

py sacados.py 
Maximum value in backpack - 140.0

Build a step-by-step, decentralized application (Ethereum Blockchain Dapp) in more than 128 words – Part 3

This article follows the first two articles on the subject:

The first 2 articles provide a better understanding of the concept of blockchain and decentralized application.

Creating the project

A directory is created for the voting application project on songs.

mkdir vote-song-dapp

To accelerate development we will use a "truffle box": https://www.trufflesuite.com/boxes

It's sort of a template, an application canvas that allows you to focus on the Dapp by having a structure already created.

I will base my explanation on the pet-shop box available here: https://www.trufflesuite.com/tutorials/pet-shop. This is one of the first truffle tutorials to create a Dapp.

This truffle box includes the basic structure of the project as well as the user interface code.

Use the truffle unbox command:

truffle unbox pet-shop

As a reminder the installation of truffle is possible via the order:

npm install -g truffle

If you open the vote-chason-dapp folder with vscode then you get the following tree:

Dapp app project tree example (based on truffle pet-shop)
  • contract: storage of the application's smart contract
  • migration: Migrations allow smart contracts to be transferred to the Ethereum blockchain (local test or mainnet). Migrations also allow you to link smart contracts with other smart contracts and start them.
  • node_modules: The node_modules folder contains libraries downloaded from npm.
  • src: Front-end application directory (customer)
  • test: Storage of tests for the application
  • truffle-config.js: Javascript file that can execute any code needed to create your configuration.

Creating the smart contract

As a reminder we are developing an application that allows to elect the favorite song of voters.

We will first create the part that allows to create a vote for the best song based on 3 eligible songs.

The contract written in solidity is as follows:

TopChanson contract
        struct Song
        uint ID;
        title string;
        uint counter;
    }
    uint public counterDeChansons;
    mapping (uint - Song) public songs;

    function addChansonElligible (string memory nomChanson) private
        CounterDeChansons;
        songs -[compteurDeChansons] Song (CounterDeChansons, NameChanson, 0);
    }

    TopChansons(public) function
        addChansonElligible ("Moonlight");
        addChansonElligible ("Mom the little boats");
        addChansonElligible ("Ah! Crocodiles");
    }

}

Note the use of "mapping (uint – Song) public songs;"

Related: https://solidity.readthedocs.io/en/v0.6.6/types.html#mapping-types

This data structure will allow us to store the titles of eligible songs like a hash table. That is, a table that takes as an access key in our case a uint that is the song ID and allows to recover the value that is a structured song type.

The Song type is structured, see solidity documentation: https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Here there is a special case on the feature addChansonElligible, it takes into argument the name of the song which is a string character chain. If you don't add the keyword "memory" you get the following error:

TypeError: Data location must be "storage" or "memory" for parameter in function, but none was given.

For function settings and return variables, the location of the data must be explained for all type variables (struct, mapping, thong).

The contract is migrated via the order:

truffle migrate --reset

We then get:

Compiling your contracts...
===========================
Compiling ./contracts/Migrations.sol
Compiling ./contracts/TopChanson.sol

To follow …

Build a step-by-step, decentralized application (Ethereum Blockchain Dapp) in more than 128 words – Part 1

This article aims to explain the key concepts of blockchain, dapp (decentralized app), smart contract and tokenization.

Blockchain

A blockchain is a decentralized database, it is shared between several nodes that has a copy of that database.

Block

A request for a user to add data to the database is a transaction. Transactions are grouped and added to a block in the blockchain.

Note that all data in this shared register, the blockchain, is secured by cryptographic hash and validated by an algorithm that is a consensus among network users.

Block concept in a blockchain

Minor

Minors are network users who use a program to validate new transactions and record them on the blockchain.

Example of a miner's farm equipped to calculate transactions on the blockchain (via complex mathematical and cryptographic problem solving), miners receive a "reward" for their work.

Blockchain Ethereum

Ethereum is an open source platform that uses blockchain technology to run decentralized applications (dapps).

This platform is based on the creation of Smart Contract, it is a program that contains data and functions called by applications.

Based on the blockchain there is no centralized database but a register shared and maintained in peer to peer by users.

This technology can be used to exchange currencies or to create decentralized applications that call smart contracts and store their data in blocks of the blockchain.

Public Blockchain

In a public blockchain there is no permission, everyone can join the blockchain network, which means they can read, write or participate with a public blockchain.

Public Blockchains are decentralized, no one has control over the network and they remain secure because the data cannot be changed once validated on the block chain.

Public blockchain platforms such as Bitcoin, Ethereum, Litecoin are un authorized blockchain platforms, striving to increase and protect the anonymity of the user.

Private Blockchain

In a private blockchain there are restrictions to filter who is allowed to participate in the network and what transactions.

Private blockchains tend to be associated with identity management tools or a modular architecture on which you can plug in your own identity management solution.

This may be an OAuth solution service provider that uses Facebook, LinkedIn, for example,…

Token Ethereum

Ethereum tokens or tokens are digital assets that are built from the Ethereum blockchain. These are tokens that attest that you have a value (economic for example). These tokens are based on Ethereum's existing infrastructure.

To store, receive, send ether (cryptocurrency on the blockchain ethereum) or tokens (which are tokens that are digital assets), you need at least one account. The easiest way to create an account is:

It is possible to create its own token to create its decentralized application that uses the public blockchain ethereum.

Tokenisation of financial assets

Tokenization is a method that converts the rights of an asset (financial, real estate …) into digital tokens (tokens).

Example for a 400,000 Euro apartment. Tokenizing it consists of turning it into 400,000 tokens (the number is arbitrary, the Issue can be 4 million or 100 chips).

Tokens are issued on a kind of platform that supports intelligent contracts, for example on Ethereum. The goal is for tokens to be freely exchanged.

When you buy a token, you actually buy a share of the ownership of the asset (from the apartment of 400,000 euros).

Buy 200,000 chips and you own half the assets. The Blockchain is shared register that is immutable, it ensures that once you buy tokens, no one can delete your property.

Decentralized application

Decentralized applications are applications that communicate with the blockchain. The decentralized application interface is similar to any website or mobile application.

The Smart Contract represents the central logic of decentralized application.

Illustration of a DApp that uses a blockchain with smart contracts combined with the looters of Swarm and Whisper.
Source: Ethereum Stack exchange

Smart Contract

Smart Contracts contain all the business logic of a DApp. They are responsible for reading and writing data in the blockchain, so they execute business logic.

Intelligent contacts are written in a programming language called SOLIDITY https://solidity.readthedocs.io, similar to Javascript.

To read on the subject:

ANGULAR in less than 128 words – TypeScript – Part 5

This article follows the first four on the subject ANGULAR and deals with the language TypeScript:

Use of classes

As in other languages a class allows to create objects and gathers variables and functions that are strongly related "Highly Related"

Class example

Class Person
  name: string;
  first name: string;

  To be more
    console.log ('My name is'- this.name' - this.prenom);
  }
}

Modules:

Class storage can be done in separate files, in this case it is a module statement.

The modules make the class accessible outside the file. The class must first be exported via "export" to be visible example of person.ts:

export class Person
  name: string;
  first name: string;

  To be more
    console.log ('My name is'- this.name' - this.prenom);
  }
}

example of hand.ts file that imports the Person class:

import - Person - from "./person";

let person - new person();

Note that there are Angular modules that will be imported with the mention @angular example:

import - Component - from '@angular/core';

Read:

https://www.typescriptlang.org/docs/handbook/modules.html

https://www.angularchef.com/recette/50/

ANGULAR in more than 128 words – Part 1

Angular is a framework for building client applications, based on HTML/CSS and JavaScript/TypeScript.

Angular offers the following benefits:

  • Revealing Pattern Module: organizes the code into one or more modules and gives a better structure.
  • Clean and structured architecture.
  • Reusable code.
  • Application more easily testable.

Architecture:

  • Front-End: Takes care of the presentation logic. Made up of HTML / CSS / TypeScript / Angular
  • Backend: Takes care of business logic. Made up of Data – API

Create a first Angular app:

NodeJS: The Node.js execution environment includes everything you need to run a program written in JavaScript. To install the link https://node.js.org

Node Package Manager: This is an online control utility that facilitates the installation of packages, version management and dependency management.

Angular-Cli: a command line interface to automate your development workflow. It allows you to:

  • Create a new Angular app.
  • Run a development server with "Live Reload" support to preview your app during development.
  • Add features to your Angular app.
  • Run unit tests
  • Run end-to-end tests
  • Build the app for deployment in production
  • Deploy your app to a server

Installing Angular-cli online ordering:

npm install -g @angular-cli

This notation with 'NPM' allows nPM packages to be spaced out of names. Each user and organization on NPM has its own reach and they are the only ones who can add packages.

This is useful for several reasons:

  • Allows organizations to clearly state which packages are "official" and which are not. For example, the scope @angular, ensures that it was published by the Angular core team.
  • The name of the package should be unique to within its scope of publication but not to the entire npm registry.
    For example, the name of the http package is already taken in the main repository npm, but Angular may also have angular/http.

For more details the documentation can be found at this link: https://docs.npmjs.com/

Create an Angular package:

ng new package-test-angular

Edit the code of the Angular project created:

I advise you to edit the code with the vsCode editor: https://code.visualstudio.com/ or with the code editor Sublime Text https://www.sublimetext.com/

If you use vscode the following command can be used at the root of your project.

Code.

Deploy your angular project on the local machine server:

ng serve

The app is then searchable on localhost:4200.

Dijkstra's algorithm in a weighted and oriented graph in more than 128 words

For a source peak given in the graph, the algorithm looks for the shortest path between that node and all the others.

Here one uses a weighted graph, which is a graph in which each arc (case of a oriented graph) receives a weight. A weighted graph is therefore a special type of labeled graph in which the labels are numbers.

The weight of a chain or path is the sum of the weights of the arcs that make up the chain.

The algorithm enters a weighted graph and a summit from which it calculates distances, the steps are:

Initialization phase:

  • On all the tops, a label equal to infinity (or at the maximum possible length – 1) is positioned on all the tops.
  • The label is started on A to 0

Treatment phase:

  • We treat a summit (here we start with A)
  • We mark the summit as visited
  • We release the outbound arches from the summit, i.e. we try to update the value of the top-of-the-finish label by distance.
  • If the value of the road to the top of the finish is lower than the calculated, the top tag is updated with this total distance.
  • The next top to be treated is the one with the lowest weight.

Example:

Algorithm start-up
The outgoing arc A-B is released, the distance is 15, 15 being a better value than infinity we update the B label with 15
The outgoing arc A-C is released the distance 4 being better than the infinity we update the label of the top C
The next top of the algorithm is the one that is not yet visited and has the label with the lowest value. Here it is the c top with the value 4.On r
eleases the outgoing arc C-E, the distance calculated from the top A is 4 – 11 – 15. 15 being better than infinity we update the label of the top E.
The outgoing Arc C-D is released, the distance calculated from the top A is 4 – 2 – 6. 6 being better than infinity we update the label of the top D.

In the next step we visit the summit D because its value is the lowest of the g
raphOn releases the outgoing arc D-E and calculates the distance from the top A which is equal to 9 or a distance shorter than 15 (calculated at the prev
ious stage)We then deselect the arc C-E which was previously calculated as the best route to go from A to E and one updates the E summit with the
value 9.The E summit is ensued treated, there is no outgoing arc so there is no update.
The B-top is processed: the outgoing B-E arc is released, the distance of 15 -5 -20 being higher than the value of 9 of the E summit there is no update and the algorithm ends.

Wide course in The Graphs (BFS)

The graph width path (BFS) is an algorithm used to browse graph data structures. BFS implements a specific strategy to visit all the tops of a graph

BFS starts with a summit, then checks the neighbors of the initial summit, then the neighbors of the neighbors, etc.

At the entrance to the algorithm there is the G graph and a starting point D for which the distance is considered to be 0.

Out of the algorithm are calculated all the distances between the top D and each top of the G graph as well as the tree covering whether the G graph is related (i.e. for any pair of topthere there is a path between them in the graph).

The following tables are used:

  • Distanc[.]e: Stores the distance between D (starting top) and another top of the graph.
  • Fathe[.]r: Stores the father top of a top of the graph traveled.
  • Visit[.]: Stores the visit status of the summit, possible list of values 0:not yet visited,1:Visit in progress,2:Visited

The following functions are used for an F-lane:

  • First (F): Returns the item to the top of the F-lane without removing it.
  • Dequeue(F): Returns the item to the top of the F-line by removing it.
  • Append (F, A): Put element A in the F-lane at the back of the line.

The steps are:

  • Initialization phase
    • 1. For all the summits do
      • Visit – 0 (Not visited yet)
      • Pere – null (Initializes the table)
      • Distance – -1
    • 2. Append (F,D) (adds the starting element)
    • 3. Distanc[R]e – 0 (starting premise)
  • Action phase (G graph route)
    • As long as the F-line is not empty
      • t – First (F)
      • For all neighbors v t do
        • If Visit[v] 0 (summit not visited) then
          • Visit [v]- 1 (Visit in progress)
          • Distance[v] – Distance[t] – 1
          • Father[v] – t
          • Append (F,v)
      • Dequeue (F)
      • Visi[t]t 2

If we detail the steps with the case of the example graph below.

Initialization phase:

Initializing element A is the remote starting element 0, it is colored orange to indicate that the visit is underway.

Visit of the neighbours of Summit A (Summit Visit B)

Summit B passes to during the visit, its distance from A is calculated and summit A is added as the father summit. It is added to the line.

Visit of the neighbours of Summit A (Summit Visit C)

Summit C passes to during the visit, its distance from A is calculated and summit A is added as the father summit. It is added to the line.

Marking A as visited and deleting the queue

A is marked as visited (blue color) and removed from the head of the queue

Visit of the neighbours of Summit B (Summit Visit D)

The summit C being marked as during the visit it will not be visited, one visits the summit D one calculates its distance 2 and one notes the summit B as father of summit B.

Marking B and C as visited and deleting the queue

B is marked as visited (blue color) and removed from the head of the line
C is marked as visited (blue color) and removed from the head of the queue (its neighbor D is marked during the visit)

Marking D as visited and end of algorithm

D is marked as visited (blue color) and removed from the head of the queue.
End of the algorithm

Building the tree covering whether the graph is related

If the graph is related, the result of the path is unfolded and the tree is covered with the graph that contains all the peaks.

Application: The width path of a graph (BFS) is useful for:

  • Check whether a graph is related (all tops are then marked as visited at the end of the algorithm).
  • Calculate distances from a given peak
  • Build a tree covering a graph