Implementing Weighted edges to graph

Question

I want to be able to implement a shortest path algorithm but I realized there is no weight to the actual edge itself. I wanted to change my structure so that I can take a numerical value for the weight of going from one vertex to the other. How would I implement this?

#include<stdio.h>
    #include<stdlib.h>
    struct edge
    {
        int vertexIndex;
        struct edge *edgePtr;
    }edge;
    struct vertex
    {
        int vertexKey;
        struct edge *edgePtr;
    }vertex;
    struct vertex graph[1000];
    int vertexCount=0;
    void InsertVertex(int vertexKey)
    {
        graph[vertexCount].vertexKey=vertexKey;
        graph[vertexCount].edgePtr=NULL;
        vertexCount++;
    }
    void insertEdge(int vertex1, int vertex2)
    {
        struct edge *e,*e1,*e2;
        e=graph[vertex1].edgePtr;
        while(e&& e->edgePtr)
        {
            e=e->edgePtr;
        }
        e1=(struct edge *)malloc(sizeof(*e1));
        e1->vertexIndex=vertex2;
        e1->edgePtr=NULL;
        if(e)
            e->edgePtr=e1;
        else
            graph[vertex1].edgePtr=e1;
        e=graph[vertex2].edgePtr;
        while(e&& e->edgePtr)
        {
            e=e->edgePtr;
        }
        e2=(struct edge *)malloc(sizeof(*e2));
        e2->vertexIndex=vertex1;
        e2->edgePtr=NULL;
        if(e)
            e->edgePtr=e2;
        else
            graph[vertex2].edgePtr=e2;
    }
    void printGraph()
    {
        int i;
        struct edge *e;
        for(i=0;i<vertexCount;i++)
        {
            printf("%d",i);
            e=graph[i].edgePtr;
            while(e)
            {
                printf("->%d",e->vertexIndex);
                e=e->edgePtr;
            }
            printf("\n");
        }
    }
    int main()
    {
        InsertVertex(1);
        InsertVertex(2);
        InsertVertex(3);
        InsertVertex(4);
        InsertVertex(5);
        insertEdge(0,1);
        insertEdge(0,2);
        insertEdge(1,3);
        insertEdge(1,4);
        insertEdge(3,5);
        printGraph();
        return 0;
    }

Standard warning: Do **not** cast `void *` as returned by `malloc` & friends. — too honest for this site, Jul 30 '15 at 00:11

Eric Z · Accepted Answer · 2015-07-30T00:27:10.567

1

Weight is an attribute of an edge so you can add it in your edge struct.

struct edge
{
   // You can use "-1" as the default invalid weight
   int weight;
   int vertexIndex;
   struct edge *edgePtr;
}edge;

edited Jul 30 '15 at 00:27

answered Jul 30 '15 at 00:05

Eric Z

14,327
7
45
69

Good call Eric Z! I implemented weight into the insertEdge method and into the structure and now it has weight !!!! – Tyler Pierog Jul 30 '15 at 00:12
@TylerPierog: As there are no classes in C, there are also no methods actually. – too honest for this site Jul 30 '15 at 00:30
@Olaf: Strickly speaking, there is no method in C++ as well. There are only **functions** and **member functions**. – Eric Z Jul 30 '15 at 00:38
@EricZ: IIRC, these _member functions_ are called _methods_ in C++. However, I'm not a C++ expert and can only refer to HLOOPL like Python. – too honest for this site Jul 30 '15 at 00:42
@Olaf: The C++ standard mentions no method. People tend to use words method and function interchangably when it causes no misunderstanding. – Eric Z Jul 30 '15 at 00:48
@EricZ: "People tend to use words method and function" Not really, as you can also provide methods in C; actually OOP in C is not that rare. There is a good reason to differentiate the two types. Methods are functions bound to an object (thus methods are functions, but not vice versa.) – too honest for this site Jul 30 '15 at 01:01
@Olaf You misunderstood what I mean. In C/C++, unofficially you can use the paired terms function and member function, or method and member method(less likely though). If you want to go official, well, there is no such thing as method. The C/C++ language takes the term function. Don't look at C/C++ in a Python way. If you still have questions, take a look at C++ ANSI ISO IEC 14882 or [here](http://stackoverflow.com/questions/8596461/in-c-what-is-the-difference-between-a-method-and-a-function) – Eric Z Jul 30 '15 at 01:20
@EricZ: I did already. And: you are right, there is no such term with respect to functions - as much as there is none such in the C standard. However, that is common OOP nomenclature and clearly related to functions bound to an object (in whichever way). That has nothing to do with Python, etc. – too honest for this site Jul 30 '15 at 01:34

Implementing Weighted edges to graph

1 Answers1