J'ai besoin de construire un graphique non dirigé. Je n'ai pas besoin de faire quelque chose de trop chic, mais idéalement, cela fonctionnerait comme ceci: existe une bonne structure de données dans SML / NJ pour modéliser ces relations? Devrais-je simplement rouler la mienne? P> Je suis allé de l'avant et j'ai essayé de rouler le mien, mais j'obtiens une erreur de déséquilibre lorsque j'essaie de le tester. Mon expérience avec les structures et les foncteurs SML est assez basique, alors je pense que je fais quelque chose de manifestement faux. Comment puis-je obtenir cela pour travailler? Aussi, pouvez-vous m'aider à faire cela un lorsque je fais p> i Obtenez une incompatibilité de type: P> mises à jour h1>
'un graphique code>? Cela semble avoir plus de sens, sémantiquement. p> code h2>
erreur h2>
Error: operator and operand don't agree [literal]
operator domain: UDG.graph * ?.UDG.node * ?.UDG.node
operand: UDG.graph * int * int
in expression:
UDG.addEdge (UDG.empty,1,2)
4 Réponses :
Il existe plusieurs possibilités avec des avantages et des inconvénients différents adaptés à différentes opérations sur les graphiques. Cette belle intro donne des antécédents et des exemples de Utilisation de listes de adjacence et de matrices d'adjacence.
Les utiliser d'une manière indéterminée implique des échanges de commerce (vitesse des vers). Ce matériel de cours passe plus en détail sur la adjacence Style de liste et fournit des réflexions sur les modifications possibles à utiliser dans une utilisation indéterminée.
Le -1 devrait-il donner une indication sur pourquoi?
Je suis désolé mais j'ai voté votre réponse afin que cela ne soit pas accepté automatiquement. Pas que ce n'est pas utile, c'est juste que je ne le pense pas (ni les autres réponses) méritent d'être accepté encore. Si vous allez de l'avant et que vous le modifiez, je rétracterai mon -1.
Assez juste, je n'ai pas beaucoup à offrir sur votre message d'erreur, j'ai bien peur, SML n'est pas ma forte, cependant de demander pourquoi vous avez roulé le vôtre en utilisant ceux fournis dans le papier lié ...
Je me sens comme un cul pour ne pas regarder vos liens; Je viens de supposer qu'ils étaient la liste des adjacents standard vs matrice. Même s'ils ne sont pas exactement ce que je cherchais, ils étaient toujours utiles.
Un très facile serait une hache de hashtable, avec la clé que le nœud source et la valeur en tant que liste de nœuds de connexion. Ensuite, écrivez une fonction Ajouter deux insertions de hashtable, une AS (SRC, TGT), l'autre que (TGT, SRC).
dans OCAML: P>
let add n1 n2 =
let aux n1 n2 =
match Hashtbl.find_option tbl n1 with
| None -> Hashtbl.add tbl n1 [n2]
| Some nodes -> Hashtbl.replace tbl n1 (n2::nodes)
in
let _ = aux n1 n2 in
aux n2 n1
OK, je ne connais pas cette langue (veuillez pardonner mon ignorance):
J'utiliserais simplement la structure suivante: p>
V.E1.E2.En+1 V2.E1.E2.En+1 Vn+1.E1.E2.En+1
C'est en fait une jolie idée astucieuse. Surtout si la structure de données doit être remplie d'abord, puis utilisée à des fins de visualisation. Je fais un projet de passe-temps qui vise à créer une telle visualisation et je vais certainement essayer cette approche.
Nous pouvons représenter un graphique en tant que liste de listes, nous appelons cette DataStructure: une liste de adjacence .
hmm dans votre message d'erreur, il est écrit 'udg.addedge (udg.empty ..... peut-être que c'est peut-être essayant de multiplier la chaîne' vide 'par udg.node? Désolé de ne pas familier avec SML