<p>The following suggestion may speed up your solution if you need to answer queries for many different words.</p>

<p>Define the set $U_i^w$ to be a set of pairs $(v, A)$ where $A \subseteq V$ and $v$ is reached by some vertex in $A$ after traversing the first $i$ labels of the word $w$.  Then to check if $w$ forms a cycle in the graph, loop through all $(v, A) \in U_{|w|}^w$ and if ever $v \in A$, then a cycle does exist.</p>

<p>Note that if the first $i$ elements of $w$ and $w&#39;$ are the same, then $U_i^w = U_i^{w&#39;}$.  Also, $U_0^w = \{(v, \{v \} ) | v \in V \} $.</p>

<p>As you process queries, dynamically construct a <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow">trie</a> such that each node (including the inner nodes) stores $U_i^w$ for some $i$ and $w$.  This way, if $w$ and $w&#39;$ have the same first $k$ elements and $w$ is processed before $w&#39;$, then $U_k^{w&#39;}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.</p>

CC BY-SA 3.0
2011-04-29T08:16:43.937Z
Surely this only works if $A$ consists of a single vertex? For example consider the digraph with 2 vertices {x, y} and a directed edge labelled 1 connecting from each to the other. If $U^{1}_{1} = \lbrace x, \lbrace x,y \rbrace \rbrace$ then $v \in A$ but the word "1" doesn't form a cycle anywhere in this graph.
qwerty1793
CC BY-SA 3.0
2011-04-29T13:05:45.630Z
Hello @qwerty.  $U_1^1$ would consist of pairs $(v, A)$ such that such that $A$ consists of all vertices $u$ which have a path to $v$ by traveling along an edge labeled 1.  In your example, $U_1^1 = \{(x, \{y\}), (y, \{x\})\}$.  Thus it contains no $(v, A)$ with $v \in A$.  Hope this helps make it clearer.
bbejot
CC BY-SA 3.0
2011-04-26T13:51:51.633Z
2011-04-26T13:51:51.633Z
bbejot
<p>Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at most 1 edge labelled $x$ connecting out of $v$, i.e. there is at most one edge labelled $x$ with tail $v$. </p>

<p>Let $w$ be a word made using elements of $X$ as letters. For a given vertex $v$, $w$ defines a path through G by following the correctly labelled edges (if they exist) starting at $v$. I would like to determine if a $w$ forms a cycle anywhere within G.</p>

<blockquote>
  <p>Is there a more efficient way to determine if there is a $v \in V$ such that $w$ forms a cycle when started at $v$ than checking where the path $w$ terminates for every starting vertex? </p>
</blockquote>

CC BY-SA 3.0
2011-04-21T14:25:22.570Z
Do you want a simple cycle (a cycle without vertex repetition), or do you allow a cycle to repeat a vertex?
Yoshio Okamoto
CC BY-SA 3.0
2011-04-21T19:56:00.263Z
I do not care about the cycle being simple. I should point out that the graph may also contain loop edges connecting back to the same vertex.
qwerty1793
CC BY-SA 3.0
2011-04-21T23:04:24.537Z
Can an edge be repeated? 

Out of curiosity, what's your interest in this question?
Josephine Moeller
CC BY-SA 3.0
2011-04-22T08:15:41.353Z
Yes, there can be multiple edges connecting from / to the same vertices (although they must have different labels in order that 'there is at most one edge labelled x with tail v'). 

The question comes from computational topology where the vertices of the graph represent simple loops on a punctured 2-manifold. The edges represent the action of Dehn twists on these loops and w is a sequence of twists specifying a monodromy for a mapping torus. The torus is reducible if and only if w forms a loop somewhere in this graph.
qwerty1793
CC BY-SA 3.0
2011-04-26T15:03:51.957Z
Which do you mean by “forms a cycle”: (1) The starting vertex and the ending vertex of the path are the same.  (2) During the path, you visit some vertex more than once.  In other words, does the path A-B-C-D-B-E (where A, B, C, D and E are vertices of a graph) “form a cycle” or not?
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-29T08:05:34.030Z
@Tsuyoshi, The path A-B-C-D-B-E does NOT form a cycle as the start and end vertices are not the same. (1) is the correct definition of cycle in this case.
qwerty1793
<ds.algorithms><reference-request><graph-theory><graph-algorithms>
How to determine if a labelled digraph contains a cycle with given labels?
qwerty1793
# How to determine if a labelled digraph contains a cycle with given labels?

(Asked by: username_0 on 2011-04-21)

Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at most 1 edge labelled $x$ connecting out of $v$, i.e. there is at most one edge labelled $x$ with tail $v$.

Let $w$ be a word made using elements of $X$ as letters. For a given vertex $v$, $w$ defines a path through G by following the correctly labelled edges (if they exist) starting at $v$. I would like to determine if a $w$ forms a cycle anywhere within G.

> Is there a more efficient way to determine if there is a $v \in V$ such that $w$ forms a cycle when started at $v$ than checking where the path $w$ terminates for every starting vertex?

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Do you want a simple cycle (a cycle without vertex repetition), or do you allow a cycle to repeat a vertex?  
> **username_0**: I do not care about the cycle being simple. I should point out that the graph may also contain loop edges connecting back to the same vertex.  
> **username_2**: Can an edge be repeated?   Out of curiosity, what's your interest in this question?  
> **username_0**: Yes, there can be multiple edges connecting from / to the same vertices (although they must have different labels in order that 'there is at most one edge labelled x with tail v').   The question comes from computational topology where the vertices of the graph represent simple loops on a punctured 2-manifold. The edges represent the action of Dehn twists on these loops and w is a sequence of twists specifying a monodromy for a mapping torus. The torus is reducible if and only if w forms a loop somewhere in this graph.  
> **username_3**: Which do you mean by “forms a cycle”: (1) The starting vertex and the ending vertex of the path are the same.  (2) During the path, you visit some vertex more than once.  In other words, does the path A-B-C-D-B-E (where A, B, C, D and E are vertices of a graph) “form a cycle” or not?  
> **username_0**: @Tsuyoshi, The path A-B-C-D-B-E does NOT form a cycle as the start and end vertices are not the same. (1) is the correct definition of cycle in this case.  

---

## 1 answers

### Answer by username_4 on 2011-04-26. Score: 1

The following suggestion may speed up your solution if you need to answer queries for many different words.

Define the set $U\_i^w$ to be a set of pairs $(v, A)$ where $A \subseteq V$ and $v$ is reached by some vertex in $A$ after traversing the first $i$ labels of the word $w$. Then to check if $w$ forms a cycle in the graph, loop through all $(v, A) \in U\_{|w|}^w$ and if ever $v \in A$, then a cycle does exist.

Note that if the first $i$ elements of $w$ and $w'$ are the same, then $U\_i^w = U\_i^{w'}$. Also, $U\_0^w = \{(v, \{v \} ) | v \in V \} $.

As you process queries, dynamically construct a [trie](http://en.wikipedia.org/wiki/Trie) such that each node (including the inner nodes) stores $U\_i^w$ for some $i$ and $w$. This way, if $w$ and $w'$ have the same first $k$ elements and $w$ is processed before $w'$, then $U\_k^{w'}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.

> **Comments:**
> **username_0**: Surely this only works if $A$ consists of a single vertex? For example consider the digraph with 2 vertices {x, y} and a directed edge labelled 1 connecting from each to the other. If $U^{1}_{1} = \lbrace x, \lbrace x,y \rbrace \rbrace$ then $v \in A$ but the word "1" doesn't form a cycle anywhere in this graph.  
> **username_4**: Hello @qwerty.  $U_1^1$ would consist of pairs $(v, A)$ such that such that $A$ consists of all vertices $u$ which have a path to $v$ by traveling along an edge labeled 1.  In your example, $U_1^1 = \{(x, \{y\}), (y, \{x\})\}$.  Thus it contains no $(v, A)$ with $v \in A$.  Hope this helps make it clearer.  

---

