   Best data structure for an adjacency graph
  I'm wondering what would be the fastest data structure for the following need:I need to be able to check whether or not two nodes are connected as fast as possible, all other operations are secondary. This leads me to think that I should use some sort of hash table based implementation, but i'm not sure what.option 1: combine both nodes into a single hashable unitclass HashTable<NodeConnection*>;class NodeConnection{    public:    inline int hashCode() { return node1->hashCode()*node2->hashCode(); }  private: Node* node1, node2;}option 2: use a map data structureclass HashMap<Node*,Node*>;--------------------I'm a proponent of option 2, but it has the drawback that i'm doing essentially option 1 except with the first node being used for hash lookup instead of both nodes as in the first example.If I were to use option 1, what would be the best way to combine the hash of node 1 and node 2?I am certain that for my application, hash values will be unique integers and if hash1 == hash2, then node1 == node2 if that helps.any ideas?   
  The fastest to lookup would be an adjacency matrix. This provides O(1) lookups, and requires O(n^2) space. If you're not down with that space requirement, you should explain a little more about what your preferred time/space tradeoff is.   ;Quote:Original post by SneftelThe fastest to lookup would be an adjacency matrix. This provides O(1) lookups, and requires O(n^2) space. If you're not down with that space requirement, you should explain a little more about what your preferred time/space tradeoff is.how would I implement said data structure? the reason why i suggested a hash table based implementation is the O(1) lookup time, and the space required for a hash table is O(n/loadFactor), better than O(n^2).What I'm doing is implementing a collision detection system where there are collision layers, a set of objects that collide with each other. Each collision layer is a node in the adjacency graph, and a connection between nodes indicate whether or not objects in those layers collide.so basically, I have to perform about O(n*log(n)) lookups per frame (actual cost varies with spatial arrangement of objects, I use an octree spatial partitioning scheme). This collision culling is performed before actual narrow phase collision detection and is meant to help speed up collision detection by allowing designers to specify different types of objects that may or may not collide with each other.Obviously, there aren't going to be 1000's of layers, but I'd like the system to scale well nonetheless.   ;Quote:Original post by AresseraQuote:Original post by SneftelThe fastest to lookup would be an adjacency matrix. This provides O(1) lookups, and requires O(n^2) space. If you're not down with that space requirement, you should explain a little more about what your preferred time/space tradeoff is.how would I implement said data structure?Start by following the link. (In case that wasn't helpful, what exactly is the problem? The matrix is simply a rectangle of boolean values, so you just pack those into memory using whatever sort of bitfield you prefer. The values for each bit are simple to determine and interpret; read the page. You do a lookup by grabbing the bit at the appropriate (row, column) position.)   ;Quote:Original post by ZahlmanQuote:Original post by AresseraQuote:Original post by SneftelThe fastest to lookup would be an adjacency matrix. This provides O(1) lookups, and requires O(n^2) space. If you're not down with that space requirement, you should explain a little more about what your preferred time/space tradeoff is.how would I implement said data structure?Start by following the link. (In case that wasn't helpful, what exactly is the problem? The matrix is simply a rectangle of boolean values, so you just pack those into memory using whatever sort of bitfield you prefer. The values for each bit are simple to determine and interpret; read the page. You do a lookup by grabbing the bit at the appropriate (row, column) position.)The problem is with the row/column position. I understand how the structure works, it's just that I'm using objects to represent nodes, and therefore I can't easily generate an index from an arbitrary collision layer. This is why I think hashing would be the best option for such a requirement.;Quote:Original post by AresseraThe problem is with the row/column position. I understand how the structure works, it's just that I'm using objects to represent nodes, and therefore I can't easily generate an index from an arbitrary collision layer.How are you planning to specify which nodes you're checking for connection, then? What are you *really* doing?Also, are the nodes *already, actually* connected (i.e. Node*s in the Node struct pointing at the connected nodes)?   ;Quote:Original post by ZahlmanQuote:Original post by AresseraThe problem is with the row/column position. I understand how the structure works, it's just that I'm using objects to represent nodes, and therefore I can't easily generate an index from an arbitrary collision layer.How are you planning to specify which nodes you're checking for connection, then? What are you *really* doing?Also, are the nodes *already, actually* connected (i.e. Node*s in the Node struct pointing at the connected nodes)?I have a hash map which maps collision objects to collision layers. I say hashMap->get(object) and it returns the layer that that object is in.As for the nodes, they are not connected to each other, just through a high level layer, the adjacency strucutre. This is why I have this question, what would be the fastest way to represent these relationships?   