## 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[][]];      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 🙂

Posted on Categories cheapest proxies

## How to mark a point on a graph?

So I’m obtaining the following graph:

``graphicDelayZOOM =   LogLinearPlot[GroupDelay /. w -> 2 \[Pi] f, {f, 10, 3000},    PlotRange -> {{100, 3000}, {0.000116, 0.0001201}},    PlotPoints -> 200,    PlotStyle -> {{AbsoluteThickness[1.5], RGBColor[1, 0, 0]}},    GridLines -> Automatic, FrameLabel -> {"f(Hz)", "time"},    Frame -> True, BaseStyle -> {FontFamily -> "Times", FontSize -> 12}] `` Now I want to display the point f1=2000, GroupDelay(f1). Is there any easy way to do it?

## Custom layered graph layout

I’d like to write a program to draw a graph taking as an input the size of the layers and the edges of the graph. e.g. For edges={} and Layers={3,3,5,1} I’d expect something like this I’ve used this code to generate the plot but (i) of course I’m just using the ‘trick’ of coloring the edges the same as the background just to put the vertices where I want them – which it’s computationally expensive to do, especially for bigger numbers of vertices, and (ii) I don’t really know how to specify the edges now.

``Layers = {3, 3, 5, 1} // Sort[#, Greater] &; Graph[CompleteGraph[Total[Layers], EdgeStyle -> White], VertexSize -> Large, GraphLayout -> {"MultipartiteEmbedding", "VertexPartition" -> Layers}] ``

Then, my question reduces to: (i) Is there a better way to force the size of the layers, and (ii) how to specify the edges within this new layout.

## How to reverse the arrows in a graph?

I have a directed graph for which I want to reverse the direction of the arrows (not the direction of edges). I don’t want to use `ReverseGraph` because it changes the layout of the graph. Can I achieve this changing `EdgeStyle`?

## Game on the graph with matchings

The game on the graph $$G$$ is defined as follows. Initially, the chip is located at one of the vertices (let’s call it the starting one). The players take turns, on each move it is necessary to move the piece along any outgoing edge to the vertex, where the piece has never been. The one who cannot make a move loses. How to Prove that the former wins if and only if the starting vertex lies in all maximal matchings?

## Independent sets into which all the vertices of the graph can be split

How to prove that if $$G$$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $$G$$?

Posted on Categories proxies

## Complexity of “does a directed graph have

I am studying the complexity classes and I am confused what is the complexity of the following problem: "Does a directed graph G has at most 1 Hamiltonian cycle?"

So, from my knowledge and understanding:

1. Existence of Hamiltonian cycle is a NP(C) problem.
2. Existence of exactly $$k$$ ($$k>1$$) Hamiltonian cycles in a graph belongs to PSPACE.
3. The stated problem would be a complement of "Does a directed graph G has at least 2 Hamiltonian cycles?"

However, I still fail to see to which class the mentioned problem belongs. Originally I though it would also belong to PSPACE, but not to any space in PSPACE. However, I have consulted my teacher and she said that, while it belongs to PSPACE, it also belongs to some subset of PSPACE. Which subset that would be? Does it belong to co-NP, and the problem from 3. then belongs to NP? If yes, how to prove it (because for now I’m just guessing it based on my teachers’ hint)? If no, where does it belong?

## Find connected components of the complementary graph

You are given an undirected graph with $$N$$ vertices and $$M$$ edges.

Find all the connected components in the compliment of the given graph optimally (in $$O(M)$$ or $$O(MlogN)$$).

``//input 4 4 //n,m 1 2  1 3 4 2 4 3  //output 2 //no of connected components 2 1 4  2 2 3  ``

Source

Editorial (I didn’t get it)

Posted on Categories proxies

## Use of graph grammars/rewriting systems in compilers?

A(n imperative) program – in a higher-level language and more importantly in assembly language or intermediate representations like LLVM – can be formalized as a directed "port graph", in which vertices are instructions and ports correspond to input/output operands/arguments. An optimization applied of a program’s code therefore corresponds to a rewrite applied to its port digraph.

Now, graph rewriting is a small but somewhat-active area, in itself. What I’m wondering if these kinds of systems have been actually put to explicit use in the context of a compiler. That is, representing the optimization phase as a rewriting process, or a derivation using a port-graph grammar.

I’m not much of a "compilers guy" – I took a basic course on them in my undergraduate degree, and I know about LLVM and its IR – but it seems to me that graph rewriting systems is the "obvious" formalism to use; and at the same time – I don’t see almost any FOSS projects involving such systems, nor do the papers about them discuss their use in compilers.

Note: I’m more interested in practical-use, popular-language compilers more than academia-only systems, but I’ll take what I can get.

Posted on Categories proxies

## Problem in UVa 1229 (graph – SCC)

I am solving UVa–1229 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=671&page=show_problem&problem=3670 From the problem I have understood what is required – given a list of dictionary words and their definitions, choose minimum set of words such that the whole dictionary can be constructed, if one is given meaning of those words. So words in dictionary must not introduce a new word in definition which has no meaning in dictionary. This implies I have to find SCC.

But there may be several SCCs, I think I must choose which is first in toposort of contracted DAG. Am I correct or is there another way to do it? I have read hints but its’ mentioned to find SCC, then use dfs that will be answer. I don’t get that. Can someone explain approach to this problem.

That’s my first question on SCC’s 🙂