{"push_id":965777350,"size":1,"distinct_size":1,"ref":"refs/heads/master","head":"af44761113af50f1955feceac9dd7dfe2d127bbf","before":"693c8d94861f627fd772c347b4644773167b3990","commits":[{"sha":"af44761113af50f1955feceac9dd7dfe2d127bbf","author":{"email":"ab697e0c623b7d127ab7c4e5c43c8f31a0c03f79@google.com","name":"jasexton"},"message":"Reduce memory footprint of mutable graphs by roughly 10%. Considering the increase that [] yielded, getting this back down is definitely good.\n\nThis is done by using HashSets instead of LinkedHashSets for the various internal data structures stored in NodeConnections. Note that we still maintain insertion order on nodes() and edges(), because those are the keysets of LinkedHashMaps. As \"outer level\" structures (i.e. only 1 per graph), making those HashMaps instead of LinkedHashMaps would have a relatively small effect on memory footprint compared to changing the many \"inner level\" Sets inside NodeConnections.\n\nAs for the question of whether we WANT to maintain insertion order, that's not what we were doing anyway, and implying it is what we were doing could be dangerous if someone relies on it. For example, the order in which nodes becomes predecessors or successors to other nodes can be completely different from the order in which the nodes were inserted to the graph. So there is no consistent ordering of nodes, each call to predecessors() or successors() will yield a different \"ordering\" than that of nodes(). To complicate the matter even further, there are methods like incidentEdges() and adjacentNodes() on directed graphs. These are simply the union of two other sets, which by its nature will not preserve any ordering (a union iterates over the elements in set1, followed by the elements of set2 that were not in set1), so we have yet another inconsistent \"ordering\". For now, I propose we should only guarantee insertion order on a graph's nodes() and edges(), and not any other accessors.\n\nAs a side note, of the two problems mentioned, the former will not be a problem when we allow \"sorted nodes/edges\" because the inner Sets can simply be TreeSets as well, preserving the same ordering as the outer level TreeMaps. The implementation of Sets.union() will still prove to be problematic, but the implementation could be presumably be modified to support SortedSets if we want to guarantee that any Set<N> or Set<E> accessor will be sorted if the Graph is created with a Comparator<N> or Comparator<E>.\n-------------\nCreated by MOE: https://github.com/google/moe\nMOE_MIGRATED_REVID=113885975","distinct":true,"url":"https://api.github.com/repos/google/guava/commits/af44761113af50f1955feceac9dd7dfe2d127bbf"}]}