 java.lang.Object

 org.jgrapht.graph.AbstractGraph<java.lang.Integer,E>

 org.jgrapht.sux4j.AbstractSuccinctGraph<E>

 org.jgrapht.sux4j.AbstractSuccinctDirectedGraph<E>

 Type Parameters:
E
 the graph edge type
 All Implemented Interfaces:
java.io.Serializable
,Graph<java.lang.Integer,E>
 Direct Known Subclasses:
SuccinctDirectedGraph
,SuccinctIntDirectedGraph
public abstract class AbstractSuccinctDirectedGraph<E> extends AbstractSuccinctGraph<E>
An abstract base class for all succinct directed implementations.Two subclasses,
AbstractSuccinctDirectedGraph.CumulativeSuccessors
andAbstractSuccinctDirectedGraph.CumulativeDegrees
, generate the monotone lists that will be encoded using the Elias–Fano representation.First, we store the monotone lists of cumulative outdegrees and indegrees.
Then, we store the outgoing edges x → y as a monotone sequence using the encoding x2^{⌈log n⌉} + y. At that point the kth edge can be obtained by retrieving the kth element of the sequence and some bit shifting (the encoding xn + y would be slightly more compact, but much slower to decode). Since we know the list of cumulative outdegrees, we know which range of indices corresponds to the edges outgoing from each vertex. If we need to know whether x → y is an edge we just look for x2^{⌈log n⌉} + y in the sequence.
Finally, we store incoming edges y → x again as a monotone sequence using the encoding xn + y  e, where e is the index of the edge in lexicographical order. In this case we just need to be able to recover the edges associated with a vertex, so we can use a more compact format.
However, in the case of a
SuccinctIntDirectedGraph
after retrieving the source and target of an incoming edge we need to index it. The slow indexing of the incoming edges is the reason why aSuccinctIntDirectedGraph
enumerates incoming edges very slowly, whereas aSuccinctDirectedGraph
does not. See Also:
 Serialized Form


Nested Class Summary
Nested Classes Modifier and Type Class Description protected static class
AbstractSuccinctDirectedGraph.CumulativeDegrees
Iterates over the cumulative degrees (starts with a zero).protected static class
AbstractSuccinctDirectedGraph.CumulativeSuccessors<E>
Turns all edges x → y into a monotone sequence using the encoding x2^{⌈log n⌉} + y, or the encoding xn + y  e, where e is the index of the edge in lexicographical order, depending on the value of thestrict
parameter.

Field Summary

Fields inherited from class org.jgrapht.sux4j.AbstractSuccinctGraph
m, n, sourceShift, targetMask, UNMODIFIABLE

Fields inherited from interface org.jgrapht.Graph
DEFAULT_EDGE_WEIGHT


Constructor Summary
Constructors Constructor Description AbstractSuccinctDirectedGraph(int n, int m)

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
degreeOf(java.lang.Integer vertex)
Returns the degree of the specified vertex.GraphType
getType()
Get the graph type.
Methods inherited from class org.jgrapht.sux4j.AbstractSuccinctGraph
addEdge, addEdge, addVertex, addVertex, assertVertexExist, containsVertex, getAllEdges, getEdgeSupplier, getEdgeWeight, getVertexSupplier, removeEdge, removeEdge, removeVertex, setEdgeWeight, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph
containsEdge, equals, hashCode, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toString, toStringFromSets

Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.Graph
containsEdge, edgeSet, edgesOf, getEdge, getEdgeSource, getEdgeTarget, incomingEdgesOf, inDegreeOf, iterables, outDegreeOf, outgoingEdgesOf, setEdgeWeight




Method Detail

degreeOf
public int degreeOf(java.lang.Integer vertex)
Description copied from interface:Graph
Returns the degree of the specified vertex.A degree of a vertex in an undirected graph is the number of edges touching that vertex. Edges with same source and target vertices (selfloops) are counted twice.
In directed graphs this method returns the sum of the "in degree" and the "out degree".
 Parameters:
vertex
 vertex whose degree is to be calculated. Returns:
 the degree of the specified vertex.

