0
$\begingroup$

Given a directed graph $D = (V,A)$ with edge-weights $w\in\mathbb{R}_{++}^A$ I'm trying to construct the following graph $D'=(V',A')$:

  • For a fixed $v\in V$ we add a vertex $(v,0)$ to $V'$
  • For every $(z,i)\in V'$ and $zu\in A'$ we add the vertex $(u,i+w_{zu})$ and the arc $(z,i)\to(u,i+w_{zu})$
  • In each path of $D'$ the only vertex of $V$ that can be repeated is $v$ (and the path most end there)

For example if we have the graph $D=(V,A)$ with:

$$V = \{u,v,x,y,z,a\}$$ $$A = \{vz,zu,uv,vy,yx,xv,xu,xa\}$$

the new graph will be given by

  • $(v,0)\to(z,w_1)\to(u,w_2)\to(v,w_3)$
  • $(v,0)\to(y,w_4)\to(x,w_5)\to(v,w_6)$
  • $(x,w_5)\to(u,w_7)\to(v,w_8)$
  • $(x,w_5)\to(a,w_9)$

where the $w$'s are the respective sums of the weights.

At first I tried to attack this problem using a DFS type of approach, but given that the nodes can be repeated under certain conditions I got stuck and with no clues on how can this graph be constructed (algorithmically). Any ideas?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Welcome to CS.SE! I'm afraid I don't understand your third bullet item. The first two bullet items define a graph $D'$. That graph doesn't have the property defined in the third bullet; there will exist paths $\cdots \to (v,i) \to \cdots \to (v,j) \to \cdots$. So, it seems like you're making a claim that is just false, or imposing a restriction that contradicts the construction of $D'$. $\endgroup$ – D.W.♦ Feb 10 at 6:21
  • $\begingroup$ Anyway, I don't see what the problem is. What is your question? You defined how to construct $D'$; constructing it in code is a straightforward matter of programming (use loops etc.). $\endgroup$ – D.W.♦ Feb 10 at 6:21
  • $\begingroup$ Thanks for the welcome. Maybe I explain myself poorly, what I want is $D’$ to be constructed following the 3 bullets. Why? because if I just use 1 and 2 the graph will be infinite whenever there is a circuit in the original graph. So what I’m saying is, first do 1, then start doing 2 and in each path you are constructing, stop it whether there is no more nodes to visit or you encounter a repeated node (first element of the tuple) but if it is v you add it, else you don’t. $\endgroup$ – esv Feb 11 at 7:30
  • $\begingroup$ And in that case I don’t feel the code will be straightforward (I can be completely wrong) because you need to keep the track of visiting nodes in each path you are constructing and I’m unsure of how to do it $\endgroup$ – esv Feb 11 at 7:33
  • $\begingroup$ Can you edit the question to state that, and state that more clearly? Also in that case I don't see what's wrong with DFS. $\endgroup$ – D.W.♦ Feb 11 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.