Package org.graph4j.ordering

Class VertexOrderings

java.lang.Object
org.graph4j.ordering.VertexOrderings
public class VertexOrderings extends Object
Contains static methods that create various vertex orderings.
Author:
Cristian Frăsinaru

  • Method Summary

    Modifier and Type
    Method
    Description
    static int[]
    breadthFirst(Graph graph, int startVertex)
    Creates an array containing the vertices of the graph in the order produced by a BFS (Breadth First Search) traversal.
    static int[]
    depthFirst(Graph graph, int startVertex)
    Creates an array containing the vertices of the graph in the order produced by a DFS (Depth First Search) traversal.
    static int[]
    largestDegreeFirst(Graph graph)
    Creates an array containing the vertices of the graph in decreasing order by their degree.
    static int[]
    lexBFS(Graph graph)
    Creates an array containing the vertices of the graph in the order produced by the Lexicographic Breadth-First Search algorithm.
    static int[]
    maximumCardinality(Graph graph)
    Creates an array containing the vertices of the graph in the order produced by the Maximum Cardinality Search (MCS) algorithm.
    static int[]
    smallestDegreeFirst(Graph graph)
    Creates an array containing the vertices of the graph in increasing order by their degree.
    static int[]
    smallestDegreeLast(Graph graph)
    Computes the vertex ordering from the end to the beginning: at each step, the node of minimum degree in the current graph is selected and then it is removed from the graph.
    static int[]
    topological(Digraph graph)
    Computes a vertex ordering of a directed graph such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • depthFirst

      public static int[] depthFirst(Graph graph, int startVertex)
      Creates an array containing the vertices of the graph in the order produced by a DFS (Depth First Search) traversal.
      Parameters:
      graph - the input graph.
      startVertex - the start vertex for the DFS traversal.
      Returns:
      the ordering produced by a DFS traversal, starting from the specified vertex.
      See Also:

    • breadthFirst

      public static int[] breadthFirst(Graph graph, int startVertex)
      Creates an array containing the vertices of the graph in the order produced by a BFS (Breadth First Search) traversal.
      Parameters:
      graph - the input graph.
      startVertex - the start vertex for the BFS traversal.
      Returns:
      the ordering produced by a BFS traversal, starting from the specified vertex.
      See Also:

    • lexBFS

      public static int[] lexBFS(Graph graph)
      Creates an array containing the vertices of the graph in the order produced by the Lexicographic Breadth-First Search algorithm.
      Parameters:
      graph - the input graph.
      Returns:
      the ordering produced by the LexBFS algorithm, starting from the specified vertex.
      See Also:

    • maximumCardinality

      public static int[] maximumCardinality(Graph graph)
      Creates an array containing the vertices of the graph in the order produced by the Maximum Cardinality Search (MCS) algorithm.
      Parameters:
      graph - the input graph.
      Returns:
      the ordering produced by the MCS algorithm, starting from the specified vertex.
      See Also:

    • largestDegreeFirst

      public static int[] largestDegreeFirst(Graph graph)
      Creates an array containing the vertices of the graph in decreasing order by their degree. In case of ties, they are ordered by their indices in the graph. If the input argument is a directed graph, the ordering is created by the outdegree of the vertices.
      Parameters:
      graph - the input graph.
      Returns:
      the vertices of the graph in decreasing order by their degree.

    • smallestDegreeFirst

      public static int[] smallestDegreeFirst(Graph graph)
      Creates an array containing the vertices of the graph in increasing order by their degree. In case of ties, they are ordered by their indices in the graph. If the input argument is a directed graph, the ordering is created by the outdegree of the vertices.
      Parameters:
      graph - the input graph.
      Returns:
      the vertices of the graph in increasing order by their degree.

    • smallestDegreeLast

      public static int[] smallestDegreeLast(Graph graph)
      Computes the vertex ordering from the end to the beginning: at each step, the node of minimum degree in the current graph is selected and then it is removed from the graph.
      Parameters:
      graph - the input graph.
      Returns:
      the vertex ordering according to the smallest-degree-last strategy.
      See Also:

    • topological

      public static int[] topological(Digraph graph)
      Computes a vertex ordering of a directed graph such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering.
      Parameters:
      graph - the input directed graph.
      Returns:
      the topological ordering, or null if the digraph is not acyclic.
      See Also: