#20 Graph impl improvements

Mark Hale

The following would help improve performance of the provided graph impls:
- use linkedhashmaps (speeds up iterating over vertices and neighbours - important for many algorithms)
- constructors to provide initial hashmap capacities (important when creating a large number of large graphs)
- addVertex() should put an EMPTY_MAP instead of a new Map (a new Map has a capacity of 16, this can waste quite alot of memory for leaf nodes)


  • Joshua O'Madadhain


    Thanks for your suggestions. Some responses:

    In future we will be refactoring the Graph implementations to allow users to provide their own Map factories to be used internally by the class. This will give you the flexibility that you're looking for.

    Yes, LinkedHashMap is faster for iterating. It also takes a bit more space, though.
    That said, we already have a couple of implementations that use LHM, mostly because it provides a consistent iteration ordering (see the Ordered implementations).

    EMPTY_MAP is immutable, so we'd have to add an extra internal method (to be used for writes to the map but not reads) to say "if this map is EMPTY_MAP, make a new one and use it instead". This isn't necessarily a huge problem but it does complicate the code slightly. You can certainly do this yourself in your own Graph implementation, however.


  • Mark Hale

    Mark Hale - 2011-03-01

    In my own impl, I actually have addVertex() use an EMPTY_MAP, and addEdge() use a singletonMap(), with these growing to a Flat3Map, then a LinkedHashMap. This made a huge difference to the size of the graphs I could hold in memory.

  • Joshua O'Madadhain

    What map creation are you talking about in addEdge()?

  • Mark Hale

    Mark Hale - 2011-03-02

    addEdge() calls addVertex() which creates a map. In my impl of addEdge(), I dont call addVertex(), I handle that part inline. If the graph does not contain v1,v2 then I do vertices.put(v1, singletonmap(v2, e)), etc. If it does, and the existing map is empty or singleton then i replace it with a modifiable map such as flat3 or hash.


Log in to post a comment.