// ==============================================================================// ------------------------------------------------------------------------------// SOURCE NAME	: UGraph.h	// AUTHOR	: Neil Kemp// DESCRIPTION	: This module declares and defines a generic class to define and//		: manipulate undirected graphs.// ------------------------------------------------------------------------------// ==============================================================================#include #ifndef ___U_GRAPH_H___#define ___U_GRAPH_H___template  class UGraph{private:	template  struct	UGraph_Node_s	{	T				Data;		std::vector<unsigned int>	Adjacency_List;	};	std::vector >		___Node_List;	void					(*___Traversal_Callback_Function_Pointer)(const T &Data);	std::vector<bool>			___Traversal_Nodes_Visited_List;	std::vector<bool>			___Adjacent_Nodes_Visited_List;		void					___Add_Node_To_List(const T &Data);	bool					___Delete_Node_From_List(unsigned int Index);	bool					___Retrieve_Node_Data(unsigned int Index, T &Data_Out) const;	void					___DFS(unsigned int Node_Index);	void					___BFS(unsigned int Node_Index, bool Traverse_Adjacents);public:	UGraph(void);	unsigned int				Add_Node(const T &Data);	bool					Add_Edge(unsigned int Node_Index_A, unsigned int Node_Index_B);	bool					Delete_Node(unsigned int Index);	bool					Delete_Edge(unsigned int Node_Index_A, unsigned int Node_Index_B);	bool					Get_Node_Data(unsigned int Node_Index, T &Data_Out) const;	bool					Get_Node_Data(unsigned int Node_Index, T &Data_Out, 							      std::vector<unsigned int> &Adjacency_List) const;	bool					Get_Node_Adjacency_List(unsigned int Node_Index, 									std::vector<unsigned int> &Adjacency_List) const;		unsigned int				Get_Node_Count(void) const;	void					Depth_First_Search(void(*Function_Pointer)(const T &Data));	void					Breadth_First_Search(void(*Function_Pointer)(const T &Data));		bool					Save_To_File(FILE* File_Pointer) const;	bool					Load_From_File(FILE* File_Pointer);};// PRI M FUNCTION	: ___Add_Node_To_List()// PARAMETERS		: p0(IN) const &T - Node data of type T// RETURN VALUE		: void// DESCRIPTION		: Add a node to the private vector list of UGraph_Node_s //			: with initialized data of type T// ------------------------------------------------------------------------------template  void UGraph::___Add_Node_To_List(const T &Data){	// Create the node	UGraph_Node_s Temp_Node;	Temp_Node.Data = Data;	// Add the node to the list	___Node_List.push_back(Temp_Node);}// End ___Add_Node_To_List()// ------------------------------------------------------------------------------// PRI M FUNCTION	: ___Delete_Node_From_List()// PARAMETERS		: p0(IN) unsigned int - Node index// RETURN VALUE		: bool// DESCRIPTION		: Delete a node from the private vector list of nodes at //			: the index parameter location. Shift all adjacency indices//			: which are > to the index deleted.// ------------------------------------------------------------------------------template  bool UGraph::___Delete_Node_From_List(unsigned int Index){	// Check bounds of index	if(Index >= ___Node_List.size())		return false;	// Remove every edge referenced in the node's adjacency list	size_t Adjacency_List_Size = ___Node_List[Index].Adjacency_List.size();	for(size_t i=0; i	{		Delete_Edge(Index, ___Node_List[Index].Adjacency_List);		// Decrement the loop variable to compensate for deleted item		i--;		// Decrement the adjacency list size		Adjacency_List_Size --;	}	// Get a node iterator	std::vector >::iterator I = ___Node_List.begin() + Index;	// Erase Node	___Node_List.erase(I);		// Shift all adjacency lists for every node	size_t NList_Size = ___Node_List.size();	for(size_t i=0; i	{		size_t AList_Size = ___Node_List.Adjacency_List.size();		for(size_t j=0; j		{			// Decrement the adjacency list indices if greater than deleted index			if(___Node_List.Adjacency_List[j] > Index)				___Node_List.Adjacency_List[j]--;		}	}	return true;}// End ___Add_Node_To_List()// ------------------------------------------------------------------------------// PRI M FUNCTION	: ___Retrieve_Node_Data()// PARAMETERS		: p0(IN) unsigned int - Node index//			: p1(OUT) &T - The data reference to be returned// RETURN VALUE		: bool// DESCRIPTION		: Return the node data located in the node specified by the//			: index parameter using an ouput parameter reference.// ------------------------------------------------------------------------------template  bool UGraph::___Retrieve_Node_Data(unsigned int Index, 							    T &Data_Out) const{	// Check bounds of index	if(Index >= ___Node_List.size())		return false;	// Set the data parameter to the specified data	Data_Out = ___Node_List[Index].Data;	return true;}// End ___Retrieve_Node_Data()// ------------------------------------------------------------------------------// PRI M FUNCTION	: ___DFS()// PARAMETERS		: p0(IN) unsigned int - Node index// RETURN VALUE		: void// DESCRIPTION		: A recursive Depth-First-Search function calls the private//			: Traversal Callback Function for every node visited in the//			: graph.// ------------------------------------------------------------------------------template  void UGraph::___DFS(unsigned int Node_Index){	// Mark node as visited	___Traversal_Nodes_Visited_List[Node_Index] = true;	// Call the traversal callback function	___Traversal_Callback_Function_Pointer(___Node_List[Node_Index].Data);	// Recursive call for every unvisited adjacent node	size_t Adjacency_List_Size = ___Node_List[Node_Index].Adjacency_List.size();	for(size_t i=0; i	{		// DFS for every unvisited adjacent node		if(___Traversal_Nodes_Visited_List[				___Node_List[Node_Index].Adjacency_List] == false)			___DFS(___Node_List[Node_Index].Adjacency_List);	}}// End ___DFS()// ------------------------------------------------------------------------------// PRI M FUNCTION	: ___BFS()// PARAMETERS		: p0(IN) unsigned int - Node index//			: p1(IN) bool - Traverse adjacent nodes or not// RETURN VALUE		: void// DESCRIPTION		: A recursive Breadth-First-Search function calls the private//			: Traversal Callback Function for every node visited in the//			: graph.// ------------------------------------------------------------------------------template  void UGraph::___BFS(unsigned int Node_Index, 					     bool Traverse_Adjacents){	// If the node is unvisited	if(	___Traversal_Nodes_Visited_List[Node_Index] == false)	{		// Call the traversal callback function		___Traversal_Callback_Function_Pointer(___Node_List[Node_Index].Data);		// Mark node as visited		___Traversal_Nodes_Visited_List[Node_Index] = true;	}			// Traverse adjacent nodes	if(Traverse_Adjacents)	{		// Set the adjacent nodes have been visited		___Adjacent_Nodes_Visited_List[Node_Index] = true;		// Recursive call for adjacent nodes		size_t Adjacency_List_Size = ___Node_List[Node_Index].Adjacency_List.size();		for(size_t i=0; i		{			// DFS for every unvisited adjacent node - 			// the BFS call IS NOT allowed to traverse adjacent nodes			if(___Traversal_Nodes_Visited_List[___Node_List[Node_Index].Adjacency_List] == false)				___BFS(___Node_List[Node_Index].Adjacency_List, false);		}		// Recursive call for adjacent nodes		for(size_t i=0; i		{			// DFS for every unvisited adjacent node - 			// the BFS call IS allowed to traverse adjacent nodes			if(___Adjacent_Nodes_Visited_List[___Node_List[Node_Index].Adjacency_List] == false)				___BFS(___Node_List[Node_Index].Adjacency_List, true);		}	}	}// End ___BFS()// ------------------------------------------------------------------------------// PUB M FUNCTION	: UGraph() CONSTRUCTOR// PARAMETERS		: void// RETURN VALUE		: void// DESCRIPTION		: The default constructor// ------------------------------------------------------------------------------template  UGraph::UGraph(void){	}// End UGraph() CONSTRUCTOR// ------------------------------------------------------------------------------// PUB M FUNCTION	: Add_Node()// PARAMETERS		: p0(IN) const &T - Data to initialize node with// RETURN VALUE		: unsigned int - The index of the node just added// DESCRIPTION		: Add a node to the graph and return the index where it can//			: be accessed.// ------------------------------------------------------------------------------template  unsigned int UGraph::Add_Node(const T &Data){	// Add the node	___Add_Node_To_List(Data);	// Return the new node index	return (unsigned int)___Node_List.size() - 1;	}// End Add_Node()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Add_Edge()// PARAMETERS		: p0(IN) unsigned int - Node index A//			: p1(IN) unsigned int - Node index B// RETURN VALUE		: bool// DESCRIPTION		: Add an edge between two nodes located at the specified //			: indices.// ------------------------------------------------------------------------------template  bool UGraph::Add_Edge(unsigned int Node_Index_A, 					       unsigned int Node_Index_B){	// Check bounds of indices	if(Node_Index_A >= ___Node_List.size())		return false;	if(Node_Index_B >= ___Node_List.size())		return false;	// Add undirected edge between both nodes by registering	// each in both nodes adjacency lists	___Node_List[Node_Index_A].Adjacency_List.push_back(Node_Index_B);	___Node_List[Node_Index_B].Adjacency_List.push_back(Node_Index_A);	return true;}// End Add_Edge()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Delete_Node()// PARAMETERS		: p0(IN) unsigned int - Node index// RETURN VALUE		: bool// DESCRIPTION		: Delete a node from the graph// ------------------------------------------------------------------------------template  bool UGraph::Delete_Node(unsigned int Index){	// Delete the node from the list	return ___Delete_Node_From_List(Index);}// End Delete_Node()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Delete_Edge()// PARAMETERS		: p0(IN) unsigned int - Node index A//			: p1(IN) unsigned int - Node index B// RETURN VALUE		: bool// DESCRIPTION		: Delete an edge that connects two nodes specified with the//			: parameter indices.// ------------------------------------------------------------------------------template  bool UGraph::Delete_Edge(unsigned int Node_Index_A, 						  unsigned int Node_Index_B){	// Check bounds of indices	if(Node_Index_A >= ___Node_List.size())		return false;	if(Node_Index_B >= ___Node_List.size())		return false;	// Update the adjacency lists of the two nodes	// Remove references to node[index_b] in node[index_a] 	size_t List_Size = ___Node_List[Node_Index_A].Adjacency_List.size();	for(size_t i=0; i	{		// Check for references to node[index_b] in node[index_a]		if(___Node_List[Node_Index_A].Adjacency_List == Node_Index_B)		{			// Delete reference			std::vector<unsigned int>::iterator I = 					___Node_List[Node_Index_A].Adjacency_List.begin() + i;			___Node_List[Node_Index_A].Adjacency_List.erase(I);				// Decrement the loop variable to compensate for deleted item			i--;			// Decrement the list size			List_Size --;		}	}	// Remove references to node[index_a] in node[index_b] 	List_Size = ___Node_List[Node_Index_B].Adjacency_List.size();	for(size_t i=0; i	{		// Check for references to node[index_b] in node[index_a]		if(___Node_List[Node_Index_B].Adjacency_List == Node_Index_A)		{			// Delete reference			std::vector<unsigned int>::iterator I = 					___Node_List[Node_Index_B].Adjacency_List.begin() + i;			___Node_List[Node_Index_B].Adjacency_List.erase(I);				// Decrement the loop variable to compensate for deleted item			i--;			// Decrement the list size			List_Size --;		}	}	return true;}// End Delete_Edge()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Get_Node_Data() OVERLOADED A// PARAMETERS		: p0(IN) unsigned int - Node index//			: p1(OUT) &T - The returned data// RETURN VALUE		: bool// DESCRIPTION		: Return the node data from the node specified at the index//			: parameter// ------------------------------------------------------------------------------template  bool UGraph::Get_Node_Data(unsigned int Node_Index, 						    T &Data_Out) const{	// Check bounds of index	if(Node_Index >= ___Node_List.size())		return false;	// Set output parameter data	Data_Out = ___Node_List[Node_Index].Data;	return true;}// End Get_Node_Data() OVERLOADED A// ------------------------------------------------------------------------------// PUB M FUNCTION	: Get_Node_Data() OVERLOADED B// PARAMETERS		: p0(IN) unsigned int - Node index//			: p1(OUT) &T - The returned data//			: p2(OUT) &std::vector - Returned list of //			:				       adjacent node indices// RETURN VALUE		: bool// DESCRIPTION		: Return the node data and the list of adjacent node indices//			: from the node specified at the index parameter.// ------------------------------------------------------------------------------template  bool UGraph::Get_Node_Data(unsigned int Node_Index, 						    T &Data_Out, 						    std::vector<unsigned int> &Adjacency_List) const{	// Check bounds of index	if(Node_Index >= ___Node_List.size())		return false;	// Set output parameter data	Data_Out = ___Node_List[Node_Index].Data;	// Set output parameter adjacency list	Adjacency_List = ___Node_List[Node_Index].Adjacency_List;	return true;}// End Get_Node_Data() OVERLOADED B// ------------------------------------------------------------------------------// PUB M FUNCTION	: Get_Node_Adjacency_List()// PARAMETERS		: p0(IN) unsigned int - Node index//			: p1(OUT) &std::vector - Returned list of //			:  				       adjacent node indices// RETURN VALUE		: bool// DESCRIPTION		: Return the list of adjacent node indices from the node //			: specified at the index parameter.// ------------------------------------------------------------------------------template  bool UGraph::Get_Node_Adjacency_List(unsigned int Node_Index, 							      std::vector<unsigned int> &Adjacency_List) const{	// Check bounds of index	if(Node_Index >= ___Node_List.size())		return false;	// Set output parameter adjacency list	Adjacency_List = ___Node_List[Node_Index].Adjacency_List;	return true;}	// End Get_Node_Adjacency_List()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Get_Node_Count()// PARAMETERS		: void// RETURN VALUE		: unsigned int// DESCRIPTION		: Return the number of nodes in the graph// ------------------------------------------------------------------------------template  unsigned int UGraph::Get_Node_Count(void) const{	return ___Node_List.size();}// End Get_Node_Adjacency_List()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Depth_First_Search()// PARAMETERS		: p0(IN) void(*)(const T &Data) - The callback function// RETURN VALUE		: void// DESCRIPTION		: Seach the graph using a depth first search. The callback//			: function is called for every node visited and is passed the//			: node data as a parameter.// ------------------------------------------------------------------------------template  void UGraph::Depth_First_Search(void(*Function_Pointer)(const T &Data)){	// Check for graph nodes	if(!___Node_List.size())		return;	// Clear and resize the nodes visited list	___Traversal_Nodes_Visited_List.resize(___Node_List.size());	___Traversal_Nodes_Visited_List.assign(___Node_List.size(), false);	// Set the callback function pointer	___Traversal_Callback_Function_Pointer = Function_Pointer;    	// Traverse the nodes	___DFS(0);	// Dump the visited list data	___Traversal_Nodes_Visited_List.clear();}// End Depth_First_Search()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Breadth_First_Search()// PARAMETERS		: p0(IN) void(*)(const T &Data) - The callback function// RETURN VALUE		: void// DESCRIPTION		: Seach the graph using a breadth first search. The callback//			: function is called for every node visited and is passed the//			: node data as a parameter.// ------------------------------------------------------------------------------template  void UGraph::Breadth_First_Search(void(*Function_Pointer)(const T &Data)){	// Check for graph nodes	if(!___Node_List.size())		return;	// Clear and resize the nodes visited list	___Traversal_Nodes_Visited_List.resize(___Node_List.size());	___Traversal_Nodes_Visited_List.assign(___Node_List.size(), false);	// Clear and resize the adjacent visited list	___Adjacent_Nodes_Visited_List.resize(___Node_List.size());	___Adjacent_Nodes_Visited_List.assign(___Node_List.size(), false);	// Set the callback function pointer	___Traversal_Callback_Function_Pointer = Function_Pointer;	// Traverse the nodes	___BFS(0, true);	// Dump the visited lists data	___Traversal_Nodes_Visited_List.clear();	___Adjacent_Nodes_Visited_List.clear();}// End Breadth_First_Search()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Save_To_File()// PARAMETERS		: p0(IN) FILE* - A file pointer already initialized to write //			:		 binary data and set to the proper location //			:		 of the file where the graph is the be //			:		 written.// RETURN VALUE		: bool// DESCRIPTION		: Save the graph to a file using a file pointer parameter//			: which is initialized to write binary.// ------------------------------------------------------------------------------template  bool UGraph::Save_To_File(FILE* File_Pointer) const{	// Check file pointer	if(!File_Pointer)		return false;	// Graph is saved in the following format	// unsigned int - Number of nodes	// For each node	//	T - The data for the node	//	unsigned int - Number of adjacent indices	//	For each adjacent index	//		unsigned int - Adjacent index	unsigned int Node_Count;	unsigned int Adjacency_Count;	// Ouput number of graph nodes	Node_Count = (unsigned int)___Node_List.size();	fwrite(&Node_Count, 1, sizeof(unsigned int), File_Pointer);		// For every node    	for(unsigned int i=0; i	{		// Ouput the graph node data		fwrite(&___Node_List.Data, 1, sizeof(T), File_Pointer);				// Output the number of adjacent graph nodes		Adjacency_Count = (unsigned int)___Node_List.Adjacency_List.size();		fwrite(&Adjacency_Count, 1, sizeof(unsigned int), File_Pointer);		// For every adjacent index		for(unsigned int j=0; j		{			// Ouput the graph adjacent indices			fwrite(&___Node_List.Adjacency_List[j], 1, sizeof(unsigned int), File_Pointer);		}			}	return true;}// End Save_To_File()// ------------------------------------------------------------------------------// PUB M FUNCTION	: Load_From_File()// PARAMETERS		: p0(IN) FILE* - A file pointer already initialized to read //			:		 binary data and set to the proper location //			:		 of the file where the graph is the be //			:		 read from.// RETURN VALUE		: bool// DESCRIPTION		: Load the graph from a file using a file pointer parameter//			: which is initialized to read binary.// ------------------------------------------------------------------------------template  bool UGraph::Load_From_File(FILE* File_Pointer){	// Check file pointer	if(!File_Pointer)		return false;	// Clear the node list	___Node_List.clear();	// Graph loaded in the following format	// unsigned int - Number of nodes	// For each node	//	T - The data for the node	//	unsigned int - Number of adjacent indices	//	For each adjacent index	//		unsigned int - Adjacent index	unsigned int Node_Count;	unsigned int Adjacency_Count;	// Read number of graph nodes	fread(&Node_Count, 1, sizeof(unsigned int), File_Pointer);	// Resize the node list to the size needed	___Node_List.resize(Node_Count);	// For every node    	for(unsigned int i=0; i	{		// Read in the graph node data		fread(&___Node_List.Data, 1, sizeof(T), File_Pointer);		// Read in the number of adjacent graph nodes		fread(&Adjacency_Count, 1, sizeof(unsigned int), File_Pointer);		// Resize node's adjacency list		___Node_List.Adjacency_List.resize(Adjacency_Count);		// For every adjacent index		for(unsigned int j=0; j		{			// Ouput the graph adjacent indices			fread(&___Node_List.Adjacency_List[j], 1, sizeof(unsigned int), File_Pointer);		}	}	return true;}// End Load_From_File()// ------------------------------------------------------------------------------#endif

// Save the graph from a temp filevoid Save_Graph(const UGraph<char> &Test_Graph){	FILE* File_Pointer = fopen("Test_Graph.ug", "wb");	if(!File_Pointer)		return;	Test_Graph.Save_To_File(File_Pointer);	fclose(File_Pointer);}// Load the graph from a temp filevoid Load_Graph(UGraph<char> &Test_Graph){	FILE* File_Pointer = fopen("Test_Graph.ug", "rb");	if(!File_Pointer)		return;	Test_Graph.Load_From_File(File_Pointer);	fclose(File_Pointer);}// The graph search callback function void Callback_Print(const char &Data){		std::cout << Data << " ";}// Test the graph interfaceint main(void){	UGraph<char> Test_Graph;	// Create this graph	//	 v	//	/|\	//     u w x	//    / \ 	//   q   t	//  / \	// r   s	// Add the nodes	Test_Graph.Add_Node('v');	Test_Graph.Add_Node('u');	Test_Graph.Add_Node('w');	Test_Graph.Add_Node('x');	Test_Graph.Add_Node('q');	Test_Graph.Add_Node('t');	Test_Graph.Add_Node('r');	Test_Graph.Add_Node('s');	// Add the edges	Test_Graph.Add_Edge(0, 1);	Test_Graph.Add_Edge(0, 2);	Test_Graph.Add_Edge(0, 3);	Test_Graph.Add_Edge(1, 4);	Test_Graph.Add_Edge(1, 5);	Test_Graph.Add_Edge(4, 6);	Test_Graph.Add_Edge(4, 7);	// Save the graph to file	Save_Graph(Test_Graph);		// BF Seach the graph to print it from 'v'	Test_Graph.Breadth_First_Search(Callback_Print);	std::cout << std::endl;	// DF Seach the graph to print it from 'v'	Test_Graph.Depth_First_Search(Callback_Print);	// Delete the root node	Test_Graph.Delete_Node(0);	//	  u w x	//       / \ 	//	q   t	//     / \	//    r   s	std::cout << std::endl;	// BF Seach the graph to print it from 'u'	Test_Graph.Breadth_First_Search(Callback_Print);    	// Add edges to reconnect 'w' and 'x'	Test_Graph.Add_Edge(0, 1);	Test_Graph.Add_Edge(3, 2);	//	  u	//       /|\ 	//	q t w	//     /|\	//    r s x	std::cout << std::endl;	// BF Seach the graph to print it from 'u'	Test_Graph.Breadth_First_Search(Callback_Print);	// Load the graph from file	Load_Graph(Test_Graph);		//	 v	//	/|\	//     u w x	//    / \ 	//   q   t	//  / \	// r   s		std::cout << std::endl;	// BF Seach the graph to print it from 'v'	Test_Graph.Breadth_First_Search(Callback_Print);	std::cout << "\n" << std::endl;	return 0;}