Is there any other Data structure to represent Gra

Question

I was looking for different Data structures for representing Graph and I came accross Nvidia CUDA Toolkit and found out new way to represent graph with the help of source_indices, destination_offsets.

Fascinated by this innovative representation of graph, I searched out for other ways of representing Graphs. But not found anything new.

I was wondering if there was any other way to represent Graph other than Adjacency Matrix or Lists...

Answer 1

There is another representation of graphs using Adjacency Set. It is very much similar to adjacency list but instead of using Linked lists, Disjoint Sets [Union-Find] are used. You can read about disjoint sets ADT here.

If E is the number of edges and V is the number of vertices in the graph, then Adjacency set representation of graph takes up (E+V) space.

Complexities of other operations while using adjacency set representation:

Checking edge between vertex v and w : log(Degree(v))
Iterate over edges incident to vertex v: Degree(v)

Answer 2

I was wondering if there was any other way to represent Graph other than Adjacency Matrix or Lists...

There are alternatives to the adjacency list or the adjacency matrix, such as edge list, adjacency map or forward star to name a few. Given this graph (images taken from here):

• this is the adjacency matrix representation:

• this is the adjacency list representation:

• this would be another alternative, the edge list:

• and another pretty common one is the forward star representation:

If you get into this research field you will find a good number of approaches, mainly optimizations for specific cases, taking into account factors such as:

• Graph size (number of nodes)
• Density of the graph
• Directed or undirected graph
• Static or dynamic graph
• Graph known at compile time or constructed at runtime
• Node IDs (labeled sequentially or not)
• ...

These optimizations can, for example, support reordering of the nodes in a preprocessing stage to increase reference locality. There is a lot of work for shortest path algorithms, specially when calculating the shortest path in a world map.

One example of optimization would be a dynamic graph structure (Packed-Memory Graph (PMG)) which is suited for large-scale transportation networks.