The hunt for the missing data type

> All I'm saying is that lou1306 is correct in their definition of a graph.

I never claimed otherwise. I explicitly said the opposite - there are multiple correct definitions. That's literally one of the reasons why there's no general purpose graph type - there are multiple definitions with different properties, all of which are referred to in various contexts as "graphs".

> If that means that both you and ylow are wrong, that's fine with me!

This gives off very strong "somebody is wrong on the internet" vibes...

All I said was (a) in the context of the current discussion (not decided by me!), graphs were already assumed to encompass more than the vanilla undirected V x V definition people are pointing me to, and (b) in that context, one more example (supporting the parent's point that I was replying to!) was graphs with multiple edges. All of which seems quite uncontroversial, true, and in line with the context of the parent comment I replied to. I have nothing to add.

I seriously don't get where the desire to die on this hill is coming from, but I don't share it to keep continuing here.

I really enjoyed reading this thread. The opening line (and core argument?) "Graphs are ubiquitous in software engineering" triggered my neural network to respond.

TLDR: graphs are ubiquitous in _science_, and for a data type to be useful it should not put the crossbar too high.

(some history.) The Center for Nonlinear Studies (https://cnls.lanl.gov/External/) has a rich legacy of organizing annual Los Alamos Lab driven conferences in Santa Fe that bring together emergent disciplines. We combine overview talks by world experts and enough spaces in between these talks so that new bridges can be built at outstanding Santa Fe restaurants. I was co-organizer of the 2003 conference on Complex Networks, and this one was turning out to be a real banger. Sitting in the back with Aric Hagberg and Dan Schult (from Colgate University, but then spending his sabbatical at the CNLS) we were struck by how many really smart people were using "complex networks", but with very few computational tools available to them. That was the origin of networkx ( = network "X", reflecting the multidisciplinary renaissance we were watching). At that time python was a high-productivity starting framework to build the infrastructure, but I honestly expected that eventually there will be another language plugged in under the hood to make it more efficient for huge data sets on supercomputing architectures. We used the Guido v Rossum dict of dicts data structure idea (a few years old at that time) and built the most natural setup designed for a range of the disciplines. The python dict data type was a well-tested and integrated part of the language, so we felt this to be a solid base to work on. We freely borrowed ideas from many smarter than us. E.g. from David Eppstein [1] - one should be able to just say "if n in G" for "if the node n is in the graph G" and "G[n]" for "the neighborhood of node n in the grap G". We loved the graphviz drawing tools but quickly decided that graph drawing was a separate challenge [2]. Our goal was platform-independent, open source tools that will allow any graduate student, from any country, to use it in any field. Often when I came up with some strange subset of mathy graph stuff Aric would push back with YAGNI! [3]. Fast forward a few years, and the success of networkx --- due to the wise management and long midnight hours leadership by Aric and Dan, who inspired many new contributors --- continued to surprise us. The python dict-of-dicts technology allowed a wide range of fields to use these tools, and smart graduate students (working in diverse fields such as epidemiology, proteomics, ecology, architecture, social sciences, ...) could learn "applied graph theory" on the fly and easily write their own code. If we used C++ Boost BGL or some other more efficient C data structures, this would likely have bypassed all these thousands [4] of applications. The evolution of networkx continues with great new ideas, as for example explained in the recent scipy talks by current maintainers and contributors. Thanks Jarrod Millman ! [5].

Many programmers ached at better faster newer graph libraries, and I know that they used networkx as part of their development, as they should. Borrowing from paper dictionaries, there are some humorous quirks added into old code that allows one to track borrowed memes [6]. One reason the abundance of graph libraries will continue is that programmers, like woodworkers, enjoy the great joy of crafting them. I look forward to a future AI that creates a superb graph library just because it should be done. I hope it will contain random_lobster, and the Aric Hagberg Ankh-Morporkian quote "it is dictionaries all the way down".

Pieter Swart

Theoretical Division and Center for Nonlinear Studies, LANL

[1] https://ics.uci.edu/~eppstein/ )

[2] In his CNLS 2003 talk, Bill Cheswick made the point that for typical internet related graphs any drawing tool soon delivers a "peacock splattered onto your windshield." https://www.cheswick.com/ches/

[3] https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it

[4] https://scholar.google.com/citations?view_op=view_citation&h...

[5] https://www.jarrodmillman.com/

[6] https://networkx.org/documentation/stable/reference/generate...

    (I pay homage to the wise soul that gave it its own web page 

https://randomlobster.com/)

til thanks.

(And Java doesn't let you change after construction.)

In all of your earlier examples (and actually, including the current one too), you're treating vertices as first-class objects, but edges as second-class. There's no way to even identify an edge in your formulation -- only vertices.

This is a common oversight in graph structures that ends up being very annoying in many applications. You keep trying to work around it by associating the edge's properties with those of the vertex pairs and hoping that's sufficient for the application, but I'm trying to point out that the abstraction you're implicitly dancing around -- and the one that many practical uses need -- is actually one that treats edges as first-class. In fact, I would go further and say that if anything should be second-class, it ought to be the vertices, since they're already implied by the edges. (That is to say, for many practical applications of graphs, an edge determines its endpoints, but the endpoints don't determine the edge.)

How many times you had to program recursion with detection and special-casing of cycles? How many times the tree thing you wrote was artificially constraining the domain due to not allowing multiple parents? Those are the cases where graph is the right mental model, and graph structure ought to be considered (you may still hack the solution from special-cased recursion on lists, for engineering reasons).

Also, how much does the control flow jump between objects in your code? There's nothing more core to enterprise programming (at least of C++/Java school of thought) than the object graph. Which is what it says on the tin: a runtime directed graph of objects connected by pointers/references. A lot of enterprise code is, in a way, graph algorithms, just inlined and so smeared out that people don't recognize them for what they are.

Also, how many times the domain model you were using was plain broken, because whoever designed it didn't understand that most things in life don't arrange well into hierarchy - they tend to form directed graphs.