201–210 of 259 posts
> There’s a gap between how often software engineers could use graphs and how little our programming ecosystems support them. Where are all the graph types? They've been there for quite a while :-) https://www.erlang.org/doc/man/digraph.html https://www.erlang.org/doc/man/digraph_utils And if you want to do some set theoretical stuff you're covered as well: https://www.erlang.org/doc/man/sofs.html
Graphviz has its own foundation graph library, that's not used by any other project. It has its good and bad points. Based on that experience, we had our very own second-system-syndrome experience. We decided our graph library should be modular, type safe, and efficient. (These properties came up in the comments here, too.) This is probably just a variation of "good, fast, cheap - pick any two." By modular, want to w…
I use graphviz dot syntax, parsing with networkx to plan expensive tool execution and the graph structure lets me automatically paralellize.
I’ve been building an interactive fiction platform built in C# with a world model contained within a bidirectional graph data structure. Since IF stories are relatively small in graph terms, it’s a reasonable solution. Locations and objects are nodes and movement and location of objects are edges. Nodes and edges both can have dynamic properties. I’ve also noticed the lack of graph structures in programming languages…
sounds neat. link?
Finding the balance between OO principals, Fluid coding capabilities, separating the data, grammar, parser, and world model and then constructing a standard IF library of common IF "things" is like juggling 20 kittens and 10 chainsaws.
Some things are confounding like do I define a container with a boolean property on an object or is a container a subclass of the base Thing? How does that extend to the underlying graph data store? What will queries look like and which solution is more meaningful to authors?
Seriously, 95% of the fun is figuring all of these things out.
graph is a data structure, not a data type. if you squint enough pointers are the building blocks (the data type is you please) for building graph data structure. a->b is pointer access, looks like an edge in the graph. graph data structure is parent of tree, code execution/ function call stacks work like a tree, think flame graphs. stacks and pointers are baked in assembly and cpu architecture. your claims can't be…
graph is a data structure, not a data type. It can refer to either. Any concrete data structure that uses indirection — which means pretty much anything more complicated than dense arrays and records — is indeed a form of graph. But graphs, and more constrained forms like DAGs and trees, can also be abstract data types, implemented by a variety of concrete representations. One of life’s little ironies is that impleme…
A graph is a group of two sets, the set of nodes and set of edges.
As an abstract data type, you may define operations on the data structure (aka abstract data type).
In case of graph, for example, you can define connectivity check (existence of an edge). And graph theory provides plenty more.
And set (in set theoretic sense) is also a data structure, you may define the membership check as on operation on that.
On the other hand, a data type is a tag that a compiler associates with raw bits and bytes on the memory in order to operate on them. Examples, datetime is a data type, string is a data type, array is a data type, numbers are data type, these are not data structures. These are language primitives.
Further graph is superseded by hi-graph (which is foundation for relational data bases and tuple algebra), and subseded by for example DAGs and trees.
To build an edge in a graph, you need something that could point to something. Like A points to B, the most fundamental way to capture this mapping is by using pointers (that is the address of B, stored at a known location accessible by A). A->B or A.B are just syntactic elements that underlie this.
Arrays, Matrices, Structs, Strings, are all made possible by pointers.
Pointers are a data type, it tags the value (usually in range 0..usize), as being an address of something else in the memory. Pointers are not data structures.
I should say primitives vs non-primitives if that makes the difference between what is data type vs data structure.
graph is a data structure, not a data type. if you squint enough pointers are the building blocks (the data type is you please) for building graph data structure. a->b is pointer access, looks like an edge in the graph. graph data structure is parent of tree, code execution/ function call stacks work like a tree, think flame graphs. stacks and pointers are baked in assembly and cpu architecture. your claims can't be…
Pointer-based graph structure will make matrix algos painful to implement. A graph is a concept. Article is quite meaningful about how it follows the various subtypes. Would recommend reading.
That should provides you some more context about my earlier comment.
By definition of concept (think conceptnet) anything is a concept. Any noun is a concept. Graph theory defines graph as set of two more sets. The set of nodes and set of edges, where each edge itself is set of two nodes (or tuple of two nodes if directionality of the edge also needs to be encoded). A node is anything that you can consider putting into set. And according to set theory, a set is well defined collection of things.
According web ontology language, a "thing" is the root of all things that can exist (see https://www.w3.org/TR/owl-ref/, specifically owl:Thing), except "nothing" maybe.
What all this means is a graph is collection of things, with things pointing to each other sometimes.
Pointers are the underlying data type that makes all other higher level data structures possible, including arrays, matrices, hashmaps, graphs, structs and more.
This is an interesting article but one major effort it doesn’t mention is the Boost Graph Library [0]. It is kind of clunky in places because it is written in C++03 and uses some weird idioms to simulate keyword arguments and provide generic ways of getting attributes for nodes. Also it suffers from the terrible template instantiation errors that most C++ template libraries do. But I still think it addresses a lot of…
It's a little disappointing that BGL didn't make an appearance in TFA.
Some comments here mention GraphBLAS, which is the big breakthrough in decoupling the layout of the graph from an efficient implementation of an algorithm, but none mention MLIR-GraphBLAS [0] which is the most promising integration into a compiler that I've seen.
I still think it's early days, I wouldn't throw in the towel quite yet :)
[0]: https://mlir-graphblas.readthedocs.io/en/latest/index.html
You might want to run generic graph algorithms on such emergent graph data structures, but usually they don't have a uniform graph interface that you can make use of. So you either would need to copy the graph over to some normalized graph data structure, or implement a uniform graph interface facade over the existing objects. The latter is usually more efficient.
Anyway, there are libraries that tend to do this decently, I think Boost does it well[1]. But there are a lot of inherent complexities and so much open design space that you can't really serve with one or even a handful of data structures.
[1] https://www.boost.org/doc/libs/1_84_0/libs/graph/doc/index.h...
This is a good write up, but for me seems to miss the mark. I agree with the author that different algorithms require differently organized data structures. But what if your problem requires 2 different algorithms, which each work best with a different data structure? Either you pick one and run both (which is not ideal) or you run the first algorithm with one structure, convert it, and the run the second algorithm i…
Earlier quoted context omitted.
What do you mean by "textual graph literal"?
Textual array literal: [1,2,3] Textual dict literal: {"a": 1} Textual graph literal: ???