logo CodeStepByStep logo

containsBidiPath

Language/Type: C++ Graph collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named containsBidiPath that accepts two parameters: a reference to a BasicGraph, and a reference to a Vector of strings representing vertex names for a path; and returns true if that path is can be traveled in the graph in both directions, or false if not. In other words, you would return true if every vertex in the path is found in the graph, and where there is an edge between each neighboring pair of vertexes in the path along the way from start to end, and also back from the end to the start.

For example, if your function were passed given the graph below and the path {A, B, F, G}, you would return true because all of those vertexes are part of the graph and you can travel that path from A to G and back from G to A. If you were passed the same graph and the path {A, E, F, I}, you would return false because that path does not go back from I to A. If you were passed the path {A, X, Z, B}, you would return false because X and Z are not in the graph. You may assume that the graph's state is valid, and that the path and its elements are not NULL.

 A <---> B <---> C
 |       ^       |
 |       |       |
 |       |       |
 V       V       V
 E ----> F <---> G
 |       |
 |       |
 |       |
 V       V
 H <---- I

Constraints: You may assume that the graph's state is valid, and that contains no self-edges (e.g. from V1 to V1). You may define private helper functions if so desired, and you may construct auxiliary collections as needed to solve this problem. You should not modify the contents of the graph such as by adding or removing vertexes or edges from the graph, though you may modify the state variables inside individual vertexes/edges such as visited, cost, etc.

Type your C++ solution code here:


This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.