Hello all, I was building a program which needs to output in alphabetical order and i got stuck.
(Program reads in text file and then do dijkstra's shortest path)

My output is fine except that it is not in alphabetical order....
can anyone help me with this???

here is my code:

void dijkstra(string s, NodeMap &nodes)
{
	// check and report or abort
	Node* source = nodes.nodemap[s];
	if(source==0)
    {
                 cout << "Sorry we don't fly from "<< s << endl; return;
    }
	reset_nodes(nodes);

	// put the source into pq and loop until empty
	priority_queue<Node *, deque<Node*>, compare>pq;
	pq.push(source);
	while(!pq.empty())
    {
		// process least cost node.
		Node* curr = pq.top(); 
		pq.pop();
		curr->visited = true;
		// process neighbors
		list<Edge*>::iterator edge;
		for(edge = curr->neighbors.begin(); edge != curr->neighbors.end(); edge++)
        {
			Node *ne = (*edge)->dest;
			if(!ne->visited)
            {
				ne->cost += (*edge)->weight + curr->cost;
				ne->visited = true;
				ne->back_pointer = curr;
				cout << "Cheapest price to "<< ne->name << "                  = " << ne->cost << endl;;
				pq.push(ne);
			}		
        }
	}
}

Start with these:

Then you should explain what you mean with: ...output should be in alphabetical order... (give an example)
Do you mean the following?

[U]File looks like:[/U]
[I]lalal nn[/I]
[U]Output should be:[/U]
[I]aalllnn[/I]

My output should looks like

Enter filename : qantum.txt
Enter start city : Tokyo
Cheapest price to Brussels = 700
Tokyo Paris Brussels
Cheapest price to London = 900
Tokyo Paris London
Cheapest price to Melbourne = 2200
Tokyo Paris London Sydney Melbourne
Cheapest price to New York = 500
Tokyo New York
Cheapest price to Paris = 600
Tokyo Paris
Cheapest price to Sydney = 2000
Tokyo Paris London Sydney

where the city name next to weight is should be in alphabetical order.

> where the city name next to weight is should be in alphabetical order.

What exactly do you mean by this statement? What "weight" are you referring to? And by "city name should be in alphabetical order", did you mean that the last line(for example) in your Output should look like this - "London Paris Sydney Tokyo"? If not, then try and explain your problem more clearly...

Enter filename : qantum.txt
Enter start city : Tokyo
Cheapest price to Brussels = 700
Tokyo Paris Brussels
Cheapest price to London = 900
Tokyo Paris London
Cheapest price to Melbourne = 2200
Tokyo Paris London Sydney Melbourne
Cheapest price to New York = 500
Tokyo New York
Cheapest price to Paris = 600
Tokyo Paris
Cheapest price to Sydney = 2000
Tokyo Paris London Sydney

hmm sry my english isnt perfect....

wat i mean is

those city names comes after Cheapest price to .....

it should be in alphabetical order

where mine is start with

Cheapest price to New York = 500

Member Avatar for iamthwee

What does qantum.txt look like?

Post a sample or attach the file.

the things in text is...

Sydney New York 1300
New York Paris 1200
London Sydney 1100
Sydney London 1300
Paris New York 900
New York London 700
London Paris 200
Sydney Paris 900
Paris London 300
Brussels Paris 200
London Brussels 300
Sydney Brussels 700
Brussels New York 400
Paris Brussels 100
Tokyo New York 500
Tokyo Paris 600
Sydney Tokyo 300
Sydney Melbourne 200

Member Avatar for iamthwee

Please post an example of your full code to test.

Here is my full code

Member Avatar for iamthwee

Your code doesn't do anything.

sry didnt attach the text file

Member Avatar for iamthwee

Nope, still doesn't do anything, are you sure you posted the right code?

thats stragne i'll upload it again...

Member Avatar for iamthwee

No still nothing:

What compiler are you using?

using dev-cpp

are u using unix??? then remove 'system("PAUSE")'

from the code

Member Avatar for iamthwee

Nope, I've tested it with both dev-cpp and in ubuntu.

It only does something when I comment out the line:

get_graph(filename, nodes);

under int main

Member Avatar for iamthwee

Ok I've got it, it must have been a problem with the newline at the end of the file or something - it works when I use your attached text file.

hmm i dont know it's fine with me,,,

then i'll attach wat my output looks like

>Nope, I've tested it with both dev-cpp and in ubuntu.
Essentially they both use the same compiler :)

To the OP: Have you already noticed number 3 of my signature ?

Member Avatar for iamthwee

I would do something like:

#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <queue>
#include <vector>

using namespace std;

class Student
{
public:
   string name;
   double tuition;
};

//This function sorts by tuitions fees
bool SortStudentByTute ( const Student& left, const Student& right )
{
   if ( left.tuition > right.tuition )
   {
      return false;
   }
   else if ( left.tuition < right.tuition )
   {
      return true;
   }
} 



class Edge;

class Node
{
public:
   string    name;
   list<Edge*> neighbors;
   bool      visited;
   double       cost;
   Node      *back_pointer;

   Node ( string const &n ) : name ( n ), visited ( false ), cost ( 0 )
   {}
};

class Edge
{
public:
   double weight;
   Node * dest;

   Edge ( double c, Node *d = NULL ) : weight ( c ), dest ( d )
   {}

   ~Edge()
   {
      if ( dest ) delete dest;
   }
};

class NodeMap
{
public:
   map<string, Node*> nodemap;

   Node* find_in_nodemap ( string const &name )
   {
      Node* result = nodemap[name];
      if ( result == 0 )
      {
         result = nodemap[name] = new Node ( name );
      }
      return result;
   }
   friend ostream& operator<< ( ostream& o, NodeMap nm )
   {
      map<string, Node*>::iterator im;
      for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
      {
         //pair<string,Node*> p = *im;
         //o << p.second->name << endl;
         o << ( *im ).second->name << endl;
         list<Edge*> neighbors = ( *im ).second->neighbors;
         list<Edge*>::iterator e;
      }
      return o;
   }
};

struct compare
{

   bool operator() ( Node * &a, Node * &b ) const
   {
      // least to greatest
      return b->cost < a->cost;
   }
};
// for each solution, reset node information
void reset_nodes ( NodeMap &nm )
{
   map<string, Node*>::iterator im;
   for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
   {
      ( *im ).second->cost = 0;
      ( *im ).second->back_pointer = 0;
      ( *im ).second->visited = false;
   }
}

void dijkstra ( string s, NodeMap &nodes )
{
   Student myStudent [500]; //create an array of objects

   int i = 0;

   // check and report or abort
   Node* source = nodes.nodemap[s];
   if ( source == 0 )
   {
      cout << "Sorry we don't fly from " << s << endl;
      return;
   }
   reset_nodes ( nodes );

   // put the source into pq and loop until empty
   priority_queue<Node *, deque<Node*>, compare > pq;
   pq.push ( source );
   while ( !pq.empty() )
   {
      // process least cost node.
      Node* curr = pq.top();
      pq.pop();
      curr->visited = true;
      // process neighbors
      list<Edge*>::iterator edge; 
      for ( edge = curr->neighbors.begin(); edge != curr->neighbors.end(); edge++ )
      {
         Node *ne = ( *edge )->dest;
         if ( !ne->visited )
         {
            ne->cost += ( *edge )->weight + curr->cost;
            ne->visited = true;
            ne->back_pointer = curr;
            //cout << "Cheapest price to "<< ne->name << " = " << ne->cost << endl; 

            myStudent[i].name = ne->name;
            myStudent[i].tuition = ne->cost;
            i++; 


            pq.push ( ne );
         }
      }
   }

   std::sort ( myStudent, myStudent + i, SortStudentByTute );
   for ( int j = 0; j < i; j++ )
   {
      cout << "Cheapest price to " << myStudent[j].name << " = " << myStudent[j].tuition << endl;
   }
}

void get_graph ( string const &filename, NodeMap &node_map )
{
   ifstream inf ( filename.c_str() );
   string from, to;
   double weight;
   while ( !inf.eof() )
   {
      inf >> from >> to >> weight;
      if ( inf.good() )
      {
         Node *Target = node_map.find_in_nodemap ( to );
         Node *Source = node_map.find_in_nodemap ( from );
         Edge *connector = new Edge ( weight, Target );
         Source->neighbors.push_back ( connector );
      }
   }
}
int main()
{
   NodeMap nodes;
   ifstream inf;
   string filename;
   cout << "Enter filename : ";
   cin >> filename;
   inf.open ( filename.c_str() );
   get_graph ( filename, nodes );

   string s;
   cout << "Enter start city : ";
   cin >> s;
   dijkstra ( s, nodes );

   system ( "PAUSE" );
   return 0;
}

Not tested?

Thx but it still gives the same output

not in alphabetical order

Member Avatar for iamthwee

Oh I thought you wanted it in order of cost lowest to highest.

For alphabetical order just do:

#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <queue>
#include <vector>

using namespace std;

class Student
{
public:
   string name;
   double tuition;
};

//This function sorts by tuitions fees
bool SortStudentByTute ( const Student& left, const Student& right )
{
   if ( left.tuition > right.tuition )
   {
      return false;
   }
   else if ( left.tuition < right.tuition )
   {
      return true;
   }
} 

bool SortStudentByName ( const Student& left, const Student& right )
{
   //Here you can define whatever the sort criterion
   //needs to be. It can be as complicated as you wish
 
   if ( left.name > right.name )
   {
      return false;
   }
   else if ( left.name < right.name )
   {
      return true;
   }
   //else //i.e if both are equal
 
}



class Edge;

class Node
{
public:
   string    name;
   list<Edge*> neighbors;
   bool      visited;
   double       cost;
   Node      *back_pointer;

   Node ( string const &n ) : name ( n ), visited ( false ), cost ( 0 )
   {}
};

class Edge
{
public:
   double weight;
   Node * dest;

   Edge ( double c, Node *d = NULL ) : weight ( c ), dest ( d )
   {}

   ~Edge()
   {
      if ( dest ) delete dest;
   }
};

class NodeMap
{
public:
   map<string, Node*> nodemap;

   Node* find_in_nodemap ( string const &name )
   {
      Node* result = nodemap[name];
      if ( result == 0 )
      {
         result = nodemap[name] = new Node ( name );
      }
      return result;
   }
   friend ostream& operator<< ( ostream& o, NodeMap nm )
   {
      map<string, Node*>::iterator im;
      for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
      {
         //pair<string,Node*> p = *im;
         //o << p.second->name << endl;
         o << ( *im ).second->name << endl;
         list<Edge*> neighbors = ( *im ).second->neighbors;
         list<Edge*>::iterator e;
      }
      return o;
   }
};

struct compare
{

   bool operator() ( Node * &a, Node * &b ) const
   {
      // least to greatest
      return b->cost < a->cost;
   }
};
// for each solution, reset node information
void reset_nodes ( NodeMap &nm )
{
   map<string, Node*>::iterator im;
   for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
   {
      ( *im ).second->cost = 0;
      ( *im ).second->back_pointer = 0;
      ( *im ).second->visited = false;
   }
}

void dijkstra ( string s, NodeMap &nodes )
{
   Student myStudent [500]; //create an array of objects

   int i = 0;

   // check and report or abort
   Node* source = nodes.nodemap[s];
   if ( source == 0 )
   {
      cout << "Sorry we don't fly from " << s << endl;
      return;
   }
   reset_nodes ( nodes );

   // put the source into pq and loop until empty
   priority_queue<Node *, deque<Node*>, compare > pq;
   pq.push ( source );
   while ( !pq.empty() )
   {
      // process least cost node.
      Node* curr = pq.top();
      pq.pop();
      curr->visited = true;
      // process neighbors
      list<Edge*>::iterator edge; 
      for ( edge = curr->neighbors.begin(); edge != curr->neighbors.end(); edge++ )
      {
         Node *ne = ( *edge )->dest;
         if ( !ne->visited )
         {
            ne->cost += ( *edge )->weight + curr->cost;
            ne->visited = true;
            ne->back_pointer = curr;
            //cout << "Cheapest price to "<< ne->name << " = " << ne->cost << endl; 

            myStudent[i].name = ne->name;
            myStudent[i].tuition = ne->cost;
            i++; 


            pq.push ( ne );
         }
      }
   }

   std::sort ( myStudent, myStudent + i, SortStudentByName );
   for ( int j = 0; j < i; j++ )
   {
      cout << "Cheapest price to " << myStudent[j].name << " = " << myStudent[j].tuition << endl;
   }
}

void get_graph ( string const &filename, NodeMap &node_map )
{
   ifstream inf ( filename.c_str() );
   string from, to;
   double weight;
   while ( !inf.eof() )
   {
      inf >> from >> to >> weight;
      if ( inf.good() )
      {
         Node *Target = node_map.find_in_nodemap ( to );
         Node *Source = node_map.find_in_nodemap ( from );
         Edge *connector = new Edge ( weight, Target );
         Source->neighbors.push_back ( connector );
      }
   }
}
int main()
{
   NodeMap nodes;
   ifstream inf;
   string filename;
   cout << "Enter filename : ";
   cin >> filename;
   inf.open ( filename.c_str() );
   get_graph ( filename, nodes );

   string s;
   cout << "Enter start city : ";
   cin >> s;
   dijkstra ( s, nodes );

   system ( "PAUSE" );
   return 0;
}

again not tested.

Yay thx vry much

if u dont mind can i ask u one more favour?

u see from my input text file it has

Sydney NewYork 1300

my program also should read

Sydney New York 1300

(where the space can be tab space)

How do u make it to read that???

If you help me ill really appreciate it :)

Member Avatar for iamthwee

Sorry I have customers to serve at McDonald's.

Good luck though.

However, if I didn't I might do something like:

#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <queue>
#include <vector>

using namespace std;

string s;

class Student
{
public:
   string name;
   double tuition;
};

//This function sorts by tuitions fees
bool SortStudentByTute ( const Student& left, const Student& right )
{
   if ( left.tuition > right.tuition )
   {
      return false;
   }
   else if ( left.tuition < right.tuition )
   {
      return true;
   }
} 

bool SortStudentByName ( const Student& left, const Student& right )
{
   //Here you can define whatever the sort criterion
   //needs to be. It can be as complicated as you wish
 
   if ( left.name > right.name )
   {
      return false;
   }
   else if ( left.name < right.name )
   {
      return true;
   }
   //else //i.e if both are equal
 
}



class Edge;

class Node
{
public:
   string    name;
   list<Edge*> neighbors;
   bool      visited;
   double       cost;
   Node      *back_pointer;

   Node ( string const &n ) : name ( n ), visited ( false ), cost ( 0 )
   {}
};

class Edge
{
public:
   double weight;
   Node * dest;

   Edge ( double c, Node *d = NULL ) : weight ( c ), dest ( d )
   {}

   ~Edge()
   {
      if ( dest ) delete dest;
   }
};

class NodeMap
{
public:
   map<string, Node*> nodemap;

   Node* find_in_nodemap ( string const &name )
   {
      Node* result = nodemap[name];
      if ( result == 0 )
      {
         result = nodemap[name] = new Node ( name );
      }
      return result;
   }
   friend ostream& operator<< ( ostream& o, NodeMap nm )
   {
      map<string, Node*>::iterator im;
      for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
      {
         //pair<string,Node*> p = *im;
         //o << p.second->name << endl;
         o << ( *im ).second->name << endl;
         list<Edge*> neighbors = ( *im ).second->neighbors;
         list<Edge*>::iterator e;
      }
      return o;
   }
};

struct compare
{

   bool operator() ( Node * &a, Node * &b ) const
   {
      // least to greatest
      return b->cost < a->cost;
   }
};
// for each solution, reset node information
void reset_nodes ( NodeMap &nm )
{
   map<string, Node*>::iterator im;
   for ( im = nm.nodemap.begin(); im != nm.nodemap.end(); im++ )
   {
      ( *im ).second->cost = 0;
      ( *im ).second->back_pointer = 0;
      ( *im ).second->visited = false;
   }
}

void dijkstra ( string s, NodeMap &nodes )
{
   Student myStudent [500]; //create an array of objects

   int i = 0;

   // check and report or abort
   Node* source = nodes.nodemap[s];
   if ( source == 0 )
   {
      cout << "Sorry we don't fly from " << s << endl;
      return;
   }
   reset_nodes ( nodes );

   // put the source into pq and loop until empty
   priority_queue<Node *, deque<Node*>, compare > pq;
   pq.push ( source );
   while ( !pq.empty() )
   {
      // process least cost node.
      Node* curr = pq.top();
      pq.pop();
      curr->visited = true;
      // process neighbors
      list<Edge*>::iterator edge; 
      for ( edge = curr->neighbors.begin(); edge != curr->neighbors.end(); edge++ )
      {
         Node *ne = ( *edge )->dest;
         if ( !ne->visited )
         {
            ne->cost += ( *edge )->weight + curr->cost;
            ne->visited = true;
            ne->back_pointer = curr;
            //cout << "Cheapest price to "<< ne->name << " = " << ne->cost << endl; 

            myStudent[i].name = ne->name;
            myStudent[i].tuition = ne->cost;
            i++; 


            pq.push ( ne );
         }
      }
   }

   std::sort ( myStudent, myStudent + i, SortStudentByName );
   for ( int j = 0; j < i; j++ )
   {
      cout << "Cheapest price from " << s << " to "  << myStudent[j].name << " = " << myStudent[j].tuition << endl;
   }
}

void get_graph ( string const &filename, NodeMap &node_map )
{
   ifstream inf ( filename.c_str() );
   string from, to;
   double weight;
   while ( !inf.eof() )
   {
      inf >> from >> to >> weight;
      if ( inf.good() )
      {
         Node *Target = node_map.find_in_nodemap ( to );
         Node *Source = node_map.find_in_nodemap ( from );
         Edge *connector = new Edge ( weight, Target );
         Source->neighbors.push_back ( connector );
      }
   }
}
int main()
{
   NodeMap nodes;
   ifstream inf;
   string filename;
   cout << "Enter filename : ";
   cin >> filename;
   inf.open ( filename.c_str() );
   get_graph ( filename, nodes );

   
   cout << "Enter start city : ";
   cin >> s;
   dijkstra ( s, nodes );

   system ( "PAUSE" );
   return 0;
}
commented: You're long enough on this forum to know that giving full code isn't allowed !! -1

iamthwee, you should have known better: Do you know that we don't give full code on this forum?
How is he supposed to learn from code we write for him?
You can only learn to program by writing code yourself, not by copying it from someone else.
BTW, Apparently you even don't understand why to avoid [B]system("pause");[/B] , and because some people are too lazy to just take a look at my signature and review the link I am going to copy what's in my signature and paste it below:
Avoid using system("pause"); use cin.get(); instead.
(and here's the reason: http://www.gidnetwork.com/b-61.html, and please take the time to review it carefully!!)

commented: I agree :) +1
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.