51–60 of 259 posts
Ok, trees are not graphs but they are very related, and algebraic data types are trees, so they are ubiquitous in functional programming. Why don't we have graphs in FP (or in Rust)? Because graphs require mutation (respectively break linearity). Why don't we have graphs in imperative languages? Perhaps because very few imperative languages have ADTs? Just a thought.
I think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the re…
Two problems I see here, based on the research I've done in high-performance graph algorithms: - It's hard to find a "good-enough" graph implementation. The best hashtable is only a handful of percent better than the built-in ones. The best graph impl is 1000x or more better than any generic built-in one could be, so there's much more incentive to specialize (and people already specialize hashtables for just a handfu…
Have you tried doing it? My experience was that it was surprisingly simple. We may have different expectations for what is "reasonable", of course.
Earlier quoted context omitted.
I like DOT a lot. Way back in the day we had a semi-serious proposal to use it in the Puppet configuration language to describe dependencies
Same - DOT is a great way to go from zero to functional in near minimal time. It's also pretty trivial to generate since it's not order dependent, which is great for lightweight automation. Fine-tuning layout can be a real hassle though, sadly. I haven't found any quick tools for that yet.
Deciding where the appropriate subgroups are is a bit of an art. Sometimes it's obvious, as in bipartite graphs that are intentionally bipartite. Or, if there is a staged layout like for pipeline architectures. Sometimes it's not obvious even when it seems it should be, like when graphviz really wants to make a certain edge really short. Be ready to backtrack sometimes. Then I usually remove the subgroup border after I'm done, but a few times they have been useful to leave there.
One thing I really like about DOT is that adding hyperlinks to the vertices and edges that translate decently into the compiled output is really nice. I had an oncall dashboard that made liberal use of this feature that I still think back on fondly sometimes.
Earlier quoted context omitted.
RDF is not dependent on XML. There is a XML representation of RDF, but alternatives include JSON (using JSON-LD) and simple textual formats such as N3 and Turtle.
One trouble w/ RDF is that there are two official ways to do ordered collections, the RDF list which is basically a LISP list, and then RDF collections where the order is encoded in predicates. Neither is well-supported in most tools, for instance SPARQL lacks the list handling capabilities that you'd see in https://docs.arangodb.com/3.12/aql/ or https://www.couchbase.com/products/n1ql/ The XMP spec, for instance, ha…
I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
let x = 1; // edge named x
let y = f(x); // node named f with input edge x and output edge y> Mathematica, MATLAB, Maple, etc all have graph libraries of some form or another. I am not paying the thousands of dollars in licensing needed to learn more. Wolfram provides a free Mathematica called Wolfram Engine https://www.wolfram.com/engine/ . It's Mathematica without the UI. I hear you can combine it with Jupyter Notebook to get a similar experience to Mathematica.
Earlier quoted context omitted.
I like DOT a lot. Way back in the day we had a semi-serious proposal to use it in the Puppet configuration language to describe dependencies
Same - DOT is a great way to go from zero to functional in near minimal time. It's also pretty trivial to generate since it's not order dependent, which is great for lightweight automation. Fine-tuning layout can be a real hassle though, sadly. I haven't found any quick tools for that yet.
I wonder if it would be possible to mathematically define (in a theorem proving language like Coq) a bunch of accessor methods as well as a bunch of implementation primitives and then "compile" a custom graph implementation with whatever properties you need for your application. Some accessor methods will be very efficient for some implementations and very inefficient for others, but every method will still be availa…
I know this has been done for procedural languages and for declarative logical languages but I'm not aware of something like this specifically for graph processing and highly specialized code generation of graph processing. I wouldn't be surprised if Mix has been extended for this already, even if it has I'm sure there is still value in it.
I'd highly recommend Erwigs FGL library in Haskell as a really nice example of a generally performant graph data structure that is easy to work with. The API feels like working with lists because you are essentially consing contexts(node, neighbours) into a list of contexts that form your graph. Many standard graph algorithms are then built up from depth or breadth first search and you can compose really succinct pro…
In my experience this leaves FGL in an awkward spot: on the one hand, it isn't sufficient for heavy-duty graph processing; on the other, if you don't need fancy high-performance graph algorithms, chance are that encoding your problem as a graph is going to be more awkward than defining some domain-specific types for what you're doing. Graphs are such a general structure that they're usually the wrong level of abstraction for higher-level domain-specific logic.
Of course, sometimes you're writing graph code specifically and you need a nice way to express your graph algorithms without worrying about performance. In that case, FGL is great. I wrote a tutorial about using it to [generate mazes][1] and it helped me express the algorithms better than I would have been able to do without it. But that still leaves it as too narrow for something to be "the" graph representation in a language's standard library.
[1]: https://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/
And once you can do that… why not have every algorithm ensure it runs in its best structure, and convert where necessary (and possible) on the way in? Yes, there’s absolutely a performance or storage cost… but if the algorithm is that much faster, it should be worth it.
Basically a beefier version of sorting your data before searching in it. If an algorithm works best with a specific model of a graph, then let that be part of the algorithm.