Создание неориентированного графа с правильными краями

Question

Здравствуйте, я создаю 100 графиков для тестирования в алгоритме Дейкстры. У меня есть проверка, чтобы убедиться, что два случайно сгенерированных номера узла для соединения не совпадают. Однако я не понимаю, как проверить, существует ли пара, чтобы между двумя узлами возникло более одного ребра. Как предотвратить появление двух ребер между двумя узлами?

void mapDataGenerator(int start, int end, int iterations,
                        int *pathCount, int *weightCount, int *timeCount)
{
int nodeCount = rand() % 8128 + 64;
edgeListTemplate edgeList(nodeCount);
//cout << "The node count is: " << nodeCount;
int n = 0;
list<vertex_v> path;
vector<weight_w> min_distance;
vector<vertex_v> previous;


while (n != nodeCount)
{

    int nodeNumb = (rand() % nodeCount); // Generates a possible node 1 
    int nodeDest = (rand() % nodeCount); // Generates a possible node 2

    //cout << "The node connection 1 is: " << nodeNumb << endl;
    //cout << "The node connection 2 is: " << nodeDest << endl;
    int node_weight = rand() % 5 + 1; // Generate random weight of node

    //cout << "The node weight is: " << node_weight << endl;

    // Create adjacency list
    if (nodeNumb != nodeDest) // if the random nodes generated are not same
    {
        edgeList[nodeNumb].push_back(node(nodeDest, node_weight));
        // For undirected graph create opposite connection back 
        edgeList[nodeDest].push_back(node(nodeNumb, node_weight));
        ++n;
    }
  }

Answer 1

Вы можете просто использовать карту / установить структуру данных, чтобы отслеживать уже имеющиеся ребра. Именно карта пары будет делать эту работу.

Код

// map declaration
map<pair<int, int>, bool> M;

if (nodeNumb != nodeDest && !M.count(make_pair(nodeNumb, nodeDest))) // if the random nodes generated are not same
{
     // Marking the pair of edges
     M[make_pair(nodeNumb, nodeDest)] = true;
     edgeList[nodeNumb].push_back(node(nodeDest, node_weight));
     // For undirected graph create opposite connection back 
     edgeList[nodeDest].push_back(node(nodeNumb, node_weight));
     ++n;
 }