| /************************************************************************************\ |
| * * |
| * Copyright � 2014 Advanced Micro Devices, Inc. * |
| * Copyright (c) 2015 Mark D. Hill and David A. Wood * |
| * All rights reserved. * |
| * * |
| * Redistribution and use in source and binary forms, with or without * |
| * modification, are permitted provided that the following are met: * |
| * * |
| * You must reproduce the above copyright notice. * |
| * * |
| * Neither the name of the copyright holder nor the names of its contributors * |
| * may be used to endorse or promote products derived from this software * |
| * without specific, prior, written permission from at least the copyright holder. * |
| * * |
| * You must include the following terms in your license and/or other materials * |
| * provided with the software. * |
| * * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * |
| * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * |
| * IMPLIED WARRANTIES OF MERCHANTABILITY, NON-INFRINGEMENT, AND FITNESS FOR A * |
| * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER * |
| * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT * |
| * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * |
| * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * |
| * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING * |
| * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY * |
| * OF SUCH DAMAGE. * |
| * * |
| * Without limiting the foregoing, the software may implement third party * |
| * technologies for which you must obtain licenses from parties other than AMD. * |
| * You agree that AMD has not obtained or conveyed to you, and that you shall * |
| * be responsible for obtaining the rights to use and/or distribute the applicable * |
| * underlying intellectual property rights related to the third party technologies. * |
| * These third party technologies are not licensed hereunder. * |
| * * |
| * If you use the software (in whole or in part), you shall adhere to all * |
| * applicable U.S., European, and other export laws, including but not limited to * |
| * the U.S. Export Administration Regulations ("EAR") (15 C.F.R Sections 730-774), * |
| * and E.U. Council Regulation (EC) No 428/2009 of 5 May 2009. Further, pursuant * |
| * to Section 740.6 of the EAR, you hereby certify that, except pursuant to a * |
| * license granted by the United States Department of Commerce Bureau of Industry * |
| * and Security or as otherwise permitted pursuant to a License Exception under * |
| * the U.S. Export Administration Regulations ("EAR"), you will not (1) export, * |
| * re-export or release to a national of a country in Country Groups D:1, E:1 or * |
| * E:2 any restricted technology, software, or source code you receive hereunder, * |
| * or (2) export to Country Groups D:1, E:1 or E:2 the direct product of such * |
| * technology or software, if such foreign produced direct product is subject to * |
| * national security controls as identified on the Commerce Control List (currently * |
| * found in Supplement 1 to Part 774 of EAR). For the most current Country Group * |
| * listings, or for additional information about the EAR or your obligations under * |
| * those regulations, please refer to the U.S. Bureau of Industry and Security's * |
| * website at http://www.bis.doc.gov/. * |
| * * |
| \************************************************************************************/ |
| |
| #include "parse.h" |
| #include "stdlib.h" |
| #include "stdio.h" |
| #include <string.h> |
| #include <algorithm> |
| #include <sys/time.h> |
| #include "util.h" |
| |
| bool doCompare(CooTuple elem1, CooTuple elem2) |
| { |
| if (elem1.row < elem2.row) { |
| return true; |
| } |
| return false; |
| } |
| |
| ell_array *csr2ell(csr_array *csr, int num_nodes, int num_edges, int fill) |
| { |
| int size, maxheight = 0; |
| for (int i = 0; i < num_nodes; i++) { |
| size = csr->row_array[i + 1] - csr->row_array[i]; |
| if (size > maxheight) |
| maxheight = size; |
| } |
| |
| ell_array *ell = (ell_array *)malloc(sizeof(ell_array)); |
| if (!ell) printf("malloc failed"); |
| |
| ell->max_height = maxheight; |
| ell->num_nodes = num_nodes; |
| |
| ell->col_array = (int*)malloc(sizeof(int) * maxheight * num_nodes); |
| ell->data_array = (int*)malloc(sizeof(int) * maxheight * num_nodes); |
| |
| |
| for (int i = 0; i < maxheight * num_nodes; i++) { |
| ell->col_array[i] = 0; |
| ell->data_array[i] = fill; |
| } |
| |
| for (int i = 0; i < num_nodes; i++) { |
| int start = csr->row_array[i]; |
| int end = csr->row_array[i + 1]; |
| int lastcolid = 0; |
| for (int j = start; j < end; j++) { |
| int colid = csr->col_array[j]; |
| int data = csr->data_array[j]; |
| ell->col_array[i + (j - start) * num_nodes] = colid; |
| ell->data_array[i + (j - start) * num_nodes] = data; |
| lastcolid = colid; |
| } |
| for (int j = end; j < start + maxheight; j++) { |
| ell->col_array[i + (j - start) * num_nodes] = lastcolid; |
| ell->data_array[i + (j - start) * num_nodes] = fill; |
| } |
| } |
| |
| return ell; |
| |
| } |
| |
| csr_array *parseMetis(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed) |
| { |
| |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char *line = (char *)malloc(8192); |
| int num_edges = 0, num_nodes = 0; |
| |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| |
| while (fgets(line, 8192, fptr)) { |
| int head, tail, weight = 0; |
| CooTuple temp; |
| |
| if (line[0] == '%') continue; // skip comment lines |
| |
| if (lineno == 0) { //the first line |
| |
| sscanf(line, "%d %d", p_num_nodes, p_num_edges); |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| } else if (lineno > 0) { //from the second line |
| |
| char *pch; |
| pch = strtok(line , " ,.-"); |
| while (pch != NULL) { |
| head = lineno; |
| tail = atoi(pch); |
| if (tail <= 0) break; |
| |
| if (tail == head) printf("reporting self loop: %d, %d\n", lineno + 1, lineno); |
| |
| temp.row = head - 1; |
| temp.col = tail - 1; |
| temp.val = weight; |
| |
| tuple_array[cnt++] = temp; |
| |
| pch = strtok(NULL, " ,.-"); |
| |
| } |
| } |
| |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| |
| lineno++; |
| |
| } |
| |
| // Metis files are stored in row-order, so sorting is unnecessary |
| // std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *row_array = (int *)malloc((num_nodes + 1) * sizeof(int)); |
| int *col_array = (int *)malloc(num_edges * sizeof(int)); |
| int *data_array = (int *)malloc(num_edges * sizeof(int)); |
| |
| int row_cnt = 0; |
| int prev = -1; |
| int idx; |
| for (idx = 0; idx < num_edges; idx++) { |
| int curr = tuple_array[idx].row; |
| if (curr != prev) { |
| row_array[row_cnt++] = idx; |
| prev = curr; |
| } |
| col_array[idx] = tuple_array[idx].col; |
| data_array[idx] = tuple_array[idx].val; |
| |
| } |
| row_array[row_cnt] = idx; |
| |
| csr_array *csr = (csr_array *)malloc(sizeof(csr_array)); |
| memset(csr, 0, sizeof(csr_array)); |
| csr->row_array = row_array; |
| csr->col_array = col_array; |
| csr->data_array = data_array; |
| |
| fclose(fptr); |
| free(tuple_array); |
| free(line); |
| |
| return csr; |
| |
| } |
| |
| |
| csr_array *parseCOO(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed) |
| { |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char line[128], sp[2], a, p; |
| int num_nodes = 0, num_edges = 0; |
| |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| |
| while (fgets(line, 100, fptr)) { |
| int head, tail, weight; |
| switch (line[0]) { |
| case 'c': |
| break; |
| case 'p': |
| sscanf(line, "%c %s %d %d", &p, sp, p_num_nodes, p_num_edges); |
| |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| break; |
| |
| case 'a': |
| sscanf(line, "%c %d %d %d", &a, &head, &tail, &weight); |
| if (tail == head) printf("reporting self loop\n"); |
| CooTuple temp; |
| temp.row = head - 1; |
| temp.col = tail - 1; |
| temp.val = weight; |
| tuple_array[cnt++] = temp; |
| if (!directed) { |
| temp.row = tail - 1; |
| temp.col = head - 1; |
| temp.val = weight; |
| tuple_array[cnt++] = temp; |
| } |
| |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| break; |
| default: |
| fprintf(stderr, "exiting loop\n"); |
| break; |
| } |
| lineno++; |
| } |
| |
| std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *row_array = (int *)malloc((num_nodes + 1) * sizeof(int)); |
| int *col_array = (int *)malloc(num_edges * sizeof(int)); |
| int *data_array = (int *)malloc(num_edges * sizeof(int)); |
| |
| int row_cnt = 0; |
| int prev = -1; |
| int idx; |
| for (idx = 0; idx < num_edges; idx++) { |
| int curr = tuple_array[idx].row; |
| if (curr != prev) { |
| row_array[row_cnt++] = idx; |
| prev = curr; |
| } |
| |
| col_array[idx] = tuple_array[idx].col; |
| data_array[idx] = tuple_array[idx].val; |
| } |
| |
| row_array[row_cnt] = idx; |
| |
| fclose(fptr); |
| free(tuple_array); |
| |
| csr_array *csr = (csr_array *)malloc(sizeof(csr_array)); |
| memset(csr, 0, sizeof(csr_array)); |
| csr->row_array = row_array; |
| csr->col_array = col_array; |
| csr->data_array = data_array; |
| |
| return csr; |
| |
| } |
| |
| // Parse Metis file with double edges |
| double_edges *parseMetis_doubleEdge(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed) |
| { |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char line[4096]; |
| int num_edges = 0, num_nodes = 0; |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| |
| while (fgets(line, 4096, fptr)) { |
| int head, tail, weight = 0; |
| CooTuple temp; |
| |
| if (line[0] == '%') continue; // skip comment lines |
| |
| if (lineno == 0) { //the first line |
| |
| sscanf(line, "%d %d", p_num_nodes, p_num_edges); |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| if (!tuple_array) printf("xxxxxxxx\n"); |
| |
| } else if (lineno > 0) { //from the second line |
| char *pch; |
| pch = strtok(line , " ,.-"); |
| while (pch != NULL) { |
| head = lineno; |
| tail = atoi(pch); |
| if (tail <= 0) break; |
| |
| if (tail == head) printf("reporting self loop: %d, %d\n", lineno + 1, lineno); |
| |
| temp.row = head - 1; |
| temp.col = tail - 1; |
| temp.val = weight; |
| |
| tuple_array[cnt++] = temp; |
| |
| pch = strtok(NULL, " ,.-"); |
| } |
| } |
| |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| |
| lineno++; |
| } |
| |
| // Metis files are stored in row-order, so sorting is unnecessary |
| // std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *edge_array1 = (int *)malloc(num_edges * sizeof(int)); |
| int *edge_array2 = (int *)malloc(num_edges * sizeof(int)); |
| |
| for (int i = 0; i < num_edges; i++) { |
| edge_array1[i] = tuple_array[i].row; |
| edge_array2[i] = tuple_array[i].col; |
| } |
| |
| fclose(fptr); |
| free(tuple_array); |
| |
| double_edges *de = (double_edges *)malloc(sizeof(double_edges)); |
| de->edge_array1 = edge_array1; |
| de->edge_array2 = edge_array2; |
| |
| return de; |
| |
| } |
| |
| // Parse COO file with double edges |
| double_edges *parseCOO_doubleEdge(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed) |
| { |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char line[128], sp[2], a, p; |
| int num_nodes = 0, num_edges = 0; |
| |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| |
| while (fgets(line, 100, fptr)) { |
| int head, tail, weight; |
| switch (line[0]) { |
| case 'c': |
| break; |
| case 'p': |
| sscanf(line, "%c %s %d %d", &p, sp, p_num_nodes, p_num_edges); |
| |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| break; |
| case 'a': |
| sscanf(line, "%c %d %d %d", &a, &head, &tail, &weight); |
| if (tail == head) printf("reporting self loop\n"); |
| CooTuple temp; |
| temp.row = head - 1; |
| temp.col = tail - 1; |
| temp.val = weight; |
| tuple_array[cnt++] = temp; |
| if (!directed) { |
| temp.row = tail - 1; |
| temp.col = head - 1; |
| temp.val = weight; |
| tuple_array[cnt++] = temp; |
| } |
| |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| break; |
| default: |
| fprintf(stderr, "exiting loop\n"); |
| break; |
| |
| } |
| lineno++; |
| } |
| |
| std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *edge_array1 = (int *)malloc(num_edges * sizeof(int)); |
| int *edge_array2 = (int *)malloc(num_edges * sizeof(int)); |
| |
| for (int i = 0; i < num_edges; i++) { |
| edge_array1[i] = tuple_array[i].row; |
| edge_array2[i] = tuple_array[i].col; |
| } |
| |
| fclose(fptr); |
| free(tuple_array); |
| |
| double_edges *de = (double_edges *)malloc(sizeof(double_edges)); |
| de->edge_array1 = edge_array1; |
| de->edge_array2 = edge_array2; |
| |
| return de; |
| } |
| |
| // Parse matrix market file |
| csr_array *parseMM(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed, bool weight_flag) |
| { |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char line[128]; |
| int num_nodes = 0, num_edges = 0, num_nodes2 = 0; |
| |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| |
| while (fgets(line, 100, fptr)) { |
| int head, tail, weight; |
| if (line[0] == '%') continue; |
| if (lineno == 0) { |
| sscanf(line, "%d %d %d", p_num_nodes, &num_nodes2, p_num_edges); |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| if (!tuple_array) { |
| printf("tuple array not allocated succesfully\n"); |
| exit(1); |
| } |
| |
| } |
| if (lineno > 0) { |
| |
| if (weight_flag) { |
| sscanf(line, "%d %d %d", &head, &tail, &weight); |
| } else { |
| sscanf(line, "%d %d", &head, &tail); |
| printf("(%d, %d)\n", head, tail); |
| weight = 0; |
| } |
| |
| if (tail == head) { |
| printf("reporting self loop\n"); |
| continue; |
| }; |
| |
| CooTuple temp; |
| temp.row = head - 1; |
| temp.col = tail - 1; |
| temp.val = weight; |
| tuple_array[cnt++] = temp; |
| |
| if (!directed) { |
| temp.row = tail - 1; |
| temp.col = head - 1; |
| temp.val = weight; |
| tuple_array[cnt++] = temp; |
| } |
| |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| } |
| lineno++; |
| } |
| |
| std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *row_array = (int *)malloc((num_nodes + 1) * sizeof(int)); |
| int *col_array = (int *)malloc(num_edges * sizeof(int)); |
| int *data_array = (int *)malloc(num_edges * sizeof(int)); |
| |
| int row_cnt = 0; |
| int prev = -1; |
| int idx; |
| for (idx = 0; idx < num_edges; idx++) { |
| int curr = tuple_array[idx].row; |
| if (curr != prev) { |
| row_array[row_cnt++] = idx; |
| prev = curr; |
| } |
| |
| col_array[idx] = tuple_array[idx].col; |
| data_array[idx] = tuple_array[idx].val; |
| } |
| row_array[row_cnt] = idx; |
| |
| fclose(fptr); |
| free(tuple_array); |
| |
| csr_array *csr = (csr_array *)malloc(sizeof(csr_array)); |
| memset(csr, 0, sizeof(csr_array)); |
| csr->row_array = row_array; |
| csr->col_array = col_array; |
| csr->data_array = data_array; |
| |
| return csr; |
| } |
| |
| // Parse Metis file with transpose |
| csr_array *parseMetis_transpose(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed) |
| { |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char *line = (char *)malloc(8192); |
| int num_edges = 0, num_nodes = 0; |
| int *col_cnt = NULL; |
| |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| while (fgets(line, 8192, fptr)) { |
| int head, tail, weight = 0; |
| CooTuple temp; |
| |
| if (line[0] == '%') continue; // skip comment lines |
| |
| if (lineno == 0) { //the first line |
| |
| sscanf(line, "%d %d", p_num_nodes, p_num_edges); |
| |
| col_cnt = (int *)malloc(*p_num_nodes * sizeof(int)); |
| if (!col_cnt) { |
| printf("memory allocation failed for col_cnt\n"); |
| exit(1); |
| } |
| memset(col_cnt, 0, *p_num_nodes * sizeof(int)); |
| |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| } else if (lineno > 0) { //from the second line |
| char *pch; |
| pch = strtok(line , " ,.-"); |
| while (pch != NULL) { |
| head = lineno; |
| tail = atoi(pch); |
| if (tail <= 0) { |
| break; |
| } |
| |
| if (tail == head) printf("reporting self loop: %d, %d\n", lineno + 1, lineno); |
| |
| if (directed) { |
| temp.row = tail - 1; |
| temp.col = head - 1; |
| } else { |
| // Undirected matrices are symmetric, so there is no need |
| // to transpose and then re-sort the edges |
| temp.row = head - 1; |
| temp.col = tail - 1; |
| } |
| temp.val = weight; |
| |
| col_cnt[head - 1]++; |
| if (cnt >= num_edges) { |
| fprintf(stderr, "Error when opening file: %s.\n" \ |
| " Check if graph is undirected Metis format\n", tmpchar); |
| exit(1); |
| } |
| tuple_array[cnt++] = temp; |
| |
| pch = strtok(NULL, " ,.-"); |
| } |
| } |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| lineno++; |
| } |
| |
| if (directed) { |
| // Metis files are stored in row-order, so transposed, directed |
| // matrices must be re-sorted! |
| std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| } |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *row_array = (int *)malloc((num_nodes + 1) * sizeof(int)); |
| int *col_array = (int *)malloc(num_edges * sizeof(int)); |
| int *data_array = (int *)malloc(num_edges * sizeof(int)); |
| |
| int row_cnt = 0; |
| int prev = -1; |
| int idx; |
| for (idx = 0; idx < num_edges; idx++) { |
| int curr = tuple_array[idx].row; |
| if (curr != prev) { |
| row_array[row_cnt++] = idx; |
| prev = curr; |
| } |
| col_array[idx] = tuple_array[idx].col; |
| data_array[idx] = tuple_array[idx].val; |
| } |
| row_array[row_cnt] = idx; |
| |
| csr_array *csr = (csr_array *)malloc(sizeof(csr_array)); |
| memset(csr, 0, sizeof(csr_array)); |
| csr->row_array = row_array; |
| csr->col_array = col_array; |
| csr->data_array = data_array; |
| csr->col_cnt = col_cnt; |
| |
| fclose(fptr); |
| free(tuple_array); |
| |
| return csr; |
| } |
| |
| // Parse COO file with transpose |
| csr_array *parseCOO_transpose(char* tmpchar, int *p_num_nodes, int *p_num_edges, bool directed) |
| { |
| int cnt = 0; |
| unsigned int lineno = 0; |
| char line[128], sp[2], a, p; |
| int num_nodes = 0, num_edges = 0; |
| |
| FILE *fptr; |
| CooTuple *tuple_array = NULL; |
| |
| fptr = fopen(tmpchar, "r"); |
| if (!fptr) { |
| fprintf(stderr, "Error when opening file: %s\n", tmpchar); |
| exit(1); |
| } |
| |
| printf("Opening file: %s\n", tmpchar); |
| |
| while (fgets(line, 100, fptr)) { |
| int head, tail, weight; |
| switch (line[0]) { |
| case 'c': |
| break; |
| case 'p': |
| fflush(stdout); |
| |
| sscanf(line, "%c %s %d %d", &p, sp, p_num_nodes, p_num_edges); |
| |
| if (!directed) { |
| *p_num_edges = *p_num_edges * 2; |
| printf("This is an undirected graph\n"); |
| } else { |
| printf("This is a directed graph\n"); |
| } |
| |
| num_nodes = *p_num_nodes; |
| num_edges = *p_num_edges; |
| |
| printf("Read from file: num_nodes = %d, num_edges = %d\n", num_nodes, num_edges); |
| tuple_array = (CooTuple *)malloc(sizeof(CooTuple) * num_edges); |
| break; |
| |
| case 'a': |
| sscanf(line, "%c %d %d %d", &a, &head, &tail, &weight); |
| if (tail == head) printf("reporting self loop\n"); |
| CooTuple temp; |
| temp.val = weight; |
| temp.row = tail - 1; |
| temp.col = head - 1; |
| tuple_array[cnt++] = temp; |
| if (!directed) { |
| temp.val = weight; |
| temp.row = tail - 1; |
| temp.col = head - 1; |
| tuple_array[cnt++] = temp; |
| } |
| |
| #ifdef VERBOSE |
| printf("Adding edge: %d ==> %d ( %d )\n", head, tail, weight); |
| #endif |
| break; |
| default: |
| fprintf(stderr, "exiting loop\n"); |
| break; |
| } |
| lineno++; |
| } |
| |
| std::stable_sort(tuple_array, tuple_array + num_edges, doCompare); |
| |
| #ifdef VERBOSE |
| for (int i = 0 ; i < num_edges; i++) { |
| printf("%d: %d, %d, %d\n", i, tuple_array[i].row, tuple_array[i].col, tuple_array[i].val); |
| } |
| #endif |
| |
| int *row_array = (int *)malloc((num_nodes + 1) * sizeof(int)); |
| int *col_array = (int *)malloc(num_edges * sizeof(int)); |
| int *data_array = (int *)malloc(num_edges * sizeof(int)); |
| |
| int row_cnt = 0; |
| int prev = -1; |
| int idx; |
| for (idx = 0; idx < num_edges; idx++) { |
| int curr = tuple_array[idx].row; |
| if (curr != prev) { |
| row_array[row_cnt++] = idx; |
| prev = curr; |
| } |
| col_array[idx] = tuple_array[idx].col; |
| data_array[idx] = tuple_array[idx].val; |
| } |
| while (row_cnt <= num_nodes) { |
| row_array[row_cnt++] = idx; |
| } |
| |
| csr_array *csr = (csr_array *)malloc(sizeof(csr_array)); |
| memset(csr, 0, sizeof(csr_array)); |
| csr->row_array = row_array; |
| csr->col_array = col_array; |
| csr->data_array = data_array; |
| |
| fclose(fptr); |
| free(tuple_array); |
| |
| return csr; |
| } |
| |
