storing edges in a data structure

Question

I have a class called Edge, which has attribute source id, target id and weight. 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?

I wrote this blog post a while back about using Nodes and Edges to find a route on a graph representing the London underground, talks about HashMaps and this sort of thing: http://digitalist-alex.blogspot.com/2011/01/breadth-first-implementation-for.html — Alex, Apr 16 '11 at 01:37

score 3 · Accepted Answer · answered Apr 16 '11 at 01:25

3

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.

answered Apr 16 '11 at 01:25

Raph Levien

5,088
25
24

okay so if I were going to use a HashMap then the source, target pair would be another class? Could you please give me a concrete code example of this as I've never done this before.. – aherlambang Apr 16 '11 at 01:30
You can create your own class for the pair. If the id's are just int's, that's probably the most lightweight way to do it. Do remember, though, that you have to override .equals() and .hashCode(). See http://stackoverflow.com/questions/156275/what-is-the-equivalent-of-the-c-pairl-r-in-java for a more general example. – Raph Levien Apr 16 '11 at 01:48
what if the key is just the two strings concatenated together, therefore I don't have to override the equals? as the key is string – aherlambang Apr 16 '11 at 01:50
Concatenating the strings carries a danger. You'll treat ("a", "bc") and ("ab", "c") as the same edge. Using a separator carries a similar danger if the strings might contain that separator. The best way is to create your Edge class, which is basically a pair. – Raph Levien Apr 16 '11 at 02:01
I won't be concatenating three source at a time.. just two.. an edge is a pair – aherlambang Apr 16 '11 at 02:15
Read carefully http://stackoverflow.com/questions/815782/what-is-a-more-unique-delimiter-than-comma-for-separating-strings and then come to your senses and code it as a real datastructure rather than hacking around with string concatenation. Two or three, doesn't matter. – Raph Levien Apr 16 '11 at 02:31
Sorry, but I just still don't get it... if a, b, c is a node then how would I it be possible to get the same edge for this? The possible combinations is only a - b, b = a, a - c, c - a, b -c, c- b – aherlambang Apr 16 '11 at 06:02

Andy Thomas · Answer 2 · 2011-04-16T01:53:19.270

1

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

edited Apr 16 '11 at 01:53

answered Apr 16 '11 at 01:19

Andy Thomas

84,978
11
107
151

So the set of edges in the edge class? – aherlambang Apr 16 '11 at 01:25
The set of edges could itself be a class -- e.g., the Edges class above. That's just an example, by the way. If you develop your own class, you control the interface exposed to clients -- not me, and not the Set class. – Andy Thomas Apr 16 '11 at 01:30
but then inside addEdge I'd have to iterate over m_edges and check if the source target already exists? – aherlambang Apr 16 '11 at 01:33
The map ideas is great, however how could you have a key of source, target? In other words two integer as a key? – aherlambang Apr 16 '11 at 01:39
maybe if I just concatenate two ints together and put it as a String it would work – aherlambang Apr 16 '11 at 01:41
Raph Levien's suggestion of using a Map instead of a Set is a good one. Personally, I'd go with wrapping a Map as shown above, with classes Edge and EdgeData -- the former holding the two nodes, and the latter holding the Edge itself, the weight, and any other data you wish to associate with the edge. – Andy Thomas Apr 16 '11 at 01:42

score 1 · Answer 3 · answered Apr 16 '11 at 05:38

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

storing edges in a data structure

3 Answers3