Algorithm to traverse all edges in a graph
graph-theory, model-based-testing, python, traversal
Solution
Approach 1
You can change your graph G into a new graph G' where each edge in G becomes a node in G'. Make an edge from t1 to t2 in G' if "A -> t1 -> B -> t2 -> C" is possible in G for some A,B and C.
Then you need to find a path cover in G'.
Approach 2
- Your position P initially is some node P0 (e.g. idle).
- For each edge T (from A to B), find any route from P to A, then use T to go to B. Update P to be B.
- Finally find any route from P back to P0.
Problem
As a personal easter project I'm trying to implement some model-based testing at work. I've got a graph implemented in python and I need to traverse all edges / do all transitions of the graph, at least once. Traversing an edge twice or more does not matter, but I need to start and end in the same node and get a sequence of edges/transitions back. Simpler algorithm > shortest sequence. I've looked around and found a lot of algorithms, but I couldn't find one / a combination that works for me. It would be great if someone could point me in the right direction or give me some tips on how to do this. My graph implementation looks like this: ``` graph = { A : {'IDLE': 't8', 'B': 't2', 'C': 't4'}, B : {'A': 't3', 'C': 't4', 'IDLE': 't6'}, C : {'A': 't5', 'IDLE': 't7', 'B': 't2'}, IDLE : {'A': 't1'} } ```