c - 删除从文件中读取的重复边缘

Question

我编写了一个从不同文件(node1 和 node2 ...它们是源节点和目标节点)读取边的代码。

但是，这些文件可能具有重复的边(正在读取相同的节点 1 和节点 2)。 如何删除这些重复的边缘？谁能提供一个C代码吗？ 至少有一个示例 c 代码？

P.S:我想记录实际的边数(意味着没有重复的边)。

Answer 1

假设有边作为两个节点 N1 和 N2 之间的连接，并且这些边是有向的(因此 N1 -> N2 与 N2 -> N1 不同)，那么问题就变成了对边进行排序，并取独特的值(value)观。根据您使用的平台，您可能内置了实用程序来执行此操作。例如，如果您在Linux/Mac平台上运行，您可能会执行以下操作:

1. 读入所有边缘，并且不关心重复项(暂时)
2. 将边缘(N1 空间 N2)作为长列表打印到文本文件(包括重复项)
3. 对文件进行排序
4. 将排序结果发送给uniq命令；结果将是唯一边缘的(排序)列表。
5. 计算 uniq 输出的行数 - 即不同边的数量。

示例:

>cat inputFile.txt
2 3
3 4
4 5
3 4
4 3
1 2
2 3

>sort inputFile.txt | uniq
1 2
2 3
3 4
4 3
4 5

>>sort inputFile.txt | uniq -c
   1     1 2
   2     2 3
   2     3 4
   1     4 3
   1     4 5

这显示了每条边被看到的次数

>>sort inputFile.txt | uniq | wc -l
5

这显示了总共有多少条边。

如果您的平台上没有这样的实用程序，您可以编写自己的 C 代码来执行此操作；但这比使用已经存在的东西需要更多的工作。

更新这里有一些低效代码，可以满足您的要求。效率低下，因为 isnew 函数检查所有先前的元素(顺序 N^2 操作)。这对于小集合来说还可以，但对于大集合来说就变得非常糟糕 - 但你明白了。如果对数组进行排序，可以提高效率，但我无法为您编写该代码。您可以做很多事情来改进此代码 - 错误检查等。这只是“总体方向的插入”，您应该能够从这里获取它(或雇用某人为您编写代码......)

#include <stdio.h>
#define NE 20

int isnew(int* e, int nd[NE][2], int n) {
// return 0 if same edge is found in nd
  int ii;
  for(ii = 0; ii < n; ii++) {
    if(e[0] == nd[ii][0] && e[1] == nd[ii][1]) return 0;
  }
  return 1;
}

int main(void) {
  FILE *fp;
  char buf[NE]; // to read in lines
  int ii, uc, rowCount;
  int edges[NE][2]; // make it big enough
  int nodup[NE][2]; // only unique edges
  fp = fopen("inputFile.txt", "r");
  if(fp == NULL) {
    printf("file not found\n");
    return -1;
  }

  ii = 0;
  while(fgets(buf, sizeof(buf), fp) && ii < NE) {
    if(sscanf(buf, "%d %d", &edges[ii][0], &edges[ii][1]) != 2) break;
    ii++;

  }
  fclose(fp);
  rowCount = ii;
  printf("all elements read in: \n");
  for(ii = 0; ii < rowCount; ii++) {
    printf("%d %d\n", edges[ii][0], edges[ii][1]);
  }
  // now only unique ones
  nodup[0][0] = edges[0][0];
  nodup[0][1] = edges[0][1];
  uc = 1;
  for(ii = 1; ii < rowCount; ii++) {
    if(isnew(edges[ii], nodup, uc)) {
      nodup[uc][0] = edges[ii][0];
      nodup[uc][1] = edges[ii][1];
      uc++;
    }
  }
  printf("\nfound %d unique entries; they are:\n", uc);
  for(ii = 0; ii < uc; ii++) {
    printf("%d %d\n", nodup[ii][0], nodup[ii][1]);
  }
}

输出(使用我之前使用的相同文件):

all elements read in: 
2 3
3 4
4 5
3 4
4 3
1 2
2 3

found 5 unique entries; they are:
2 3
3 4
4 5
4 3
1 2