#1
  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];
        int am[MAX][MAX];//adjacency matrix
    }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. #2
  3. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,859
    Rep Power
    509
    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
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. 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
  6. #4
  7. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,859
    Rep Power
    509
    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!
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo