I don’t see what I could possibly be doing wrong to keep getting this valgrind error. I’m not leaking any memory..

In my project, I have to implement a graph, a fundamental graph algorithm, and have a working maps application that can find paths in real data. I cannot use new in this project, nor edit the signatures of the public member functions, or add public member variables of the graph class. I may add private member variables and functions. I may not modify the signatures of other functions. However, I may add additional helper functions. I may only modify graph.h and application.cpp.

My graph class represents graphs with all of the following properties:

• Directed – edges have a start and an end.

• Simple – for any two nodes A and B, there is at most one directed edge from A to B.

  • The directed edge from B to A is a separate edge that can also exist. ● Weighted – each edge has data associated with it.

The goal is to represent a map using a graph. Vertices represent places people can exist, and edges between vertices show how people can move between these places. A node in OSM (OpenStreetMaps) is a single point in the real world, and consists of 3 values that we care about:

• ID (long long, unique identifier)

• Latitude (double)

• Longitude (double)

OSM’s data tells me that the starting and ending nodes happen to be part of other ways. This is how I connect footpaths to other footpaths, and build up the entire graph. The other kind of way I’m interested in is a building. OSM defines a building by the nodes in its perimeter. For example, a college campus could be made up of 13 nodes, despite seeming rectangular-ish. To simplify my navigation problem, I have to convert each building to a single node by averaging the coordinates of the nodes in its perimeter. Because these nodes aren’t connected to the graph by footways, I have tol add new edges from building centers to nearby footway nodes.

• A FootwayInfo contains a vector<long long> of nodes that make up the footway. I converted these into edges between consecutive pairs of nodes.

• A BuildingInfo contains a Coordinates. I added a vertex for the building to the graph, then created an edge from the building’s node to any other node within 0.041 miles that is on a footway.

Rather than shortest paths from A to B, my application will take two starting points, and have them “meet in the middle”. I have to assume one person starts at building A, and another person starts at building B. I:

1. Found the building closest to the midpoint of the line between buildings A and B; called this building M.

2. Ran Dijkstra’s algorithm to find the shortest path from building A to building M.

3. Ran Dijkstra’s algorithm to find the shortest path from building B to building M.

I had to use a slightly altered version of Dijkstra’s: the paths should not include buildings, except for the buildings at the start and end of the path. More generally, I want to be able to specify a set of nodes that the shortest paths should not go through.

•  The constant double INF = numeric_limits<double>::max() at the top of my file is suppose to be used for “infinity” in my code.

• The returned vector should be the vertices on the path, in order from start to target.

  • If the target is unreachable from start, I return an empty path.

  • If start and target are the same, I return a vector containing just start.

• I (thought I) processed vertices that are in ignoreNodes, unless the vertex is target.

To implement Dijkstra’s, I had to use a priority queue.

I can only modify graph.h and application.cpp.

My graph.h:

#pragma once

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>

using namespace std;

/// @brief Simple directed graph using an adjacency list.
/// @tparam VertexT vertex type
/// @tparam WeightT edge weight type
template <typename VertexT, typename WeightT>
class graph {
   private:
    // TODO_STUDENT
    /*We are dealing with an adjacency list representation. The elements
      are not required to be sorted based on keys*/
    unordered_map<VertexT, unordered_map<VertexT, WeightT> > adjacencyList;

   public:
    /// Default constructor
    graph() {
        // No initialization needed for the adjacency list
    }

    /// @brief Add the vertex `v` to the graph, must run in at most O(log |V|).
    /// @param v
    /// @return true if successfully added; false if it existed already
    bool addVertex(VertexT v) {
        // TODO_STUDENT
        /*1a. Attempts to insert a new element into 'adjacencyList' unordered_map.
            If successful, returns pair containing an iterator to the newly inserted element
            AND a boolean indication if the insertion took place or not
          1b. '.second' gets the second element of the pair returned by emplace().
            It gets the true or false indicating whether the insertion took place*/
        return adjacencyList.emplace(v, unordered_map<VertexT, WeightT>()).second;
    }

    /// @brief Add or overwrite directed edge in the graph, must run in at most O(log |V|).
    /// @param from starting vertex
    /// @param to ending vertex
    /// @param weight edge weight / label
    /// @return true if successfully added or overwritten;
    ///         false if either vertices isn't in graph
    bool addEdge(VertexT from, VertexT to, WeightT weight) {
        // TODO_STUDENT
        /*Checks if both the starting vertex (from) and the ending vertex (to) exist
          in the adjacencyList for both from and to.*/
        if (adjacencyList.find(from) != adjacencyList.end() && adjacencyList.find(to) 
            != adjacencyList.end()) {
                adjacencyList[from][to] = weight;
                return true;
        }    
        return false;
    }

    /// @brief Maybe get the weight associated with a given edge, must run in at most O(log |V|).
    /// @param from starting vertex
    /// @param to ending vertex
    /// @param weight output parameter
    /// @return true if the edge exists, and `weight` is set;
    ///         false if the edge does not exist
    bool getWeight(VertexT from, VertexT to, WeightT& weight) const {
        // TODO_STUDENT
        /*Searches the adjacencyList from the entry related to the starting vertex (from).
          Returns an iterator (fromIt) pointing to that entry if it exists, or 
          adjacencyList.end() if the vertex is not found */
        auto fromIt = adjacencyList.find(from);
        if (fromIt != adjacencyList.end()) {
            auto toIt = fromIt->second.find(to);
            if (toIt != fromIt->second.end()) {
                weight = toIt->second;
                return true;
            }
        }

        return false;
    }

    /// @brief Get the out-neighbors of `v`. Must run in at most O(|V|).
    /// @param v
    /// @return vertices that v has an edge to
    set<VertexT> neighbors(VertexT v) const {
        set<VertexT> S; //A set that will store the out-neighbors of the vertex v
        
        // TODO_STUDENT
        /*Searches for the vertex v in the adjacencyList list, returning an iterator
          pointing to the entry corresponding to the vertex*/
        auto it = adjacencyList.find(v); 

        /*If the vertex is found, it has out-neighbors*/
        if (it != adjacencyList.end()) {
            /*Loops over each entry in the 'second' part of the entry corresponding to
              the vertex in the adjacency list*/
            for (const auto& neighbor : it->second) {
                /*For each out-neighor found, the neighbor vertex is inserted into S*/
                S.insert(neighbor.first);
            }
        }
        return S; //Returns the out-neighbors of the vertex
    }

    /// @brief Return a vector containing all vertices in the graph
    vector<VertexT> getVertices() const {
        // TODO_STUDENT
        vector<VertexT> vertices; //Vector that will store all vertices present in the graph
        for (const auto& pair : adjacencyList) {
            vertices.push_back(pair.first);
        }
        return vertices;
    }

    /// @brief Get the number of vertices in the graph. Runs in O(1).
    size_t NumVertices() const {
        // TODO_STUDENT
        return adjacencyList.size();
    }

    /// @brief Get the number of directed edges in the graph. Runs in at most O(|V|).
    size_t NumEdges() const {
        // TODO_STUDENT
        size_t numEdges = 0;
        for (const auto& pair : adjacencyList) {
            numEdges += pair.second.size(); // Increment by the number of outgoing edges for each vertex
        }
        
        return numEdges;
    }
};

My application.cpp:

#pragma once

#include <map>
#include <set>
#include <vector>

#include "graph.h"
#include "osm.h"

/// @brief Build a `graph` from the given map data. Building centers that are
///        "close to" footway nodes are manually linked.
/// @param Nodes OSM nodes in the graph
/// @param Footways OSM footways, to be converted to edges
/// @param Buildings OSM building centers, to be linked to nodes on footways
/// @return constructed graph; edge weights are distances
graph<long long, double> buildGraph(
    const map<long long, Coordinates>& Nodes,
    const vector<FootwayInfo>& Footways,
    const vector<BuildingInfo>& Buildings);

/// @brief Run Dijkstra's algorithm on G to find the shortest path from `start` to
///        `target` that does not include any ignored nodes.
/// @param G graph
/// @param start starting node ID
/// @param target ending node ID
/// @param ignoreNodes node IDs to skip; may contain `start` / `target`
/// @return node IDs on shortest path from `start` to `target`
vector<long long> dijkstra(
    const graph<long long, double>& G,
    long long start,
    long long target,
    const set<long long>& ignoreNodes);

/// Command loop to request input
void application(
    const vector<BuildingInfo>& Buildings,
    const graph<long long, double>& G);

My osm.h:

/*osm.h*/

//
// Adam T Koehler, PhD
// University of Illinois Chicago
// CS 251, Fall 2022
//
// Project Original Variartion By:
// Joe Hummel, PhD
// University of Illinois at Chicago
//

#pragma once

#include <iostream>
#include <map>
#include <string>
#include <vector>

#include "tinyxml2.h"

using namespace std;
using namespace tinyxml2;

//
// Coordinates:
//
// the triple (ID, lat, lon)
//
struct Coordinates {
    long long ID;
    double Lat;
    double Lon;
    bool OnFootway;

    Coordinates() {
        ID = 0;
        Lat = 0.0;
        Lon = 0.0;
        OnFootway = false;
    }

    Coordinates(long long id, double lat, double lon) {
        ID = id;
        Lat = lat;
        Lon = lon;
        OnFootway = false;
    }
};

//
// FootwayInfo
//
// Stores info about one footway in the map.  The ID uniquely identifies
// the footway.  The vector defines points (Nodes) along the footway; the
// vector always contains at least two points.
//
// Example: think of a footway as a sidewalk, with points n1, n2, ...,
// nx, ny.  n1 and ny denote the endpoints of the sidewalk, and the points
// n2, ..., nx are intermediate points along the sidewalk.
//
struct FootwayInfo {
    long long ID;
    vector<long long> Nodes;

    FootwayInfo() {
        ID = 0;
    }

    FootwayInfo(long long id) {
        ID = id;
    }
};

//
// BuildingInfo
//
// Defines a campus building with a fullname, an abbreviation (e.g. SEO),
// and the coordinates of the building (id, lat, lon).
//
struct BuildingInfo {
    string Fullname;
    string Abbrev;
    Coordinates Coords;

    BuildingInfo() {
        Fullname = "";
        Abbrev = "";
        Coords = Coordinates();
    }

    BuildingInfo(string fullname, string abbrev, long long id, double lat, double lon) {
        Fullname = fullname;
        Abbrev = abbrev;
        Coords = Coordinates(id, lat, lon);
    }
};

//
// Functions:
//
bool LoadOpenStreetMap(string filename, XMLDocument& xmldoc);
int ReadMapNodes(XMLDocument& xmldoc, map<long long, Coordinates>& Nodes);
int ReadFootways(XMLDocument& xmldoc,
                 map<long long, Coordinates>& Nodes,
                 vector<FootwayInfo>& Footways);
int ReadUniversityBuildings(XMLDocument& xmldoc,
                            const map<long long, Coordinates>& Nodes,
                            vector<BuildingInfo>& Buildings);

My main.cpp:

#include <iostream>
#include <iomanip>  /*setprecision*/
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <cassert>

#include "tinyxml2.h"
#include "graph.h"
#include "osm.h"
#include "application.h"

using namespace std;
using namespace tinyxml2;


int main() {
  // maps a Node ID to it's coordinates (lat, lon)
  map<long long, Coordinates>  Nodes;
  // info about each footway, in no particular order
  vector<FootwayInfo>          Footways;
  // info about each building, in no particular order
  vector<BuildingInfo>         Buildings;
  XMLDocument                  xmldoc;

  cout << "** Navigating UIC open street map **" << endl;
  // cout << endl;
  cout << std::setprecision(8);

  string default_filename = "uic-2024.osm";
  string filename;

  // cout << "Enter map filename> ";
  // getline(cin, filename);

  if (filename == "") {
    filename = default_filename;
  }

  // Load XML-based map file
  if (!LoadOpenStreetMap(filename, xmldoc)) {
    cout << "**Error: unable to load open street map." << endl;
    cout << endl;
    return 0;
  }

  // Read the nodes, which are the various known positions on the map:
  int nodeCount = ReadMapNodes(xmldoc, Nodes);

  // Read the footways, which are the walking paths:
  int footwayCount = ReadFootways(xmldoc, Nodes, Footways);

  // Read the university buildings:
  int buildingCount = ReadUniversityBuildings(xmldoc, Nodes, Buildings);

  // Stats
  assert(nodeCount == (int)Nodes.size());
  assert(footwayCount == (int)Footways.size());
  assert(buildingCount == (int)Buildings.size());

  // cout << endl;
  cout << "# of nodes: " << Nodes.size() << endl;
  cout << "# of footways: " << Footways.size() << endl;
  cout << "# of buildings: " << Buildings.size() << endl;

  // Build graph from input data
  graph<long long, double> G = buildGraph(Nodes, Footways, Buildings);

  // More stats
  cout << "# of vertices: " << G.NumVertices() << endl;
  cout << "# of edges: " << G.NumEdges() << endl;
  application(Buildings, G);

  cout << "** Done **" << endl;
  return 0;
}

My expected output (which I have):

Person 1’s point:

UIC Academic and Residential Complex (ARC)

664275388

(41.87478, -87.650866)

Person 2’s point:

Science & Engineering Offices (SEO)

151960667

(41.870851, -87.650375)

Destination Building:

Stevenson Hall (SH)

151676521

(41.872875, -87.650468)

Person 1’s distance to dest: 0.13975891 miles

Path: 664275388->2412572929->1645208827->464345369->463814052->464748194->462010750->462010751->9862302685->9870872111->151676521

Person 2’s distance to dest: 0.16077909 miles

Path: 151960667->1647971930->462010746->462010758->11257988853->464345492->462010740->9870872102->462010759->151676521