#include "StdAfx.h"
#include "NetworkGraph.h"
// ========================================================================================
// ========================================================================================
// ----------------------------------------------------------------------------------------
// NETWORK EDGE OBJECT
// ----------------------------------------------------------------------------------------
// ========================================================================================
NetworkGraphEdge::NetworkGraphEdge( )
{
in_list_ptr = NULL;
node1_ptr = NULL;
node2_ptr = NULL;
length = 0;
ID = 0;
}
NetworkGraphEdge::~NetworkGraphEdge( )
{
}
void NetworkGraphEdge::setParameters( NetworkGraphNode *n1, NetworkGraphNode *n2, float edge_length,
edge_id eID, LinkedListNode<NetworkGraphEdge> *list_node_ptr )
{
node1_ptr = n1;
node2_ptr = n2;
length = edge_length;
ID = eID;
in_list_ptr = list_node_ptr;
}
NetworkGraphNode* NetworkGraphEdge::getOtherSideNodePtr( NetworkGraphNode *node )
{
if ( node1_ptr->ID == node->ID )
{
return node2_ptr;
}
if ( node2_ptr->ID == node->ID )
{
return node1_ptr;
}
// Provided node did not belong to this edge!
return NULL;
}
// ========================================================================================
// ========================================================================================
// ----------------------------------------------------------------------------------------
// NETWORK NODE OBJECT
// ----------------------------------------------------------------------------------------
// ========================================================================================
NetworkGraphNode::NetworkGraphNode( )
{
flags = 0;
in_list_ptr = NULL;
ID = 0;
}
NetworkGraphNode::~NetworkGraphNode( )
{
}
void NetworkGraphNode::setParameters( Vect3usi &node_coordinate, node_id nID,
LinkedListNode<NetworkGraphNode> *list_node_ptr )
{
coordinate_list.insertAtEnd( node_coordinate );
ID = nID;
in_list_ptr = list_node_ptr;
}
int NetworkGraphNode::unlinkEdgeFromNode( edge_id eID )
{
// Search edge list for specified ID
LinkedListNode<NetworkGraphEdge*> *edge_node_ptr = edge_ptrs_list.getHeadPtr();
while ( edge_node_ptr )
{
if ( edge_node_ptr->item->ID == eID )
{ // Found it, now remove and return
edge_ptrs_list.removeNode( edge_node_ptr );
return 0;
}
edge_node_ptr = edge_node_ptr->next;
}
// If we get this far, then we did not find a matching edge ID
return 1;
}
// ========================================================================================
// ========================================================================================
// ----------------------------------------------------------------------------------------
// GRAPH CLASS
// ----------------------------------------------------------------------------------------
// ========================================================================================
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
NetworkGraph::NetworkGraph( )
{
quick_coord_search_enabled = false;
next_id_val = 0;
number_of_nodes = 0;
number_of_edges = 0;
root_node_ptr = NULL;
nodes_in_set_list_ptr = new LinkedList<NetworkGraphNode>( 500 );
edges_in_set_list_ptr = new LinkedList<NetworkGraphEdge>( 500 );
}
NetworkGraph::~NetworkGraph( )
{
delete nodes_in_set_list_ptr;
delete edges_in_set_list_ptr;
if ( quick_coord_search_enabled )
{
for ( unsigned int i = 0; i < matrix_rows; i++ )
{
delete[] quick_search_matrix[i];
}
delete[] quick_search_matrix;
}
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
NetworkGraphNode* NetworkGraph::createNewNode( Vect3usi &new_coord )
{
LinkedListNode<NetworkGraphNode> *new_node_ptr = nodes_in_set_list_ptr->getNewNode();
new_node_ptr->item.setParameters( new_coord, next_id_val++, new_node_ptr );
nodes_in_set_list_ptr->insertAtEnd( new_node_ptr );
// If this is first node to be created, make it the root node
if ( nodes_in_set_list_ptr->getSize() == 1 )
{
root_node_ptr = &new_node_ptr->item;
}
++ number_of_nodes;
// If quick search enabled, add coordinate to matrix
if ( quick_coord_search_enabled )
{
NetworkGraphNode *tmp_node_ptr = &(new_node_ptr->item);
quick_search_matrix[new_coord.z][new_coord.y].insertAtEnd( tmp_node_ptr );
}
return &(new_node_ptr->item);
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
NetworkGraphNode* NetworkGraph::createNewNodeAndLink( Vect3usi &new_coord, NetworkGraphNode *link_to_node_ptr, float distance )
{
NetworkGraphNode *new_node_ptr = createNewNode( new_coord );
createNewEdge( new_node_ptr, link_to_node_ptr, distance );
return new_node_ptr;
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
NetworkGraphEdge* NetworkGraph::createNewEdge( NetworkGraphNode *node1_ptr, NetworkGraphNode *node2_ptr, float distance )
{
LinkedListNode<NetworkGraphEdge> *new_edge_ptr = edges_in_set_list_ptr->getNewNode();
NetworkGraphEdge *cur_edge_ptr;
new_edge_ptr->item.setParameters( node1_ptr, node2_ptr, distance, next_id_val++, new_edge_ptr );
edges_in_set_list_ptr->insertAtEnd( new_edge_ptr );
if ( node1_ptr )
{
cur_edge_ptr = &new_edge_ptr->item;
node1_ptr->edge_ptrs_list.insertAtEnd( cur_edge_ptr );
}
// Avoid double adding if edge loops back to same node.
if ( node2_ptr != node1_ptr )
{
cur_edge_ptr = &new_edge_ptr->item;
node2_ptr->edge_ptrs_list.insertAtEnd( cur_edge_ptr );
}
// There are place holder edges with a distance of '0', do not count them as edges
if ( distance > 0.0f )
{
++ number_of_edges;
}
#if CHECK_GRAPH_INTEGRITY
if ( checkSingleEdgeIntegrity(&new_edge_ptr->item) == false )
{
write_to_log("NetworkGraph::createNewEdge - ERROR - Integrity test failed.");
}
#endif
return &new_edge_ptr->item;
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
int NetworkGraph::deleteEdge( NetworkGraphEdge *edge_ptr )
{
// If edge connects same node, only need to unlink once
if ( edge_ptr->node1_ptr == edge_ptr->node2_ptr )
{
if ( edge_ptr->node1_ptr->unlinkEdgeFromNode(edge_ptr->ID) )
{
return 3;
}
}
else
{
// First try to unlink the edge from nodes it is connected to
if ( edge_ptr->node1_ptr->unlinkEdgeFromNode(edge_ptr->ID) )
{
// Edge did not belong to node
return 1;
}
if ( edge_ptr->node2_ptr->unlinkEdgeFromNode(edge_ptr->ID) )
{
return 2;
}
}
// Now remove the edge from graph set
edges_in_set_list_ptr->removeNode( edge_ptr->in_list_ptr );
-- number_of_edges;
#if CHECK_GRAPH_INTEGRITY
//if ( checkGraphIntegrity() == false )
//{
// write_to_log("NetworkGraph::deleteEdge - ERROR - Integrity test failed.");
//}
#endif
return 0;
}
// ----------------------------------------------------------------------------------------
//
// Description - Enables quick searching for coordinates. Uses more memory.
// Note: Adding additional coordinates to a node should be followed
// by a call to updateQuickSearchMatrix() before any search operations.
// ----------------------------------------------------------------------------------------
void NetworkGraph::enableQuickCoordSearch( Vect3usi &coord_limits )
{
if ( quick_coord_search_enabled == false )
{
quick_coord_search_enabled = true;
matrix_rows = coord_limits.z;
quick_search_matrix = new LinkedList<NetworkGraphNode*>* [matrix_rows];
for ( unsigned int i = 0; i < matrix_rows; i++ )
{
quick_search_matrix[i] = new LinkedList<NetworkGraphNode*> [coord_limits.y];
}
// Add coordinates for any existings nodes
LinkedListNode<NetworkGraphNode> *cur_node_ptr = nodes_in_set_list_ptr->getHeadPtr();
while ( cur_node_ptr )
{
updateQuickSearchMatrix( &cur_node_ptr->item );
cur_node_ptr = cur_node_ptr->next;
}
}
}
// ----------------------------------------------------------------------------------------
//
// Description - Disables quick search, and frees all associated memory
//
// ----------------------------------------------------------------------------------------
void NetworkGraph::disableQuickCoordSearch( )
{
if ( quick_coord_search_enabled )
{
quick_coord_search_enabled = false;
for ( unsigned int i = 0; i < matrix_rows; i++ )
{
delete[] quick_search_matrix[i];
}
delete[] quick_search_matrix;
}
}
// ----------------------------------------------------------------------------------------
//
// Description - Validates quick search for specific node. Should be called after
// additional coordinates are added to node
// ----------------------------------------------------------------------------------------
void NetworkGraph::updateQuickSearchMatrix( NetworkGraphNode *node_ptr )
{
if ( quick_coord_search_enabled )
{
LinkedListNode<Vect3usi> *cur_coord_ptr = node_ptr->coordinate_list.getHeadPtr( );
while ( cur_coord_ptr )
{
// Add coordinate if it does not belong to node already
if ( findNodeWithCoordinate( cur_coord_ptr->item ) == NULL )
{
quick_search_matrix[cur_coord_ptr->item.z][cur_coord_ptr->item.y].insertAtEnd( node_ptr );
}
cur_coord_ptr = cur_coord_ptr->next;
}
}
}
// ----------------------------------------------------------------------------------------
//
// Description - Used for degree 2 node removal! Will remove the middle node,
// connecting the others together (adding distances)
// ----------------------------------------------------------------------------------------
int NetworkGraph::convertNodeToEdge( NetworkGraphNode *node_to_delete_ptr )
{
// Make sure node only has 2 edges
if ( node_to_delete_ptr->edge_ptrs_list.getSize() != 2 )
{
write_to_log( "NetworkGraph::convertNodeToEdge - Warning - Delete Node called on a node with not exactly 2 outgoing edges." );
return 1;
}
// Add the distances of the two edges
float tot_dist = node_to_delete_ptr->edge_ptrs_list.getHeadPtr()->item->length +
node_to_delete_ptr->edge_ptrs_list.getTailPtr()->item->length;
// Fnd the two nodes to connect
NetworkGraphNode *node0 = node_to_delete_ptr->edge_ptrs_list.getHeadPtr()->item->getOtherSideNodePtr( node_to_delete_ptr );
NetworkGraphNode *node1 = node_to_delete_ptr->edge_ptrs_list.getTailPtr()->item->getOtherSideNodePtr( node_to_delete_ptr );
// Delete both edges
if ( deleteEdge( node_to_delete_ptr->edge_ptrs_list.getHeadPtr()->item ) ||
deleteEdge( node_to_delete_ptr->edge_ptrs_list.getTailPtr()->item ) )
{
write_to_log( "NetworkGraph::convertNodeToEdge - Warning - Could not unlink node to delete." );
return 1;
}
// Delete node
if ( node_to_delete_ptr == root_node_ptr )
{
nodes_in_set_list_ptr->removeNode( node_to_delete_ptr->in_list_ptr );
findRootNode();
}
else
{
nodes_in_set_list_ptr->removeNode( node_to_delete_ptr->in_list_ptr );
}
-- number_of_nodes;
// We have two possible cases:
// 1) The node to delete has two edges to a single other node (node0 == node1). In this case we want to add a
// single self looping edge to that node. A sub-case is if the remaining node was last one in graph set,
// in which case the graph becomes a single edge (one loop).
if ( node0 == node1 )
{
if ( (number_of_nodes == 1) && (number_of_edges == 0) )
{
number_of_nodes = 0;
nodes_in_set_list_ptr->removeAllNodes();
createNewEdge( NULL, NULL, tot_dist );
}
else
{
// Add two edges (one of length 0) to indicate that there are really two connections (even though it is one edge)
createNewEdge( node0, node1, tot_dist );
createNewEdge( node1, node0, 0.0f );
}
}
// 2) Normal case of two different nodes, simply relink them
else
{
createNewEdge( node0, node1, tot_dist );
}
return 0;
}
// ----------------------------------------------------------------------------------------
//
// Description - Breaks link between two nodes, and does a union of all outgoing edges.
// If nodes are connected by more than 1 edge, only the specified edge gets deleted.
// ----------------------------------------------------------------------------------------
int NetworkGraph::combineNeighboringNodes( NetworkGraphNode *to_keep_ptr, NetworkGraphNode *to_merge_ptr, NetworkGraphEdge *edge_ptr )
{
float distance = edge_ptr->length;
// If to_keep_ptr and to_merge_ptr nodes are one and the same, nothing more than edge deletion needs to be done
if ( to_keep_ptr == to_merge_ptr )
{
deleteEdge( edge_ptr );
// There is also a zero length edge that needs to be deleted
LinkedListNode<NetworkGraphEdge*> *edge_node_ptr = to_keep_ptr->edge_ptrs_list.getHeadPtr();
while ( edge_node_ptr )
{
if ( (edge_node_ptr->item->node1_ptr->ID == edge_node_ptr->item->node2_ptr->ID) &&
(edge_node_ptr->item->length == 0.0f) )
{
deleteEdge( edge_node_ptr->item );
return 0;
}
edge_node_ptr = edge_node_ptr->next;
}
return 0;
}
else
{
// Find and delete the connecting edge(s)
LinkedListNode<NetworkGraphEdge*> *edge_node_ptr = to_keep_ptr->edge_ptrs_list.getHeadPtr();
while ( edge_node_ptr )
{
// See if either of the edge connects nodes
if ( (edge_node_ptr->item->node1_ptr->ID == to_merge_ptr->ID) ||
(edge_node_ptr->item->node2_ptr->ID == to_merge_ptr->ID) )
{
// If this linking edge is not the desired one, create a new self looping edge
if ( edge_node_ptr->item->ID != edge_ptr->ID )
{
createNewEdge( to_keep_ptr, to_keep_ptr, 0.0f );
createNewEdge( to_keep_ptr, to_keep_ptr, edge_node_ptr->item->length );
}
if ( edge_node_ptr->next )
{
edge_node_ptr = edge_node_ptr->next;
deleteEdge( edge_node_ptr->prev->item );
}
else
{
deleteEdge( edge_node_ptr->item );
edge_node_ptr = NULL;
}
}
else
{
edge_node_ptr = edge_node_ptr->next;
}
}
if ( distance == 0.0f )
{
// No connecting edge found
write_to_log( "NetworkGraph::combineNeighboringNodes - Warning - No edge links found." );
return 2;
}
// Add all of the merging nodes edges to the remaining node
LinkedListNode<NetworkGraphEdge*> *edge_to_merge_node_ptr = to_merge_ptr->edge_ptrs_list.getHeadPtr();
while ( edge_to_merge_node_ptr )
{
if ( edge_to_merge_node_ptr->item->length > 0.0f )
{
createNewEdge( to_keep_ptr, edge_to_merge_node_ptr->item->getOtherSideNodePtr(to_merge_ptr),
distance + edge_to_merge_node_ptr->item->length );
if ( edge_to_merge_node_ptr->item->node1_ptr->ID == edge_to_merge_node_ptr->item->node2_ptr->ID )
{
createNewEdge( to_keep_ptr, to_keep_ptr, 0.0f );
}
}
edge_to_merge_node_ptr = edge_to_merge_node_ptr->next;
}
// Break all remaining links to 'to_merge_ptr' node and delete it
while ( to_merge_ptr->edge_ptrs_list.getSize() > 0 )
{
this->deleteEdge( to_merge_ptr->edge_ptrs_list.getHeadPtr()->item );
}
}
if ( to_merge_ptr == root_node_ptr )
{
nodes_in_set_list_ptr->removeNode( to_merge_ptr->in_list_ptr );
findRootNode();
}
else
{
nodes_in_set_list_ptr->removeNode( to_merge_ptr->in_list_ptr );
}
return 0;
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
bool NetworkGraph::doesCoordinateBelongToNode( NetworkGraphNode *node_ptr, Vect3usi &coordinate )
{
LinkedListNode<Vect3usi> *cur_coord_ptr = node_ptr->coordinate_list.getHeadPtr();
while ( cur_coord_ptr )
{
if ( cur_coord_ptr->item == coordinate )
{
return true;
}
cur_coord_ptr = cur_coord_ptr->next;
}
return false;
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
NetworkGraphNode* NetworkGraph::findNodeWithCoordinate( Vect3usi &coordinate )
{
if ( quick_coord_search_enabled )
{
LinkedListNode<NetworkGraphNode*> *cur_node_ptr = quick_search_matrix[coordinate.z][coordinate.y].getHeadPtr( );
while ( cur_node_ptr )
{
if ( doesCoordinateBelongToNode(cur_node_ptr->item, coordinate) == true )
{
return cur_node_ptr->item;
}
cur_node_ptr = cur_node_ptr->next;
}
}
else
{
LinkedListNode<NetworkGraphNode> *cur_node_ptr = nodes_in_set_list_ptr->getHeadPtr();
while ( cur_node_ptr )
{
if ( doesCoordinateBelongToNode(&cur_node_ptr->item, coordinate) == true )
{
return &cur_node_ptr->item;
}
cur_node_ptr = cur_node_ptr->next;
}
}
// Couldn't find a node with specified coordinate!
return NULL;
}
// ----------------------------------------------------------------------------------------
//
// Description - When the graph gets changed, the current root node might become disconnected.
// This will find a new one (least degree node in graph)
// ----------------------------------------------------------------------------------------
int NetworkGraph::findRootNode()
{
LinkedListNode<NetworkGraphNode> *cur_node_ptr;
unsigned int lowest_degree = 0xFFFFFFFF;
if ( nodes_in_set_list_ptr->getSize() == 0 )
{
write_to_log("NetworkGraph::findRootNode - Error - No nodes present in graph.");
return 1;
}
// Find node with lowest degree
cur_node_ptr = nodes_in_set_list_ptr->getHeadPtr();
while ( cur_node_ptr )
{
if ( cur_node_ptr->item.edge_ptrs_list.getSize() < lowest_degree )
{
lowest_degree = cur_node_ptr->item.edge_ptrs_list.getSize();
root_node_ptr = &cur_node_ptr->item;
}
cur_node_ptr = cur_node_ptr->next;
}
return 0;
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
int NetworkGraph::drawGraphInCube( DS_1b_cube *res_cube, bool mark_val )
{
LinkedListNode<NetworkGraphEdge> *cur_edge_node_ptr = edges_in_set_list_ptr->getHeadPtr();
while ( cur_edge_node_ptr )
{
res_cube->drawLine6Connected( cur_edge_node_ptr->item.node1_ptr->coordinate_list.getHeadPtr()->item,
cur_edge_node_ptr->item.node2_ptr->coordinate_list.getHeadPtr()->item,
mark_val );
cur_edge_node_ptr = cur_edge_node_ptr->next;
}
return 0;
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
int NetworkGraph::writeToTextFile( char *file_name )
{
// Open the output file
fstream fout;
fout.open( file_name, ios::out );
if( !fout.is_open() )
{
write_to_log("NetworkGraph::writeToTextFile - Cannot open file '%s'.", file_name);
return 1;
}
return writeToTextFile( fout );
}
// ----------------------------------------------------------------------------------------
//
// Description -
// ----------------------------------------------------------------------------------------
int NetworkGraph::writeToTextFile( fstream &out_stream )
{
// First print out information about each node in set
LinkedListNode<NetworkGraphNode> *cur_list_node_ptr = nodes_in_set_list_ptr->getHeadPtr();
LinkedListNode<Vect3usi> *cur_coord_ptr;
out_stream << "Node Count: " << nodes_in_set_list_ptr->getSize() << endl;
while ( cur_list_node_ptr )
{
out_stream << "N" << cur_list_node_ptr->item.ID << ":\t Degree: " << (int)cur_list_node_ptr->item.edge_ptrs_list.getSize() <<
"\t Coordinates: [";
// Write out a list of all coordinates belonging to node
cur_coord_ptr = cur_list_node_ptr->item.coordinate_list.getHeadPtr();
while ( cur_coord_ptr )
{
out_stream << " (" << cur_coord_ptr->item.x << "," << cur_coord_ptr->item.y << "," << cur_coord_ptr->item.z << ")";
cur_coord_ptr = cur_coord_ptr->next;
}
out_stream << " ]" << endl;
cur_list_node_ptr = cur_list_node_ptr->next;
}
out_stream << endl << endl;
// Now print out edge details
LinkedListNode<NetworkGraphEdge> *cur_list_edge_ptr = edges_in_set_list_ptr->getHeadPtr();
out_stream << "Edge Count: " << edges_in_set_list_ptr->getSize() << endl;
while ( cur_list_edge_ptr )
{
out_stream << "E" << cur_list_edge_ptr->item.ID << ":\tN" <<
cur_list_edge_ptr->item.node1_ptr->ID << " -> N" << cur_list_edge_ptr->item.node2_ptr->ID <<
"\t Length: " << cur_list_edge_ptr->item.length << endl;
cur_list_edge_ptr = cur_list_edge_ptr->next;
}
return 0;
}
// ----------------------------------------------------------------------------------------
//
// Description - For every edge, checks the connected nodes and makes sure that the edge
// is part of that node only one time. Returns FALSE if test fails.
// ----------------------------------------------------------------------------------------
bool NetworkGraph::checkGraphIntegrity()
{
unsigned int count;
LinkedListNode<NetworkGraphEdge*> *cur_edge_node_ptr;
LinkedListNode<NetworkGraphEdge> *cur_list_edge_ptr = edges_in_set_list_ptr->getHeadPtr();
while ( cur_list_edge_ptr )
{
count = 0;
// Count number of connections to this edge from first nodes
cur_edge_node_ptr = cur_list_edge_ptr->item.node1_ptr->edge_ptrs_list.getHeadPtr();
while ( cur_edge_node_ptr )
{
if ( cur_edge_node_ptr->item->ID == cur_list_edge_ptr->item.ID )
{
++ count;
}
cur_edge_node_ptr = cur_edge_node_ptr->next;
}
if ( count != 1 )
{
return false;
}
count = 0;
// Count number of connections to this edge from second node
cur_edge_node_ptr = cur_list_edge_ptr->item.node2_ptr->edge_ptrs_list.getHeadPtr();
while ( cur_edge_node_ptr )
{
if ( cur_edge_node_ptr->item->ID == cur_list_edge_ptr->item.ID )
{
++ count;
}
cur_edge_node_ptr = cur_edge_node_ptr->next;
}
if ( count != 1 )
{
return false;
}
cur_list_edge_ptr = cur_list_edge_ptr->next;
}
return true;
}
// ----------------------------------------------------------------------------------------
//
// Description - For every edge, checks the connected nodes and makes sure that the edge
// is part of that node only one time. Returns FALSE if test fails.
// ----------------------------------------------------------------------------------------
bool NetworkGraph::checkSingleEdgeIntegrity( NetworkGraphEdge *edge_ptr )
{
unsigned int count = 0;
LinkedListNode<NetworkGraphEdge*> *cur_edge_node_ptr;
// Count number of connections to this edge from first nodes
cur_edge_node_ptr = edge_ptr->node1_ptr->edge_ptrs_list.getHeadPtr();
while ( cur_edge_node_ptr )
{
if ( cur_edge_node_ptr->item->ID == edge_ptr->ID )
{
++ count;
}
cur_edge_node_ptr = cur_edge_node_ptr->next;
}
if ( count != 1 )
{
return false;
}
count = 0;
// Count number of connections to this edge from second node
cur_edge_node_ptr = edge_ptr->node2_ptr->edge_ptrs_list.getHeadPtr();
while ( cur_edge_node_ptr )
{
if ( cur_edge_node_ptr->item->ID == edge_ptr->ID )
{
++ count;
}
cur_edge_node_ptr = cur_edge_node_ptr->next;
}
if ( count != 1 )
{
return false;
}
return true;
}