Passing dynimic matrix to a function

[MrProfit]

Hi, mates!
I tried many ways to write it, but no success :(.
for example :

cin>>N;
int A[N][N];

Can matrix A be passed to a function anyway? when we dont know its size...?
I tried this too :

            A = new int*[N];
            for(int g=0; g<=N; ++g)
            {
                    A[g] = new int[N];
            }

but there were some mistakes the compiler couldnt show me.
After searching the web i found this code:

        int** A = NULL; 
        A = malloc((n-1)*sizeof(int *));
         for (i=0;i<n-1;i++)
            A[i] = malloc((n-1)*sizeof(int));

but the compiler had an error: couldnt parse from void*...
Thank you in advance!

[firedraco]

If you don't know the size, there is no way to get it, however in the first case, you could pass N as an additional argument to the function as the size of the array. e.g.:

void doIt(double** theArray, unsigned int columns, unsigned int rows);

[MrProfit]

Yeah, i tried that. But when reaching the line of the function in main() there was an error again :

99 C:\Documents and Settings\Angel\Desktop\ÏÐÀÍÊÀ @\Homework 1\Zadacha 3\main.cpp cannot convert `int (*)[((unsigned int)((int)N))]' to `int**' for argument `1' to `int f(int**, int)'

[helios]

That example expects the the function is called
double A[N][N];
doIt(A,N,N);

[MrProfit]

The function should be something like
f(int** A, int N, int otherArgument)
Actually, my goal is to find a diameter in a non-weighted graph, and i use the matrix A to represent it.

[Duthomhas]

Are you talking about a simple adjacency matrix? Or a distance matrix (where the entries are not the number of edges but the distance or length of a single edge between points)?

As for handling a variable-size multidimensional array, there are several possibilities. The first two are using arrays directly (as in C).

You could just calculate the indices yourself:

#include <iostream>
using namespace std;

#define matrix( M, N ) M[ N * N ]
#define index( M, N, i, j ) (M)[ (j * N) + i ]

int maximal_degree( int matrix( M, 1 ), int N )
  {
  int result = 0;
  for (int i = 0; i < N; i++)
    {
    int deg_i = index( M, N, i, i );  // loops get counted twice
    for (int j = 0; j < N; j++)
      deg_i += index( M, N, i, j );
    if (deg_i > result)
      result = deg_i;
    }
  return result;
  }

int main()
  {
  int matrix( A, 3 ) = 
    {
    0, 0, 1,
    0, 0, 1,
    1, 1, 1
    };

  cout << "The maximal degree of A is " << maximal_degree( A, 3 ) << " (should be 4)\n";
  return 0;
  }

You could use an array of pointers to arrays, which requires extra effort to maintain, but doesn't require the funky macros to mess with it:

#include <iostream>
using namespace std;

int maximal_degree( int** M, int N )
  {
  int result = 0;
  for (int i = 0; i < N; i++)
    {
    int deg_i = M[ i ][ i ];  // loops get counted twice
    for (int j = 0; j < N; j++)
      deg_i += M[ i ][ j ];
    if (deg_i > result)
      result = deg_i;
    }
  return result;
  }

int main()
  {
  int A0[ 3 ] = { 0, 0, 1 };
  int A1[ 3 ] = { 0, 0, 1 };
  int A2[ 3 ] = { 1, 1, 1 };
  int* A[ 3 ] = { A0, A1, A2 };

  cout << "The maximal degree of A is " << maximal_degree( A, 3 ) << " (should be 4)\n";
  return 0;
  }

The last way is just to make a simple C++ class to maintain the matrix. This is very much like the first one, but rather than using macros and keeping track of the size of your square adjacency matrix you just collect all that into a class and do the dirty work there -- just once. Here I've used a vector as the basis (which is essentially the same thing I did in the first example with the array).

#include <iostream>
#include <vector>
using namespace std;

template <typename Number, typename Allocator = allocator <Number> >
struct matrix: vector <Number, Allocator>
  {
  int N;

  matrix( int n ): vector <Number, Allocator> ( n ), N( n ) { }

  template <typename InputIterator>
    matrix( int n, InputIterator begin ): N( n )
    {
    this->assign( begin, begin + (n * n) );
    }

  Number& operator () ( int i, int j )
    {
    return this->at( (N * j) + i );
    }

  const Number& operator () ( int i, int j ) const
    {
    return this->at( (N * j) + i );
    }
  };

int maximal_degree( const matrix <int> & M )
  {
  int result = 0;
  for (int i = 0; i < M.N; i++)
    {
    int deg_i = M( i, i );  // loops get counted twice
    for (int j = 0; j < M.N; j++)
      deg_i += M( i, j );
    if (deg_i > result)
      result = deg_i;
    }
  return result;
  }

int main()
  {
  int _A[ 3 * 3 ] =
    {
    0, 0, 1,
    0, 0, 1,
    1, 1, 1
    };
  matrix <int> A( 3, _A );

  cout << "The maximal degree of A is " << maximal_degree( A ) << " (should be 4)\n";
  return 0;
  }

BTW, don't try to mess with the [] operator to access the array values -- it is the Wrong Thing. Stay with the () operator. See the C++FAQ-Lite if you want to know why.

Hope this helps.

[MrProfit]

Thank you a lot, Douas.
Yes, I am using an adjacency matrix and i want to find the diameter of the graph, im representing by that matrix. The graph is non-weighted, undirected and acyclic, so i dont use a distance matrix. Im not sure what does your maximal_degree function returns.

My last try was this :

int f(int** A, int N, int v)
{
     int p=0;
     int counter = 1;
     int* used = new int[N];
     used[v] = 1;
     bool found = false;
     
     queue<int> q;
     q.push(v);
     
     for(int k=0; k < N; ++k) used[k] = 0;
     
     
     while(!q.empty())
     {
         
         p = q.front();
         q.pop();
         for(int i=1; i <= N; ++i)
         {
                 if(A[p][i])
                 {
                            if(!used[i])
                            {
                                        q.push(i);
                                        used[i]=1;
                                        found = true;
                            }
                 }
         }
         if(found) counter++;
         found = false;
     }
     return counter;
     
}

int main()
{
    int N;
    int** A = NULL;

    A = new int*[999];
    for(int g=0; g<=N; ++g)
    {
           A[g] = new int[999];
    }

/* getting the matrix...*/
            int result=0;
            int temp=0;
            for(int i=1; i <+ N; ++i )
            {
                    temp = f(A,N,i);
                    if(result <= temp)
                    {
                    result = temp;
                    }
            }
            cout<<result;

With my compiler (Dev-C++) its ok, but when i submit it they say there is a run time error - their compiler throws an exception somewhere :(

[Duthomhas]

Is that your complete program?
You never initialize 'N'.
You never get a matrix from the user.
You never delete[] the memory you allocate.

[MrProfit]

Sorry, here it is all my code:

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;


int f(char** A, int N, int v)
{
     int p=0;
     int counter = 1;
     int* used = new int[N];
     bool found = false;
     
     queue<int> q;
     q.push(v);
     
     for(int k=0; k < N; ++k) used[k] = 0;
     used[v] = 1;
     
     while(!q.empty())
     {
         
         p = q.front();
         q.pop();
         for(int i=1; i <= N; ++i)
         {
                 if(A[p][i])
                 {
                            if(!used[i])
                            {
                                        q.push(i); //+1 ??? ili samo i ?
                                        used[i]=1;
                                        found = true;
                            }
                 }
         }
         if(found) counter++;
         found = false;
         //cout<<"For "<<p<<": "<<counter<<endl;
     }
     return counter;
     
}




int main()
{
    int N;
    int nt = 0;
    int a,b;
    char** A = NULL;
    
    cin>>nt;
    for(int t=0; t < nt; ++t)
    {
            cin>>N;


            A = new char*[5560];
            for(int g=0; g<=N; ++g)
            {
                    A[g] = new char[5560];
            }


                        
            for(int k=0; k <= N; ++k)
             for(int s=0; s <= N; ++s)
             {
                     A[k][s] = 0;
             }
                         

            for(int w=1; w < N; ++w)  // N-1 times
            {
                    cin>>a>>b;
                    A[a][b] = 1;
                    A[b][a] = 1;
            }


            
            int result=0;
            int temp=0;
            for(int i=1; i <+ N; ++i )
            {
                    temp = f(A,N,i);
                    if(result <= temp)
                    {
                    result = temp;
                    }
            }
            cout<<result;


            for(int g=0; g<=5560; ++g)
            {
                    delete[] A[g]
            }
            delete[] A;
            

            
    }
    
    
    system("PAUSE");
    return 0;
}

PS: I know your opinion about system("pause"), but this task is kind of "silly homework" :)

[Duthomhas]

You have some fencepost errors on lines 70 and 71 (you are looping one too many times...).
You also have a significant typo on line 88.

Your algorithm does not ask the user for any input. It might be a good idea to cout some information about what is expected next. For example

            cout << "Enter the " << N - 1 << " edges of the graph\n";
            for(int w=1; w < N; ++w)  // N-1 times
            {
                    cout << w << ": a b> ";
                    cin>>a>>b;
                    A[a][b] = 1;
                    A[b][a] = 1;
            }

I haven't analyzed your algorithm, but it gives incorrect output for the graph

1 2
1 3
1 4

The result should be 2, but your program reports 3.

Hope this helps.

PS I wasn't going to give you a hard time about it. ;-)

[MrProfit]

You are right, on line 88 there is a stupid mistake. I dont know if lines 70 and 71 can influence badly on the program, even I loop more times. Its true that its much better to cout information about whats next expected, but I'm not allowed to do so, cause a software checks if my program is correct and that would lead to wrong answer.
Unfortunately, you are also right about the algorithm, there something wrong with it.
I hope everything else is fine. Thank you for your time!