Hello Friends,
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
Code:
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'.
Code:
#include<iostream>
using namespace std;
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;
//nodes[i-1].outgoing->nodeId=0;
//nodes[i-1].incoming->nodeId=0;
}
}
//----------------------------------------------------------------------------------------------------
void addEdge(myNode *nodes, int start, int end)
{
cout<<"start:"<<start<<endl;cout<<"end:"<<end<<endl;
cout<<"----- Node"<<start<<" --------"<<endl;
cout<<"node id:"<<nodes->id<<endl;
cout<<"(nodes+(start-1)):"<<(nodes+(start-1))<<endl;
cout<<(nodes+(start-1))->outgoing->nodeId<<endl;
cout<<"(nodes+(start-1)).outgoing->nodeId:"<<(nodes+(start-1)).outgoing->nodeId<<endl;
}
//----------------------------------------------------------------------------------------------------
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.
Code:
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:
Originally Posted by Bjarne Stroustrup (2000-10-14)
