Преобразование имен вершин графа в индексы в C

Question

Мне дают ввод следующим образом, где первая строка содержит количество вершин и ребер неориентированного графа;и последующие строки содержат названия вершин, между которыми есть ребро.

Ввод:

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

Это означает, что граф имеет 9 вершин и 8 ребер.Существуют ребра между элементами в каждой из вышеупомянутых пар.Конечная цель - найти связанные компоненты на этом графике.

Однако работать с вершинами в качестве порядковых номеров проще, чем со строками.Поэтому я ищу способ преобразовать вышеупомянутую информацию во что-то такое:

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

Я написал следующий код C, чтобы прочитать файл и создать структуру, содержащую ребра, в которых идентификатор вершины должен бытьсохранено.

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);

    }
   }

Answer 1

Вам необходимо иметь наивную реализацию карты (отображающую строки в целые числа) , как предложено jabberwocky .

• Определить структурукак показано ниже для хранения строк.

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

• Определите функцию, которая будет вставлять строку в hashmap, если она не существует, и возвращать индекс строки в hashmap.

  int insertInMap(hash *map, char *entry)

• Сохранить возвращенный индекс в структуре edge.

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

Полный код:

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);
}

Вывод:

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

Примечание :: Я не добавил проверку границ для hashmap