4 ms·

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.
    - nyrikki 3y ago
      Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum SETH has a sub quadratic lower bound and several other graph problems have cubic lower bounds. Many real systems are often saved because it is actually hard to write code that aren't primitive recursive functions. Cycles often are what destroy that, as considering WHILE and GOTO being the difference between primitive and general recursive functions helps show. If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help. A graph data type wouldn't have those heuristics.
      - eru 3y ago
        > Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum Those are lower bounds on worst case instances. Not lower bounds on solving typical, practical instances. > If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help. > A graph data type wouldn't have those heuristics. Sounds like your heuristic for why heuristics help with many NP problems is less than helpful here. In practice, you can encode many graph problems as eg SAT or integer programming or SMT etc and get good performance. Even biggish instances of eg the traveling salesman problem are often solved well in practice. I'm not sure why you bring up primitive recursive functions? Primitive recursion is able to express all of NP (and much more), so it's not much of a constraint in this discussion? (I agree that you have to try hard in practice to go beyond primitive recursion but stay finite.)

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.
  - nyrikki 3y ago
    Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum SETH has a sub quadratic lower bound and several other graph problems have cubic lower bounds. Many real systems are often saved because it is actually hard to write code that aren't primitive recursive functions. Cycles often are what destroy that, as considering WHILE and GOTO being the difference between primitive and general recursive functions helps show. If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help. A graph data type wouldn't have those heuristics.
    - eru 3y ago
      > Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum Those are lower bounds on worst case instances. Not lower bounds on solving typical, practical instances. > If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help. > A graph data type wouldn't have those heuristics. Sounds like your heuristic for why heuristics help with many NP problems is less than helpful here. In practice, you can encode many graph problems as eg SAT or integer programming or SMT etc and get good performance. Even biggish instances of eg the traveling salesman problem are often solved well in practice. I'm not sure why you bring up primitive recursive functions? Primitive recursion is able to express all of NP (and much more), so it's not much of a constraint in this discussion? (I agree that you have to try hard in practice to go beyond primitive recursion but stay finite.)