1 /* This file is part of Conauto.
2
3 Conauto is free software: you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation, either version 3 of the License, or
6 (at your option) any later version.
7
8 Conauto is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with Conauto. If not, see <http://www.gnu.org/licenses/>.
15 */
16
17 /* Graph representation and graph file operations */
18
19 #include <stdlib.h>
20 #include <inttypes.h>
21
22 #include "graph.h"
23
read_word(FILE * f)24 uint16_t read_word ( FILE *f )
25 {
26 int b1, b2;
27
28 b1 = fgetc ( f );
29 b2 = fgetc ( f );
30 return (uint16_t) ( b1 | ( b2 << 8 ) );
31 }
32
read_graph_sivalab(struct graph * g,FILE * f)33 void read_graph_sivalab ( struct graph *g, FILE *f )
34 {
35 uint16_t from, to;
36 uint16_t num_arc;
37 uint16_t i;
38
39 g->num_vert = read_word ( f );
40 g->deg = calloc ( (size_t)(g->num_vert), sizeof(uint64_t) );
41 g->adj = calloc ( (size_t)(g->num_vert), sizeof(uint8_t*) );
42 for ( from = 0; from < g->num_vert; from++ )
43 {
44 g->adj[from] = calloc ( (size_t)(g->num_vert), sizeof(uint8_t) );
45 for ( to = 0; to < g->num_vert; to++ )
46 g->adj[from][to] = NOT_ADJ;
47 g->deg[from] = (uint64_t)0;
48 }
49 g->num_arc = 0;
50 for ( from = 0; from < g->num_vert; from++ )
51 {
52 num_arc = read_word ( f );
53 for ( i = 0; i < num_arc; i++ )
54 {
55 to = read_word ( f );
56 g->num_arc++;
57 if ( g->adj[from][to] == NOT_ADJ )
58 {
59 g->deg[from] = g->deg[from] + UINT64_C(0x100000000) + (uint64_t)(from!=to);
60 g->deg[to] = g->deg[to] + UINT64_C(0x10000) + (uint64_t)(from!=to);
61 }
62 else
63 {
64 g->deg[from] = g->deg[from] - UINT64_C(0x10000) + UINT64_C(0x1000000000000);
65 g->deg[to] = g->deg[to] - UINT64_C(0x100000000) + UINT64_C(0x1000000000000);
66 }
67 g->adj[from][to] = g->adj[from][to] | ARC_OUT;
68 g->adj[to][from] = g->adj[to][from] | ARC_IN;
69 }
70 }
71 }
72
read_graph_dimacs(struct graph * g,FILE * f)73 void read_graph_dimacs ( struct graph *g, FILE *f )
74 {
75 const int buff_size = 1024;
76 char line[buff_size];
77 uint16_t from, to;
78 uint32_t i;
79
80 /* delete comments */
81 do {
82 fgets( line, buff_size, f );
83 } while( strncmp( line, "c ", 2 ) == 0 );
84 sscanf( line, "p edge %"SCNu16" %"SCNu32"\n", &(g->num_vert), &(g->num_arc) );
85 g->deg = calloc ( (size_t)(g->num_vert), sizeof(uint64_t) );
86 g->adj = calloc ( (size_t)(g->num_vert), sizeof(uint8_t*) );
87 for ( from = 0; from < g->num_vert; from++ )
88 {
89 g->adj[from] = calloc ( (size_t)(g->num_vert), sizeof(uint8_t) );
90 for ( to = 0; to < g->num_vert; to++ )
91 g->adj[from][to] = NOT_ADJ;
92 g->deg[from] = (uint64_t)0;
93 }
94 for( i = 0; i < g->num_arc; i++ )
95 {
96 /* delete comments */
97 do {
98 fgets( line, buff_size, f );
99 } while( strncmp( line, "c ", 2 ) == 0 );
100 sscanf( line, "e %"SCNu16" %"SCNu16"\n", &from, &to );
101 from = from - 1;
102 to = to - 1;
103 if ( g->adj[from][to] == NOT_ADJ )
104 {
105 g->deg[from] = g->deg[from] + UINT64_C(0x100000000) + (uint64_t)(from!=to);
106 g->deg[to] = g->deg[to] + UINT64_C(0x10000) + (uint64_t)(from!=to);
107 }
108 else
109 {
110 g->deg[from] = g->deg[from] - UINT64_C(0x10000) + UINT64_C(0x1000000000000);
111 g->deg[to] = g->deg[to] - UINT64_C(0x100000000) + UINT64_C(0x1000000000000);
112 }
113 g->adj[from][to] = g->adj[from][to] | ARC_OUT;
114 g->adj[to][from] = g->adj[to][from] | ARC_IN;
115 }
116 }
117
118