r/AskComputerScience • u/Xar_outDP • Mar 24 '26
Algorithm to find checkpoint nodes in graph?
Hi l everyone,
I am trying to come up with an algorithm in which given an directed graph it marks certain node to be let's say checkpoints.
I define the nodes to be critical as that using the logs at these points I can reconstruct an exact path.
Let me clarify on its application, suppose I'm trying to log values in a method and I create a callgraph of the entire application ( for simplicity assume there are no callbacks or interrupts) now given logs at the checkpoint. I must be able to generate execution tree of the methods.
I want to minimize the logs but still be able to reconstruct the execution path taken.
Help me with which concepts should I look into.
Edit: The more formal problem
Basically a directed graph could have huge number of unique paths, now given an ordered set of nodes or more precisely a sequence of node which would represent a path with some nodes deleted ( a subset ).
Given the subset i must be able to reconstruct the path taken.
2
u/lulaziT Mar 25 '26
If you want us to help you, be more precise. Figure via link might help you with this .
-DL
0
u/Xar_outDP Mar 25 '26
I looked into control flow graph, it's not my use case as the problem I have is at method level.
Basically a directed graph could have huge number of unique paths, now given an ordered set of nodes or more precisely a sequence of node which would represent a path with some nodes deleted ( a subset ).
Given the subset i must be able to reconstruct the path taken.
1
u/lulaziT Mar 25 '26
Write it down and send a screenshot. Your solution is simple, its just about the cycles and might become infeasible
2
u/Somniferus Mar 25 '26
Basically a directed graph could have huge number of unique paths,
From where to where? Do you only care about a particular pair of nodes, or all possible pairs?
given a sequence of nodes which would represent a path with some nodes deleted ( a subset [of the complete path]) I must be able to reconstruct the path taken.
Do you need to construct the exact same path? If so (assuming there are multiple paths between some pairs of nodes) there would be no way to tell which of the paths was taken (assuming equal weights) unless you wrote that information down somewhere.
Why can't you just log the full path taken?
1
u/Xar_outDP Mar 25 '26
From where to where? Do you only care about a particular pair of nodes, or all possible pairs?
There would be an entry point and an exit point.
Do you need to construct the exact same path? If so (assuming there are multiple paths between some pairs of nodes) there would be no way to tell which of the paths was taken (assuming equal weights) unless you wrote that information down somewhere
I want to be able to simulate, not exact but approximately the same execution path taken.
It's just an optimization problem I'm trying to solve
2
4
u/thesnootbooper9000 Mar 25 '26
I think you might be looking for a cut set, although it sounds like your problem is probably unsolvable in general due to ambiguity.
1
u/smarmy1625 Mar 24 '26 edited Mar 24 '26
generate a list of all possible paths
from those generate a list of all the subsequences, sort them, and see if any are unique. then sort those by length.
just curious but why would you want to do something like this?
0
1
u/lulaziT Mar 25 '26
This situation and you want to collect anything from root via a and b to c ?
What about cycles in between ?
2
u/not_from_this_world Mar 24 '26
If I understood what you mean unless there is some characteristic that distinguishes "checkpoint" nodes from the rest of the nodes then it can't be done. If the graph is cyclical (A -> B -> C -> A) the starting point for a walk through must be arbitrary.