# Graph theory notation of path concatenation

I was wondering what the proper notation would be when concatenating paths, written as a sequence of nodes, rather than a set of edges.

That is:

Given:

$$P = ( x, y, z )$$

Is it valid to write the following path concatenations?

$$\begin{eqnarray} P' & = & ( s, x, y, z, t ) \\ & = & ( s, P, t ) \\ & = & ( s ) \cup P \cup ( t ) \\ & = & ( s ) + P + ( t ) \end{eqnarray}$$

I'm assuming not all of them are regarded as valid. So which one is preferable? Or am I overlooking a better notation?

I would prefer not having to fallback to the more verbose:

$$\begin{eqnarray} P &=& \{(x,y), (y,z)\} \\ P'&=& \{( s, x ), (x, y), (y,z), (z,t)\} \\ &=& \{(s,x),(z,t)\} \cup P \end{eqnarray}$$

However, I would still like to be able to reason about the edges along the path $P$ and $P'$, e.g.:

$$(x,y) \in P$$

or write itterations over edges in P: $$\{ \text{do something with v and/or w...} \; | \; ( v, w ) \in P \}$$

-

I suggest that you pick something reasonable and unambiguous, state it clearly, and then stick with it. Do not use $\cup$, since that means set union.

For example, you might use a semicolon: $P_1;P_2$ means that $P_1$ ends at the same vertex at which $P_2$ starts, and we want the path that traces $P_1$ and then $P_2$. This expands nicely to include extra vertices: $P_1;v;P_2$ means the path that goes along $P_1$, then from the end vertex of $P_1$ to $v$, then to the start vertex of $P_2$, and so on. This notation requires that we understand the $v$ by itself as a trivial path with no edges, which is quite reasonable. Similarly $s;P;t$ is a straightforward extension of the notation.

Usually paths are sequences of edges, not sets of edges; the order of the edges in the path is important. I would avoid writing $P = \{(a,b), (b,c)\}$ for this reason, preferring something like $P = \langle a,b,c\rangle$ if there is at most one edge between any pair of vertices, or $P=a\stackrel{E_1}{\to}b\stackrel{E_2}{\to}c$ otherwise or if the names of the edges are important.

You could say that you will abuse notation by writing $E_1\in P$ when you mean that $E_1$ is one of the edges in the path $P$, and this probably won't bother anyone. If it worries you, you might say that you will use $\lvert P\rvert$ to mean the set of edges in $P$, and then $E_1\in\lvert P\rvert$ and $\{\text{do something with$v$and/or$w\ldots$} \mid (v,w)\in\lvert P\rvert\}$ are completely reasonable and also easy to understand.

You might also take a look at some elementary graph algorithm books to see what they do in similar cases.

-
I agree with your statement that writing a sequence of nodes is preferable and unambiguous. But that still leaves the question on how to write concatenations unambiguously. –  A.J.Rouvoet Feb 26 '13 at 17:20
I have added a new second paragraph that you might like better. –  MJD Feb 26 '13 at 17:26
Thank you, your suggestions have been helpful. I think I will use it. I do however would like to know if the kind of notation you proposed is common or if it is usually solved differently; it seems to me that some kind of standard has been set long ago for something this elementary. –  A.J.Rouvoet Feb 26 '13 at 17:29
I think you should wait before accepting my answer; you might get one later that you like better. –  MJD Feb 26 '13 at 17:34

In topology, a path is a function from an interval to a specified topological space, and the composition of two paths $f$ and $g$ is often just denoted $fg$.

In formal languages, a string is a sequence of characters from a specified alphabet, and the concatenation of two strings $\sigma_1$ and $\sigma_2$ is denoted $\sigma_1\sigma_2$.

Paths in a graph are closely analogous both to topological paths and to sequences of nodes/edges, which suggests denoting path concatenation simply as juxtaposition. In particular, I would write the path in your question simply as $sPt$, or as $e_1Pe_2$ where $e_1$ and $e_2$ join $s$ to $x$ and $z$ to $t$ respectively.

-

It depends. If your paths are simple (i.e. no vertex can appear twice), then the usual set operations should be enough.

If you can have arbitrarily complex paths, then consider the following solutions:

• Define a new operator for path concatenation, for example $\circ$ or $\oplus$, and then use it like $\langle s \rangle \circ P \circ \langle t \rangle$, remember to differentiate between sets of nodes and paths, e.g. by using $\{$ braces $\}$ and $\langle$ brackets $\rangle$.
• Use notation from rewriting systems, where usually a single edge is denoted by $\alpha \to \beta$ or $\alpha \leadsto \beta$, while multiple edges get a star (or a plus $+$ if there is at least one edge), $\alpha \to^* \beta$ or $\alpha \leadsto^* \beta$. Of course, if you need you can label edges $\alpha \xrightarrow{e_{\alpha\beta}} \beta$ or entire paths $\alpha \xrightarrow{P}{\!\!}^* \beta$. If you were to use this one, I recommend \xrightarrow{text} instead of \stackrel{text}{\to}.

Have fun ;-)

-