<p>Nomenclature aside (a line graph is something different than what you describe), you appear to be describing the problem of ''maintaining order in a list''. You have a list of items $v_i$ (your graph), you can remove an item from one point in the list and re-insert it elsewhere, and you want to check whether one item appears earlier than another in the list. This problem has a constant-time solution; see Dietz and Sleator, "Two algorithms for maintaining order in a list", STOC 1987, <a href="https://www.cs.cmu.edu/~sleator/papers/maintaining-order.html" rel="noreferrer">https://www.cs.cmu.edu/~sleator/papers/maintaining-order.html</a> and <a href="https://en.wikipedia.org/wiki/Order-maintenance_problem" rel="noreferrer">https://en.wikipedia.org/wiki/Order-maintenance_problem</a></p>

CC BY-SA 3.0
2017-05-09T22:17:09.497Z
2017-05-09T22:17:09.497Z
David Eppstein
<blockquote>
  <p>Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely</p>
  
  <ul>
  <li><p>$\mathsf{move}(v_i, v_j)$:  this operator moves $v_i$ to the position immediately after $v_j$; that is, after calling this function, the graph $G$ becomes (if $i &gt; j$)
  $$
v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_j \rightarrow v_i \rightarrow v_{j+1} \rightarrow \cdots \rightarrow v_{i-1} \rightarrow v_{i+1} \rightarrow \cdots
$$</p></li>
  <li><p>$\mathsf{reachable}(v_i, v_j)$: whether $v_j$ is reachable from $v_i$ in $G$; that is, whether there is a path from $v_i$ to $v_j$</p></li>
  </ul>
</blockquote>

<p>My current idea is to arrange $v_1$, $v_2$, $\cdots$, $v_n$ in a balanced binary tree such that if $v_j$ is reachable from $v_i$, then either one of below holds:</p>

<ul>
<li><p>$v_j$ is in the right subtree of $v_i$;</p></li>
<li><p>$v_i$ is in the left subtree of $v_j$;</p></li>
<li><p>there is a node $v_k$ such that $v_i$ is in the left subtree of $v_k$ and $v_j$ is in the right subtree of $v_k$.</p></li>
</ul>

<p>Using a balanced BST, we can get the rank of each node and by comparing the ranks of two nodes, we can know whether a node is reachable from another.  Therefore, two operations above can be implemented in $O(\log n)$ time.</p>

<blockquote>
  <p><strong>Q:</strong> Is there a better data structure with better complexity please?</p>
</blockquote>

CC BY-SA 3.0
2017-05-09T15:12:53.043Z
Are you sure you don't confuse between line graph (https://en.wikipedia.org/wiki/Line_graph) and directed path?
Lamine
<ds.algorithms><graph-theory><graph-algorithms><ds.data-structures>
Reachability in Dynamic Line Graph
fatelasu
# Reachability in Dynamic Line Graph

(Asked by: username_0 on 2017-05-09)

> Given a directed line graph $G = v\_1 \rightarrow v\_2 \rightarrow \cdots \rightarrow v\_n$, there are two operators, namely
>
> * $\mathsf{move}(v\_i, v\_j)$: this operator moves $v\_i$ to the position immediately after $v\_j$; that is, after calling this function, the graph $G$ becomes (if $i > j$)
>   $$
>   v\_1 \rightarrow v\_2 \rightarrow \cdots \rightarrow v\_j \rightarrow v\_i \rightarrow v\_{j+1} \rightarrow \cdots \rightarrow v\_{i-1} \rightarrow v\_{i+1} \rightarrow \cdots
>   $$
> * $\mathsf{reachable}(v\_i, v\_j)$: whether $v\_j$ is reachable from $v\_i$ in $G$; that is, whether there is a path from $v\_i$ to $v\_j$

My current idea is to arrange $v\_1$, $v\_2$, $\cdots$, $v\_n$ in a balanced binary tree such that if $v\_j$ is reachable from $v\_i$, then either one of below holds:

* $v\_j$ is in the right subtree of $v\_i$;
* $v\_i$ is in the left subtree of $v\_j$;
* there is a node $v\_k$ such that $v\_i$ is in the left subtree of $v\_k$ and $v\_j$ is in the right subtree of $v\_k$.

Using a balanced BST, we can get the rank of each node and by comparing the ranks of two nodes, we can know whether a node is reachable from another. Therefore, two operations above can be implemented in $O(\log n)$ time.

> **Q:** Is there a better data structure with better complexity please?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, ds.data-structures
> **Comments:**
> **username_1**: Are you sure you don't confuse between line graph (https://en.wikipedia.org/wiki/Line_graph) and directed path?  

---

## 1 answers

### Answer by username_2 on 2017-05-09. Score: 5 | Accepted answer

Nomenclature aside (a line graph is something different than what you describe), you appear to be describing the problem of ''maintaining order in a list''. You have a list of items $v\_i$ (your graph), you can remove an item from one point in the list and re-insert it elsewhere, and you want to check whether one item appears earlier than another in the list. This problem has a constant-time solution; see Dietz and Sleator, "Two algorithms for maintaining order in a list", STOC 1987, <https://www.cs.cmu.edu/~sleator/papers/maintaining-order.html> and <https://en.wikipedia.org/wiki/Order-maintenance_problem>


---

