| Siri Cruise <chine.bleu@yahoo.com>: Aug 19 06:20PM -0700 In article <slrnshtei9.5o3.grahn+nntp@frailea.sa.invalid>, > design my C++ code I pay attention to ownership and lifetime, and I > rarely or never find a need for garbage collection or reference > counting/shared_ptr. Implement a directed graph with dynamic edges and nodes which has no naturally distinguished edges from back edges. Try to figure out how to pay careful enough attention to avoid reference tracing or counting. So do reference counting. Now when you delete an edge to a node, you have to check if it only receives back edges, and if so converts a back edge to an edge. This conversion has nothing to do with the directed graph itself but an artifact of reference counting. -- :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @ 'I desire mercy, not sacrifice.' /|\ Discordia: not just a religion but also a parody. This post / \ I am an Andrea Doria sockpuppet. insults Islam. Mohammed |
| Juha Nieminen <nospam@thanks.invalid>: Aug 20 06:13AM > back edges, and if so converts a back edge to an edge. This > conversion has nothing to do with the directed graph itself but > an artifact of reference counting. I can't think of a data structure where the elements require reference counting, when those elements are solely used within that data structure itself. Usually GC or reference counting is needed when *something else* may have a reference/pointer to the object that may last longer than the data container. |
| Jorgen Grahn <grahn+nntp@snipabacken.se>: Aug 20 06:17AM On Fri, 2021-08-20, Siri Cruise wrote: >> counting/shared_ptr. > Implement a directed graph with dynamic edges and nodes which has > no naturally distinguished edges from back edges. No doubt there are scenarios where Java-style garbage collection is the best solution -- it's just that I have never been in that situation. When I've done graphs, it has been enough to let a Graph object (or just a std::set<Edge>) own everything. /Jorgen -- // Jorgen Grahn <grahn@ Oo o. . . \X/ snipabacken.se> O o . |
| Siri Cruise <chine.bleu@yahoo.com>: Aug 20 12:03AM -0700 In article <slrnshui7h.5o3.grahn+nntp@frailea.sa.invalid>, > No doubt there are scenarios where Java-style garbage collection is > the best solution -- it's just that I have never been in that > situation. Directed graphs are an ideal way of handling complex relations. Encode the relation into a graph; use Tarjan's algorithm to find strongly connected component; factor the graph by SCCs. The resulting reduced graph is a DAG which is the partial order with each SCC being an equivalence class. Do topological sorting on the DAG. You can then deal with the original relation equivalence class by equivalence class either from the sources or sinks. From the sinks means every edge in the SCC is to the same SCC or to a node of a previously processed equivalence class. Many programming problems are about distributing information around a relation of nodes. The usual method is to find fix points on bit vectors. > When I've done graphs, it has been enough to let a Graph object (or > just a std::set<Edge>) own everything. That just means someone else had to deal with back edges. -- :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @ 'I desire mercy, not sacrifice.' /|\ Discordia: not just a religion but also a parody. This post / \ I am an Andrea Doria sockpuppet. insults Islam. Mohammed |
| Juha Nieminen <nospam@thanks.invalid>: Aug 20 11:03AM > class by equivalence class either from the sources or sinks. From > the sinks means every edge in the SCC is to the same SCC or to a > node of a previously processed equivalence class. If you need to be constantly adding and removing elements from that graph during the runtime of the program, then sure, it's probably best to allocate individual elements and handle them by reference (ie. pointer). Or, if for some reason the elements can be of different types. However, if what you describe is "build the graph at startup and then just read its contents during the execution of the program", it may well be more efficient to put all the elements in one single array, and then have connections between the elements with pointers or indices. This requires no memory management of any kind (other than, obviously, freeing the array when the graph isn't needed anymore). There might even be room for low-level optimization by rearranging the elements in an optimal way in the array so that they are accessed as linearly as possible in most cases. (With individually allocated elements you cannot do this kind of optimization even if you wanted to.) Moreover, this approach allows for Data-Oriented Design. If the graph nodes contain several member variables, and usually you are only interested in particular ones, you could do the DOD thing and split the elements into their own arrays, further increasing cache locality. |
| "Alf P. Steinbach" <alf.p.steinbach@gmail.com>: Aug 20 02:26PM +0200 On 20 Aug 2021 03:20, Siri Cruise wrote: > no naturally distinguished edges from back edges. Try to figure > out how to pay careful enough attention to avoid reference > tracing or counting. I don't see why one would have to think or pay attention to avoid reference counting for a directed graph. Just use Boost Graph, or a DIY thing based on e.g. `std::vector`. Is it that when you write "dynamic edges and nodes" you mean dynamically allocated node objects, with the edges represented as pointers to nodes? We did that at college, early 1980's, finding shortest route between any two cities in Norway. We had one DEC Rainbow workstation to do color graphics on. Otherwise had to use HP monochrome graphics terminals :( Anyway, if that's what you're thinking of then that is an inefficient way to do things. E.g. I doubt that Boost Graph does that internally. But even when that approach is adopted I still fail to see the alleged practical need for reference counting. The pointers are internal in the structure. They're not owning pointers. (In passing, for efficient removal of nodes just let each node keep a list of all edges to it, not just a list of all edges from it, but better: use Boost Graph). > So do reference counting. Now when you > delete an edge to a node, you have to check if it only receives > back edges, and if so converts a back edge to an edge. Huh? (Forgive me if I'm dumb here, not yet on first coffee.) > This > conversion has nothing to do with the directed graph itself but > an artifact of reference counting. Someone at one time gave a slightly similar (if I understood you) example that /actually/ required garbage collection, or else incurring some heavy complexity. It was about function representations with parts of functions being referenced and reused with abandon. The person who came up with it had a background in functional programming and hence, I believe, mathematics, and the example was convincing. Cheers, - Alf (BTDT) |
| mickspud@downthefarm.com: Aug 20 03:19PM On Fri, 20 Aug 2021 11:03:59 -0000 (UTC) >with pointers or indices. This requires no memory management >of any kind (other than, obviously, freeing the array when >the graph isn't needed anymore). If only there was a standard library that came with C++ that had containers that could do something like that.... hmmm.... |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment