Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGr_BreadthFirstSearch:  breadth-first search dispatch
       3             : //------------------------------------------------------------------------------
       4             : 
       5             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       6             : // SPDX-License-Identifier: BSD-2-Clause
       7             : //
       8             : // For additional details (including references to third party source code and
       9             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      10             : // Contributors.txt for a full list of contributors. Created, in part, with
      11             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      12             : // DM22-0790
      13             : 
      14             : // Contributed by Scott McMillan, SEI Carnegie Mellon University
      15             : 
      16             : //------------------------------------------------------------------------------
      17             : 
      18             : // Breadth-first-search via push/pull method if using SuiteSparse:GraphBLAS
      19             : // and its GxB extensions, or a push-only method otherwise.  The former is
      20             : // much faster.
      21             : 
      22             : // This is an Advanced algorithm.  SuiteSparse can use a push/pull method if
      23             : // G->AT and G->out_degree are provided.  G->AT is not required if G is
      24             : // undirected.  The vanilla method is always push-only.
      25             : 
      26             : #include "LG_alg_internal.h"
      27             : 
      28          40 : int LAGr_BreadthFirstSearch_Extended
      29             : (
      30             :     // output:
      31             :     GrB_Vector *level,
      32             :     GrB_Vector *parent,
      33             :     // input:
      34             :     const LAGraph_Graph G,
      35             :     GrB_Index src,
      36             :     int64_t max_level,  // < 0: no limit; otherwise, stop at this level
      37             :     int64_t dest,       // < 0: no destination; otherwise, stop if dest
      38             :                         // node is reached
      39             :     bool many_expected, // if true, the result is expected to include a fair
      40             :                         // portion of the graph.  If false, the result (parent
      41             :                         // and level) is expected to be very sparse.
      42             :     char *msg
      43             : )
      44             : {
      45             : 
      46             : #if LAGRAPH_SUITESPARSE
      47          40 :     return LG_BreadthFirstSearch_SSGrB_Extended
      48             :         (level, parent, G, src, max_level, dest, many_expected, msg) ;
      49             : #else
      50             :     return LG_BreadthFirstSearch_vanilla_Extended
      51             :         (level, parent, G, src, max_level, dest, msg) ;
      52             : #endif
      53             : }
      54             :