Module org.jgrapht.core
Package org.jgrapht.traverse

Class MaximumCardinalityIterator<V,​E>

  • Type Parameters:
    V - the graph vertex type.
    E - the graph edge type.
    All Implemented Interfaces:
    java.util.Iterator<V>, GraphIterator<V,​E>
    public class MaximumCardinalityIterator<V,​E>
extends AbstractGraphIterator<V,​E>
    A maximum cardinality search iterator for an undirected graph.

    For every vertex in graph its cardinality is defined as the number of its neighbours, which have been already visited by this iterator. Iterator chooses vertex with the maximum cardinality, breaking ties arbitrarily. For more information of maximum cardinality search see: Berry, A., Blair, J., Heggernes, P. et al. Algorithmica (2004) 39: 287. https://doi.org/10.1007/s00453-004-1084-3 Maximum Cardinality Search for Computing Minimal Triangulations.

    For this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.

    Note: only vertex events are fired by this iterator.

    • Field Detail

      • maxCardinality

        private int maxCardinality
        The maximum index of non-empty set in buckets.

      • remainingVertices

        private int remainingVertices
        Number of unvisited vertices.

      • current

        private V current
        Contains current vertex.

      • buckets

        private java.util.ArrayList<java.util.Set<V>> buckets
        Disjoint sets of vertices of the graph, indexed by the cardinalities of already visited neighbours.

      • cardinalityMap

        private java.util.Map<V,​java.lang.Integer> cardinalityMap
        Maps every vertex to its cardinality.

    • Constructor Detail

      • MaximumCardinalityIterator

        public MaximumCardinalityIterator​(Graph<V,​E> graph)
        Creates a maximum cardinality iterator for the graph.
        Parameters:
        graph - the graph to be iterated.

    • Method Detail

      • hasNext

        public boolean hasNext()
        Checks whether there exists unvisited vertex.
        Returns:
        true if there exists unvisited vertex.

      • next

        public V next()
        Returns the next vertex in the ordering.
        Returns:
        the next vertex in the ordering.

      • isCrossComponentTraversal

        public boolean isCrossComponentTraversal()
        Test whether this iterator is set to traverse the graph across connected components.

        Always returns true since this iterator doesn't care about connected components.

        Specified by:
        isCrossComponentTraversal in interface GraphIterator<V,​E>
        Overrides:
        isCrossComponentTraversal in class AbstractGraphIterator<V,​E>
        Returns:
        true if traverses across connected components, otherwise false.

      • setCrossComponentTraversal

        public void setCrossComponentTraversal​(boolean crossComponentTraversal)
        Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.

        Trying to disable the cross components nature of this iterator will result into throwing a IllegalArgumentException.

        Overrides:
        setCrossComponentTraversal in class AbstractGraphIterator<V,​E>
        Parameters:
        crossComponentTraversal - if true traverses across connected components.

      • advance

        private V advance()
        Retrieves a vertex from the buckets with the maximum cardinality and returns it.
        Returns:
        vertex retrieved from buckets.

      • removeFromBucket

        private int removeFromBucket​(V vertex)
        Removes vertex from the bucket it was contained in.
        Parameters:
        vertex - the vertex, which has to be removed from the bucket it was contained in.
        Returns:
        the cardinality of the removed vertex or -1, if the vertex wasn't contained in any bucket.

      • addToBucket

        private void addToBucket​(V vertex,
                         int cardinality)
        Adds the vertex to the bucket with the given cardinality.
        Parameters:
        vertex - the vertex, which has to be added to the the bucket.
        cardinality - the cardinality of the destination bucket.

      • updateNeighbours

        private void updateNeighbours​(V vertex)
        Increments the cardinalities of the neighbours of the vertex by 1. If the maximum cardinality increases, increments maxCardinality by 1.
        Parameters:
        vertex - the vertex whose neighbours are to be updated.