-1

I am trying to find a path (any path) between points using a directed weighted graph. My implementation is below:

I am not very used to the object-oriented style of c++ so my class representation might be wrong.

So I have two questions:

  1. How can I get the name of the visited vertex name as the output?

  2. How can I calculate the overall distance (summation of the corresponding weights)?

goku
  • 167
  • 10
  • 1
    Currently every call to `addVertex` replaces the singular vertex name that your graph stores. This makes no sense. Just store a `std::vector` for your vertex names. Then you can just index into it with the visited vertices, which presumably are stored in `path` when your traversal meets its end condition. On the subject of vectors, you should also use that for your visited list instead of manual allocation which is not exception-safe and you're also leaking memory right now. – paddy May 05 '22 at 09:17
  • 1
    As you travel through the graph, use a stack to store the information you need to show the users when finished. When going from one node to another push the information, when backtracking pop the information. Once done you have all the information you need in the stack (albeit in reverse order). – Some programmer dude May 05 '22 at 09:18
  • I understand the necessity of using stacks but implementing this is probably beyond my c++ level at the moment @Someprogrammerdude – goku May 05 '22 at 09:20
  • Any easier to implement idea? – goku May 05 '22 at 09:20
  • 1
    You know [`std::stack`](https://en.cppreference.com/w/cpp/container/stack) already exists, right? You don't need to write it yourself, just call `push` and `pop` ... – Useless May 05 '22 at 09:22
  • No, I did not know that. I am used to using C and we write our own push and pop @Useless – goku May 05 '22 at 09:25
  • 1
    OK, then this is the point at which we tell you that learning C++ based on some C knowledge and asking questions when you get stuck is going to be a nightmare, and you should [get a good book](https://stackoverflow.com/q/388242/212858). – Useless May 05 '22 at 09:27
  • 1
    Other useful references are the [C++ Core Guideline](https://isocpp.github.io/CppCoreGuidelines/) and cppreference which I already linked above. Start with a book if possible though. – Useless May 05 '22 at 09:30

1 Answers1

1

How can I get the name of the visited vertex name as the output?

Well, you need to store the name of each vertex.

Currently you store a single name_vert which is the name of the last vertex added - this isn't useful.

How can I calculate the overall distance (summation of the corresponding weights)?

You also need to store the weights somewhere. You pass a weight argument to addEdge and then ignore it, so how could you possibly get it back later?

I am not very used to the object-oriented style of c++ so my class representation might be wrong.

The general process is to think about what kind of entities you're dealing with, what kind of state and behaviour they need, and then to decide how to model them. This is exactly the same as object-oriented design in any other language, and was good practice in C even without the syntactic sugar and other improvements.

What I'm saying is that your problem is nothing to do with OO, it's to do with the fact that you haven't thought about what data you need to store and how to structure that in the first place.

  • What is a Graph? It's a collection of edges and vertices
  • What is an Edge? It's an ordered pair of vertices and a weight
  • What is a Vertex? It's apparently a name and an integer ID

So at least you need to store those data somehow. They don't necessarily need to be types: you could write a class Vertex, or you could just keep a std::vector<std::string> vertex_names in your graph to provide an implicit mapping between index and name. But you do need to think clearly about what data you're storing and then decide how to structure and represent it.

Useless
  • 64,155
  • 6
  • 88
  • 132
  • Thank you for the comprehensive explanation. I thought I am storing the name of each vertex by passing the names. And I should probably store weights in an array or stack as commented above – goku May 05 '22 at 09:29
  • 1
    Well, you have a single `string name_vert`, and every time you assign a new value to that, the old one is overwritten. Just use `std::vector` for your arrays when it's convenient to be able to change or set their size at runtime, like here. `vector` is usually preferred to `list`, and definitely to raw C-style arrays except in very specific circumstances – Useless May 05 '22 at 09:32
  • Can you check my edit and tell me if it makes sense? Defining globals might be a bad habit – goku May 05 '22 at 09:56
  • Using globals is definitely a bad habit - what if your program ends up containing two Graph objects? If the vertex names and weights should not be shared, they ought to be properties of your `Graph` class. This isn't a [code review](https://codereview.stackexchange.com/) site anyway, so I'm not going to either rewrite your code or keep offering live feedback. – Useless May 05 '22 at 12:07
  • I did not ask you to rewrite my code, no need to be agressive – goku May 05 '22 at 12:47