I need to implement these methods using an Adjacency Matrix. I am struggling wit
ID: 3861580 • Letter: I
Question
I need to implement these methods using an Adjacency Matrix. I am struggling with the removeNode method. Removing a node at the end of the matrix is simple, but if I need to remove a node somewhere in the middle, then all of my index's get screwed up. This is the code I am using so far:
interface Graph boolean addNode (T x) Adds x to the set of nodes for this graph Returns true if and only if the node set changes as a result of this call boolean addEdge(T x, T y); Adds the edge (x,y) to this graph. If either x or y are new nodes, they are also added to the node set. Returns true if and only if the edges set changes as result of this call Set removeNode (T x) Removes x from the graph, as well as all edges for which x is either a source or target Returns the set of edges that was renoved ed. boolean remove Edge (T x, T y); Removes the edg (x,y) from this graph, as well as the e (y,x), if the dge graph is undirected. Neither of the nodes x or y are removed. Returns true if the graph changes as a result of this call.Explanation / Answer
#include<stdio.h>
#define max 20
int adj[ max ][ max ];
int n;
main()
{
int choice;
int node, origin, destin;
create_graph();
while ( 1 )
{
printf( "1.Insert a node " );
printf( "2.Insert an edge " );
printf( "3.Delete a node " );
printf( "4.Delete an edge " );
printf( "5.Dispaly " );
printf( "6.Exit " );
printf( "Enter your choice : " );
scanf( "%d", &choice );
switch ( choice )
{
case 1:
insert_node();
break;
case 2:
printf( "Enter an edge to be inserted : " );
fflush( stdin );
scanf( "%d %d", &origin, &destin );
insert_edge( origin, destin );
break;
case 3:
printf( "Enter a node to be deleted : " );
fflush( stdin );
scanf( "%d", &node );
delete_node( node );
break;
case 4:
printf( "Enter an edge to be deleted : " );
fflush( stdin );
scanf( "%d %d", &origin, &destin );
del_edge( origin, destin );
break;
case 5:
display();
break;
case 6:
exit();
default:
printf( "Wrong choice " );
break;
} /*End of switch*/
} /*End of while*/
} /*End of main()*/
create_graph()
{
int i, max_edges, origin, destin;
printf( "Enter number of nodes : " );
scanf( "%d", &n );
max_edges = n * ( n – 1 ); /* Taking directed graph */
for ( i = 1;i <= max_edges;i++ )
{
printf( "Enter edge %d( 0 0 ) to quit : ", i );
scanf( "%d %d", &origin, &destin );
if ( ( origin == 0 ) && ( destin == 0 ) )
break;
if ( origin > n || destin > n || origin <= 0 || destin <= 0 )
{
printf( "Invalid edge! " );
i–;
}
else
adj[ origin ][ destin ] = 1;
} /*End of for*/
} /*End of create_graph()*/
display()
{
int i, j;
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
printf( "%4d", adj[ i ][ j ] );
printf( " " );
}
} /*End of display()*/
insert_node()
{
int i;
n++; /*Increase number of nodes in the graph*/
printf( "The inserted node is %d ", n );
for ( i = 1;i <= n;i++ )
{
adj[ i ][ n ] = 0;
adj[ n ][ i ] = 0;
}
} /*End of insert_node()*/
delete_node( char u )
{
int i, j;
if ( n == 0 )
{
printf( "Graph is empty " );
return ;
}
if ( u > n )
{
printf( "This node is not present in the graph " );
return ;
}
for ( i = u;i <= n – 1;i++ )
for ( j = 1;j <= n;j++ )
{
adj[ j ][ i ] = adj[ j ][ i + 1 ]; /* Shift columns left */
adj[ i ][ j ] = adj[ i + 1 ][ j ]; /* Shift rows up */
}
n–; /*Decrease the number of nodes in the graph */
} /*End of delete_node*/
insert_edge( char u, char v )
{
if ( u > n )
{
printf( "Source node does not exist " );
return ;
}
if ( v > n )
{
printf( "Destination node does not exist " );
return ;
}
adj[ u ][ v ] = 1;
} /*End of insert_edge()*/
del_edge( char u, char v )
{
if ( u > n || v > n || adj[ u ][ v ] == 0 )
{
printf( "This edge does not exist " );
return ;
}
adj[ u ][ v ] = 0;
}