5
$\begingroup$

Not sure exactly how to define this but here's the basis of the question (very loosely)

  • All lists can be contained in tree's
  • all trees can be contained in a graph
  • all graphs can be contained in a multi graph,
  • and all multigraphs can be contained in a hypergraph (never actually heard of a hypergraph before searching for an answer to this, so may not have it quite right)

So there's a containment hierarchy of 'complexity' of data structures. Is Hypergraph the highest one, is there a proof of this, and is there a name for the study of whatever this is.

By highest one, I mean all structures can be represented as a hypergraph if I chose to. So in any code I could represent all the structures by using a number of hypergraphs (not that I would). tia

[Update] Perhaps an alternative way to ask it is, for any arrangement of data structures consisting of nodes and edges. Does there exist a structure that can't be contained in a hypergraph.

Then there is a second question - is there any data structure which can't be represented using nodes and edges.

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ I don't know how clearly defined this question is. I can imagine that for any structure you come up with, I can create a higher order one. $\endgroup$
    – Dave Clarke
    Sep 27, 2012 at 10:46
  • $\begingroup$ how so? I can't think of any thing that I'd need more than a multi graph for, e.g. 3d space and so on. If I need a multigraph of multigraphs then that is a multigraph as well (in the most abstract relationship sense) $\endgroup$
    – daven11
    Sep 27, 2012 at 10:49
  • 1
    $\begingroup$ I could probably add edges between nodes and edges at one level. Then I could add edges between edges (of the lower level). Then for each new level, I could add new kinds of edges that go between edges of the lower level .... $\endgroup$
    – Dave Clarke
    Sep 27, 2012 at 10:53
  • 1
    $\begingroup$ I cannot connect edges with edges in a multigraph. $\endgroup$
    – Dave Clarke
    Sep 27, 2012 at 11:00
  • 1
    $\begingroup$ Don't think you can have a "directed" hypergraph, since it's just a family of sets. Hence: "Does there exist a structure that can't be contained in a hypergraph." ... any directed graph. $\endgroup$
    – badroit
    Sep 27, 2012 at 11:41

1 Answer 1

Reset to default
3
$\begingroup$

Perhaps this is an interesting question with explicit answers, but you probably really have a problem with "exactly how to define this".

A list does not directly corresponds to a unique data structure, nor does a tree. A singly linked list corresponds to a (sufficiently unique) data structure, as does a binary tree. When you say multi graph, you probably want to refer to a quiver, i.e. a directed multigraph (edges with own identity). A binary or ternary quiver would again correspond to a (sufficiently unique) data structure.

However, any sufficiently canonical (and efficient) realization of a (n-ary) quiver as a data structure would probably not match well with the way datatypes are handled in "common" programming languages, where the size of an object with a certain datatype shouldn't depend on the actual content of that object. Therefore, this would be the point at which I would stop to look for a higher order data structure (than a quiver, looking for function like data structures and continuations certainly is useful). My reason for this is that I don't see the practical usefulness of a higher order data structure if it cannot be realized efficiently within "common" programming languages.

Improve this answer
$\endgroup$
3
  • $\begingroup$ hmm, it does seem the problem is definition, thought someone would have done this for me, strangely enough I have an application where an answer would be helpful. There is an intuitive notion of complexity of structures, which needs to be defined, and is there a 'supreme' data structure? $\endgroup$
    – daven11
    Sep 27, 2012 at 22:53
  • $\begingroup$ @daven11 I think you have a problem with "exactly how to define this", because it's unclear to me what you are looking for "exactly". You mentioned "nodes" and "edges" in your question, hence I tried to give an answer in that direction. If you are just looking for mathematical structures (without any concrete corresponding "realizable" data structure), then "set" is the universal structure which is used to define all other structures (when set theory is used as the foundational system for mathematics). In this direction, a simple "pair" should be enough to implement any other data structure... $\endgroup$
    – Thomas Klimpel
    Sep 28, 2012 at 11:27
  • $\begingroup$ thanks, I must admit I thought someone would point me towards a definition. I'll probably have to do a bit more research and figure out exactly what I mean :-). $\endgroup$
    – daven11
    Sep 28, 2012 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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