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()