stocker des arêtes dans une structure de données

Question

J'ai une classe appelée Edge, qui a un identifiant de source d'attribut, un identifiant de cible et un poids. Je veux stocker ce bord dans une structure de données définie, donc dans l'ensemble il n'y aura pas de doublons d'arêtes (c'est-à-dire des arêtes avec les mêmes identifiants source et cible). Le problème est le suivant: Je souhaite ajouter un Edge à cette structure de données. Si une arête existe déjà dans la structure de données, je n'ai pas besoin de la rajouter, j'ai juste besoin d'ajouter le poids du bord existant avec le bord que j'essaye d'ajouter.

Je suis assez sûr que je dois remplacer la fonction d'ajout de l'ensemble. Quelqu'un peut-il me donner un pointeur? Quelle est la meilleure structure de données à utiliser dans Java pour cela?

Answer 1

Quelques suggestions.

La structure de données sous-jacente que vous voulez est probablement une carte (avec HashMap étant probablement la meilleure implémentation concrète), pas un ensemble. La clé doit être la paire (source, cible) et la valeur peut être votre objet Edge. Si vous êtes très préoccupé par la duplication, il existe des façons de gérer cela, dont l'une consiste à ne stocker que le poids comme valeur. Deuxièmement, cela appelle une classe Graph. Si vous concevez bien l'interface, elle cache les détails de l'implémentation interne. Je recommande fortement d'utiliser la composition plutôt que l'héritage. En d'autres termes, votre graphique a une carte plutôt qu'une carte.

Jetez également un coup d'oeil au code existant tel que JGraphT, qui a déjà un graphe orienté pondéré, la même bête que celle que vous décrivez ci-dessus. Parfois, il vaut mieux ne pas réinventer les choses à partir de zéro.

Bonne chance.

Answer 2

Une alternative consiste à envelopper l'ensemble des bords dans votre propre classe, ce qui fournit exactement l'interface que vous souhaitez prendre en charge.

Ceci est un cas spécifique de choix entre composition et héritage. En général, la composition est préférée à l'héritage, bien que cela ait aussi sa place.

Par exemple, voici une esquisse d'une classe possible (EDIT: en utilisant une carte)

public class Edge { ... } 

    public class EdgeData { 
     public Edge getEdge() { ... } 
     public float getWeight() { ... } 
    } 

    public class Edges { 
     private Map<Edge,EdgeData> m_edges = new HashMap<Edge,EdgeData>(); 
     public addEdge(EdgeData edge) { 
      // Do what you've said above. 

     } 
     public Map<Edge,EdgeData> getEdges() { return Collections.unmodifiableMap(m_edges); } 
    } 

Answer 3

Eh bien, la méthode Set.add() renvoie une valeur booléenne indiquant si un nouvel élément a été ajouté avec succès à l'ensemble. Si elle renvoie false est parce que l'élément était déjà là. Basé sur cela, vous pouvez facilement écrire votre algorithme. La partie la plus laide est d'avoir à répéter l'ensemble pour mettre à jour la valeur, non?

if(!edges.add(newEdge)){ 
    Iterator<Edge> iter = edges.iterator(); 
    while(iter.hasNext()){ 
    Edge edge = iter.next(); 
    if(edge.equals(newEdge)){ 
     edge.updateWeight(newEdge.getWeight()); //this.weight+=moreWeight 
    } 
    } 
} 

Sur cette base, je suppose que ce que vous voulez est juste une façon d'embellir toute cette itération code passe-partout.

Une solution que j'aime utilise LambdaJ Collections pour mettre à jour le poids d'un Edge existant. Je ne sais pas ce que vous cherchez, mais cette approche ne serait que de trois lignes de code. Assez simple de mon point de vue.

J'ai écrit un petit exemple pour mieux illustrer l'idée:

Jedi obiwan = new Jedi("Obiwan", 30, 40); // name, age and power 
Jedi luke = new Jedi("Luke", 18, 25); 
Jedi mace = new Jedi("Mace-Windu", 100, 450); 
Jedi yoda = new Jedi("Yoda", 150, 1000); 

Jedi obiAgain = new Jedi("Obiwan", 11, 40); 

Set<Jedi> jedis = new HashSet<Jedi>(asList(obiwan, luke, mace, yoda)); 

if (!jedis.add(obiAgain)) { 
    with(jedis).first(is(obiAgain)).updatePower(obiAgain.getPower()); 
} 

System.out.println(jedis);