Guava: Graph.successors(): add support for ordering the nodes

[mfulton26]

Graph.successors() returns nodes in an undetermined order which makes it difficult to use Graph as a rooted tree where the ordering of the children is important (e.g. something similar to XML) with a schema that orders some elements).

I have the following workaround but it seems expensive (although for small trees I suppose it doesn't really matter):

fun <N> Graph<N>.children(node: N): Set<N> {
    return nodes().toMutableSet().apply { retainAll(successors(node)) }
}

Can supported be added to specify the order of nodes returned by successors()?

[jrtom]

I agree, that seems like a really expensive workaround. :(

A somewhat less expensive workaround is below, assuming that your tree is fixed (not being mutated). It costs you an extra HashMap and a copy of successors(), but for nodes with a small number of successors that shouldn't be a big deal.

If your tree is being mutated, I don't have any great suggestions for you; you'd essentially have to listen to the mutations and update nodeIndex ad hoc, which would be kind of a pain (and probably hideously inefficient). :/

In general, at the moment, if you want successors() to be ordered, you need to do the sorting yourself.

// build this index once at tree creation time; this establishes the ordering
// as returned by nodes()' Iterator
Map<N, Integer> nodeIndex = new HashMap<>();
int i = 0;
for (N node : graph.nodes()) {
  nodeIndex.put(node, i++);
}

Comparator<N> nodeComparator = new Comparator<N>() {
  int compare(N n1, N n2) {
    return nodeIndex.get(n1) - nodeIndex.get(n2);
  }
}
...
fun <N> Graph<N>.children(node: N): Set<N> {
    return Collections.sort(new ArrayList<N>(graph.successors(node)), nodeComparator));
}

[jrtom]

Adding to my observations from above: if you want the successors of a node in a specified order, then your major options are:
(1) roll your own implementation of the interface (subclassing AbstractGraph if at all possible)
(2) sort the successors yourself as you retrieve them.

I don't expect Guava to provide an implementation that provides the in the near future; if you're reading this and you'd like us to reconsider, please leave a comment (and ideally explain why (2) is not practical in your case).

[ejemba]

Hi @jrtom
I'm considering using common.graph for an important project and the fact that successors() is not sorted was kind of unexpected ... I'll sort them (2) but this is not practical since I'll need a full scan of all my nodes before (I can have a huge number of them) . I'd prefer not having to do it myself :)

[jrtom]

@ejemba
In general, one should assume that Sets are unsorted. Even their iteration order is not guaranteed to be the same from iteration to iteration.

The reasons that we don't (and probably won't) provide support for sorting the successors() are:
(1) Insertion-ordered sorting on a per-successors()would either be inconsistent with the overall insertion ordering for the graph as a whole, or would require extra internal data structures (such as the one listed above) to maintain that ordering for each adjacency set.
(2) Comparator-ordered sorting would require that we either (a) pay the cost of sorting internally every time you called for a node's successors, or (b) use a different data structure for each node to keep the sorted order; this would require considerably more space. The former is not an improvement over what you can do yourself, and the latter bloats the size of the graph implementation considerably.
(3) In all the above cases (except for the "use different per-node data structures" one) it would be at best really difficult--perhaps impractical--to retain the current invariant that successors() returns an unmodifiable view, i.e., if the successor set changes that will be reflected in the set returned.

Note that you don't need a separate scan of your nodes in order to sort them; you can create indices for them as you add them to the graph, which should be fast:

// build the graph
MutableGraph<N> graph = GraphBuilder.directed().build();
// import the nodes
Map<N, Integer> node_index = new HashMap<>();
int index = 0;
for (N node : inputNodes) {
  graph.addNode(node);
  node_index.put(node, index++);
}

// add edges, etc.

Of course, if your node type is Comparable you don't even need to do that.

Hope that helps.

[Gaff]

@jrtom Apologies for the thread-necromancy - but as a corollary to this, since the traverser classes call sucsessors() - does this mean that one should never expect graph traversal to be done in a deterministic order?

[nymanjens]

Hi, I'm a also a maintainer of this library and just added the possibility of returning successors in insertion order. This should be included in the next Guava release for Graph and ValueGraph. Network support comes later.

Example of how to enable this:

GraphBuilder.directed().incidentEdgeOrder(ElementOrder.stable()).build()

This gives the following guarantees:

• edges(): Stable order
• adjacentNodes(node): Connecting edge insertion order
• predecessors(node): Connecting edge insertion order
• successors(node): Connecting edge insertion order
• incidentEdges(node): Edge insertion order

[Gaff]

@nymanjens - Any idea when this might get released? Thanks!

[nymanjens]

The master branch has this implemented for Graph and ValueGraph. I'm currently working on Network support.

Looks like the latest release doesn't yet contain this, but it should be in the next one. I don't know when that will be though.

[nymanjens]

This was released yesterday: https://github.com/google/guava/releases/tag/v29.0

[ckiatng]

Hi @nymanjens , thank you and I have been waiting for this. However, it does not work for me though I tried as suggested
GraphBuilder.directed().incidentEdgeOrder(ElementOrder.stable()).build()

[nymanjens]

Your snippet should build a MutableGraph that guarantees a stable edge order. Can you explain what expectation you exactly had about the built graph?

[ckiatng]

Yes I was building MutableGraph as well, I did a deeper dive. It looks like my test using org.hamcrest.Matchers.contains(E... items) doesn't assert the Iterable returned from treeGraph.depthFirstPreOrder() properly.

I would test properly again and provide you my findings.