Traverse a directed graph visiting all edges at least once?

I am working on a project utilizing the Chinese Postman Problem where I want to find the shortest path in a directed matrix that visits each edge at least once starting from a specified node. Are there any Graph Theory functions that deal with this kind of problem?

Answer 1

[Christine Tobler]

There aren't any functions for MATLAB's graph object that solve this problem. Possibly you can formulate this as an optimization problem? See https://www.mathworks.com/help/optim/ug/traveling-salesman-problem-based.html for an example of how to solve the related Traveling Salesman Problem using the optimization toolbox.

[Michael Bockwoldt]

Thank you for the reply and the reference link. The TSP approach seems interesting, though the critical element to my problem is that each edge is traversed.

So far the closest I think I've come to a solution has involved using the depth-first search functions. I can get each edge to be traversed, but I'm not sure if its the optimal path in the graph.

[Christine Tobler]

You could try to introduce a new node in the middle of each edge, at which point the goal becomes to visit each node at least once instead of doing so for each edge.

I'm not sure how straightforward allowing the TSP approach to traverse a node several times would be, though.

[Michael Bockwoldt]

Introducing a new node in the middle of each edge could potentially work.

Doing some more research, I found some code you made/commented on from 2018 on another question thread. Can this code be manipulated such that all nodes must be traversed, but nodes can be visited more than once if needed?

Thanks again for your help!

W = [5 1 5 4 6 1 1 4 7 2 6 7 3 2 1 2 3 8 2 8];
DG = sparse([1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6],...
            [2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5],W);
g = graph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 6:
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths 6*ones(size(paths, 1), 1)];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
      path = paths(ii, :);
      edgeID = findedge(g, path(1:end-1), path(2:end));
      if all(edgeID ~= 0)
          dist(ii) = sum(g.Edges.Weight(edgeID));
      end
  end
[~, id] = min(dist)
paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, paths(id, :), 'EdgeColor', 'red')

[Christine Tobler]

This could be used to solve the Traveling Salesman problem (not efficiently), but not for the variant your looking for.

Here I'm just going through all possible ways of visiting each node exactly once, and then taking the minimum of that large set of possibilities. But when nodes can be visited many times, there's no way to just write up all possible orders of visiting the nodes, there are infinitely many ways to do this.