#pragma once #include "DS_1b_cube.h" #include "LinkedList.h" // Set this to '1' to have an integrity test run on the graph any time something changes in it. #define CHECK_GRAPH_INTEGRITY 0 // Forward declaration (needed by Edge) class NetworkGraphNode; // ======================================================================================== // ======================================================================================== // ---------------------------------------------------------------------------------------- // NETWORK EDGE OBJECT // ---------------------------------------------------------------------------------------- // ======================================================================================== typedef unsigned int edge_id; class NetworkGraphEdge { public: NetworkGraphEdge( ); ~NetworkGraphEdge( ); void setParameters( NetworkGraphNode *n1, NetworkGraphNode *n2, float edge_length, edge_id eID, LinkedListNode<NetworkGraphEdge> *list_node_ptr ); NetworkGraphNode* getOtherSideNodePtr( NetworkGraphNode *node ); NetworkGraphNode *node1_ptr; NetworkGraphNode *node2_ptr; unsigned char flags; edge_id ID; float length; // For quick deletes LinkedListNode<NetworkGraphEdge> *in_list_ptr; }; // ======================================================================================== // ======================================================================================== // ---------------------------------------------------------------------------------------- // NETWORK NODE OBJECT // ---------------------------------------------------------------------------------------- // ======================================================================================== typedef unsigned int node_id; class NetworkGraphNode { public: NetworkGraphNode( ); ~NetworkGraphNode( ); void setParameters( Vect3usi &node_coordinate, node_id nID, LinkedListNode<NetworkGraphNode> *list_node_ptr ); int unlinkEdgeFromNode( edge_id eID ); LinkedList<NetworkGraphEdge*> edge_ptrs_list; unsigned char flags; node_id ID; // Coordinates belonging to this node LinkedList<Vect3usi> coordinate_list; // For quick deletes LinkedListNode<NetworkGraphNode> *in_list_ptr; }; // ======================================================================================== // ======================================================================================== // ---------------------------------------------------------------------------------------- // GRAPH CLASS // ---------------------------------------------------------------------------------------- // ======================================================================================== class NetworkGraph { public: NetworkGraph( ); ~NetworkGraph( ); // Operations for creating nodes and adding them to graph set NetworkGraphNode* createNewNode( Vect3usi &new_coord ); NetworkGraphNode* createNewNodeAndLink( Vect3usi &new_coord, NetworkGraphNode *link_to_node_ptr, float distance ); // Operations for creating edges and adding them to graph set NetworkGraphEdge* createNewEdge( NetworkGraphNode *node1_ptr, NetworkGraphNode *node2_ptr, float distance ); // Quick search operations void enableQuickCoordSearch( Vect3usi &coord_limits ); void disableQuickCoordSearch( ); void updateQuickSearchMatrix( NetworkGraphNode *node_ptr ); // Other operations int deleteEdge( NetworkGraphEdge *edge_ptr ); int convertNodeToEdge( NetworkGraphNode *node_to_delete ); int combineNeighboringNodes( NetworkGraphNode *to_keep_ptr, NetworkGraphNode *to_merge_ptr, NetworkGraphEdge *edge_ptr ); bool doesCoordinateBelongToNode( NetworkGraphNode *node_ptr, Vect3usi &coordinate ); int findRootNode(); NetworkGraphNode* findNodeWithCoordinate( Vect3usi &coordinate ); int drawGraphInCube( DS_1b_cube *res_cube, bool mark_val ); int writeToTextFile( char *file_name ); int writeToTextFile( fstream &out_stream ); bool checkGraphIntegrity(); bool checkSingleEdgeIntegrity( NetworkGraphEdge *edge_ptr ); NetworkGraphNode *root_node_ptr; unsigned int number_of_nodes, number_of_edges; unsigned int next_id_val; LinkedList<NetworkGraphNode> *nodes_in_set_list_ptr; LinkedList<NetworkGraphEdge> *edges_in_set_list_ptr; private: bool quick_coord_search_enabled; unsigned int matrix_rows; LinkedList<NetworkGraphNode*> **quick_search_matrix; };