Provide simple example on a graph problem

[LianhaoYin]

Is it possible to provide a simple example of a graph problem such as a travel salesman problem?

[bengioe]

Should be possible, I'm not too familiar with standard TSP benchmarks, like say the distribution of pairwise distances. Are there widely recognized libraries that generate these? Or perhaps some standard distribution people sample from?

[LianhaoYin]

Thanks for your response. I was thinking about a simple case like the grid environment. A graph with a few nodes and attributes to the edges, for example in the following image: .

In the beginning, there are no edges and the task is to add edges to connect A to F with the shortest path. The reward will be the inverse of the path length in this case. One can also change the reward function to change it a more general graph. If it is not that clear, I can create a simple Env class in a separate branch and we can work together.

[bengioe]

Yes that should be straightforward enough. You may want to take inspiration from this simple environment (it's still in a branch but I'm hoping to clean it up and merge all of this eventually). If you start a PR/branch I'm happy to give feedback.

[zdhNarsil]

Hi @LianhaoYin, I have a code base for some graph combinatorial optimization problems (not including TSP but hopefully you may find it helpful): https://github.com/zdhNarsil/GFlowNet-CombOpt