Package it.unimi.dsi.law.big.graph

Class BFS

java.lang.Object
it.unimi.dsi.law.big.graph.BFS
public class BFS
extends Object
Computes the visit order with respect to a breadth-first visit.
Author:
Marco Rosa, Thibault Allançon

  • Constructor Summary

    Constructors
    Constructor Description
    BFS()  

  • Method Summary

    Modifier and Type Method Description
    static long[][] bfs​(ImmutableGraph graph, long startingNode, int bufferSize)
    Performs a breadth-first visit.
    static long[][] bfs​(ImmutableGraph graph, long startingNode, long[][] startPerm, int bufferSize)
    Performs a breadth-first visit.
    static long[][] bfsperm​(ImmutableGraph graph, long startingNode, int bufferSize)
    Return the permutation induced by the visit order of a breadth-first visit.
    static long[][] bfsperm​(ImmutableGraph graph, long startingNode, long[][] startPerm, int bufferSize)
    Return the permutation induced by the visit order of a breadth-first visit.
    static long[][] bfsperm​(ImmutableGraph graph, long startingNode, long[][] startPerm, int bufferSize, boolean doPerm)
    Return the permutation induced by the visit order of a breadth-first visit.
    static void main​(String[] args)  

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • BFS

      public BFS()

  • Method Details

    • bfsperm

      public static long[][] bfsperm​(ImmutableGraph graph, long startingNode, long[][] startPerm, int bufferSize) throws IOException
      Return the permutation induced by the visit order of a breadth-first visit.
      Parameters:
      graph - a graph.
      startingNode - the only starting node of the visit, or -1 for a complete visit.
      startPerm - a permutation that will be used to shuffle successors, or null.
      bufferSize - internal queue buffer size (will be minimized with Long.SIZE times the number of nodes in the graph).
      Returns:
      the permutation induced by the visit order of a depth-first visit.
      Throws:
      IOException

    • bfsperm

      public static long[][] bfsperm​(ImmutableGraph graph, long startingNode, int bufferSize) throws IOException
      Return the permutation induced by the visit order of a breadth-first visit.
      Parameters:
      graph - a graph.
      startingNode - the only starting node of the visit, or -1 for a complete visit.
      bufferSize - internal queue buffer size (will be minimized with Long.SIZE times the number of nodes in the graph).
      Returns:
      the permutation induced by the visit order of a depth-first visit.
      Throws:
      IOException

    • bfs

      public static long[][] bfs​(ImmutableGraph graph, long startingNode, int bufferSize) throws IOException
      Performs a breadth-first visit.
      Parameters:
      graph - a graph.
      startingNode - the only starting node of the visit, or -1 for a complete visit.
      bufferSize - internal queue buffer size (will be minimized with Long.SIZE times the number of nodes in the graph).
      Returns:
      the permutation induced by the visit order of a depth-first visit.
      Throws:
      IOException

    • bfs

      public static long[][] bfs​(ImmutableGraph graph, long startingNode, long[][] startPerm, int bufferSize) throws IOException
      Performs a breadth-first visit.
      Parameters:
      graph - a graph.
      startingNode - the only starting node of the visit, or -1 for a complete visit.
      startPerm - a permutation that will be used to shuffle successors, or null.
      bufferSize - internal queue buffer size (will be minimized with Long.SIZE times the number of nodes in the graph).
      Returns:
      the permutation induced by the visit order of a depth-first visit.
      Throws:
      IOException

    • bfsperm

      public static long[][] bfsperm​(ImmutableGraph graph, long startingNode, long[][] startPerm, int bufferSize, boolean doPerm) throws IOException
      Return the permutation induced by the visit order of a breadth-first visit.
      Parameters:
      graph - a graph.
      startingNode - the only starting node of the visit, or -1 for a complete visit.
      startPerm - a permutation that will be used to shuffle successors, or null.
      bufferSize - internal queue buffer size (will be minimized with Long.SIZE times the number of nodes in the graph).
      doPerm - if true, returns a permutation; otherwise, null.
      Returns:
      the permutation induced by the visit order of a depth-first visit.
      Throws:
      IOException

    • main

      public static void main​(String[] args) throws JSAPException, IOException
      Throws:
      JSAPException
      IOException