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:
  • Constructor Details

    • AbstractSuccinctUndirectedGraph

      public AbstractSuccinctUndirectedGraph(int n, int m)
  • Method Details

    • 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