943,845 Members | Top Members by Rank

Software Development > C++ > Depth first traversal of a graph
Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 3298
  • C++ RSS
Permalink
Nov 15th, 2008
0

Depth first traversal of a graph

Expand Post »
I am having a problem writing the last part of my code for this program.
There is a DFS function that I need to write that is included in the header file of the graph.h my program.

Here is the sample of code that my instructor gave me.
c++ Syntax (Toggle Plain Text)
  1. template<class VertexType>
  2. void DepthFirstSearch(GraphType<VertexType> graph,
  3. VertexType startVertex, VertexType endVertex)
  4. // Assumes VertexType is a type for which the “==“ and "<<"
  5. // operators are defined
  6. {
  7. using namespace std;
  8. StackType<VertexType> stack;
  9. QueType<VertexType> vertexQ;
  10. bool found = false;
  11. VertexType vertex;
  12. VertexType item;
  13. graph.ClearMarks();
  14. stack.Push(startVertex);
  15. do
  16. {
  17. stack.Pop(vertex);
  18. if (vertex == endVertex)
  19. {
  20. cout << vertex);
  21. found = true;
  22. }
  23. else
  24. {
  25. if (!graph.IsMarked(vertex))
  26. {
  27. graph.MarkVertex(vertex);
  28. cout << vertex;
  29. graph.GetToVertices(vertex, vertexQ);
  30. while (!vertexQ.IsEmpty())
  31. {
  32. vertexQ.Dequeue(item);
  33. if (!graph.IsMarked(item))
  34. stack.Push(item);
  35. }
  36. }
  37. }
  38. } while (!stack.IsEmpty() && !found);
  39. if (!found)
  40. cout << "Path not found." << endl;
  41. }
But when I try to write it I keep getting errors when it compiles.

This is his email to us the students on the DFS function.

DepthFirstSearch() tasks
- DFS requires one stack (static), one queue (static), and one queue (dynamic) to hold the path. Instead of printing out each vertex on the path, DFS queues them by name in the dynamic queue. When DFS ends, it must return the address of the dynamic queue to main() so that main() can complete its tasks. Otherwise, the DFS algorithm follows that presented in the book/notes.

This function is in the graph.cpp file.
I have attached all the files that are used in this program.
What an I doing wrong on this function?
Attached Files
File Type: cpp graph.cpp (3.2 KB, 145 views)
File Type: h graph.h (2.5 KB, 101 views)
File Type: cpp graphmain.cpp (2.0 KB, 77 views)
File Type: cpp queue.cpp (1.7 KB, 60 views)
File Type: h queue.h (1.1 KB, 48 views)
File Type: cpp stack.cpp (1,017 Bytes, 51 views)
File Type: h stack.h (971 Bytes, 53 views)
Reputation Points: 10
Solved Threads: 0
Light Poster
JustLearning is offline Offline
31 posts
since Sep 2008
Permalink
Nov 16th, 2008
0

Re: Depth first traversal of a graph

Narrow the problem down a bit and you'll recieve more help.
Reputation Points: 69
Solved Threads: 28
Posting Whiz
Clockowl is offline Offline
376 posts
since May 2008
Permalink
Nov 16th, 2008
0

Re: Depth first traversal of a graph

I don't understand what I am doing wrong in the DFS function. Since the DFS function is is declared in the graph.h file and it is part of the class in the definition, why can't I just call the function in the implementation of the DFS function?
Example: if(!IsMarked(vertex)) Why can't I do this? I have also attached my graph.cpp file. What do I need to do?
Reputation Points: 10
Solved Threads: 0
Light Poster
JustLearning is offline Offline
31 posts
since Sep 2008
Permalink
Nov 16th, 2008
0

Re: Depth first traversal of a graph

you need to have the concept of 'object oriented programing' . A behavior(function) is belong to a object, it can not exist seprately. just like a hand can not do anything if it is not a part of a body....
Thinking in this way you 'll get the idea.
if you still want to use it in traditional way, you can not declare the function in a class.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
james_zheng is offline Offline
15 posts
since Nov 2008
Permalink
Nov 16th, 2008
0

Re: Depth first traversal of a graph

Click to Expand / Collapse  Quote originally posted by james_zheng ...
you need to have the concept of 'object oriented programing' . A behavior(function) is belong to a object, it can not exist seprately. just like a hand can not do anything if it is not a part of a body....
Thinking in this way you 'll get the idea.
if you still want to use it in traditional way, you can not declare the function in a class.
Not quite.

You can have behavior functions via the 2nd and 3rd levels of polymorphism also.

The 3 (or maybe '4') levels of Polymorphism that I know of are-

1.) Virtual
2.) Static
3.) Callback
[4.) Delegation]

- the 4th is questionable since I've only recently heard about it and it seems to be an implementation in only a select few languages @_@.

You can have a Callback method that uses polymorphism via calling some function that meets the required signature (return, parameters, and class/nonclass info, and any other info regarding if the method is meant for const and non-const objects or just non-const objects... possibly even calling convention... possibly even the restriction of the scope of the function (though I don't think I've encountered that issue), etc). Of course the method may not have the same name as another but it will have enough similar traits to be invoked as a generalized type at run-time.

There's also Static polymorphism. This is typical with template-types where method and member lookup for an object is resolved at compile time. I'm still a bit fuzzy on this topic, but from what I understand you can use any class as a template argument for a class so long as it meets the minimum requirements of operations used on the template. For example, if the generalized-type is constructed anywhere as a temporary reference for the execution of a method, the class argument that is standing in place of the templated type must have its default constructor defined... etc.

Delegation is a topic I can't explain >_<. You'd have to look it up, and potentially experiment with it to understand it @_@.

So in a nutshell you can have multiple objects with the same behavior functions without using the virtual mechanism, but instead either the static mechanism (which is popular in C++), or the traditional callback mechanism (which was the solution for C-based polymorphism).


@JustLearning

To save us some document-sifting, can you be more elaborate as to what type of error you're getting? What does it say when you try to compile?
Reputation Points: 392
Solved Threads: 108
Posting Shark
Alex Edwards is offline Offline
971 posts
since Jun 2008
Permalink
Nov 17th, 2008
0

Re: Depth first traversal of a graph

Maybe you didnt understand what i mean,
A behavior(function) is belong to a object, it can not exist seprately.
In the situation of this problem, it is definitely correct.

1.) Virtual
2.) Static
3.) Callback
4.) Delegation
the Polymorphism features you mentioned above are also defined in 'object' scope or 'class' scope(e.g.static).
1) virtual function , even if it is a virtual method, its behavior can be overridden within an inheriting class by a function with the same signature. this function must have specific behavior in runtime, at that time , it must belong to a specific object .
2) Static. in this case, a behavior is belong to the whole class , and every object of this class shares this behavior. Although it is not belong to a single object , it BELONG TO a class. it can not exist separately ,either.
3) Callback. Strictly speaking, i dont think callback belongs to OOP, any executable code that is passed as an argument to other code can be a type of callback.
4) Delegation. in c# programing, you can easily find this feature . it seems like a pointer of a function in c/c++. And also, i don't think it contains any OOP features.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
james_zheng is offline Offline
15 posts
since Nov 2008
Permalink
Nov 17th, 2008
0

Re: Depth first traversal of a graph

Click to Expand / Collapse  Quote originally posted by james_zheng ...
Maybe you didnt understand what i mean,
A behavior(function) is belong to a object, it can not exist seprately.
In the situation of this problem, it is definitely correct.

1.) Virtual
2.) Static
3.) Callback
4.) Delegation
the Polymorphism features you mentioned above are also defined in 'object' scope or 'class' scope(e.g.static).
1) virtual function , even if it is a virtual method, its behavior can be overridden within an inheriting class by a function with the same signature. this function must have specific behavior in runtime, at that time , it must belong to a specific object .
2) Static. in this case, a behavior is belong to the whole class , and every object of this class shares this behavior. Although it is not belong to a single object , it BELONG TO a class. it can not exist separately ,either.
3) Callback. Strictly speaking, i dont think callback belongs to OOP, any executable code that is passed as an argument to other code can be a type of callback.
4) Delegation. in c# programing, you can easily find this feature . it seems like a pointer of a function in c/c++. And also, i don't think it contains any OOP features.
Static isn't defined strictly for classes. Static implies that something is resolved at compile-time (or in Java, something is used for the first time (Static Fields)). If this is hard to believe, refer to the use of static in C, a non object-oriented language where static referred to (in short) 'as part of this file' and not a shared member of instances of an object of the class-type.

It is possible to use different functions (different behavior) from different files (non-class types, but the concept is similar) using a combination of Static and Callback polymorphism with functions (behavior in other files) that can both resolve the type at compile time and use the type abstractly in a way that the behavior can still differ among types without the use of classes.

I'd have to do some research on statically calling storage-type members of a namespace via the static mechanism. I wonder if that is also possible (in theory it should be)?

Oh and here's a question for you. Why do you think a Callback is not a valid form of OOP? The virtual mechanism is very similar, except you are relying on a virtual table of a class instead of a reference to a function with the same signature.

I'm honestly not convinced that Polymorphism belongs only to OOP.
Reputation Points: 392
Solved Threads: 108
Posting Shark
Alex Edwards is offline Offline
971 posts
since Jun 2008
Permalink
Nov 17th, 2008
0

Re: Depth first traversal of a graph

I found out what I was doing wrong I put the function heading like this
c++ Syntax (Toggle Plain Text)
  1. Queue* DepthFirstSearch(string startVertex, string endVertex);

instead of like this
c++ Syntax (Toggle Plain Text)
  1. Queue* [COLOR="Red"]Graph::[/COLOR]DepthFirstSearch(string startVertex, string endVertex);
Reputation Points: 10
Solved Threads: 0
Light Poster
JustLearning is offline Offline
31 posts
since Sep 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: airplane seating assignmnet {homework arrays}
Next Thread in C++ Forum Timeline: C++ system (cmd) and variable





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC