graph interface adjustments for big graphs

[Dimitrios Michail]

Hi guys,

following the discussion for enhancing our interface in order to support big graphs, I

created a first draft:

https://github.com/d-michail/jgrapht/tree/biggraph-interface-support

This means adding the following methods, all with default implementations which 

just delegate to our current set implementation.

```

Iterable<E> edgeSetIterable();

int numberOfEdges();

long numberOfEdgesAsLong();

Iterable<V> vertexSetIterable();

int numberOfVertices();

long numberOfVerticesAsLong();

Iterable<E> edgesOfIterable(V vertex);

long degreeOfAsLong(V vertex);

Iterable<E> incomingEdgesOfIterable(V vertex);

long inDegreeOfAsLong(V vertex);

Iterable<E> outgoingEdgesOfIterable(V vertex);

long outDegreeOfAsLong(V vertex);

```

A big graph implementation will be free to implement these differently and thus many algorithms will be able to execute without instantiating Sets. Some of our algorithms will need to be changed in order to use these methods instead of the Set versions.

In any case these changes are backward compatible.

Questions:

  - Do we also add an iterable version of `Set<E> getAllEdges(V sourceVertex, V targetVertex)`?

  - Do we also add an iterable version of `Set<E> removeAllEdges(V sourceVertex, V targetVertex)`?

  - Better names?

  - Other ideas?

Best,

Dimitrios

[Dimitrios Michail]

Sebastiano pointed out that we should also explain in the interface of `numberOfVertices()` what happens in case the graph has more vertices than can fit inside an int. 

Do we return -1, Integer.MAX_SIZE or throw an java.lang.ArithmeticException? 

I would probably go with the latter. Opinions?

--Dimitrios

[John Sichi]

Adding types to names make the overall interface a bit clunky.  A different approach would be to introduce a new interface GraphIterables, and put all the new methods there.  Then the existing Graph interface would only get one new method:  GraphIterables<V,E> graphIterables().  The default implementation would return an inner class which delegates to the old methods.

interface GraphIterables<V,E>

{

Iterable<E> edges();

long edgeCount();

Iterable<V> vertices();

long vertexCount();

Iterable<E> edgesOf(V vertex);

Iterable<E> allEdges(V sourceVertex, V targetVertex);

...
}

I think this will also make our documentation clearer, emphasizing that it's a conscious choice that an application/algorithm developer needs to make consistently when accessing a graph.  What do you think?

Then we don't need really new int-returning methods (I assume you're adding those just for parity with the existing degreeOf methods?).  The question about what to do about larger-than-32-bit integer counts still applies if someone calls graph.edgeSet().size(), however.  I agree that throwing an exception would be best.

It's a good question about removeAllEdges; feels like overkill.  An application that really needed it could first query the edges-between iterable, make a copy of that somehow, and then pass it in to the existing boolean-returning removeAllEdges (too bad that one takes a Collection instead of an Iterable).

[Dimitrios Michail]

I like this approach better!  Take a look at the same branch for a preliminary version.

[Sebastiano Vigna]

Il giorno giovedì 29 ottobre 2020 alle 15:13:29 UTC+1 dimitrio...@gmail.com ha scritto:

I like this approach better!  Take a look at the same branch for a preliminary version.

Me too! I was hating edgesOfIterable() since the start :).