3 ms·

I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sen

by jjice 3y ago

I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sense to implement them at a domain-ish level (the article mentions this in the "There are too many implementation choices" section). Then I saw Petgraph [0] which is the first time I had really looked at a generic graph library. It's very interesting, but I still have implemented graphs at a domain level. [0] https://github.com/petgraph/petgraph https://github.com/petgraph/petgraph

nickpsecurity 3y ago
You might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.
- sanderjd 3y ago
  Yeah this is exactly how I think of it. I think "graphs" are just at a different level of the abstraction hierarchy than the data structures they're often grouped together with. This is even further up the abstraction hierarchy, but to illustrate the point, nobody really wonders why languages don't ship with a built-in database implementation. And it's the same basic reason as with graphs; one size doesn't fit most.
  - eru 3y ago
    Well, the original article actually describes that relations are great way to model graphs, and suggests that your language (or its standard library) should ship with a good datastructure for relations. You would get most of a what you need for a simple relation database this way.
TachyonicBytes 3y ago
Why wouldn't an abstract `Graph` type and specific implementations of that work? Like Java has for `Set` and various implementations?
- gryn 3y ago
  even at that level of abstraction there are many flavors of "graphs". what some people call graph are actually hypergraphs, or attributed graphs.
- skybrian 3y ago
  For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.) So it's not clear what the interface would do. What methods should there be? Again, there are too many choices, and a Graph interface often isn't the best way to represent a view of some subset of a graph.
  - nyrikki 3y ago
    To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time. One of the big reasons to fight to make dependencies DAG like is because exhaustive search gets you to exponential time. NP-complete, NP-hard are easy to run into with graphs. Graph k-colorability, finding Hamiltonian cycles, max cliques, max independent sets, and vertex cover on (n)vertex graphs aren't just NP, they have no sub-exponential time algorithms. Finding those subgraphs is often impractical.
    - deleted 3y ago
      [deleted]
    - eru 3y ago
      Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality. But you need to move away from writing your own solvers. Instead you use a library that lets you describe your problem, and then throws off-the-shelf solvers at them. See eg https://developers.google.com/optimization https://developers.google.com/optimization That's a good approach even for problems that are in P, because minor changes in the business logic requirements often only translate into minor changes in the programmatic problem description, but would translate to major changes in the a bespoke, custom algorithm to solve them, even if everything stays in P. It also separates the description of the problem from the solution. In the real world, the business logic requirements are seldom written down explicitly somewhere, and are only available implicitly as described by the code. So without this separation, it can be hard to disentangle what's a real requirement, and what's just something your custom heuristic algorithm happens to spit out.

by jjice 3y ago

nickpsecurity 3y ago

You might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.

sanderjd 3y ago
Yeah this is exactly how I think of it. I think "graphs" are just at a different level of the abstraction hierarchy than the data structures they're often grouped together with. This is even further up the abstraction hierarchy, but to illustrate the point, nobody really wonders why languages don't ship with a built-in database implementation. And it's the same basic reason as with graphs; one size doesn't fit most.
- eru 3y ago
  Well, the original article actually describes that relations are great way to model graphs, and suggests that your language (or its standard library) should ship with a good datastructure for relations. You would get most of a what you need for a simple relation database this way.

TachyonicBytes 3y ago

Why wouldn't an abstract `Graph` type and specific implementations of that work? Like Java has for `Set` and various implementations?

gryn 3y ago
even at that level of abstraction there are many flavors of "graphs". what some people call graph are actually hypergraphs, or attributed graphs.
skybrian 3y ago
For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.) So it's not clear what the interface would do. What methods should there be? Again, there are too many choices, and a Graph interface often isn't the best way to represent a view of some subset of a graph.
- nyrikki 3y ago
  To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time. One of the big reasons to fight to make dependencies DAG like is because exhaustive search gets you to exponential time. NP-complete, NP-hard are easy to run into with graphs. Graph k-colorability, finding Hamiltonian cycles, max cliques, max independent sets, and vertex cover on (n)vertex graphs aren't just NP, they have no sub-exponential time algorithms. Finding those subgraphs is often impractical.
  - deleted 3y ago
    [deleted]
  - eru 3y ago
    Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality. But you need to move away from writing your own solvers. Instead you use a library that lets you describe your problem, and then throws off-the-shelf solvers at them. See eg https://developers.google.com/optimization https://developers.google.com/optimization That's a good approach even for problems that are in P, because minor changes in the business logic requirements often only translate into minor changes in the programmatic problem description, but would translate to major changes in the a bespoke, custom algorithm to solve them, even if everything stays in P. It also separates the description of the problem from the solution. In the real world, the business logic requirements are seldom written down explicitly somewhere, and are only available implicitly as described by the code. So without this separation, it can be hard to disentangle what's a real requirement, and what's just something your custom heuristic algorithm happens to spit out.