In how many ways you can represent a graph ( data type )?

Question

I need some references that go beyond the classical and graphical representation of a graph with vertices and edges; I'm trying to dive into the math world and see if I can get an alternative representation for this data structure . My research includes just everything, from graphical representations, text representations, to more abstract representation with matrices ( ?, if this option exists at all ) or other math objects .

My question is literally open for any valid representation you can think of .

Thanks.

EDIT:

to clarify further my intentions I will say this:

• my research is intentionally generic and it focuses on the best way to think about graphs given a particular problem, sometimes a matrix is better than a graphical representation, sometimes a picture is the best option, other times there is probably an even better choice including things I don't know yet .
• currently I have 2 major scenarios that need the perfect solution :
  • a representation of multiple links between a widget and an $n$ number of properties, a problem about data structures and their representation, where I have a set $W$ composed of multiple instances of different widgets $w_n$ that need a connection to another set $P$ of multiple instances of different properties $p_n$ ( basically something like the CSS in the web world, it's an exemplification, but it's basically what I need )
  • how to retrieve the informations about the connections, from said data structure algorithmically without incurring is incredibly large magnitudes and big scaling factors .

For now I can tell that a data structure that scales quadratically is not practical, I also need multiple links from-to each vertex, so a "plain" graph is not enough anyway and I need an hypergraph .

Answer 1

This a matrix representation:

To every graph you can associate an adjacency matrix. Let $G=(V,E)$ be a graph with vertex $V$ and edges $E$. Then the adjacency matrix $A\in \Bbb R^{|V|\times |V|}$ associated to $G$ is defined as follow. For every edge $(i,j)\in E$, we set $A_{i,j}$ to be the wight of the edge (set $A_{i,j}=1$ if your graph is unweighted).

Following the same logic, you can also represent hypergraphs using tensors.

Answer 2

It really depends on what you are doing. If you are algorithmically parsing the graph such as with path finding, flow, or spanning tree algorithms, then an adjacency list is usually a helpful tool. The adjacency list relates each vertex $v$ to exactly those vertices to which $v$ is adjacent.

An incidence list is similar to an adjacency list, except that each vertex is related to exactly those edges incident to it.

The adjacency matrix is a symmetric matrix analog to the adjacency list. Similarly, the incidence matrix is a $V \times E$ dimensional matrix analog to the incidence list. The matrix representations are nice for algebraic analysis of the graph. Certain algorithms, such as the Hungarian algorithm or Floyd's algorithm, also utilize matrix representations over list representations. However, the adjacency matrix is a poor choice for something like Dijkstra's algorithm.

Edit: Based on your update, my gut reaction is that this really isn't a math question. Rather, it feels like you are interested in implementation. It sounds like Object-Oriented Programming is really the best way to go for this. Design a Property class, and a Widget class with a Collection of Properties, such as a List or Set.