Re: Wrong Output, Cant catch the mistake (DFS) - C / C++ / MFC Discussion Boards

Wrong Output, Cant catch the mistake (DFS)

zeego4-Oct-09 20:51

4-Oct-09 20:51

Hi I made the following program for depth first search but I am having wrong path. Can anyone catch or tell me what I am doing wrong here. I dont know much how to use the debugger in turbo c professional.

Thanks and regards, Mike.

#include <stdio.h>
#include <conio.h>
#define MAX 6 // Node/Vertex count
int adj[MAX][MAX]={ // Adjacency Matrix 2x2
{0,1,1,1,0,0},
{1,0,0,0,1,1},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{0,1,0,0,0,0},
{0,1,1,0,0,0}
};

int visited[MAX]; // Visited array

void bfs(int goal); // bfs function

int main ()
{
int g=5; //set Goal node
clrscr();
printf("The nodes order is ");
bfs(g);
return 0;

}

void bfs(int goal)
{

int queue[MAX];
int i,front,rear,root;
front=rear=0;

for (i=1;i<=MAX;i++)
visited[i]=0;

visited[goal]=1;
queue[rear++]=goal;

while(front!=rear)
{
root=queue[front];
for(i=1;i<=MAX;i++)
{
if (adj[root][i] && !visited[i])
{
visited[i]=1;
queue[rear++]=i;
printf("%d",i);
}
front++;
}
}

}

Re: Wrong Output, Cant catch the mistake (DFS)

DeepakMega4-Oct-09 21:26

DeepakMega

4-Oct-09 21:26

Is the queue circular , if so you need to check for ends and rotate the queue's front/rear back to 0.
Refer here Circular Queue[^]

Re: Wrong Output, Cant catch the mistake (DFS)

zeego4-Oct-09 22:30

zeego

4-Oct-09 22:30

No, it is not circular. It is just a FIFO queue.

Re: Wrong Output, Cant catch the mistake (DFS)

Saurabh.Garg4-Oct-09 22:53

Saurabh.Garg

4-Oct-09 22:53

For loops be for(i=0 ; i<MAX ; ++i)

front++; should be outside the for loop.

-Saurabh

Re: Wrong Output, Cant catch the mistake (DFS)

zeego4-Oct-09 23:07

zeego

4-Oct-09 23:07

Output is wrong if I take it out of the for loop Cry | :((

Re: Wrong Output, Cant catch the mistake (DFS)

DeepakMega4-Oct-09 23:32

DeepakMega

4-Oct-09 23:32

Sry im not good at algorithms, when i ran your code in vs there was an error in
the 3rd line of the code below

root=queue[front];
for(i=1;i<=MAX;i++)
{
if (adj[root][i] && !visited[i])

ie : adj[root][i] , the root value was garbage,
and root=queue[front]; here front was 6 and queue[6] was uninitialized

Re: Wrong Output, Cant catch the mistake (DFS)

zeego4-Oct-09 23:45

zeego

4-Oct-09 23:45

thanks for the reply. I am using the turbo c 3.0 IDE, I never knew it could run in visual studio. Sniff | :^)

I had a hard time debugging this inside the turbo c ide so I posted it here.
Mike.

Re: Wrong Output, Cant catch the mistake (DFS)

zeego12-Oct-09 20:52

zeego

12-Oct-09 20:52

Cant get it to work. The output is a blank screen Frown | :(

#include <stdio.h>
#include <conio.h>
#define MAX 6			// Node/Vertex count
int adj[MAX][MAX]={      // Adjacency Matrix 2x2
			    {0,1,1,1,0,0},
			    {1,0,0,0,1,1},
			    {1,0,0,0,0,0},
			    {1,0,0,0,0,0},
			    {0,1,0,0,0,0},
			    {0,1,1,0,0,0}
			};

int visited[MAX];	// Visited array
void bfs(int goal);	// bfs function


int main ()
	{
		int s=3;	//set Source node
		clrscr();
		printf("The nodes order is ");
		bfs(s);
		return 0;


	}

void bfs(int source)
	{
	   int queue[MAX];
	   int i,front,rear,root;
	   front=rear=0;

	   for (i=1;i<MAX;i++)
	   {
		   visited[i]=0;
	   }



	   queue[++rear]=source;
	   visited[source]=1;

	   printf("%d :",source);

		while(rear!=front)
			{
				root=queue[++front];
				for(i=0;i<MAX;i++)

					if (adj[root][i] && !visited[i])
					{
						queue[rear++]=i;
						visited[i]=1;
						printf("%d",i);
					}


				front++;
			}


	   }

Re: Wrong Output, Cant catch the mistake (DFS)

DeepakMega12-Oct-09 22:17

DeepakMega

12-Oct-09 22:17

What is your required output.
Please specify the output needed for the above program inputs.

Re: Wrong Output, Cant catch the mistake (DFS)

zeego12-Oct-09 23:14

zeego

12-Oct-09 23:14

Hello mate, thanks for the reply. I need breadth first traversal on a graph, but its not working properly. Unsure | :~

The program hangs inside my turbo c ide and I have to use 'break' to get out of the infinite loop. Also I dont know how to debug inside turbo c 3 IDE so having a hard time debugging the problem in my code.Please help me. Sniff | :^)

Thanks and best regards, Mike.

Re: Wrong Output, Cant catch the mistake (DFS)

DeepakMega12-Oct-09 22:48

DeepakMega

12-Oct-09 22:48

Changes made :

for (i=0;i<MAX;i++)
{
visited[i]=0;
}
queue[rear++]=source; // its not ++rear as it becomes queue[1] instead of queue[0]

.....
.....
while(rear!=front)
{
root=queue[front]; //no need to increment front here

This is the output i got

The nodes order is 3 :01245

Re: Wrong Output, Cant catch the mistake (DFS)

zeego12-Oct-09 23:11

zeego

12-Oct-09 23:11

The program is for breadth first traversal of a graph. The output is there but program is crashing. I have to use break to stop from infinite looping. Confused | :confused:

Re: Wrong Output, Cant catch the mistake (DFS)

DeepakMega12-Oct-09 23:45

DeepakMega

12-Oct-09 23:45

rear=0;
1) queue[rear++]=source; // is same as queue[0]=source; and rear increments after assignment;
2) queue[++rear]=source; // is same as queue[1]=source; here rear increments before assignment;

Its from the precedence of operators in c, check operator precedence table[^]

The below program with minor changes as specified above runs fine in my turbo c , just add a getch() in main

#include <stdio.h>
#include <conio.h>
#define MAX 6			// Node/Vertex count
int adj[MAX][MAX]={      // Adjacency Matrix 2x2
			    {0,1,1,1,0,0},
			    {1,0,0,0,1,1},
			    {1,0,0,0,0,0},
			    {1,0,0,0,0,0},
			    {0,1,0,0,0,0},
			    {0,1,1,0,0,0}
			};

int visited[MAX];	// Visited array
void bfs(int goal);	// bfs function


int main ()
	{
		int s=3;	//set Source node
		clrscr();
		printf("The nodes order is ");
		bfs(s);
		getch();
		return 0;


	}

void bfs(int source)
	{
	   int queue[MAX];
	   int i,front,rear,root;
	   front=rear=0;

	   for (i=0;i<MAX;i++)
	   {
		   visited[i]=0;
	   }



	   queue[rear++]=source;
	   visited[source]=1;

	   printf("%d :",source);

		while(rear!=front)
			{
				root=queue[front];
				for(i=0;i<MAX;i++)

					if (adj[root][i] && !visited[i])
					{
						queue[rear++]=i;
						visited[i]=1;
						printf("%d",i);
					}


				front++;
			}


	   }

Re: Wrong Output, Cant catch the mistake (DFS)

zeego13-Oct-09 21:39

zeego

13-Oct-09 21:39

Thanks so much for the reply and the link, the program is working fine now. Big Grin | :-D

Best Regards, Mike.

Re: Wrong Output, Cant catch the mistake (DFS)

zeego12-Oct-09 23:38

zeego

12-Oct-09 23:38

Thanks for the reply mate. Isn't ++rear=rear+1 ?
What is the difference between the two ?

Also queue[rear++]=source means queue[0]=source ?

Best regards, Mike.

VARIANT to CString

Davitor4-Oct-09 20:28

Davitor

4-Oct-09 20:28

Hi
how can i chane VARIANT to CString?

 VARIANT var=pRange->GetValue();
CString strp;
str=CString(var.bstrVal);

some time i got exception

Unhandled exception at 0x7c80a30a in test.exe: 0xC0000005: Access violation reading location 0x001e2000.

Call stack show

test.exe!ATL::ChTraitsCRT<char>::GetBaseTypeLength(const wchar_t * pszSource=0x001e1f98)  Line 284 + 0x1e bytes	C++

in cstring.h class pointing

static int __cdecl GetBaseTypeLength( _In_z_ LPCWSTR pszSource ) throw()
	{
		// Returns required buffer length in XCHARs
		return ::WideCharToMultiByte( _AtlGetConversionACP(), 0, pszSource, -1, NULL, 0, NULL, NULL )-1;
	}

Can any one tell me region behind of exception.
Plz help me

Re: VARIANT to CString

Code-o-mat4-Oct-09 20:37

Code-o-mat

4-Oct-09 20:37

Maybe your VARIANT doesn't contain a string but something else?

> The problem with computers is that they do what you tell them to do and not what you want them to do. <
> Sometimes you just have to hate coding to do it well. <

Re: VARIANT to CString

Davitor4-Oct-09 20:41

Davitor

4-Oct-09 20:41

Thanks for reply.
Can you give me idea to solve that problem?

Re: VARIANT to CString

Code-o-mat4-Oct-09 21:00

Code-o-mat

4-Oct-09 21:00

Well, as i said, it could be that your VARIANT contains something else than a string, like an integer for example, check this[^] out and you will see there can be a lot of datatypes a VARIANT can hold. So -based on what you see there- you should either skip non-string values or maybe convert what you can to a string if you really need to work with a string.

> The problem with computers is that they do what you tell them to do and not what you want them to do. <
> Sometimes you just have to hate coding to do it well. <

Re: VARIANT to CString

Stuart Dootson4-Oct-09 22:13

Stuart Dootson

4-Oct-09 22:13

Use VariantChangeType[^] to convert the VARIANT to one holding a BSTR representation of the data before trying to use the BSTR.

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p

How to pass the command to createprocess()

WindowsVsLinux4-Oct-09 20:16

WindowsVsLinux

4-Oct-09 20:16

Hi,
i write this simple program and execcte it. i thought that it will give all the name of directories where it was placed , but it is not working as i was thinking.i don't want to use system() function in place of crateprocess().my code is following-

#include<windows.h>
#include<stdio.h>

int main()
{
char *command="dir";
STARTUPINFO si = {sizeof(STARTUPINFO)};
PROCESS_INFORMATION pi;
CreateProcess("C:\\Windows\\System32\\cmd.exe", command, NULL, NULL, 0, 0, NULL, NULL, &si, &pi);

return 0;
}

please help me.i want to give command to createprocess() only when program is written not after execution of program.

Re: How to pass the command to createprocess()

Madhu Nair4-Oct-09 20:56

Madhu Nair

4-Oct-09 20:56

ravi 12 wrote:
char *command="dir";

change to
char *command="/C dir";

Re: How to pass the command to createprocess()

WindowsVsLinux4-Oct-09 22:16

WindowsVsLinux

4-Oct-09 22:16

thanks Madhu Nair, it works fine but i didn't understant why you put /C dir .can you please explain it?

Re: How to pass the command to createprocess()

Michael Schubert4-Oct-09 21:10

Michael Schubert

4-Oct-09 21:10

I don't really understand what you're trying to do, especially this is confusing:

ravi 12 wrote:
i want to give command to createprocess() only when program is written not after execution of program.

Anyway, it seems that you want to start a new command shell and pass a parameter. In order to do that you would need this:
cmd /C dir

To do that with CreateProcess() I suggest the following code:

STARTUPINFO si;
PROCESS_INFORMATION pi;
::ZeroMemory(&si, sizeof(STARTUPINFO));
::ZeroMemory(&pi, sizeof(PROCESS_INFORMATION));
si.cb = sizeof(STARTUPINFO);

if (::CreateProcess(NULL, "cmd.exe /C dir", NULL, NULL, FALSE, 0, NULL, NULL, &si, &pi) == 0)
 return FALSE;

Re: How to pass the command to createprocess()

WindowsVsLinux4-Oct-09 22:20

WindowsVsLinux

4-Oct-09 22:20

thanks Michael Schubert, same thing i want to know with you.actually when i use
CreateProcess(NULL, "cmd.exe ", command, NULL, FALSE, 0, NULL, NULL, &si, &pi)
it will open a command prompt and then i have to write dir but i don't want that.
anyway it works fine but i didn't understant why you put /C dir .can you please explain it?

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.