How to find all possible paths between a collection of vertices in a DAG graph

I have a toy example "system" that is a DAG and has 16 vertices. Suppose I have a collection of vertices "collection". How can I find all paths that passes through at least all vertices present in "collection"? The functions available all seem to work with source and target vertices but not with a collection of vertices.

My only solution up to now is rather naïve and I need to know the source and target vertex. I would like to avoid that if possible.

``g = Graph[{1 \[DirectedEdge] 2, 1 \[DirectedEdge] 3,       2 \[DirectedEdge] 6, 3 \[DirectedEdge] 7, 3 \[DirectedEdge] 8,       7 \[DirectedEdge] 9, 7 \[DirectedEdge] 10, 6 \[DirectedEdge] 11,       6 \[DirectedEdge] 12, 12 \[DirectedEdge] 13, 13 \[DirectedEdge] 14,       8 \[DirectedEdge] 10, 6 \[DirectedEdge] 10, 12 \[DirectedEdge] 15,       15 \[DirectedEdge] 16, 15 \[DirectedEdge] 17, 17 \[DirectedEdge] 14,      2 \[DirectedEdge] 12, 11 \[DirectedEdge] 16, 10 \[DirectedEdge] 16,      9 \[DirectedEdge] 16}, VertexLabels->Automatic]; collection = {1, 3, 10, 16}; HighlightGraph[g, collection, VertexLabels -> Automatic] ``

Now I search for all paths between the vertices 1 and 16

``allpaths = FindPath[g, 1, 16, All, All] HighlightGraph[g, allpaths, ImageSize -> 300] ``

Now I collect the possible candidates

``paths = If[ContainsAll[#, collection], #, Nothing] & /@ allpaths HighlightGraph[g, paths, ImageSize -> 300] ``

As asked above are there other ways to do this WITHOUT knowing that I need paths between vertex 1 and 16?

Wildcard redirects for paths in Google Domains

The Goal: redirect www.example.com/product/* to www.example.com/product using Google Domains

Background: I’m using github pages to host my site so I cannot add an htaccess file like a more traditional site. Also I had some issues with emails from my domain going to spam when I used Cloudflare.

There doesn’t seem to be an option to simply set up wildcard redirects for paths. it’s just subdomain.

Efficiently determining the K shortest paths in a graph

My goal is to efficiently find the $$k$$ shortest paths between a source and a destination in an undirected graph. I implemented two solutions of this problem myself, but, as I am very interesting in efficiency, was wondering if there might be a more efficient solution to this problem.

The first solution is based on Yen’s algorithm (https://en.wikipedia.org/wiki/Yen%27s_algorithm):

``yen[graph_, source_, destination_, k_] :=    Module[{a, b, gtemp, spurnode, roothpath, sp, roothminusspur,      double, WAmatrix, dirgraph},    a = {FindShortestPath[graph, source, destination]};    b = {};    Do[     Do[      gtemp = graph;      roothpath = a[[-1]][[1 ;; i + 1]];      roothminusspur = Drop[roothpath, -1];      double =        Table[If[         a[[l]][[1 ;; Min[i + 1, Length[a[[l]]]]]] == roothpath,          a[[l]][[i + 1]] \[UndirectedEdge] a[[l]][[i + 2]], {}], {l, 1,          Length[a]}];      gtemp = EdgeDelete[gtemp, Union[Flatten@double]];      gtemp = VertexDelete[gtemp, roothminusspur];      sp = FindShortestPath[gtemp, roothpath[[-1]], destination];      If[Length[sp] > 0,        AppendTo[        b, {GraphDistance[gtemp, roothpath[[-1]], destination],          Flatten@{roothminusspur, sp}}]];      , {i, 0, Length[a[[-1]]] - 2}];     If[Length[b] == 0, Break[],       b = SortBy[Union[b], First];      AppendTo[a, b[[1]][[2]]];      b = Drop[b, 1]];     , {j, 1, k - 1}];    Return[a]    ]; ``

The second solution is a bit ugly and can be arbitrary slow, but works quite well on graphs that have a lot of arcs and the weights between these arcs do not differ that much. The idea is to use the build-in `FindPath` function of Mathematica and increase the costs, until you have indeed found $$k$$ or more paths. If you have found more than $$k$$ paths, you delete the paths with the most costs:

``nmatrix = WeightedAdjacencyMatrix[graph]; maxcosts = Total[nmatrix, 2]; costs = GraphDistance[graph, source, destination]; Do[  paths = FindPath[graph, source, destination, costs + l, All];  If[Length[paths] >= k, costest = costs + l - 1; Break[]],   {l, 0, Round[maxcosts - costs]}]; If[Length[paths] > k,   defpaths = FindPath[graph, source, destination, costest, All];  possiblepaths = Complement[paths, defpaths];  costpaths =    Table[Sum[     nmatrix[[possiblepaths[[j]][[i]]]][[possiblepaths[[j]][[i +           1]]]], {i, Length[possiblepaths[[j]]] - 1}], {j,      Length[possiblepaths]}];  paths = Join[defpaths,     possiblepaths[[Ordering[costpaths][[1 ;; k - Length[defpaths]]]]]];  ]; ``

Any hints/suggestions for speed-up techniques or more elegant solutions are more than welcome 🙂

How many shortest paths are there from source to destination?

I am not sure if my question is clear or not to you. In fact this question is not clear to me. My university teacher has assigned this question to me.

Can you answer it? or need clarification like- if the graph is directed edged or not, if they are weighted or not, which algorithm will be used?

I have no such information. Only the question.

Calculate the area of the shape created by multiple paths

I’m trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example:

Basics

• 4 separate paths (A,B,C,D) which are a collection of vertices (A1,A2,…)
• Area desired is represented by green

Edge Cases

• As shown with B, a path might have segments that don’t contribute to a filled shape
• As shown with C, a path might be completely enclosed by other paths and therefore should basically be ignored.
• As shown with D, paths may create independent shapes
• As shown with A and B, it should be a union of all the shapes

My first question is if an algorithm for this already exists. If it does, it would save me a lot of effort :). I tried searching around but I don’t even know how to describe this problem concisely.

Assuming one doesn’t exist for this exact purpose I have to move on to figuring it out myself. I’m assuming the right data structure for the job is a graph. I’m thinking I will add points for each intersection (highlighted in red) as I insert paths into the graph.

Then "all I need" is an algorithm for tracing around the outside of each shape because calculating the area of those irregular polygons will be simple. Does something like that already exist? My primary hangups when I think about how to do this are:

• What vertex do I "start" at?
• How do I account for multiple shapes (D as well as A,B,C)?
• How do I account for the parts of shapes like formed by A1,A5,A5 where I’ll be visiting that intersection point multiple times?

I’m not necessarily looking for a complete solution, I’d love thoughts on if you think I’m approaching this the best way so far and if you have any ideas/suggestions on how to achieve this.

Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths

I have a graph like this that starts from one top node and has cycles:

I need to write an algorithm to figure if `node1` depends on `node2`. The most primitive algorithm I’ve written simply starts with `node1` and recursively follows all available edges looking for `node2` starting from `node1`. It’s very inefficient because I traverse the graph over and over again. I’m wondering if there’s an algorithm I can look at that caches nodes and dependencies it already walked through so that I don’t go through paths I’ve walked once and can figure if there’s a dependency or not from cache?

For example, if I’m given node `D` and the question is whether it depends on node `F`, I’ll walk `D->E->F`, and when next time I get the question if node `E` depends on `F`, I’ll get that from cache without walking the graph.

Thanks for any ideas and suggestions!

Where in the Sargauth Level are the paths into Skullport?

In Waterdeep: Dungeon of the Mad Mage and its Maps and Miscellany, there is a map of the Sargauth level and a map of the levels of Skullport.

Skullport’s maps show the five paths in and out: Shadow Pass, Beggar’s Rest Pass, Taglath’s Gap, Steamfall Pass and Whisperhaunt Pass.

However, the Sargauth Level’s maps only shows two paths labelled "To Skullport" how are these paths connected?

Reference for counting the number of paths in a DAG

Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .

Is there a reference or name for the algorithm? If not, are there well known applications?

Directed Grid Graphs; All Possible Paths Through Nodes

I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary number. I want to search for a list of paths (sets of edges essentially) that traverse through the grid space of the same dimension & create the paths such that the # of edges in a path going through a node is equal to the nodes weight (from the matrix). Ie: if a particular index in my matrix was "3", there would be 3 edges that would run into (and out of) this node.

Some important restrictions. Firstly, The only direction the edges can move is rightward (so vertical edges are disallowed) but only one column distance at a time. I do allow for the edges to go from any row_j (in column_i) to any other possible row_j in column_i+1, so diagonal edges (either upwards or downwards are allowed). Here’s an example of such a solution (it is non singular which is why Im interested in ALL possible paths)

Most importantly, I am interested in two things. First I want all possible paths from this process, and even more critically, I want to minimise the number of possible diagonal edges that my resulting paths will contain.

Any sort of algorithm here to solve this would be hugely helpful.

I have managed to solve the case when I don’t care about the number of diagonal edges, and just want a set of paths that match with the weights. To do that, I used the weights at adjacent columns to generate a Markov transition process. This gave me a series of transition matrices (of length ncol-1) which from there I was able to construct probabilistically what my paths through my weights were.

Let me know if anyone needs any more details/explanations here.

Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson’s Algorithm can be used to solve the APSP-Problem in $$O(V^2\log V + VE)$$ in stead of $$O(V^3)$$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the case that some weights are negative. Is there a faster way to compute this given that all weights are positive?