Asked by Skylar Cox
on 9 Nov 2019 at 21:12

I am trying to find the maximum path through a series of nodes. I have forumulated the problem as a shortest path problem using negative weights for distances between nodes. Node sets are grouped and I want to find a path that only passes through one node of each group. For example, nodes are labeled as start (s) and end (e) and A1, A2, B1, B2, C1, and C2. If a path passes through A1, it cannot pass back through A2. The node groups represent a task that is to be accomplished (letter indicator) while the numeric value indicates a time. This means that task A can be accomplished at two different times but not both. The figure is included for additional information.

I originally started using the 'shortestpath' function in matlab but realized it was revisiting tasks. Are there any algorithms out there that I should look into?

Walter Roberson
님의 답변 9 Nov 2019 21:26

shortest path with negative weights is subject to looping.

You should instead use weights that are the maximum weight plus 1, minus the existing weights.

Skylar Cox
on 9 Nov 2019 at 21:41

Walter Roberson
11 Nov 2019 4:44

Sorry, I did not notice the groups of nodes part before.

For situations like this, you need to work incrementally creating augmented directed graphs.

When you are at S, you have a choice of going to A1. You find the subgraph of all of the places you can get to from A1, and you clone that subgraph into new nodes but with the links back to other members of A deleted, and replace the S -> A1 link with a link from S to that cloned graph. And you do similar things for the other groups, recursively. This can lead to a bunch of branching.

So instead of S -> A1 -> {B1, B2, C3, C4} you would have S -> newA1 -> {A1B1, A1B2, A1C3, A1C4} where A1B1 is like B1 but there is no A1B1 -> A2 link, just A1B1 -> {A1C3, A1C4}

Once S has traversed to newA1 that is disconnected from the previous A1 subtree, then because it is a directed graph, there is no cross-link possible to reach something that could get to a different member of the A group.

Yes, the number of nodes can increase by a fair bit. There might be ways to reduce the branching in some cases.

This approach might perhaps sound too made-up-on-the-spot, but it is similar to the approach that is used to convert Non-Deterministic Finite Automata (NDFA) into Deterministic Finite Automata (DFA), by following all of the paths "simultaneously". A cross-product of states ends up being created, which is the sort of thing that is a nuisance if you are trying to work everything out by hand, but which you can hand over to computers to compute all of.

Sign in to comment.

Answer by Thiago Henrique Gomes Lobato
on 10 Nov 2019 at 10:24

Skylar Cox
10 Nov 2019 15:43

Sign in to comment.

Answer by Christine Tobler
on 11 Nov 2019 at 12:53

There is no direct graph-based algorithm to solve this. I would suggest using the optimization toolbox to define this as an optimization problem. Here's an example:

n = 14;

rng default;

g = digraph(triu(sprand(n, n, 0.3), 1));

g = reordernodes(g, randperm(n));

g.Edges.Weight(findedge(g, 14, 10)) = 0.2;

s = 13; e = 11;

path = shortestpath(g, s, e)

A = adjacency(g, 'weight');

tsp = optimproblem;

edges = optimvar('edges',size(A),'Type','integer','LowerBound',0,'UpperBound',1);

tsp.Constraints.Start = sum(edges(s, :)) == 1;

tsp.Constraints.End = sum(edges(:, e)) == 1;

tsp.Constraints.OnlyExisting = edges.*(A==0) == 0;

intermediateEdges = setdiff(1:numnodes(g), [s e]);

tsp.Constraints.InputEqualOutput = sum(edges(:, intermediateEdges)) == sum(edges(intermediateEdges, :), 2)';

tsp.Constraints.MaxOnePassThroughNode = sum(edges, 1) <= 1;

tsp.Objective = -sum(A.*edges, 'all');

tspsol = solve(tsp);

sg = digraph(tspsol.edges)

figure(1)

p = plot(g);

highlight(p, sg)

% Additional objective: Don't use two nodes from the same group (here,

% let's say 3 and 14 are in the same group):

group = [3 14]

% Allow exactly one outgoing edge among all edges coming out of all nodes

% in the group:

tsp.Constraints.Group = sum(edges(:, group), 'all') <= 1;

tspsol2 = solve(tsp);

sg2 = digraph(tspsol2.edges)

figure(2)

p = plot(g);

highlight(p, sg2)

Every group of nodes can be added as an additional constraint to this formulation.

Note one potential problem with this is that the constraints just say that every node except the start and end node must have as many in-edges as out-edges. If the graph wasn't acyclic, this would mean that it's possible to have a disconnected cycle of nodes that doesn't connected to the path from the start to the end node.

Another possible concern is performance: Calling intlinprog with a numnodes(g)-by-numnodes(g) variable to optimize could be significantly slower than the shortestpath method, for larger graphs.

Skylar Cox
11 Nov 2019 15:39

Excellent. This makes sense. However, when I run the code above, I get an error on the following line:

tsp.Constraints.OnlyExisting = edges.*(A==0) == 0;

I'm not familiar with the optimization toolbox but will start reading up on it. The error says:

"Conversion to optim.problemdef.OptimizationExpression from logical is not possible."

Any suggestions on how to avoid this error? I am running 2018b but can upgrade to a different version if necessary. Thanks.

Christine Tobler
environ 22 heures ago

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.