How do I fix BST based graph that seems to be overwriting the same vertex?

Question

I hope this isn't a duplicate but I couldn't find any similar posts.

The build on this may seem overly convoluted but I am trying to learn binary sorting trees and apply it to my graph knowledge. I understand it may be easier to use an adjacency list.

Currently the build utilizes two structs and a class, one struct for Edges, one for Vectors, and the "Graph" class functions as a binary search tree.

    // Vertex node stores name and neighbors
    struct Vertex {
        string name;
        vector<Edge *> *neighbors;
    };


    class Graph {
        // Functions like BST and stores a Vertex object with each node
        int value;
        Graph *left, *right;
        struct Vertex *node;

The functions that interact with this portion of the program are my default and parameterized constructors:

    Graph::Graph() : value(0), left(NULL), right(NULL), node(){};

    Graph::Graph(int data, Vertex* node) {
        value = data;
        left = right = NULL;
        Vertex* newNode = new Vertex;
        newNode = node;
    };

and my addVertex function:

    Graph* Graph::addVertex(Graph* root, string name, int data){
        if (!root) {
            Vertex* newVertex = new Vertex;
            newVertex->name = name;
            newVertex->neighbors = new vector<Edge *>();
            node = newVertex;
            return new Graph(data, node);
        }
        if (value > root->value){
            root->right = addVertex(root->right, name, data);
        }
        else if (value < root->value){
            root->left = addVertex(root->left, name, data);
        }
        return root;
    };

I have tried removing each one of the constructors separately, tried creating a new Vertex within the constructors. Changing the variable order within the class and structs. It seems like the program is only creating over vertex and is overwriting the vertex repeatedly.

What I expect to happen is the program would create a new Vertex and store its name for later comparison, but my output is this:

    Vertex name: g Graph Node Value: 3
    vertex name: g Neighbors:
    Vertex name: g Graph Node Value: 2
    vertex name: g Neighbors:
    Vertex name: g Graph Node Value: 1
    vertex name: g Neighbors:

So I am getting the value that is assigned to the node in the BST but I am not getting the name stored in the Vertex.

Answer 1

In your graph constructor you have:

    Vertex* newNode = new Vertex;
    newNode = node;

The constructs a new vertex and a pointer to it in a local variable, newNode.

Then the local variable is assigned to point to a different vertex, the one passed in as a parameter

Then it exits. The new vertex that was constructed remains, but nothing remains that can reference it. This is a memory leak.

There are a number of other problems with your code ( the left and right pointers should be in the Vertex class, not the Graph class ... ) which I will not go into here.

Here is the code for a complete application that does what you need:

#include <string>
#include <sstream>
#include <iostream>
#include <vector>

struct Edge
{
};

// Vertex node stores name, value and neighbors
struct Vertex
{
    std::string name;
    int value;
    std::vector<Edge *> *neighbors;
    Vertex *left, *right;

    Vertex(const std::string &n,
           int v)
        : name(n), value(v),
          left(0), right(0)
    {
    }
    std::string text() const
    {
        std::stringstream ss;
        ss << name << " " << value << "\n";
        return ss.str();
    }
};

// Functions like BST and stores a Vertex object with each node
class Graph
{
    struct Vertex *root;

public:
    /// @brief Construct empty graph
    Graph()
        : root(0)
    {
    }
    /// @brief Construct graph with root vertex
    /// @param name root vertex name
    /// @param value root vertex value

    cGraph(
        const std::string &name,
        int value)
    {
        root = new Vertex(name, value);
    }

    /// @brief Add root vertex to empty graph
    /// @param name
    /// @param value

    void setRoot(
        const std::string &name,
        int value)
    {
        if (root)
            throw std::runtime_error(
                "root already set");
        root = new Vertex(name, value);
    }

    /// @brief add vertex to graph
    /// @param name
    /// @param value
    /// @param cur  // application code must omit this parameter
    
    void addVertex(
        const std::string &name,
        int value,
        Vertex *cur = 0)
    {
        if (!cur) {
            if (!root)
                setRoot("defaultRoot", 0);
            cur = root;
        }

        if (value < cur->value)
        {
            if (!cur->left)
            {
                cur->left = new Vertex(name, value);
                return;
            }
            else
                addVertex(name, value, cur->left);
        }
        else
        {
            if (!cur->right)
            {
                cur->right = new Vertex(name, value);
                return;
            }
            else
                addVertex(name, value, cur->right);
        }
    }

    // display graph contents
    void text()
    {
        text(root);
    }

private:
    void text(Vertex *v)
    {
        if (!v)
            return;
        text(v->left);
        std::cout << v->text();
        text(v->right);
    }
};

main()
{
    Graph g;

    g.setRoot("A", 10);

    g.addVertex("B", 20);
    g.addVertex("C", 5);

    g.text();

    return 0;
}

which outputs

C 5
A 10
B 20