Module org.jgrapht.unimi.dsi

Package org.jgrapht.sux4j

Class AbstractSuccinctUndirectedGraph<E>

java.lang.Object

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

org.jgrapht.sux4j.AbstractSuccinctGraph<E>

org.jgrapht.sux4j.AbstractSuccinctUndirectedGraph<E>

Type Parameters:

E - the graph edge type

All Implemented Interfaces:

Serializable, Graph<Integer,E>

Direct Known Subclasses:

SuccinctIntUndirectedGraph, SuccinctUndirectedGraph

public abstract class AbstractSuccinctUndirectedGraph<E>
extends AbstractSuccinctGraph<E>

An abstract base class for all succinct undirected implementations.

Two subclasses, AbstractSuccinctUndirectedGraph.CumulativeSuccessors and AbstractSuccinctUndirectedGraph.CumulativeDegrees, generate the monotone lists that will be encoded using the Elias–Fano representation.

We use the representation described in AbstractSuccinctDirectedGraph applied to the directed graph obtained by choosing the direction x → y for an edge x — y if x ≤ y (loops are represented twice). Each edge now appears exactly once in the list of outgoing edges, and thus can be indexed as in the directed base.

The set of vertices adjacent to a given vertex can then be retrieved by enumerating both outgoing and incoming edges, being careful to avoid enumerating twice loops.

However, in the case of a SuccinctIntUndirectedGraph 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 a SuccinctIntUndirectedGraph enumerates edges very slowly, whereas a SuccinctUndirectedGraph does not.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	AbstractSuccinctUndirectedGraph.CumulativeDegrees<E>	Iterates over the cumulative degrees (starts with a zero).
protected static class	AbstractSuccinctUndirectedGraph.CumulativeSuccessors<E>	Turns all edges x — y, x ≤ y, into a monotone sequence using the encoding x2⌈log n⌉ + y, or all edges x — y, x ≥ y, using the encoding xn + y - e, where e is the index of the edge in lexicographical order, depending on the value of the sorted 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
AbstractSuccinctUndirectedGraph(int n, int m)

Method Summary

Modifier and Type	Method	Description
protected boolean	containsEdge(it.unimi.dsi.sux4j.util.EliasFanoIndexedMonotoneLongBigList successors, int x, int y)
GraphType	getType()	Get the graph type.
int	inDegreeOf(Integer vertex)	Returns the "in degree" of the specified vertex.
int	outDegreeOf(Integer vertex)	Returns the "out degree" of the specified vertex.

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, degreeOf, edgeSet, edgesOf, getEdge, getEdgeSource, getEdgeTarget, incomingEdgesOf, iterables, outgoingEdgesOf, setEdgeWeight

Constructor Detail

AbstractSuccinctUndirectedGraph

public AbstractSuccinctUndirectedGraph(int n,
                                       int m)

Method Detail

inDegreeOf

public int inDegreeOf(Integer vertex)

Description copied from interface: Graph

Returns the "in degree" of the specified vertex.

The "in degree" of a vertex in a directed graph is the number of inward directed edges from that vertex. See http://mathworld.wolfram.com/Indegree.html.

In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (self-loops) are counted twice.

Parameters:

vertex - vertex whose degree is to be calculated.

Returns:

the degree of the specified vertex.

outDegreeOf

public int outDegreeOf(Integer vertex)

Description copied from interface: Graph

Returns the "out degree" of the specified vertex.

The "out degree" of a vertex in a directed graph is the number of outward directed edges from that vertex. See http://mathworld.wolfram.com/Outdegree.html.

In the case of undirected graphs this method returns the number of edges touching the vertex. Edges with same source and target vertices (self-loops) are counted twice.

Parameters:

vertex - vertex whose degree is to be calculated.

Returns:

the degree of the specified vertex.

containsEdge

protected boolean containsEdge(it.unimi.dsi.sux4j.util.EliasFanoIndexedMonotoneLongBigList successors,
                               int x,
                               int y)

getType

public GraphType getType()

Description copied from interface: Graph

Get the graph type. The graph type can be used to query for additional metadata such as whether the graph supports directed or undirected edges, self-loops, multiple (parallel) edges, weights, etc.

Returns:

the graph type