1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2016
Posts
14
Rep Power
0

#### Graphs concatenation

I need help with the following problem:

Given the representation of undirected and connected graph:
Code:
```typedef struct
{
int n;
int info[MAX];
}graph;```
Write a function with variable number of arguments that concatenates variable number of graphs
and returns new graph which is defined as:
Code:
```typedef struct
{
int n;
int *info;
int **am;
}new_graph;```
First function arguments is the number of graphs - p,
and optional arguments are pointers to graphs.

Concatenate graphs such that the last node of previous graph is linked with the first node of next graph
(graphs are processed one by one by using va_arg function).

New formed graph, after concatenation, will be new_graph.

In the new_graph, allocate exactly how much memory is needed for each node of each graph.

Here is what I have so far:
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#define MAX 100

typedef struct
{
int n;
int info[MAX];
int am[MAX][MAX];
}graph;

typedef struct
{
int n;
int *info;
int **am;
}new_graph;

new_graph* f(int p,...)
{
new_graph *ng;
ng->n=0;
int i,j;

va_list args;

va_start(args,p);

//store 'n' 'graphs' to array 'arr'
graph **arr=malloc(p * sizeof(graph *));
for(i=0;i<p;i++)
{
arr[i]=malloc(sizeof( va_arg(args,graph *) ) );
ng->n=ng->n+arr[i]->n;
ng->am=calloc(ng->n , sizeof(int *));
for(j=0;j<ng->n;j++)
ng->am[j]=calloc(ng->n , sizeof(int));

ng->info=malloc((MAX * p) * sizeof(int));

//for each 'graph' link the last node of previous
// to the first node of next graph
}
va_end(args);

return ng;
}

int main()
{
new_graph *ng;
graph g1={6, { 1, 2, 3, 4, 5, 6 },
{ { 0, 1, 1, 1, 0, 0 },
{ 1, 0, 0, 1, 0, 0 },
{ 1, 0, 0, 1, 1, 0 },
{ 1, 1, 1, 0, 1, 0 },
{ 0, 0, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0 } } };
graph g2={3, { 1, 2, 3 },
{ { 0, 1, 1 },
{ 1, 0, 0 },
{ 1, 0, 0 } } };

ng=f(2,&g1,&g2);

return 0;
}```
Question: How to make links with each previous and next graph in concatenation and allocate exactly
how much memory is needed for new_graph?
2. Per my understanding you'll need to create from the example
Code:
```0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
1 1 1 0 1 0 0 0
0 0 1 1 0 1 0 0
0 0 0 0 1 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0```
rows and columns are (the sum of all n's) minus (p - 1). For the p is 2 graphs the final dimensions are (and the result is square) (6 + 3) - (2 - 1) is 8. The simplest thing for info is allocate space for (in this case 8) integers and set them to 1 through 8.
Then incrementally go through the (the sum of all n's) minus (p - 1) to find the top left offsets for copying successive graphs into the combined graph.
Last edited by b49P23TIvg; October 10th, 2016 at 03:19 PM. Reason: as usual, missing text restored
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2016
Posts
14
Rep Power
0
Shouldn't the adjacency matrix be 9 X 9 (new graph has 9 nodes)?
Code:
```0 1 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 0
1 1 1 0 1 0 0 0 0
0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0```
4. I've given you my interpretation of
Originally Posted by assignment
Concatenate graphs such that the last node of previous graph is linked with the first node of next graph
Maybe you have explicit examples from the instructor that show otherwise.
Good luck!