Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_SwapEdges: randomly swaps edges in a graph
       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 Gabriel Gomez, Texas A&M University
      15             : 
      16             : //------------------------------------------------------------------------------
      17             : 
      18             : // References:
      19             : 
      20             : // R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, and U. Alon, “On the 
      21             : // uniform generation of random graphs with prescribed degree sequences,” 2004.
      22             : #include "LG_internal.h"
      23             : #include "LAGraphX.h"
      24        5245 : int LAGraph_SwapEdges
      25             : (
      26             :     // output
      27             :     LAGraph_Graph *G_new,  // A new graph with the same degree for each node
      28             :     double *pQ,            // Actual Swaps proformed per edge
      29             :     // input: not modified
      30             :     const LAGraph_Graph G, // Graph to be randomized.
      31             :     double Q,              // Swaps per edge
      32             :     char *msg
      33             : )
      34             : {
      35        5245 :     LG_ASSERT(pQ != NULL, GrB_NULL_POINTER);
      36        5245 :     LG_ASSERT(Q > 0.0, GrB_INVALID_VALUE);
      37        5245 :     GrB_Index numEdges = 0;
      38        5245 :     GrB_Matrix_nvals(&numEdges, G->A) ;
      39        5245 :     numEdges /= 2;
      40        5245 :     uint64_t pSwaps = 0; 
      41        5245 :     int info = LAGr_SwapEdges(
      42             :         G_new, &pSwaps, G, .70, .10, 
      43        5245 :         (uint64_t) (numEdges * Q), 891234789234ull, msg) ;
      44        5245 :     *pQ = ((double) pSwaps / (double) numEdges);
      45        5245 :     return  info;
      46             : }