Elysian Shadows

Posted: **Thu Dec 11, 2008 3:09 pm**

bugmenot wrote:
can you do tree traversal in C++ without pointers and references?
Yes. A link is not necessary has to be maintained via a pointer (*) or a reference (&), you can easily do this via a GUID. Out of interest, how are you maintaining the list of friends for a node?

i would like to see an example of lets say inorder traversal of a binary tree without pointers. (just because i have no idea how i would do it.

)

right now i dont have a program, but if i was going to make a friend list id use a linked list just so i have it dynamic.
but for the superpose of doing it without pointers if i had to. i would just use a static array[someSize] (which technically is not dif)

Posted: **Thu Dec 11, 2008 3:56 pm**

This is a breadth first graph traversal without references or pointers with the simplified version of the original problem and one way links between nodes (I had half the code written already). Excuse the sloppy coding as it was done in a rush:

Code: Select all

#include <iostream>
#include <map>
#include <string>
#include <cassert>
#include <vector>

class Person
{
public:
	explicit Person( const std::string & name );
	int GetId() const;
	bool IsConnectedTo( const Person & otherPerson ) const;
	void AddFriendToList( const Person & aFriend );
	
private:
	struct FriendNode
	{
		bool mDirtyFlag;
		const Person & mFriend;
	};

	static int msIdCounter;
	int mId;
	std::string mName;
	std::vector<int> mFriendIds;
};

std::map<int, Person> gNetwork;
int Person::msIdCounter = 0;

Person::Person( const std::string & name ) : mId( msIdCounter ), mName( name )
{
	msIdCounter += 1;
}

int Person::GetId() const
{
	return mId;
}

bool Person::IsConnectedTo( const Person & otherPerson ) const
{
	std::vector<int> currentSearchingIds, nextSearchingIds; 
	currentSearchingIds.push_back( GetId() );
	bool personFound = false;
	
	while( !personFound && currentSearchingIds.size() != 0 )
	{
		std::vector<int>::const_iterator currentItrId = currentSearchingIds.begin();
		while( currentItrId != currentSearchingIds.end() )
		{
			if( otherPerson.GetId() == *currentItrId )
			{
				personFound = true;
				break;
			}
			else
			{
				const Person & aPerson = gNetwork.find( *currentItrId )->second;
				std::vector<int>::const_iterator friendsIdsItr = aPerson.mFriendIds.begin();
				while( friendsIdsItr != aPerson.mFriendIds.end() )
				{
					std::cout << *friendsIdsItr << std::endl;
					nextSearchingIds.push_back( *friendsIdsItr );
					++friendsIdsItr;			
				}
				++currentItrId;
			}
		}
		currentSearchingIds = nextSearchingIds;
		nextSearchingIds.clear();
	}
	
	return personFound;
}

void Person::AddFriendToList( const Person & aFriend )
{
	mFriendIds.push_back(aFriend.GetId());
}

int main()
{
	Person Andre( "Andre" ), Claire( "Claire" ), Bob( "Bob" ), Mick( "Mick" ), RandomGuy( "RandonGuy" );
	
	Andre.AddFriendToList( Claire );
	Andre.AddFriendToList( Bob );
	Claire.AddFriendToList( Mick );
	
	gNetwork.insert( std::make_pair( Andre.GetId(), Andre ) );
	gNetwork.insert( std::make_pair( Claire.GetId(), Claire ) );
	gNetwork.insert( std::make_pair( Bob.GetId(), Bob ) );
	gNetwork.insert( std::make_pair( Mick.GetId(), Mick ) );
	gNetwork.insert( std::make_pair( RandomGuy.GetId(), RandomGuy ) );
	
	assert( Andre.IsConnectedTo( Mick ) );
	assert( !Andre.IsConnectedTo( RandomGuy ) );
}

Posted: **Thu Dec 11, 2008 4:00 pm**

bugmenot wrote:This is a breadth first graph traversal without references or pointers with the simplified version of the original problem and one way links between nodes (I had half the code written already). Excuse the sloppy coding as it was done in a rush:

Code: Select all

#include <iostream>
#include <map>
#include <string>
#include <cassert>
#include <vector>

class Person
{
public:
	explicit Person( const std::string & name );
	int GetId() const;
	bool IsConnectedTo( const Person & otherPerson ) const;
	void AddFriendToList( const Person & aFriend );
	
private:
	struct FriendNode
	{
		bool mDirtyFlag;
		const Person & mFriend;
	};

	static int msIdCounter;
	int mId;
	std::string mName;
	std::vector<int> mFriendIds;
};

std::map<int, Person> gNetwork;
int Person::msIdCounter = 0;

Person::Person( const std::string & name ) : mId( msIdCounter ), mName( name )
{
	msIdCounter += 1;
}

int Person::GetId() const
{
	return mId;
}

bool Person::IsConnectedTo( const Person & otherPerson ) const
{
	std::vector<int> currentSearchingIds, nextSearchingIds; 
	currentSearchingIds.push_back( GetId() );
	bool personFound = false;
	
	while( !personFound && currentSearchingIds.size() != 0 )
	{
		std::vector<int>::const_iterator currentItrId = currentSearchingIds.begin();
		while( currentItrId != currentSearchingIds.end() )
		{
			if( otherPerson.GetId() == *currentItrId )
			{
				personFound = true;
				break;
			}
			else
			{
				const Person & aPerson = gNetwork.find( *currentItrId )->second;
				std::vector<int>::const_iterator friendsIdsItr = aPerson.mFriendIds.begin();
				while( friendsIdsItr != aPerson.mFriendIds.end() )
				{
					std::cout << *friendsIdsItr << std::endl;
					nextSearchingIds.push_back( *friendsIdsItr );
					++friendsIdsItr;			
				}
				++currentItrId;
			}
		}
		currentSearchingIds = nextSearchingIds;
		nextSearchingIds.clear();
	}
	
	return personFound;
}

void Person::AddFriendToList( const Person & aFriend )
{
	mFriendIds.push_back(aFriend.GetId());
}

int main()
{
	Person Andre( "Andre" ), Claire( "Claire" ), Bob( "Bob" ), Mick( "Mick" ), RandomGuy( "RandonGuy" );
	
	Andre.AddFriendToList( Claire );
	Andre.AddFriendToList( Bob );
	Claire.AddFriendToList( Mick );
	
	gNetwork.insert( std::make_pair( Andre.GetId(), Andre ) );
	gNetwork.insert( std::make_pair( Claire.GetId(), Claire ) );
	gNetwork.insert( std::make_pair( Bob.GetId(), Bob ) );
	gNetwork.insert( std::make_pair( Mick.GetId(), Mick ) );
	gNetwork.insert( std::make_pair( RandomGuy.GetId(), RandomGuy ) );
	
	assert( Andre.IsConnectedTo( Mick ) );
	assert( !Andre.IsConnectedTo( RandomGuy ) );
}

i would have never thought of doing is that way. uou use the push_back call, where does that come from? and it seems you are still using references.

Posted: **Thu Dec 11, 2008 4:13 pm**

Look at the C++ vector in the STL. The references used have nothing to do with how the links are being stored and are just there out of habit from programming practises. You can remove all the & signs and it will still work but pass everything by value. (In fact, I accidentally left some dead code which was a bit misleading)

Code: Select all

#include <iostream>
#include <map>
#include <string>
#include <cassert>
#include <vector>

class Person
{
public:
	explicit Person( const std::string  name );
	int GetId() const;
	bool IsConnectedTo( const Person  otherPerson ) const;
	void AddFriendToList( const Person  aFriend );
	
private:

	static int msIdCounter;
	int mId;
	std::string mName;
	std::vector<int> mFriendIds;
};

std::map<int, Person> gNetwork;
int Person::msIdCounter = 0;

Person::Person( const std::string  name ) : mId( msIdCounter ), mName( name )
{
	msIdCounter += 1;
}

int Person::GetId() const
{
	return mId;
}

bool Person::IsConnectedTo( const Person  otherPerson ) const
{
	std::vector<int> currentSearchingIds, nextSearchingIds; 
	currentSearchingIds.push_back( GetId() );
	bool personFound = false;
	
	while( !personFound && currentSearchingIds.size() != 0 )
	{
		std::vector<int>::const_iterator currentItrId = currentSearchingIds.begin();
		while( currentItrId != currentSearchingIds.end() )
		{
			if( otherPerson.GetId() == *currentItrId )
			{
				personFound = true;
				break;
			}
			else
			{
				const Person  aPerson = gNetwork.find( *currentItrId )->second;
				std::vector<int>::const_iterator friendsIdsItr = aPerson.mFriendIds.begin();
				while( friendsIdsItr != aPerson.mFriendIds.end() )
				{
					std::cout << *friendsIdsItr << std::endl;
					nextSearchingIds.push_back( *friendsIdsItr );
					++friendsIdsItr;			
				}
				++currentItrId;
			}
		}
		currentSearchingIds = nextSearchingIds;
		nextSearchingIds.clear();
	}
	
	return personFound;
}

void Person::AddFriendToList( const Person  aFriend )
{
	mFriendIds.push_back(aFriend.GetId());
}

int main()
{
	Person Andre( "Andre" ), Claire( "Claire" ), Bob( "Bob" ), Mick( "Mick" ), RandomGuy( "RandonGuy" );
	
	Andre.AddFriendToList( Claire );
	Andre.AddFriendToList( Bob );
	Claire.AddFriendToList( Mick );
	
	gNetwork.insert( std::make_pair( Andre.GetId(), Andre ) );
	gNetwork.insert( std::make_pair( Claire.GetId(), Claire ) );
	gNetwork.insert( std::make_pair( Bob.GetId(), Bob ) );
	gNetwork.insert( std::make_pair( Mick.GetId(), Mick ) );
	gNetwork.insert( std::make_pair( RandomGuy.GetId(), RandomGuy ) );
	
	assert( Andre.IsConnectedTo( Mick ) );
	assert( !Andre.IsConnectedTo( RandomGuy ) );
}

Posted: **Thu Dec 11, 2008 4:20 pm**

For the sake of the following, lets assume the friend links are one way, as I understand your algorithm, your data store is like:

However, as start your algorithm from A, it conceptually becomes:

The links between the parent and the child is maintained in some form be it a direct link to the node or storing a reference to the GUID of it hence why I deem it to be a tree traversal.

Posted: **Thu Dec 11, 2008 4:25 pm**

in the method i showed. if we used your tree structure. F can in no way be a child of A.
im in the progress of writing the program, maybe that will explain it better, but i still doubt that you will change you point of view.

if i may ask, what is your technical background?

Posted: **Thu Dec 11, 2008 4:31 pm**

avansc wrote:in the method i showed. if we used your tree structure. F can in no way be a child of A.

Why not? Andre(A) -> Claire(B) -> Mick(F).

if i may ask, what is your technical background?

MSc and 2 years in the industry.

Posted: **Thu Dec 11, 2008 4:39 pm**

oops. sorry, i totally miss looked the wrong letters.

where do you work if i may ask.

edit: masters in CSC? (not that im questioning your computer science knowledge, its very clear that you are no slouch in that department. just interested.)

Posted: **Thu Dec 11, 2008 4:42 pm**

avansc wrote:where do you work if i may ask.

Sorry, I have to keep that confidential due to contractual reasons.

Edit: MSc in Games Programming.

Posted: **Thu Dec 11, 2008 4:48 pm**

bugmenot wrote:
avansc wrote:where do you work if i may ask.
Sorry, I have to keep that confidential due to contractual reasons.

Edit: MSc in Games Programming.

i understand.. pretty nifty.

Posted: **Thu Dec 11, 2008 7:27 pm**

here is a solution to the problem.
its very messy, i did not plan, and it was written in haste. please look over bugs, i didnt read over, just ran it and it worked.

info.h

Code: Select all

#ifndef _info_h
#define _info_h

struct info
{
	char *dest;
	char *next;
	int cost;
};

info *newInfo(char *dest, char *next, int cost);

#endif

info.cpp

Code: Select all

#include <stdlib.h>
#include "info.h"

info *newInfo(char *dest, char *next, int cost)
{
	info *temp = (info*)malloc(sizeof(info));
	temp->dest = dest;
	temp->next = next;
	temp->cost = cost;
	return temp;
}

person.h

Code: Select all

#include "info.h"

#ifndef _person_h
#define _person_h

class person
{
public:
	person(char *name);
	void addFriend(person *p);
	void printFriends();
	void tellFriends();
	void newInf(char *dest, char *next, int cost);

	bool message;
	bool told;
	info *dat;

	bool semaphore;
	char *name;
	int count;
	person *friends[20];
private:
};

#endif

person.cpp

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "person.h"

person::person(char *name)
{
	this->name = (char*)malloc((strlen(name))*sizeof(char));
	this->name = name;
	this->count = 0;
	this->dat = NULL;
	this->message = false;
	this->semaphore = false;
	this->told = false;
}

void person::addFriend(person *p)
{
	this->friends[this->count] = p;
	this->count++;
}

void person::printFriends()
{
	for(int a = 0;a < this->count;a++)
	{
		printf("%s\n", this->friends[a]->name);
	}
}

void person::newInf(char *dest, char *next, int cost)
{
	if(this->dat != NULL)
	{
		if(this->dat->cost > cost )
			this->dat = newInfo(dest, next, cost);
	}else{
		this->dat = newInfo(dest, next, cost);
	}
}

void person::tellFriends()
{
	if(this->told == false);
	{
	this->message = false;
	this->semaphore = true;
	this->told = true;

	for(int a = 0;a < this->count;a++)
	{
		if(this->friends[a]->message == false && !this->friends[a]->told)
		{
			printf("%s is telling %s\n",this->name, this->friends[a]->name);
			this->friends[a]->message = true;
			this->friends[a]->semaphore = true;
			this->friends[a]->newInf(this->dat->dest, this->name, this->dat->cost+1);
		}
	}
	}
}

network.h

Code: Select all

#include "person.h"
#include "info.h"

#ifndef _network_h
#define _network_h

class network
{
public:
	network();
	int count;
	void sparkMessage(char *name);
	void addPerson(char *name);
	void beFriend(char *A, char *B);
	bool valid(char *name);
	int find(char *name);
	void printList();
	void updateNetworkMessages();
	person *com[20];
	bool semaphore;
	char *semWho;
private:
};

#endif

network.cpp

Code: Select all

#include "stdio.h"

#include "network.h"

network::network()
{
	printf("Network Created.\n");
	this->count = 0;
	this->semaphore = false;
	this->semWho = NULL;
}

void network::addPerson(char *name)
{
	this->com[this->count] = new person(name);
	this->count++;
}

void network::printList()
{
	for(int a = 0;a < this->count;a++)
	{
		printf("name : %s\n", this->com[a]->name);
	}
}

bool network::valid(char *name)
{
	for(int a = 0;a <this->count;a++)
	{
		if(this->com[a]->name == name)
			return true;
	}
	return false;
}

int network::find(char *name)
{
	if(this->valid(name))
	{
		for(int a = 0;a < this->count;a++)
		{
			if(this->com[a]->name == name)
				return a;
		}
	}
	return -1;
}

void network::beFriend(char *A, char *B)
{
	if(!this->valid(A) || !this->valid(B))
	{
		printf("ERROR WITH INPUT\n");
		return;
	}
	int a = this->find(A);
	int b = this->find(B);

	this->com[a]->addFriend(this->com[b]);
	this->com[b]->addFriend(this->com[a]);
}

void network::sparkMessage(char *name)
{
	if(!this->valid(name))
		return;
	
	int a = this->find(name);

	this->com[a]->message = true;
	this->com[a]->semaphore = false;
	this->com[a]->dat = newInfo(name, NULL, 0);

}

void network::updateNetworkMessages()
{
	for(int a = 0;a < this->count;a++)
	{
		if(this->com[a]->message && !this->com[a]->told)
		{
			this->com[a]->tellFriends();
		}
	}

	for(int a = 0;a < this->count;a++)
	{
		this->com[a]->semaphore = false;
	}
}

main.cpp

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include "network.h"
#include "person.h"

int main(void)
{
	network *net = new network();
	net->addPerson("A");
	net->addPerson("B");
	net->addPerson("C");
	net->addPerson("D");
	net->addPerson("E");
	net->addPerson("F");
	net->addPerson("G");
	net->addPerson("H");
	net->addPerson("I");
	net->addPerson("X");

	net->printList();

	net->beFriend("A", "B");
	net->beFriend("A", "C");
	net->beFriend("A", "D");

	net->beFriend("B", "E");
	net->beFriend("E", "F");
	net->beFriend("E", "G");
	net->beFriend("E", "X");

	net->beFriend("G", "H");
	net->beFriend("H", "I");

	net->sparkMessage("I");

	for(int a = 0;a < 20;a++)
	{
		if(net->com[0]->dat)
		{
			printf("%s , %s , %d\n", net->com[0]->dat->dest, net->com[0]->dat->next, net->com[0]->dat->cost);
			break;
		}else
		{
		printf("nothing yet.\n");
		}
		net->updateNetworkMessages();
	}
	printf("\n");

	int f = 0;

	for(int a = 0;a < net->com[0]->dat->cost+1;a++)
	{
		//printf("%s , %s , %d\n", net->com[f]->dat->dest, net->com[f]->dat->next, net->com[f]->dat->cost);
		printf("-> %s ",net->com[f]->name);
		f = net->find(net->com[f]->dat->next);
	}

	getchar();
	return 0;
}

Posted: **Fri Dec 12, 2008 5:06 am**

You have a logic bug which screw with your algorithm (I am surprised your compiler didn't pick it up):

Code: Select all

void person::tellFriends()
{
   if(this->told == false);
   {

Note the ; at the end of the if statement.

Posted: **Fri Dec 12, 2008 6:11 am**

I had a proper look at the algorithm so let's see if I get this right in regards to the diagram I made above:

1) Initiate a message from A. A has a message
2) First iteration, go through all the nodes, if a node has a message, then iterate through all the nodes it is connected to and give them the message. B, C and D have messages from the links from A.
3) Second iteration, go through all the nodes, if a node has a message, then iterate through all the nodes it is connected to and give them the message. F and G have messages from the links from B. E has a message from C. D has no friends so no messages.
4) Second iteration, go through all the nodes, if a node has a message, then iterate through all the nodes it is connected to and give them the message. E has no friends so messages. F has no friends so messages. H has a mesesage from the links from G.

Through every iteration, we have iterated through all the nodes in one breadth
A
B, C, D
E, F, G
H

Via the links in the nodes of the breadth above therefore it is a breadth traversal of a graph. Your algorithm is exactly the same as mine except I store the GUIDs of the nodes for the next iteration where you use a flag and loop through the entire network to find nodes with this flag set.

Posted: **Fri Dec 12, 2008 8:41 am**

bugmenot wrote:I had a proper look at the algorithm so let's see if I get this right in regards to the diagram I made above:

1) Initiate a message from A. A has a message
2) First iteration, go through all the nodes, if a node has a message, then iterate through all the nodes it is connected to and give them the message. B, C and D have messages from the links from A.
3) Second iteration, go through all the nodes, if a node has a message, then iterate through all the nodes it is connected to and give them the message. F and G have messages from the links from B. E has a message from C. D has no friends so no messages.
4) Second iteration, go through all the nodes, if a node has a message, then iterate through all the nodes it is connected to and give them the message. E has no friends so messages. F has no friends so messages. H has a mesesage from the links from G.

Through every iteration, we have iterated through all the nodes in one breadth
A
B, C, D
E, F, G
H

Via the links in the nodes of the breadth above therefore it is a breadth traversal of a graph. Your algorithm is exactly the same as mine except I store the GUIDs of the nodes for the next iteration where you use a flag and loop through the entire network to find nodes with this flag set.

well you should go tell years of network theory they are wrong.
i agree that it propagates the same as a breadth first traversal.
but each node maintains it self, there is no traversal.
i think it really doesent matter anyways. i think terminology is also hindering us.
anyways, i liked you GUID code. i'll have to look into that a bit. as var as i can tell the GUID struck only has a few variables and im trying to see
how they manage to do what they do. to be honest i never use guid much more that i needed them for win 32 programming. (directx)

Posted: **Fri Dec 12, 2008 8:42 am**

bugmenot wrote:You have a logic bug which screw with your algorithm (I am surprised your compiler didn't pick it up):
Code: Select all
void person::tellFriends()
{
   if(this->told == false);
   {
Note the ; at the end of the if statement.

whoops... like i said it was written on the fly, but yeah im really surprised my compiler didn't bitch at me about that.

Elysian Shadows

a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.

Re: a little challange.