problem with pointers in structures

[venpo045]

Hello Friends,

I have some problem with pointers in structures can some help me with function void addEdge(myNode *nodes, int start, int end). My target is to assign the value which i receive as end in function to nodeId of LinkedNodes structure. When i try do the following assignment (nodes+(start-1))->outgoing->nodeId=end; in addEdge() i am getting error. Please let me know where i am doing wrong.

struct LinkedNodes{
int nodeId;
LinkedNodes *next;
};

struct myNode {
int id;
LinkedNodes *outgoing;
LinkedNodes *incoming;
};


void initNodes(myNode *nodes, int numNodes)
{
for(int i=1;i<=numNodes;i++){
nodes[i-1].id=i;
cout<<"nodes["<<i-1<<"]:"<<nodes[i-1].id<<endl;
}

}

void addEdge(myNode *nodes, int start, int end)
{
...........
(nodes+(start-1))->outgoing->nodeId=end;
............
}


int main(){
int numNodes;
.............
initNodes(nodes,numNodes);
.............
.............
int startEdge, endEdge;
.............
addEdge(nodes, startEdge, endEdge);
............
return 0;
}

[Konstantin2]

(nodes+(start-1))->outgoing is not initialized.
Do you forget

nodes[i-1].outgoing=...
nodes[i-1].incoming=...

in void initNodes(myNode *nodes, int numNodes) ?

[venpo045]

Hello Konstantin2,

My task is to construct a directed graph with nodes and edges between them. I want to write a program that reads in information about nodes & edges from the user and constructs a directed graph in memory.

Nodes must be represented using a structure
struct myNode { … };

Assume all nodes in the graph are stored in an array named 'nodes'. 'Id' of a node can
be used as an index in the array.
We will use the following structures to represent a node. structure LinkedNodes this
can be used to represent a chain of all outgoing and incoming nodes

[code]
struct LinkedNodes{
int nodeId;
LinkedNodes *next;
};

struct myNode {
int id;
LinkedNodes *outgoing;
LinkedNodes *incoming;
};
[\code]

Function initNodes() is called from the main program to initialize all the nodes, to a value starting from 1 to numNodes. Where as function addEdge() is used to add an edge from a node with value 'start' to another node with value 'end'.

Also the end of a list and a node containing either incoming/outgoing should be indicated
by pointing to NULL.

[dhayden]

To repeat Konstantin2's point, what are outgoing and incoming initialized to? addEdge assumes that outgoing points to a valid node but initNodes doesn't set it to anything so it may point to random memory. Is there some code you aren't showing that initializes it? If not, then that's your bug.

[venpo045]

Hello dhayden,

Thanks for reply.

My task is to construct a directed graph with nodes and edges between them. I want to write a program that reads in information about nodes & edges from the user and constructs a directed graph in memory.

Nodes must be represented using a structure
struct myNode { … };

Assume all nodes in the graph are stored in an array named 'nodes'. 'Id' of a node can
be used as an index in the array.
We will use the following structures to represent a node. structure LinkedNodes this
can be used to represent a chain of all outgoing and incoming nodes

Below is the description of 4 functions which i need to implement.

Function 'void initNodes(myNode *nodes, int numNodes)': This function is called from the main program to initialize all the nodes, to a value starting from 1 to numNodes(taken as input from the user in the main program) respectively. All the nodes are named serially as shown in all the figures above. Also note that node with the same value is not repeated(all are distinct).

Function 'void addEdge(myNode *nodes, int start, int end)':This function is used to add an edge from a node with value 'start' to another node with value 'end'. To store outgoing edges(from the node) and incoming edges(to the node), a separate list(one for outgoing and another for incoming) of linked structure 'LinkedNodes', can be attached to the memeber 'outgoing' and 'incoming' of the node(of type 'myNode') respectively. It also means that if there is an edge from node 'start' to node 'end', then node 'start' should have the information of the node 'end' stored as a list in the member 'outgoing' of the node 'start', and correspondingly node 'end' should have the information of the node 'start' stored as a list in the member 'incoming' of the node 'end'. If there are more than one outgoing edges from a single node(node 'a') to other nodes(node 'b' and node'c'), then the information of the edge added later(if an outgoing edge from node 'a' to node 'c' is added after an outgoing edge from node 'a' to node 'b') should be placed at the start of the list(then, the member 'outgoing' of the node 'a' should point to the list containing information of node 'c' followed by node 'b'). Similarly, if there are more than one incoming edges to a single node, then the information of the edge added later should also be placed at the start of the list.

The end of a list and a node containing either incoming/outgoing should be indicated by pointing to NULL

Note: If an edge from node 'start' to node 'end' is repeated, then it should simply be discarded.

Function 'void getOutgoingNodes(myNode *nodes, int i, int *nodesArray, int &num)': This function should store only those nodes which have incoming edges from node 'i'(i.e. node 'i' having outgoing edges to all such nodes), in an array 'nodesArray', starting from index '0' to index 'num'. In the 'main' program, the information contained is used to print all the nodes with edges from node 'i'.

Function 'void getIncomingNodes(myNode *nodes, int i, int *nodesArray, int &num)': This function should store only those nodes which have outgoing edges to node 'i'(i.e. node 'i' having incoming edges from all such nodes), in an array 'nodesArray', starting from index '0' to index 'num'. In the 'main' program, the information contained is used to print all the nodes with edges to node 'i'.

struct LinkedNodes{
int nodeId;
LinkedNodes *next;
};

struct myNode {
int id;
LinkedNodes *outgoing;
LinkedNodes *incoming;
};


void initNodes(myNode *nodes, int numNodes)
{
for(int i=1;i<=numNodes;i++){
nodes[i-1].id=i;
cout<<"nodes["<<i-1<<"]:"<<nodes[i-1].id<<endl;
}

}

void addEdge(myNode *nodes, int start, int end)
{
...........
(nodes+(start-1))->outgoing->nodeId=end;
............
}

void getOutgoingNodes(myNode *nodes, int i, int *nodesArray, int &num)
{

}

void getIncomingNodes(myNode *nodes, int i, int *nodesArray, int &num)
{

}

int main(){
  int numNodes;
  cout<<"Give number of nodes:";
  cin >> numNodes;
  cout<<numNodes<<endl;
  myNode *nodes = new myNode[numNodes];
  if(nodes == NULL){
    cout<<"Memory allocation failure."<<endl;
    return -1;
  }
  else{
    initNodes(nodes,numNodes);
  }
 
  int startEdge, endEdge;
  while (true) {
    // Reading in edges, one at a time
    cout << "Give start of edge (-1 to quit): ";
    cin >> startEdge;
    cout << startEdge << endl;
    if (startEdge == -1) break;
    cout << "Give end of edge (-1 to quit): ";
    cin >> endEdge;
    cout << endEdge << endl;
    if (endEdge == -1) break;
    addEdge(nodes, startEdge, endEdge);
  } 
  int *nodesArray = new int[numNodes];
  if(nodesArray == NULL){
    cout<<"Memory allocation failure."<<endl;
    return -1;
  }
  int num=0;
  cout << endl;
  // Printing adjacent nodes of every node
  for (int i = 0; i < numNodes; i++) {
    cout << "Nodes with edges from node " << i+1 << ": ";
    getOutgoingNodes(nodes, i, nodesArray, num);
    if(num!=0){
      for(int j=0;j<num-1;j++){
        cout<<nodesArray[j]<<" ";
      }
      cout << nodesArray[num-1] << endl;
    }
    if(num==0) cout << endl;
    num=0;
  }
  cout << endl;
  num=0; 
  for (int i = 0; i < numNodes; i++) {
    cout << "Nodes with edges to node " << i+1 << ": ";
    getIncomingNodes(nodes, i, nodesArray, num);
    if(num!=0){
      for(int j=0;j<num-1;j++){
        cout<<nodesArray[j]<<" ";
      }
      cout << nodesArray[num-1] << endl;
    }
    if(num==0) cout << endl;
    num=0;
  }
  return 0;
}

Here is the sample input and output which i need to achieve.

Input 1(with 4 nodes, edge from node '1' to node '1', a second duplicate edge from node '1' to node '1',  and -1 to terminate)

4

1

1

1

1

-1 

Output 1 for Input 1

Give number of nodes:4

Give start of edge (-1 to quit): 1

Give end of edge (-1 to quit): 1

Give start of edge (-1 to quit): 1

Give end of edge (-1 to quit): 1

Give start of edge (-1 to quit): -1

Nodes with edges from node 1: 1

Nodes with edges from node 2: 

Nodes with edges from node 3: 

Nodes with edges from node 4: 

Nodes with edges to node 1: 1

Nodes with edges to node 2: 

Nodes with edges to node 3: 

Nodes with edges to node 4: