Creating an Adjacency Matrix with Vectors

66 Views Asked by At

I am having trouble coming up with an algorithm to create an adjacency matrix. Right now I feel like I'm going down a really convoluted path of doing this and I was wondering if there was a better alternative out there? My current algorithm is meant to work as follows: I have an object called map which is built of another object called territory, each of which have various adjacent territories. I have saved the full list of territory names as a string vector in the map object. In the territory object, I have stored a full list of adjacent territories as well in the form of a string vector. In the map object, I also have a vector of Territories holding all the territory objects. In my map object I have a 2D int vector acting as the adjacency matrix. The function is suppose to:

  • parse through every every index of the string and Territory vectors
  • record the current index i as the row number
  • on every index loop through the adjacent territory array
  • return the index where the corresponding name of the adjacent territory appears in the string vector (comparing the adjacent territories of every territory to the territory string vector to find where they are in the vector). This index will be column (col)
  • then finally add an edge between both territories.

I found this to be very convoluted and I'm sure there is a better way to go about this. I tried implementing this with maps using <string, Territory>, however the map did not maintain the order at which they appear, which would cause problems when printing the adjacency matrix itself. Any help would be great, if you think that my implementation IS the way to go, some help regarding returning the index for col would be much appreciated, I am having trouble with the syntax here (no background in C++, just learning it)!

Below you can find the code I tried (the commented out part was me trying to implement it with a key-value map). The output currently is an array filled with 0s.

void Map::createAdjacencyMatrix(){
    // Resize the adjacency matrix to the size of allTerritories
    adjacencyMatrix.resize(allStringTerritories.size(), vector<int>(allStringTerritories.size(), 0));

    for(int i=0; i<allStringTerritories.size(); i++){
        Territory currTerritory = allObjTerritories[i];
        vector<string> temptAdjTerritories = currTerritory.getAdjTerritories();
        string s = currTerritory.getTerritoryName();
        int row = i;
        int col;

        //cout << s << endl;

        for(int j = 0; j<allStringTerritories; j++){
            col = distance(allStringTerritories, find(temptAdjTerritories[j],));
        }
        
    }

    /*()
    // Loop through allTerritories map
    for (const auto& pair1 : allStringTerritories) {
        //Territory currTerritory = pair1.second;
        //string currTerritoryName = currTerritory.getTerritoryName();
        string currTerritoryName = pair1;


        cout << currTerritoryName << endl;

        // Find the row index for the current territory
        int row = distance(allStringTerritories.begin(), allStringTerritories.find(currTerritoryName));

        // Loop through adjacent territories
        for (const string& adjacent : currTerritory.getAdjTerritories()) {
            // Find the column index for the adjacent territory
            int col = distance(allTerritories.begin(), allTerritories.find(adjacent));

            // Update the adjacency matrix
            adjacencyMatrix[row][col] = 1;
            adjacencyMatrix[col][row] = 1; // Assuming the graph is undirected
        }
    }
    */
    //setting the value of adjacencyMatrix to tempAdjacencyMatrix
    //adjacencyMatrix = tempAdjacencyMatrix;
}
0

There are 0 best solutions below