CODEWITHSUNDEEP
data-structuresgraph
Kat
Kat

Reputation: 493

Object and Pointer Graph representations

I keep seeing everywhere that there are 3 ways to represent graphs:

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

However, I just plain don't understand what these Object and pointer representations are - yet every recruiter, and many blogs cite Steve Yegge's blog that they are indeed a separate representation.

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

How does this representation offer any discernible analytical advantage in any scenario?

Upvotes: 17

Views: 6791

Answers (4)

Serge Mosin
Serge Mosin

Reputation: 396

Objects and pointers representation reduces space complexity to exactly V+E, where V is the number of vertices, E - the number of edges (down from V+2E in Adjacency List or even 2V+2E if you store index->Vertex mapping in a separate hash map), sacrificing time complexity: particular edge lookup will take O(E), which equals O(V^2) in a Dense graph (up from O(V) in Adjacency List). The space saving is achieved by removing duplicated edges that appear in the Adjacency List.

Upvotes: 1

The game
The game

Reputation: 1

Here a way i have been using to create 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 link between vertices is : 

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

Upvotes: 0

b.buchhold
b.buchhold

Reputation: 3896

For now I have a hard time finding a pro w.r.t typical "graph algorithms". But it sure is possible to represent a graph with objects and pointers and a very natural thing to do if you think of it as a representation of something you just drew on a whiteboard.

Think of a scenario where you want to combine nodes of a graph in a certain order. Nodes have payloads that contain domain data, the graph structure itself is not a core aspect of your program.

Sure, you can update your lists / matrix for every operation, but given an "objects and pointers" structure, you can do the merging locally. Further, if nodes have payloads, it means that lists/matrix will feature node id's that identify the actual node objects. A combination would mean you update your graph representation, follow the node identifiers and do the actual processing. It may feel more intuitively to work on your actual node objects and simply remove pointerswhen collapsing a neighbor (and delete that node) .

Besides, there are more ways to represent a graph:

  • E.g. just as triples, like Turle does
  • Or as offset representation (offsets per node into an edge array), e.g. this Boost data structure (disclaimer: I have not tested the linked implementation myself)
  • etc

Upvotes: 0

xyz
xyz

Reputation: 910

From the top of my head, I hope I have the facts correct.

Conceptually, graph tries to represent how a set of nodes (or vertices) are related (connected) to each other (via edges). However, in actual physical device (memory), we have a continuous array of memory cell.

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

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

The matrix representation gives the advantage when the graph is dense, meaning when most of the nodes/vertices are connected to each other. This is because in such cases, by using the entry of matrix, it saves us from having to allocate an extra pointer (which need a word size memory) for each connection.

For sparse graph, the list approach is better because you don't need to account for the 0 entries when there is no connection between the vertices.

Hope it helps.

Upvotes: 1

Related Questions