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 .



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 .

  • 1
    $\begingroup$ To every graph you can associate an adjacency matrix. $\endgroup$ – Surb Dec 11 '14 at 9:39
  • $\begingroup$ @Surb thanks, that's one valid option, I would appreciate some examples or sources on how to perform this mapping or any other information, like how this representation scales when a graph grows . $\endgroup$ – user2485710 Dec 11 '14 at 9:42
  • $\begingroup$ It looks like it's always a square matrix $N \times N$ where $N=number of vertex$, which means that this representation scales quadratically ? $\endgroup$ – user2485710 Dec 11 '14 at 9:45
  • $\begingroup$ yes, however if your graph is not fully connected you may use sparse matrix tools (for practical uses). $\endgroup$ – Surb Dec 11 '14 at 9:46
  • $\begingroup$ Can you provide a motivation for a different representation? Do you want to store your datas and their connections in an efficient way? You want tot test some given properties?... Give more context to get better answers ;) $\endgroup$ – Surb Dec 11 '14 at 14:55

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.

  • $\begingroup$ I edited the first question with additional info $\endgroup$ – user2485710 Dec 12 '14 at 7:52

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.

  • $\begingroup$ I edited the first question with additional info $\endgroup$ – user2485710 Dec 12 '14 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.