Interesting ideas on memory usage but executed (by someone other than myself) in non-compilable code

[Paul]

The URL http://www.infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai seems to contain useful algorithms in C/C++. (By "C/C++", I mean that the author uses C constructs but they're supposed to compile in C++ too. As in the subject title, some of it doesn't compile in either C or C++, though, using gnu).

The language of the original text is Romanian/C/C++ (I think) but Google Translate works superbly (which isn't to imply that other online translators aren't equally good or better)>

The relevant excerpt begins after "BEGIN QUOTE".
int N, M, G * [N], Deg [N]; doesn't compile, and I wouldn't expect it to compile either.
Can anyone suggest a correction? Also, I am trying to learn from this URL more generally, so I would be very interested if someone disagrees with anything on the URL or in the quote below, even if it isn't pertinent to my non-compilation problem.

Many thanks for your help,

Paul

BEGIN QUOTE
Graphs lists adjacency
It knows (or should know!) That working with pointers is very slow ... so they retain a graph rarely (number of nodes, small number of edges) with pointers (see below) greatly slow the program .

struct list
{
int n;
struct list * next;
}

typedef struct Lists;
In contiuare we present a method that is 3-4 times faster (ie Browsing DF, BF or other algorithms runs 3-4 times faster when the graph is stored so), but has the disadvantage need to read twice input file.


#include <stdlib.h>
#include <stdio.h>

// BELOW SEEMS WRONG AND IS AN ERROR ON MY COMPILER
// ****************************************************
int N, M, G * [N], Deg [N];
// ************************************************

int main ( void )
{
int i, j;

freopen ( "in.txt" , "r" , stdin);
scanf ( "% d% d" , & N & M);
for (; M> 0; M--)
{
scanf ( "% d% d" , & i, & j);
Deg [i - 1] ++, Deg [j - 1] ++;
}
for (i = 0; i <N; Deg [i ++] = 0)
G [i] = ( int *) malloc (Deg [i] * sizeof ( int ));
fseek (stdin, 0, SEEK_SET);
scanf ( "% d% d" , & N & M);
for (; M> 0; M--)
{
scanf ( "% d% d" , & i, & j);
i--, j--;
G [i] [Deg [i] ++] = j
G [j] [Deg [j] ++] = i;
}

return 0;
}
The speed increase is because the vectors are used instead of pointers and struct sites. If we can avoid reading memory allows twice the file by keeping the edges in a list of edges and then after calculating grades, inserting edges in lists. To demonstrate the effectiveness of this method do the following test: a source deploy and implement struct pointer and a BF, then write the code above with the following changes:


for (i = 0; i <N; i ++)
{
G [i] = ( int *) malloc ((Deg [i] +1) * sizeof ( int ));
G [i] [Deg [i]] = 1;
Deg [i] = 0;
}

and implement BF follows:


void BF ()
{
int Q [N], ql, qr, * p;
char U [N];
memset (U, 0, sizeof (U));
U [Q [ql = qr = 0] = n] = 1;
for (; ql <= qr; ql ++)
for (p = G [Q [ql]]; * p! = -1; p ++)
if (! U [* i]) U [Q [qr ++] = * p] = 1;
}
Then try to see the time difference between the two programs ... impressive, huh?
END QUOTE

[Christian Gollwitzer]

Am 21.05.16 um 11:11 schrieb Paul:

#include <stdio.h>
>
> // BELOW SEEMS WRONG AND IS AN ERROR ON MY COMPILER
> // ****************************************************
> int N, M, G * [N], Deg [N];
> // ************************************************

> scanf ( "% d% d" , & N & M);

> G [i] = ( int *) malloc (Deg [i] * sizeof ( int ));

This line suggests that indeed G should be an array of pointers of
length N, and Deg an array of ints of length N. SInce N is only known at
runtime, instead try:

int N, M;

scanf ( "% d% d" , & N & M);

int **G = (int **) malloc(sizeof(int*)*N);
int *Deg = (int*) malloc(sizeof(int)*N);

if you stick to C. Otherwise use either new or std::vector.
There is more to it: Deg[] is not initialized before it's used. I
suppose that the input to the algorithm goes there.

Cave: I haven't tried to compile this code.

Christian

[Ben Bacarisse]

Christian Gollwitzer <auri...@gmx.de> writes:

> Am 21.05.16 um 11:11 schrieb Paul:
> #include <stdio.h>
>>
>> // BELOW SEEMS WRONG AND IS AN ERROR ON MY COMPILER
>> // ****************************************************
>> int N, M, G * [N], Deg [N];
>> // ************************************************
>
>> scanf ( "% d% d" , & N & M);
>
>> G [i] = ( int *) malloc (Deg [i] * sizeof ( int ));
>
> This line suggests that indeed G should be an array of pointers of
> length N, and Deg an array of ints of length N. SInce N is only known
> at runtime, instead try:
>
> int N, M;
> scanf ( "% d% d" , & N & M);

It's scanf("%d%d",...) or "%d %d" (which does the same) but you can't
have a space after the %.

> int **G = (int **) malloc(sizeof(int*)*N);
> int *Deg = (int*) malloc(sizeof(int)*N);
>
> if you stick to C.

Though C (in the 1999 version) has variable length arrays and, since C++
does not, you need to use malloc when you *don't* want to stick to C (or
when you need to use old C). To make it work, though, you need to
declare

int *G[N], Deg[N];

after N has been given a value.

For purely C code, the usual idiom is:

int *Deg = malloc(N * sizeof *Deg);

But your code is clearly the way to go if C and C++ compiling is
required (though why this would be important I can't imagine).

> Otherwise use either new or std::vector.

Yes, I'd go full C++ for this sort of thing. Much simpler.

<snip>
--
Ben.