STSP.jl

Type abstrait dont d'autres types d'arêtes dériveront.

Type abstrait dont d'autres types de graphes dériveront.

Type abstrait dont d'autres types de noeuds dériveront.

Type abstrait de Queue

Type abstrait d'un composant connexe: noeud enfant pointant vers le noeud parent .

Type abstrait d'un node_priority.

Type abstrait d'un weighted_node.

Type représentant les aretes d'un graphe.

Exemple:

    noeud1 = Node("James", 12)
    noeud2= Node("Kirk",14)
    
    edge=Edge("(noeud1, noeud2)",12,noeud1,noeud2)

Type representant un graphe comme un ensemble de noeuds.

Exemple :

n1 = Node("Joe", 3.14)
n2 = Node("Steve", exp(1))
n3 = Node("Jill", 4.12)
e1=Edge("1,2",10,n1,n2)
e2=Edge("1,3",100,n1,n2)
G = Graph("Test", [n1, n2, n3],[e1,e2])
show(G)

Attention, tous les noeuds doivent avoir des données de même type.

Type représentant les noeuds d'un graphe.

Exemple:

    noeud = Node("James", [π, exp(1)])
    noeud = Node("Kirk", "guitar")
    noeud = Node("Lars", 2)

Type représentant une file de priorité avec des éléments node_priority de type T.

Constructeur d'une composante connexe à partir d'un noeud

Type node_priority contentant 4 attributs : son nom (de type String), le noeud en lui-même (de type Node{T}), son parent (qui est soit de type Node{T}, soit Nothing), et sa priorité (qui est un nombre).

node_priority(node::Node{T}) where T

Constructeur du type node_priority. On va initialiser le parent à nothing et la priorité à Inf

Arguments

• node::Node{T}: le noeud sur lequel on se base pour construire l'élément.

Type weighted_node contentant 4 attributs : son nom (de type String), le noeud en lui-même (de type Node{T}) et son poids (qui est un nombre).

weighted_node(node::Node{T}) where T

Constructeur du type node_priority. On va initialiser le poids à zero

Arguments

• node::Node{T}: le noeud sur lequel on se base pour construire l'élément.

==(p::node_priority, q::node_priority)

Définition d'une relation d'égalité entre éléments de type node_priority

isless(p::node_priority, q::node_priority)

Définition d'une relation d'ordre entre éléments de type node_priority

Donne le nombre d'éléments sur la file.

popfirst!(q::AbstractQueue{T}) where T

Retire et renvoie l'élément de plus basse priorité

Arguments

• q::AbstractQueue{T}: file de priorité considérée

push!(q::AbstractQueue{T}, item::node_priority{T}) where T

Ajoute l'élément item à la file de priorité q

Arguments

• q::AbstractQueue{T}: file de priorité considérée
• item::node_priority{T}: élément à ajouter à la file

Affiche un graphe

Affiche un arete.

Affiche un noeud.

show(q::AbstractQueue{T}) where T

Affiche une file de priorité.

Arguments

• q::AbstractQueue{T}: file de priorité considérée

Renvoie la liste des arêtes du graphe.

Renvoie le nom du graphe.

Renvoie la liste des noeuds du graphe.

Ajoute un arrete au graphe.

Ajoute un noeud au graphe.

Calculate la valeur réel du cout de la tournée retourner par un algorithme, spécifiquement pour hk, puisque le cout de l'arbre de l'arbre 1-tree change au fil des itérations.

Copie d'une graphe

Renvoie les données contenues dans l'arête.

Renvoie les données contenues dans le noeud.

calcul de degrees de chaque noeud et le sous gradient

La fonction finetuningepsilonhk permet de déterminer le meilleur critère d'arret dans list_epsilon pour trouver la tournée minimale pour hk!, tout en gardant les autres paramètres fixes.

La fonction finetuningstartepsilon_hk permet de déterminer la tournée minimale pour hk! en focntion du noeud de départ et du critère d'arret, tout en gardant les autres paramètres fixes.

La fonction finetuningstarthk permet de déterminer le point de départ optimal pour trouver la tournée minimale pour hk!, tout en gardant les autres paramètres fixes. #args: filename : Pour création du graphe epsilon : critère d'arret pour l'algorithme hk #returns: Tournée : La tournée minimale étant donnée le meilleur point de départ cost : Le cout de la tournée Id : L'indice du meilleur noeud de départ

finetuning_start_rsl(filename::String)

La fonction finetuningstartrsl permet de déterminer le point de départ optimal pour trouver la tournée minimale pour rsl. #args: filename : Pour création du graphe #returns: Tournée : La tournée minimale étant donnée le meilleur point de départ cost : Le cout de la tournée Id : L'indice du meilleur noeud de départ

Création de la tournée minimale en utilsant un parcours en préordre

L'algorithme hk pour calculer une tournée optimale. args:

graph   : Le graphe où l'on veut chercher la tournée optimale
idx     : L'indice du noeud de départ
epsilon : Critère d'arret

Indique si la file est vide.

liaison de deux composantes connexes dans un ensemble de composantes connexes

Fonction auxiliaire de read_edges, qui détermine le nombre de noeud à lire en fonction de la structure du graphe.

Renvoie le nom de l'arêtes.

Renvoie le nom du noeud.

Renvoie le nombre de arête du graphe.

Renvoie le nombre de noeuds du graphe.

Renvoie le noeud1 de l'arêtes.

Renvoie le noeud2 de l'arêtes.

Création de 1-arbre pour l'algorithme hk!

Parcours en préordre d'une arbre (Parcour dans l'ordre de visite comme Prim)

parent!(p::node_priority,parent::Node)

Mise à jour du parent d'un élément de type node_priority

Arguments

• p::node_priority: élément de type node_priority dont on va vouloir modifier le parent
• parent::Node: noeud qui sera le nouveau parent de la node_priority.

Affiche un graphe étant données un ensemble de noeuds et d'arêtes.

Exemple :

graph_nodes, graph_edges = read_stsp("bayg29.tsp")
plot_graph(graph_nodes, graph_edges)
savefig("bayg29.pdf")

Fonction de commodité qui lit un fichier stsp et trace le graphe.

prim(graph::Graph{T,S},start::Node{T}) where {T,S}

Algorithme de Prim, qui renvoie un vecteur d'arêtes représentant un arbre de recouvrement minimal du graph donné en argument, et le poids total de cet arbre de recouvrement minimal.

Arguments

• graph::Graph{T,S}: le graph considéré dont on cherche un arbre de recouvrement minimal.
• start::Node{T}: le noeud de start pour la création de l'arbre de recouvrement minimal

priority!(p::node_priority, priority::Number)

Mise à jour du poids d'un élément de type weighted_node

Arguments

• p::weighted_node: élément de type node_priority dont on va vouloir modifier la priorité
• priority::Number: nouvelle valeur de la priorité

priority!(p::node_priority, priority::Number)

Mise à jour de la priorité d'un élément de type node_priority

Arguments

• p::node_priority: élément de type node_priority dont on va vouloir modifier la priorité
• priority::Number: nouvelle valeur de la priorité

Analyse un fichier .tsp et renvoie un dictionnaire avec les données de l'entête.

Analyse un fichier .tsp et renvoie un dictionnaire des noeuds sous la forme {id => [x,y]}. Si les coordonnées ne sont pas données, un dictionnaire vide est renvoyé. Le nombre de noeuds est dans header["DIMENSION"].

Renvoie les noeuds et les arêtes du graphe.

L'algorithme rsl pour déterminer une tournée minimale approximative à partie d'un noeud départ choisi

Liaison de deux racines de noeuds données en argument dans un ensemble de composantes connexes

Mise à jour des poides des arretes d'un graphe