Module org.jgrapht.core
Package org.jgrapht.alg.isomorphism

Class GraphOrdering<V,​E>

  • Type Parameters:
    V - the type of the vertices
    E - the type of the edges
    final class GraphOrdering<V,​E>
extends java.lang.Object
    This class represents the order on the graph vertices. There are also some helper-functions for receiving outgoing/incoming edges, etc.

    • Field Detail

      • graph

        private final Graph<V,​E> graph

      • mapVertexToOrder

        private final java.util.Map<V,​java.lang.Integer> mapVertexToOrder

      • mapOrderToVertex

        private final java.util.List<V> mapOrderToVertex

      • vertexCount

        private final int vertexCount

      • outgoingEdges

        private final int[][] outgoingEdges

      • incomingEdges

        private final int[][] incomingEdges

      • edgeCache

        private final E[] edgeCache

      • adjMatrix

        private final byte[] adjMatrix
        if caching is enabled, adjMatrix contains cached information on existing edges, valid values:
        • 0 - no cached value
        • 1 - edge exists
        • -1 - no edge exists

      • cacheEdges

        private final boolean cacheEdges

    • Constructor Detail

      • GraphOrdering

        public GraphOrdering​(Graph<V,​E> graph,
                     boolean orderByDegree,
                     boolean cacheEdges)
        Parameters:
        graph - the graph to be ordered
        orderByDegree - should the vertices be ordered by their degree. This speeds up the VF2 algorithm.
        cacheEdges - if true, the class creates a adjacency matrix and two arrays for incoming and outgoing edges for fast access.

      • GraphOrdering

        public GraphOrdering​(Graph<V,​E> graph)
        Parameters:
        graph - the graph to be ordered

    • Method Detail

      • getVertexCount

        public int getVertexCount()
        Returns:
        returns the number of vertices in the graph.

      • getOutEdges

        public int[] getOutEdges​(int vertexNumber)
        Parameters:
        vertexNumber - the number which identifies the vertex $v$ in this order.
        Returns:
        the identifying numbers of all vertices which are connected to $v$ by an edge outgoing from $v$.

      • getInEdges

        public int[] getInEdges​(int vertexNumber)
        Parameters:
        vertexNumber - the number which identifies the vertex $v$ in this order.
        Returns:
        the identifying numbers of all vertices which are connected to $v$ by an edge incoming to $v$.

      • hasEdge

        public boolean hasEdge​(int v1Number,
                       int v2Number)
        Parameters:
        v1Number - the number of the first vertex $v_1$
        v2Number - the number of the second vertex $v_2$
        Returns:
        exists the edge from $v_1$ to $v_2$

      • getVertex

        public V getVertex​(int vertexNumber)
        be careful: there's no check against an invalid vertexNumber
        Parameters:
        vertexNumber - the number identifying the vertex $v$
        Returns:
        $v$

      • getEdge

        public E getEdge​(int v1Number,
                 int v2Number)
        Parameters:
        v1Number - the number identifying the vertex $v_1$
        v2Number - the number identifying the vertex $v_2$
        Returns:
        the edge from $v_1$ to $v_2$

      • getVertexNumber

        public int getVertexNumber​(V v)

      • getEdgeNumbers

        public int[] getEdgeNumbers​(E e)

      • getGraph

        public Graph<V,​E> getGraph()