Timeline for Best way to implement a heterogeneous graph that multiple algorithms have to work with, each requiring extra data and behavior for each node
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2020 at 16:50 | comment | added | Helloer | @DocBrown: yes, that's probably the best idea, thanks. | |
| Dec 22, 2020 at 16:50 | comment | added | Helloer | @RichardBamford: yes, but I was more wondering where to store the extra data associated to a node. Every node instance needs to have its own data (and the type of the data depends on the algorithm). | |
| Dec 22, 2020 at 16:30 | comment | added | user362602 | Hi you can use double dispatch to get extra information. So Node has a acceptVisitor(visitor) function and the Visitor class has a process(NodeTypeA, extra data) process(NodeTypeB, extra data) which is called by the node. | |
| Dec 22, 2020 at 8:39 | comment | added | Doc Brown | ... ok, I may not have understood everything, but I guess using #4. with a generic void pointer looks most promising. It adds only a little overhead to your nodes, allows you to add arbitrary, algorithm-specific data to each node, and if it is not fast enough for your case, other alternatives will probably be too slow, too. | |
| Dec 22, 2020 at 8:35 | comment | added | Helloer | @DocBrown: one hour ago I tried to add more context to the example, but I couldn't find a way without making the question huge. It's almost bedtime for me. Tomorrow I'll try again to describe what I'm working on and highlight some examples while keeping the post concise. | |
| Dec 22, 2020 at 8:16 | history | edited | Helloer | CC BY-SA 4.0 |
added 224 characters in body
|
| Dec 22, 2020 at 8:12 | comment | added | Helloer | @s.lg: yes, that's an option too. I'll edit my question to add it as a fourth option. My intuition suggested that adding specific-case to a generic interface was a very bad design. Given the alternatives it might be a good compromise though. | |
| Dec 22, 2020 at 8:03 | comment | added | s.lg | Do you really need to frame this as "extra data" ? Why do you need this layer of polymorphisme which looks very cool in theory? Can't you just have one uniq type of node, and have your algorythm simply not use all available field? | |
| Dec 22, 2020 at 7:30 | history | edited | Helloer | CC BY-SA 4.0 |
added 237 characters in body
|
| Dec 22, 2020 at 7:18 | comment | added | Helloer |
About "place extra data right before the node" I mean that, when the factory allocates a node, it can allocate a struct { ExtraData; Node; }. Then it returns a pointer to the Node. By using that pointer it should be able to access the ExtraData.
|
|
| Dec 22, 2020 at 7:16 | comment | added | Helloer | By "extra data" I mean data (variables, function pointers etc) that the algorithm needs to store for every node in order to work. Different algorithms require different data. Some don't require any, others require a couple of ints, other require a stack of pointers or other complex objects. The graph is fixed and it's a directed acyclic graph. The algorithms never modify the nodes (except for their algorithm-specific "extra data"). Usually the nodes are between 50 and 1000. An algorithm might process some nodes hundreds of thousand of times. | |
| Dec 22, 2020 at 5:33 | history | asked | Helloer | CC BY-SA 4.0 |