Representation of objects and pointers

Question

I see all the time that there are 3 ways to present graphs:

1. Objects and Pointers
2. Adjacency matrix
3. Adjacency lists

However, I just don’t understand what these representations of objects and pointers are - but every recruiter and many blogs cite a blog in Steve Yegg that they really are a separate view.

This widely accepted answer to a very similar question seems to suggest that the vertex structures themselves do not have internal pointers to other vertices, and instead all the edges are represented by edge structures that contain pointers to adjacent vertices.

How does this view provide any tangible analytic advantages in any scenario?

Answer 1

Above my head, I hope I have the right facts.

Conceptually, the graph tries to imagine how a set of nodes (or vertices) is connected (connected) to each other (through edges). However, in a real physical device (memory) we have a continuous array of memory cells.

So, to represent the graph, we can choose to use a matrix. In this case, we use the vertex index as a row and column, and the record has a value of 1 if the vertices are adjacent to each other, 0 otherwise.

Alternatively, you can also represent the graph by selecting an object to represent node / vertex, which points to a list of all nodes adjacent to it.

The matrix representation gives an advantage when the graph is dense, which means that most nodes / vertices are connected to each other. This is due to the fact that in such cases, using the matrix entry, this eliminates the need to allocate an additional pointer (which requires word size memory) for each connection.

For a sparse graph, the approach to the list is better because you do not need to consider 0 entries when there is no connection between the vertices.

Hope this helps.

Answer 2

At the moment, it’s hard for me to find the typical “graphical algorithms” pro wrt. But, of course, you can imagine a graph with objects and pointers, and this is a very natural thing if you think of it as representing what you simply drew on the board.

Think of a scenario in which you want to combine the nodes of a chart in a specific order. Nodes have a payload that contains domain data; the graph structure itself is not the main aspect of your program.

Of course, you can update your lists / matrix for each operation, but given the "objects and pointers" structure, you can merge locally. In addition, if the nodes have a payload, this means that the identifier node will be displayed in the lists / matrices, which identifies the actual node objects. The combination means that you update your chart view, follow the node identifiers, and do the actual processing. It can feel more intuitive to work with your actual node objects and just delete pointers when collapsing a neighbor (and delete that node).

In addition, there are many ways to present a graph:

• eg. just like triples for example turle does
• Or as an offset representation (offset by node into the edge array), for example. this Improve data structure (disclaimer: I have not tested the related implementation itself)
• etc.

Answer 3

Here is the way I used to create a Graph with this concept:

#include <vector> class Node { public: Node(); void setLink(Node *n); // *n as argument to pass the address of the node virtual ~Node(void); private: vector<Node*> m_links; }; 

And the function responsible for creating the connection between the vertices:

 void Node::setLink(Node *n) { m_links.push_back(n); } 

Answer 4

Objects and pointers Representation of objects and pointers reduces the complexity of space to accuracy V+E , where V is the number of vertices, E is the number of edges (compared to V+2E in the V+2E List or even 2V+2E if you keep index-> ​​vertex mapping in a separate hash map), sacrificing time complexity: for a specific search for an edge, O(E) required, which is O(V^2) in a dense graph (instead of O (V) in the Adjacency List ). Space saving is achieved by removing duplicated edges that appear in the adjacency list .