start variable pointer in struct

cpit · #1 06-Jan-2006, 11:23

I need to know how to start the atribute connections in Vertex Struct.

CPP / C++ / C Code:

typedef struct
{
	 int weight;
	 int dest;
} DijkEdge;

typedef struct
{
	 DijkEdge* connections; 
	 int numconnect;
	 int distance;
	 int isDead;
} Vertex;

davekw7x · #2 06-Jan-2006, 12:54

Quote:

Originally Posted by cpit

I need to know how to start the atribute connections in Vertex Struct.

The typedef does not create any structs or any other objects in memory.

If you want to create a struct, then you can simply declare it. If you want to initialize all members to zero, you can initialize it:

CPP / C++ / C Code:

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

typedef struct
{
	 int weight;
	 int dest;
} DijkEdge;

typedef struct
{
	 DijkEdge* connections; 
	 int numconnect;
	 int distance;
	 int isDead;
} Ver;

int main()
{
  Ver vertex = {0}; /* all members set to zero */

  printf("vertex.connections = %p\n", vertex.connections);
  printf("vertex.numconnect  = %d\n", vertex.numconnect);
  printf("vertex.distance    = %d\n", vertex.distance);
  printf("vertex.isDead      = %d\n", vertex.isDead);

  return 0;
}

Regards,

Dave

cpit · #3 06-Jan-2006, 14:04

OK, but I still have a dubt.

in the last sample, if I put 1, dont run!

I need know how to call the function Dijkstra in main(), I don't undestanding how pass the parameters.

I have a follow data:

array.

1 3 1 <source><destination><weight>
1 5 1
2 3 1
2 4 1
3 4 1
4 5 1

nodecount = 5.

how can I execute this function with these data?

regards.

Code:

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
	 int weight;
	 int dest;
} DijkEdge;
typedef struct
{
	 DijkEdge* connections; /* An array of edges which has this as the starting node */
	 int numconnect;
	 int distance;
	 int isDead;
} Vertex;

void Dijkstra(Vertex* graph, int nodecount, int source)
{
	 for(int i = 0; i < nodecount; i++)
	 {
		 if(i == source)
		 {
			 graph[i].distance = 0;
			 graph[i].isDead = 0;
		 }
		 else
		 {
			 graph[i].distance = INFINITY;
			 graph[i].isDead = 0;
		 }
	 }
	 for(int i = 0; i < nodecount; i++)
	 {
		 int next;
		 for(int j = 0; j < nodecount; j++)
		 {
			 int min = INFINITY+1;
			 if(!graph[j].isDead && graph[j].distance < min)
			 {
				 next = j;
				 min = graph[j].distance;
			 }
		 }
		 for(int j = 0; j < graph[next].numconnect; j++)
		 {
			 if(graph[graph[next].connections[j].dest].distance > graph[next].distance + graph[next].connections[j].weight)
			 {
				 graph[graph[next].connections[j].dest].distance = graph[next].distance + graph[next].connections[j].weight;
			 }
		 }
		 graph[next].isDead = 1;
	 }
	 for(int i = 0; i < nodecount; i++)
	 {
		 printf("The distance between nodes %i and %i is %i", source, i , graph[i].distance);
	 }
}

void main(){



system("PAUSE");
return 0;
}

davekw7x · #4 06-Jan-2006, 14:27

Quote:

Originally Posted by cpit

in the last sample, if I put 1, dont run!

What happened? "Don't run" doesn't tell me anything. I just initialized everything to zero. If you put {1} as the initializer list, it initializes the first struct member to 1 and the others to zero.

Note that initializing a pointer to zero or initialializing a pointer to 1 doesn't do anything useful (but doesn't cause any errors unless you dereference it).

Quote:

Originally Posted by cpit

I need know how to call the function Dijkstra in main(), I don't undestanding how pass the parameters.

You invoke a function by calling the function (using the function name in the calling program) with actual variables in place of the formal parameters of the function's definition. If the called function uses value(s) of any of the arguments, then the outer function assigns values before invoking the function.

The function Dijkstra is defined to take arguments that are
1. Pointer to Vertex
2. int
3. int

In your main():
1. You could have an array of Vertex variables declared in main(). If this is the case, use the name of the array as the first argument (the name of an array used by itself in a function argument is taken to be a pointer to the first element of the array). Or you could have declared a pointer to Vertex in main(), in which case the pointer probably would have been given a value pointing to a block of dynamically allocated memory (malloc() for C or new[] for C++). The number of Vertex structs in the array and values of some of the members of each element of the array are somehow assigned from the input data (I assume).

2. It appears as if the second argument will be an int that tells the Dijkstra function how many Vertex objects are in the array.

3. The third argument is an int that is used for something in the function.

If you didn't write the function Dijkstra() (and I'm guessing that you didn't), then you should have been given some explanation of the nature of the arguments. And some idea of what the function is supposed to accomplish. And some idea of what the input means. And some idea of what to expect for the output.

If you did write the function, then you already know the nature of the arguments, and all of the other stuff, and I don't understand your question.

Regards,

Dave

cpit · #5 06-Jan-2006, 14:53

Dave,

I'm not wrote this code, but i need to test this...

here is my function main, i have declared a array matrizO[]

but I think this are wrong.

matrizO[0].connections.dest=1;
matrizO[0].connections.weight=1;

Code:

void main(){

//An array of variable vertex

Vertex matrizO[10]={0};

matrizO[0].connections.dest=1;   //number of each node
matrizO[0].connections.weight=1;
matrizO[0].numconnect=5; //five nodes of the network.
matrizO[0].distance=1; //distance of nodes
matrizO[0].isDead=0;


system("PAUSE");
return 0;
}

davekw7x · #6 07-Jan-2006, 08:32

Quote:

Originally Posted by cpit

Dave,

I'm not wrote this code, but i need to test this...

here is my function main, i have declared a array matrizO[]

but I think this are wrong.

CPP / C++ / C Code:

matrizO[0].connections.dest=1;
matrizO[0].connections.weight=1;

It appears that you are approaching the problem the way that I might do it: Rather than start with a complete program that does everything, get something into the data structure by "hard coding" it and worry about I/O later. (In some cases I might do it in the opposite sequence: nail down the I/O first, then apply it to test the function. But I'll go with what you are actually asking here, since, either way, you have to be able to get something into the data base for the function to work on. There is nothing wrong with this approach.)

Well, lets see the sequence that I might follow in developing a main() program to test the function.

1. Allocate an array of Vertex objects by simple declaration.

2. Enter values into the elements of the array directly instead of trying to read from an input file.

3. Call the function and see if the output is what I expected.

4. Now, go back and read input values from a file and look at the complete program results.

Progress so far:

1. OK. Good job.

2. Well, let's see...

For each element in the array of Vertex objects, the member "connections" is a pointer to an edge struct. Now, it doesn't really matter if we explicitly initialize the pointer or not, the fact is that it doesn't point to anything useful. Usually we would allocate memory (using malloc() in a C program, or new in C++) so that the pointer points to a block of memory that we treat as an array of DijkEdge structs.

Maybe something like the following:

CPP / C++ / C Code:

int main(){

  Vertex matrizO[10]; /* an array of Vertex structs */


  /* Initialize the first Vertex struct */
  matrizO[0].connections = malloc(2 * sizeof(DijkEdge)); /* two connections*/
                                        /* we should test the return value */
                                        /* and abort the program if malloc */
                                        /* returned a null value           */

  matrizO[0].connections[0].dest = 3;   /* first edge has destination = 3  */
  matrizO[0].connections[0].weight = 1; /* first edge has weight = 1       */
  matrizO[0].connections[1].dest = 5;   /* second edge has destination = 5 */
  matrizO[0].connections[1].weight = 1; /* second edge has weight = 1      */
  matrizO[0].numconnect = 2;            /* first edge has two connections  */

  /* Initialize the second Vertex struct */
  matrizO[1].connections = malloc(2 * sizeof(DijkEdge)); /* two connections*/
                                        /* we should test the return value */
                                        /* and abort the program if malloc */
                                        /* returned a null value           */
  matrizO[1].connections[0].dest = 3;
  matrizO[1].connections[0].weight = 1;
  matrizO[1].connections[1].dest = 4;
  matrizO[1].connections[1].weight = 1;
  matrizO[1].numconnect = 2;           /* second edge has two connections */

  /* 
   * Maybe print out the values just to make sure that everything can
   * be addressed properly
   *
   */

  /* Initialize the remaining Vertex structs and call the function        */
  

  /* finally: de-allocate storage obtained from malloc() */
  free(matrizO[0].connections);
  free(matrizO[1].connections);
  return 0;
}

Note that it appears that the Dijkstra function calculates and assign values to the "distance" and "isDead" members, so initializing them in main() seems superfluous.

Regards,

Dave

cpit · #7 09-Jan-2006, 03:17

Here is my main() function, I have entered with all data for the graph attached (fig. jpg), but the output is not what I expected.

see:
The output actual:

"The distance between nodes 0 and 0 is 0"
"The distance between nodes 0 and 1 is 1073741823"
"The distance between nodes 0 and 2 is 1"
"The distance between nodes 0 and 3 is 1073741823"
"The distance between nodes 0 and 4 is 1"

The output expected:

"The distance between nodes 0 and 0 is 0"
"The distance between nodes 0 and 1 is 2"
"The distance between nodes 0 and 2 is 1"
"The distance between nodes 0 and 3 is 2"
"The distance between nodes 0 and 4 is 1"

Because for the node 0 to transmit something to node eg. 3, it need to do 2 hops. (0-2-3 or 0-4-3).

I see that if I call the function Dijkstra with start at 2 or more, the output is OK.

Dijkstra(matrizO,5,0) - output wrong.
Dijkstra(matrizO,5,1) - outout wrong.
Dijkstra(matrizO,5,2) - output OK.
Dijkstra(matrizO,5,3) - output OK.
Dijkstra(matrizO,5,4) - output OK.

But I don´t see where i can change to obtain OK in start 0 and 1!

Code:

void main(){

Vertex matrizO[10];

matrizO[0].connections = new DijkEdge[2]; .
   matrizO[0].connections[0].dest = 2;   /* first edge has destination = 2  */
   matrizO[0].connections[0].weight = 1; /* first edge has weight = 1       */
   matrizO[0].connections[1].dest = 4;   /*second edge has destination = 4*/
   matrizO[0].connections[1].weight = 1; /* second edge has weight = 1 */
   matrizO[0].numconnect = 2;            /* first edge has two connections  */

matrizO[1].connections = new DijkEdge[2];
  matrizO[1].connections[0].dest = 2;
  matrizO[1].connections[0].weight = 1;
  matrizO[1].connections[1].dest = 3;
  matrizO[1].connections[1].weight = 1;
  matrizO[1].numconnect = 2;        

matrizO[2].connections = new DijkEdge[3];
  matrizO[2].connections[0].dest = 0;
  matrizO[2].connections[0].weight = 1;
  matrizO[2].connections[1].dest = 1;
  matrizO[2].connections[1].weight = 1;
  matrizO[2].connections[2].dest = 3;
  matrizO[2].connections[2].weight = 1;
  matrizO[2].numconnect = 3;

matrizO[3].connections = new DijkEdge[3];
  matrizO[3].connections[0].dest = 1;
  matrizO[3].connections[0].weight = 1;
  matrizO[3].connections[1].dest = 2;
  matrizO[3].connections[1].weight = 1;
  matrizO[3].connections[2].dest = 4;
  matrizO[3].connections[2].weight = 1;
  matrizO[3].numconnect = 3;   

matrizO[4].connections = new DijkEdge[2];
  matrizO[4].connections[0].dest = 0;
  matrizO[4].connections[0].weight = 1;
  matrizO[4].connections[1].dest = 3;
  matrizO[4].connections[1].weight = 1;
  matrizO[4].numconnect = 2;         

Dijkstra(matrizO, 5, 0); //call of function

free(matrizO[0].connections);
free(matrizO[1].connections);
free(matrizO[2].connections);
free(matrizO[3].connections);
free(matrizO[4].connections);

thanks for your pacience!

regards

davekw7x · #8 09-Jan-2006, 07:54

Quote:

Originally Posted by cpit

Here is my main() function, I have entered with all data for the graph attached (fig. jpg), but the output is not what I expected.

When the output is not what you expected, four possibilities come to mind:

1. Your expectations are wrong. (The specified functionality is not what you think.)

2. The input that program was given is not consistent with the expected output.

3. There is a bug in the program that is exhibited by applying your test data.

4. Any combination of one or more of the above.

If you are sure that your input data is what you had in mind and you are sure that you understand what the program is supposed to be doing, then that leaves number 3.

Look at the value shown in the unexpected outputs: 1073741823. Where the heck did this come from? (Hint use a print statement to show the value of INFINITY as #defin'ed in this program.)

Now look at the graph and look at the places where the program found the distance to be INFINITY. Is there a pattern there?

My understanding is that you were given the function, Dijsktra(), and your assignment was to test it. It seems that you have done the work to test the function. What are your conclusions?

Regards,

Dave

If you are interested in further detective work/debugging, you might try calling the function for all source nodes. So, in main(), you could have something like:

CPP / C++ / C Code:

    int i;
.
.
.
    for (i = 0; i < 5; i++) {
      Dijkstra(matrizO, 5, i);
      printf("\n");
    }

cpit · #9 10-Jan-2006, 03:18

Hi Friend,

I did all the test of you suggest, but I still cannot find out where are wrong in this code.

I think my input are correct, see attach file (nettest1.jpg), but the program insist in prints not expected.

Output of sample 1:

The distance between nodes 0 and 0 is 0
The distance between nodes 0 and 1 is 1
The distance between nodes 0 and 2 is 1
The distance between nodes 0 and 3 is 1

The distance between nodes 1 and 0 is 1
The distance between nodes 1 and 1 is 0
The distance between nodes 1 and 2 is 2
The distance between nodes 1 and 3 is 2

The distance between nodes 2 and 0 is 1
The distance between nodes 2 and 1 is 2
The distance between nodes 2 and 2 is 0
The distance between nodes 2 and 3 is 2

The distance between nodes 3 and 0 is 1
The distance between nodes 3 and 1 is 2
The distance between nodes 3 and 2 is 2
The distance between nodes 3 and 3 is 0

Output of sample 2:

The distance between nodes 0 and 0 is 1
The distance between nodes 0 and 1 is 1073741823
The distance between nodes 0 and 2 is 1
The distance between nodes 0 and 3 is 1073741823
The distance between nodes 0 and 4 is 1

The distance between nodes 1 and 0 is 1073741823
The distance between nodes 1 and 1 is 0
The distance between nodes 1 and 2 is 1
The distance between nodes 1 and 3 is 1
The distance between nodes 1 and 4 is 1073741823

The distance between nodes 2 and 0 is 1
The distance between nodes 2 and 1 is 1
The distance between nodes 2 and 2 is 0
The distance between nodes 2 and 3 is 1
The distance between nodes 2 and 4 is 2

The distance between nodes 3 and 0 is 2
The distance between nodes 3 and 1 is 1
The distance between nodes 3 and 2 is 1
The distance between nodes 3 and 3 is 0
The distance between nodes 3 and 4 is 1

The distance between nodes 4 and 0 is 1
The distance between nodes 4 and 1 is 2
The distance between nodes 4 and 2 is 2
The distance between nodes 4 and 3 is 1
The distance between nodes 4 and 4 is 0

--> The lines that shown 1073741823 are wrong

The sample 1 is OK, but int the sample 2, the lines that shown 1073741823 are wrong. As the attached figure (netteste1.jpg), for the sample 2, the distance between 0 and 1 would be 2. (and not 1073741823).
The distance between 0 and 3 would be 2.
The distance between 1 and 0 would be 2.
The distance between 1 and 4 would be 2.

The other lines are correct, I do not find out where are wrong in this code.

Code:

#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
	 int weight;
	 int dest;
} DijkEdge;

typedef struct
{
	 DijkEdge* connections; /* An array of Edges DijkEdge.*/
	 int numconnect;
	 int distance;
	 int isDead;
} Vertex;

void Dijkstra(Vertex* graph, int nodecount, int source)
{
	 for(int i = 0; i < nodecount; i++)
	 {
		 if(i == source)
		 {
			 graph[i].distance = 0;
			 graph[i].isDead = 0;

		 }
		 else
		 {
			 graph[i].distance = INFINITY;
			 graph[i].isDead = 0;
		 }
	 }
	 for(int i = 0; i < nodecount; i++)
	 {
		 int next;
		 for(int j = 0; j < nodecount; j++)
		 {
			 int min = INFINITY+1;
			 if(!graph[j].isDead && graph[j].distance < min)
			 {
				 next = j;
				 min = graph[j].distance;

			 }
		 }

		 for(int j = 0; j < graph[next].numconnect; j++)
		 {
             printf("\n j vale  %d  e next vale %d ", j, next);
			 if(graph[graph[next].connections[j].dest].distance > graph[next].distance + graph[next].connections[j].weight)
			 {
				 graph[graph[next].connections[j].dest].distance = graph[next].distance + graph[next].connections[j].weight;
			 }
		 }
		 graph[next].isDead = 1;  
   	 }

	 for(int i = 0; i < nodecount; i++)
	 {
		 printf("\nThe distance between nodes %i and %i is %i", source, i , graph[i].distance);

	 }
}

void main(){

//sample 1.
Vertex matrizO1[4];
matrizO1[0].connections = new DijkEdge[3];
   matrizO1[0].connections[0].dest=1;
   matrizO1[0].connections[1].dest=2;
   matrizO1[0].connections[2].dest=3;
   matrizO1[0].connections[0].weight=1;
   matrizO1[0].connections[1].weight=1;
   matrizO1[0].connections[2].weight=1;
matrizO1[0].numconnect = 3;

matrizO1[1].connections = new DijkEdge[1];
   matrizO1[1].connections[0].dest=0;
   matrizO1[1].connections[0].weight=1;
matrizO1[1].numconnect = 1;

matrizO1[2].connections = new DijkEdge[1];
   matrizO1[2].connections[0].dest=0;
   matrizO1[2].connections[0].weight=1;
matrizO1[2].numconnect = 1;

matrizO1[3].connections = new DijkEdge[1];
   matrizO1[3].connections[0].dest=0;
   matrizO1[3].connections[0].weight=1;
matrizO1[3].numconnect = 1;

   for (int i = 0; i < 4; i++) {
      Dijkstra(matrizO1, 4, 1);
      printf("\n");
    }

free(matrizO1[0].connections);
free(matrizO1[1].connections);
free(matrizO1[2].connections);
free(matrizO1[3].connections);
//-----------------------------------------------


//Sample 2

Vertex matrizO[5];

matrizO[0].connections = new DijkEdge[2]; 
   matrizO[0].connections[0].dest = 2;   /* First edge with destination = 2  */
   matrizO[0].connections[1].dest = 4;   /* Second edge with destination = 4/
      matrizO[0].connections[0].weight = 1; /* First edge with weight 1*/
      matrizO[0].connections[1].weight = 1; /* Second edge with weight =1    */
         matrizO[0].numconnect = 2;            /* First node with two connect */

matrizO[1].connections = new DijkEdge[2];
  matrizO[1].connections[0].dest = 2;
  matrizO[1].connections[1].dest = 3;
     matrizO[1].connections[0].weight = 1;
     matrizO[1].connections[1].weight = 1;
        matrizO[1].numconnect = 2;

matrizO[2].connections = new DijkEdge[3];
  matrizO[2].connections[0].dest = 0;
  matrizO[2].connections[1].dest = 1;
  matrizO[2].connections[2].dest = 3;
    matrizO[2].connections[0].weight = 1;
    matrizO[2].connections[1].weight = 1;
    matrizO[2].connections[2].weight = 1;
       matrizO[2].numconnect = 3;

matrizO[3].connections = new DijkEdge[3];
  matrizO[3].connections[0].dest = 1;
  matrizO[3].connections[1].dest = 2;
  matrizO[3].connections[2].dest = 4;
     matrizO[3].connections[0].weight = 1;
     matrizO[3].connections[1].weight = 1;
     matrizO[3].connections[2].weight = 1;
        matrizO[3].numconnect = 3;

matrizO[4].connections = new DijkEdge[2];
  matrizO[4].connections[0].dest = 0;
  matrizO[4].connections[1].dest = 3;
     matrizO[4].connections[0].weight = 1;
     matrizO[4].connections[1].weight = 1;
        matrizO[4].numconnect = 2;


 for (int i = 0; i < 5; i++) {
      Dijkstra(matrizO, 5, 1);
      printf("\n");
    }

free(matrizO[0].connections);
free(matrizO[1].connections);
free(matrizO[2].connections);
free(matrizO[3].connections);
free(matrizO[4].connections);

//-----------------------------------------------

system("PAUSE");
return 0;
}

davekw7x · #10 10-Jan-2006, 08:39

Quote:

Originally Posted by cpit

Hi Friend,

I did all the test of you suggest, but I still cannot find out where are wrong in this code.

It appears to me (based on observations of your original example) that the code is not measuring distances between nodes unless they are adjacent (distance = 1). (But maybe I am looking at it wrong.) So you must look at the code and see how it is doing what it does. Step through the code with node 0 and see how it could possibly get to all of the other nodes.

Maybe you can tell us exactly what your assignment is. You previously said that you were given the code to test. Are you also supposed to debug it? (Assuming that your interpretation of the expected results is correct, and that the code itself is incorrect.)

In other words, what background information was covered (or assumed) that would put you in a postition to understand the algorithm and/or the code that is trying to implement it? What is the precise specification of what the Dijkstra() function is supposed to do?

I personally have no way of knowing how to help any more, since I don't know what the prerequisites of your assignment are and I have no way of knowing what your level of knowledge is (knowledge of C? knowledge of graph theory? knowledge of anything else that would help you understand?).

After looking at some code (my code or someone else's code), if I don't understand why it gives unexpected results, the way that I debug a program is to sprinkle printf (or cout) statements liberally over the landscape and see exactly what the code is working on at each step. I compare what the program sees and the results of its calculations and/or comparisons with my understanding of the algorithm that the code is implementing.

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
2D arrays:dynamic allocation and freeing	bravetanveer	C Programming Language	48	27-Nov-2007 15:55
Urgent ! Pls Help Me !	mycashmoney	C Programming Language	4	01-Jul-2006 22:49
Pointer Usage in C++: Beginner to Advanced	varunhome	C++ Forum	0	19-Aug-2005 09:25
[Tutorial] Pointers in C (Part II)	Stack Overflow	C Programming Language	0	27-Apr-2005 17:36

start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct

Re: start variable pointer in struct