Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Graph DFS implementation (stack usage)

Reply
Thread Tools

Graph DFS implementation (stack usage)

 
 
Scott Dabot
Guest
Posts: n/a
 
      11-10-2004
Im trying to print out the order in which the vertexes of a graph are
pushed on to the stack then print out the order in which they are popped
off the stack. My current approach is
void dfs(struct ADJACENCY *G_adj,int v)
{
int i,u;

G_adj->mark[v]=1;
visit(v,G_adj);
while ((u=next_adj_vertex(v,G_adj))>=0) {

if (G_adj->mark[u]==0)
{
dfs(G_adj,u);

}


}
visit(v,G_adj);
}

int visit(int v, struct ADJACENCY *G_adj)
{
printf("%c ", G_adj->vertexlabel[v]);

return v;
}

With this approach the order in which my graph should print out should
be A, B, D, E , C , F ( order in which its pushed) ... but by me adding
the visit function to the end of the dfs call , im trying to print out
the order in which its popped off ... and thus i get this:

pushed: a b d e , then popped: e d b pushed: c f popped f c popped: a

which way could i reprogram this so that it prints out pushed: a b d e c
f , popped f c e d b a ?????????
 
Reply With Quote
 
 
 
 
Craig Barkhouse
Guest
Posts: n/a
 
      11-10-2004
I don't think this NG is here to do your homework for you.


 
Reply With Quote
 
 
 
 
Michael Mair
Guest
Posts: n/a
 
      11-10-2004
Scott Dabot wrote:

> Im trying to print out the order in which the vertexes of a graph are
> pushed on to the stack then print out the order in which they are popped
> off the stack. My current approach is
> void dfs(struct ADJACENCY *G_adj,int v)
> {
> int i,u;
>
> G_adj->mark[v]=1;
> visit(v,G_adj);
> while ((u=next_adj_vertex(v,G_adj))>=0) {
>
> if (G_adj->mark[u]==0)
> {
> dfs(G_adj,u);
>
> }
>
>
> }
> visit(v,G_adj);
> }
>
> int visit(int v, struct ADJACENCY *G_adj)
> {
> printf("%c ", G_adj->vertexlabel[v]);
>
> return v;
> }


This is very nice and seems to be code that might work.

> With this approach the order in which my graph should print out should
> be A, B, D, E , C , F ( order in which its pushed) ... but by me adding
> the visit function to the end of the dfs call , im trying to print out
> the order in which its popped off ... and thus i get this:
>
> pushed: a b d e , then popped: e d b pushed: c f popped f c popped: a
>
> which way could i reprogram this so that it prints out pushed:
> a b d e c f , popped f c e d b a ?????????


Your request is offtopic around here as you are essentially asking
for an algorithm.

One way to achieve what you want is to look at what you want:
You want to print out the push order and the reverse push order.
So, the latter provides no new information. You could print
everything into a string and print the string first normal,
then in reverse.
Another, which I would prefer, is creating an index table.
Add to struct ADJACENCY an entry currindex as well as a pointer
indextable. Provide a function to reset currindex to zero and realloc()
indextable to a size s.t. it can contain all vertex indices.
Then, you start your depth first search. Every time you push a
vertex, you add its index to indextable[currindex] and increase
currindex by one.
Afterwards you can just run through your indextable in any order
you like and get the vertex labels. In addition, it separates
algorithm and output.

If you want to save memory and do not care about time complexity
or computational effort, you can instead only reset currindex to
0, increase currindex by one before pushing and writing this
increased currindex into mark.
So, afterwards you can extract the information from mark (which
unfortunately just goes the wrong direction and reversing that
will cost you -- either memory and the linear complexity of a
bucket sort, meaning you are not better off, or no memory and
higher complexity).


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Boost.Graph] graph.vertices property creates new objects George Sakkis Python 1 01-29-2007 11:09 PM
Help with initialization of graph (Boost Graph Library) Jef Driesen C++ 3 01-24-2006 01:44 PM
Missing Graph.h and (Graph.lib) woes - any help Dr Ann Huxtable C Programming 6 12-21-2004 11:15 AM
Graph algorithms - DFS, generators callbacks, and optimisation Paul Moore Python 3 11-29-2003 11:03 PM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM



Advertisments