Extending this adjacency list implementation

Question

What would be the best way to change the implementation of this adjacency list implementation to include a 'weight' between two vertices?

If I later add an edge between the two same vertices I've previously made, I just want to increase it's weight.

http://www.keithschwarz.com/interesting/code/edmonds-matching/UndirectedGraph.java.html

Andrew Lutsenko Andrew Lutsenko · Accepted Answer · 2014-10-16T00:43:06

Instead of storing the graph as a map of nodes to set of nodes you can store it as map of nodes to set of (node,weight) pairs (which also can be a map) So instead of

    private final Map<T, Set<T>> mGraph = new HashMap<T, Set<T>>();

it will be

    private final Map<T, Map<T, Integer>> mGraph = new HashMap<T, Map<T, Integer>>();

In current implementation adding an edge is simply inserting a new one into a set, with weights you will have to read current weight, increment it and store in the map. Be mindful of corner cases to check like when removing an edge and if it's weight becomes 0 you should remove the entry from the map.

Extending this adjacency list implementation

1 Answers