storing edges in a data structure

I have a class called Edge, which has attribute source id, target id and wei开发者_Go百科ght. I want to store this edge in a set data structure, so in the set there won't be duplicates of edges (i.e: edges with the same source and target id).

The problem is this: I want to add an Edge to this data-structure. If an edge already exist in the data-structure I don't need to add it again, I just need to add the weight of the existing edge with the edge that I am trying to add.

I am pretty sure that I have to override the add function of the set. Can someone give me a pointer on this? What's the best data structure to use in java for this?

---

A few suggestions.

The underlying data structure you want is probably a map (with HashMap probably being the best concrete implementation), not a set. The key should be the (source, target) pair, and the value can be your Edge object. If you're super concerned about duplication, there are ways of dealing with that, one of which is to actually store only weight as the value.

Second, this is calling out for a Graph class. If you design the interface well, it hides the internal implementation details. I recommend highly using composition rather than inheritance. In other words, your Graph has-a map, rather than is-a map.

Also take a look at existing code such as JGraphT, which already has a weighted directed graph, the same beast as you describe above. Sometimes it's better not to reinvent things from scratch.

Good luck.

---

An alternative is to wrap the set of edges in your own class, which provides exactly the interface you wish to support.

This is a specific case of choosing between composition and inheritance. In general, composition is preferred to inheritance, though that too has its place.

For example, here's a rough sketch of a possible class (EDIT: using a Map)

   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 ); }
   }

---

Well, the Set.add() method returns a boolean value indicating if a new item was successfully added to the set. If it returns false is because the item was already there. Based on that you could easily write your algorithm. The ugly part is having to iterate the set to update the value, right?

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
    }
   }
}

Based on this, I assume that what you want is just a way to beautify all this iteration boilerplate code.

A solution that I like is using LambdaJ Collections to update the weight of an existing Edge.

if (!edges.add(newEdge)) {
   with(edges).first(is(newEdge)).updateWeight(newEdge.getWeight());
}

I do not know what you are looking for, but this approach would be just three lines of code. Quite simple from my point of view.

I wrote a small example to illustrate better the idea:

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);