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 dont d'autres types de files dériveront.

Alias de type pour représenter un dictionnaire d'adjacence

Type représentant les arêtes d'un graphe.

Exemple:

    arête = Edge("E411", 40000, "Ottignies-Louvain-la-Neuve", "Namur")
    arête = Edge("E40", 35000, "Bruxelles", "Gand")
    arête = Edge("Meuse", 45000, "Liège", "Namur")

Construit une arête à partir d'un poids et de deux identifiants de noeud.

Construit une arête à partir d'un poids et de deux identifiants de noeud sous forme de nombre.

Type representant une forêt comme un ensemble d'identifiants de noeuds pointant vers des arbres.

Les identifiants dérivent des identifiants des noeuds d'un graphe. A partir de l'identifiant du noeud d'un graphe, cette structure permet de trouver l'arbre associé dans le dictionnaire trees`. Si l'identifiant d'un noeud pointe vers un arbre dont le parent a le même identifiant, alors ce noeud est une "racine". Les "racines" de l'arbre sont utiles pour les fusionner et pour vérifier l'existence de cycles.

Voir la documentation de la fonction merge! pour plus de détails.

Le nombre de "racines" contenue dans la forêt est également stocké dans l'attribut num_roots.

Forest(G; mode)

Initialise une forêt de composantes connexes à partir d'un graphe. Un arbre de taille 1 ou de rang 0 est créé par noeud du graphe. Cette fonction est conçue pour servir à l'initialisation de l'algorithme de Kruskal.

Arguments

• G (Graph): le graphe à partir duquel construire une forêt de composantes connexes
• mode (String="size") : ("size" ou "rank"). L'attribut à initialiser dans chaque arbre créé

Type representant un graphe comme un ensemble de noeuds et d'arêtes.

Exemple :

node1 = Node("Joe", 3.14)
node2 = Node("Steve", exp(1))
node3 = Node("Jill", 4.12)
edge1 = Edge("Joe-Steve", 2, "Joe", "Steve")
edge1 = Edge("Joe-Jill", -5, "Joe", "Jill")
G = Graph("Ick", [node1, node2, node3], [edge1,edge2])

De façon interne, les noeuds et les arêtes sont stockés en tant que dictionnaire. Ceci permet de retrouver des noeuds/arêtes rapidement à partir de leurs identifiants. De plus, l'adjacence est stockée en tant que dictionnaire ce qui permet facilement d'accéder aux voisins d'un noeud. Attention, tous les noeuds doivent avoir des données de même type. Toutes les arêtes doivent également avoir des données du même type mais pas nécessairement le même type que celui des noeuds. De plus, les noms des noeuds et des arêtes doivent être uniques.

Graph(name::String, nodes::Vector{Node{T}}, edges::Vector{Edge{U}})

Construit un graphe à partir d'une liste de noeud et d'arêtes.

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 implémentation d'une file de priorité permettant une implémentation efficace de l'algorithme de Prim.

Cette structure de donnée stocke des identifiants de noeuds ainsi que des priorités dont le type est paramétrique dans le dictionnaire items. L'ordre de supression des éléments de la file est indiqué par order dont la valeur par défaut est "max". Lors d'un appel à popfirst!, si l'ordre est max, la paire identifiant-priorité ayant la priorité la plus élevée est supprimée. Si l'ordre choisi est "min" alors c'est la paire ayant la plus petite priorité qui est supprimée.

PrimPriorityQueue{U}()

Initialise une file de priorité de Prim de type paramétrique U vide.

Type representant un arbre comme l'identifiant d'un parent, une liste d'identifiants d'enfants et une taille ou un rang d'arbre.

L'identifiant d'un parent dérive de l'identifiant du noeud d'un graphe. Les identifiants des enfants dérivent de l'identifiant de noeuds d'un graphe. La taille d'un arbre est définie comme le nombre d'arbres qui ont cet arbre comme parent. Le rang d'un arbre est un attribut utile pour la procédure d'union de composantes connexes par le rang. Un seul attribut parmi la taille et le rang n'est pas nul. Ce type est principalement utile pour le type Forest.

Tree(parent_id, value; mode)

Initialise un arbre à partir de l'identifiant de sa racine et d'une valeur de taille et de rang (option choisie par l'argumment mode).

Arguments

• parent_id (String): l'identifiant du noeud constituant la racine de l'arbre
• value (Int64): la valeur numérique de la taille ou du rang
• mode (String="size"): ("size" ou "rank"). L'attribut qui doit être initialisé à la valeur value (la taille ou le rang).

length(q)

Retourne le nombre d'éléments d'une file abstraite.

merge!(forest, root_id1, root_id2; mode)

Fonction permettant de fusionner deux arbres à partir de deux identifiants qui ont la propriété d'être des "racines". La fusion s'opère en redéfinissant le parent d'une "racine" par l'autre "racine". De plus, la fusion effectue la compression de chemin: chaque noeud de l'arbre fusionné se connecte à la racine de l'arbre qui englobe.

Pour choisir quelle racine prend l'autre racine comme enfant, 2 possibilités sont proposées.

Union par la taille

La taille des arbres associés est comparée ; l'arbre de plus grande taille englobe l'autre. Cela nécessite que les attributs size des arbres de la forêt ne soient pas nuls.

Union par le rang

Les rangs sont comparés et incrémentés selon la politique classique d'union par le rang.

Arguments

• forest (Forest): forêt dans laquelle se trouvent les 2 arbres à fusionner
• root_id1 (String): identifiant de la racine du premier arbre participant à la fusion
• root_id2 (String): identifiant de la racine du second arbre participant à la fusion
• mode (String="size"): ("size" ou "rank"). Indique le critère retenu pour l'union.

Type de retour

Aucun : fonction in-place.

popfirst!(q)

Si l'ordre de la file (stocké dans q.order) est "max", retire et renvoie un élément de la file ayant la plus grande priorité. Si l'ordre de la file (stocké dans q.order) est "min", retire et renvoie un élément de la file ayant la plus petite priorité.

popfirst!(q)

Retire et renvoie le premier élément d'une file abstraite.

push!(q, name, priority)

Rajoute une paire identifiant priorité à une file de priorité de Prim.

#Arguments

• q (PrimPriorityQueue): La file de priorité permettant une implémentation efficace de l'algorithme de Prim.
• name (String): Un identifiant de noeud qu'on ajoute à la file de priorité.
• priority (U): La priorité de l'identifiant dans la file dont le type est celui des poids des arêtes du graphe que l'algorithme de Prim résout.

	show(node::AbstractNode)

Affiche un noeud.

show(graph::Graph)

Affiche un graphe.

show(q)

Affiche les éléments d'une file abstraite.

show(edge::AbstractEdge{T,U})

Affiche une arête.

add_adjacency!(adjacency::Dict{String, Vector{Edge{U}}}, edge::Edge{U})

Ajoute une arête à un dictionnaire d'adjacence.

add_edge!(graph::Graph{T,U}, edge::Edge{T})

Ajoute une arête au graphe. Met également à jour le dictionnaire d'adjacence du graphe. Si l'identifiant de l'arête existe déjà dans le graphe, une erreur est renvoyée. Si les identifiants de noeuds correspondant à l'arête n'existent pas dans le graphe, une erreur est renvoyée.

add_edge(graph::Graph{T,U}, node_1::Node{T}, node_2::Node{T}, weight::U)

Fonction de commodité. Crée dynamiquememnt une arête à partir des noeuds node_1 et node_2. L'information est vue comme un poids : l'argument weight doit être un nombre.

add_node!(graph::Graph{T,U}, node::Node{T})

Ajoute un noeud au graphe. Si l'identifiant du noeud existe déjà dans le graphe, une erreur est renvoyée.

Construit un dictionnaire d'adjacence à partir d'une liste d'arêtes.

Exemple:

    arête1 = Edge("E19", 50000, "Bruxelles, "Anvers")
    arête2 = Edge("E40", 35000, "Bruxelles", "Gand")
    arête3 = Edge("E17", 60000, "Anvers", "Gand")
    arêtes = Vector{Edge{Int}}[arête1,arête2,arête3]
    adjacency(arêtes) = 
        ("Bruxelles" => [arête1, arête2], "Gand" => [arête2, arête3], "Anvers" => [arête1, arête3]).

data(node::AbstractNode)

Renvoie les données contenues dans le noeud.

edges(graph::AbstractGraph)

Renvoie la liste des arêtes d'un graphe.

find(forest, node_id)

Retourne la racine de l'arbre associé au noeud d'identifiant node_id dans la forêt forest. Itère de parent en parent jusqu'à trouver un identifiant dont le parent est lui-même.

Arguments

• forest (Forest): forêt dans laquelle rechercher l'arbre auquel est rattaché le noeud
• node_id (String): identifiant du noeud à rechercher dans la forêt

Exemple

julia> find("24", forest)
Tree("7", 12)
# Le noeud d'identifiant "24" est contenu dans l'arbre de la forêt dont la racine est d'identifiant "7", et de taille 12.

is_empty(q)

Indique si une file abstraite est vide.

kruskal(G; mode)

Implémentation de l'algorithme de Kruskal pour identifier un arbre de recouvrement minimal d'un graphe. Renvoie un tuple contenant le coût et une liste des arêtes formant l'arbre de poids minimal. Si le graphe n'est pas connexe, une erreur est renvoyée.

Arguments

• G (Graph): le graphe dans lequel il faut identifier un arbre de recouvrement minimal
• mode (String="size"): ("size" ou "rank"). Précise le mode d'union entre les composantes connexes qui doit être utilisé.

Type de retour

Float64, Vector{Edge}

Exemples

julia> kruskal(graph, mode="rank")

nnodesto_read(format::String, n::Int, dim::Int)

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

name(n::Any)

Renvoie le nom de l'objet passé en argument.

nb_edges(graph::AbstractGraph)

Renvoie le nombre d'arêtes d'un graphe.

nb_nodes(graph::AbstractGraph)

Renvoie le nombre de noeuds du graphe.

nodes(graph::AbstractGraph)

Renvoie la liste des noeuds du graphe.

Affiche un graphe étant donnés 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")

Trace un graphe directement depuis un objet Graph.

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

prim(G)

Implémentation de l'algorithme de Prim, le premier noeud est choisi aléatoirement parmi les noeuds du graphe. Si le graphe n'est pas connexe, une erreur est renvoyée.

Arguments

• G(Graph): le graphe sur lequel on exécute l'algorithme de Prim

prim(G, initnodeid)

Implémentation de l'algorithme de Prim. Si le graphe n'est pas connexe, une erreur est renvoyée.

Arguments

• G(Graph): le graphe sur lequel on exécute l'algorithme de Prim
• initnodeid (String): l'identifiant du noeud initial

read_edges(header::Dict{String}{String}, filename::String)

Analyse un fichier .tsp et renvoie une liste d'arêtes sous forme brute de tuples.

read_header(filename::String)

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

read_nodes(header::Dict{String}{String}, filename::String)

Analyse un fichier .tsp et renvoie une liste d'objets de type Node. Si les coordonnées ne sont pas données, les noeuds sont instanciés avec leur identifiant et NaN`. Le nombre de noeuds est dans header["DIMENSION"].

read_stsp(filename::String; quiet::Bool=true)s

Lit un fichier .tsp et instancie un objet Graph correspondant après avoir construit ses noeuds et ses arêtes.