Convert vertex names of a graph into indices in C

Question

I am given the input in the following manner, where the first line contains the number of vertices and edges of the undirected graph; and the lines to follow contain the names of vertices between which there is an edge.

Input:

9 8
sainteanne fortdefrance
bassepointe latrinite
bridgetown jackmans
fortdefrance ducos
holetown bridgetown
shanty bridgetown
fortdefrance bassepointe
jackmans shanty

This means that the graph has 9 vertices and 8 edges. There exist edges between the elements in each of the above mentioned pairs. The end goal is to find connected components in this graph.

However, working with vertices as index numbers is easier than working with strings. Therefore, I am looking for a way to convert the above information into something this:

I have written the following C code to read the file and create a structure containing edges in which the vertex id must be stored.

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

int main()
{   
    unsigned int order;                   // no.of Vertices
    unsigned int n;                       // no.of Edges
    edge *edges;

    scanf("%u %u",&order,&n);
    edges = malloc(n * sizeof(edge));
    char first_string[20];
    char second_string[20];

    for (int i=0;i<n;i++)
    {
        scanf("%s %s",first_string,second_string);

    }
   }

You are probably looking for this: https://stackoverflow.com/questions/838404/implementing-a-hashmap. Also you might want to google "_simple hashmap in c_" — Jabberwocky, Oct 03 '18 at 15:45
If your dataset is small, you can write your own naive implementation of a map (mapping strings to integers). That should be about 15-20 lines of code. — Jabberwocky, Oct 03 '18 at 15:49

kiran Biradar · Accepted Answer · 2018-10-03T16:23:25.210

You need to have naive implementation of a map (mapping strings to integers) as suggested by jabberwocky.

Define a structure as below to store the strings.

    typedef struct {
       unsigned int hashed;
       char **map;
   } hash;

Define a function which will insert the string into hashmap if it is not exists and return the index of string in hashmap.

int insertInMap(hash *map, char *entry)
Store the returned index into edge structure.

edges[i].first =insertInMap(&map,first_string); edges[i].second =insertInMap(&map,second_string)

Complete code:

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;


typedef struct {
    unsigned int hashed;
     char **map;
} hash;


int insertInMap(hash *map, char *entry)
{
  int i =0;
  for (i=0;i<map->hashed;i++)
  {
    if (strcmp(map->map[i],entry) == 0)
    return i;
  }
  /* Warning no boundary check is added */
  map->map[map->hashed++] = strdup(entry);   
  return map->hashed-1;
}

int main()
{   
    unsigned int order;                   // no.of Vertices
    unsigned int n;                       // no.of Edges
    edge *edges;
    hash map;    
    scanf("%u %u",&order,&n);
    edges = malloc(n * sizeof(edge));

    map.map = malloc(n * sizeof(char*));
    map.hashed = 0;

    char first_string[20];
    char second_string[20];

    for (int i=0;i<n;i++)
    {
        scanf("%s %s",first_string,second_string);
        edges[i].first =insertInMap(&map,first_string);
        edges[i].second =insertInMap(&map,second_string);

    }

   for (int i =0;i<n;i++)
   printf("%d->%d\n", edges[i].first, edges[i].second);

   /* Do your work*/

   for (int i=0;i<n;i++)
     free(map.map[i]);
     free(map.map);
     free(edges);
}

output:

0->1
2->3
4->5
1->6
7->4
8->4
1->2
5->8

Note:: I have not added boundary checking for hashmap

Convert vertex names of a graph into indices in C

1 Answers1