Table of graph paths Hi all! I have the following problem…
0 reactions
Table of graph paths
Hi all! I have the following problem, and I can't find an efficient solution.
I have a directed weighted acyclical graph. I need to create a table of all possible paths within the graph (and, for each row, compute a function on the weights).
This table is finite, because the graph is finite and acyclical, and can be created by taking all nodes that have no in-edges, and doing a graph search for all of them (maybe with some optimizations when it looks like I'm revisiting the same path segments). So far so good.
The problem is - the graph can change. That is, nodes or edges may be removed or added. When it changes, I need to update the table.
I'm trying to think of how to do this without having to rebuild the entire table from scratch, but I'm hitting dead ends everywhere. I don't have any full solution, and even the partial ones look like I'd need to maintain huge amounts of extra tracking information.
Any ideas?
#technology
Hi all! I have the following problem, and I can't find an efficient solution.
I have a directed weighted acyclical graph. I need to create a table of all possible paths within the graph (and, for each row, compute a function on the weights).
This table is finite, because the graph is finite and acyclical, and can be created by taking all nodes that have no in-edges, and doing a graph search for all of them (maybe with some optimizations when it looks like I'm revisiting the same path segments). So far so good.
The problem is - the graph can change. That is, nodes or edges may be removed or added. When it changes, I need to update the table.
I'm trying to think of how to do this without having to rebuild the entire table from scratch, but I'm hitting dead ends everywhere. I don't have any full solution, and even the partial ones look like I'd need to maintain huge amounts of extra tracking information.
Any ideas?
#technology
| 4,000 mlx | |
| 7 | |
| 0 |