How to code/explore multiple linear orderings of a DAG
Consider directed acyclic graph G(V,E), where V={1,2,3,4,5,6,7} and E={(1,2),(1,3),(1,4),(2,5),(3,5),(4,6),(5,7),(6,7)}
The problem here is to explore multiple linear orderings of the graph. Therefore, how to code/decode it in a way that it always leads to a feasible linear ordering of the graph (topological order)?
One possible way to explore different linear orderings of a DAG could be defining a string (chromosome) with the same size of V, where each element of the string denotes a cost for each vertex, i.e., the cost of the ith vertex is given by the ith element in the string.
A custom transversal graph algorithm could be used for decoding. Every time more than on vertex with all its predecessors visited can be found, the algorithm should visit then in ascending order based on the cost provided by the string.
For the DAG given above and a cost string {0.6, 0.8, 0.5, 0.1, 0.5, 0,3, 0.9}, the linear order obtained would be {1, 4, 6, 3, 2, 5, 7}.