<p>A simple DFS+DP implementation was added to SAGE 4.8 last year:
sage.graphs.graph_decompositions.vertex_separation.path_decomposition</p>

<p>It's implemented in Cython (GNU GPL) <a href="http://trac.sagemath.org/sage_trac/browser/sage/graphs/graph_decompositions/vertex_separation.pyx" rel="nofollow">here</a> and <a href="http://trac.sagemath.org/sage_trac/browser/sage/graphs/graph_decompositions/fast_digraph.pyx" rel="nofollow">here</a>. Very simple and short if you ignore everything nonessential. $O(n\omega 2^n)$ time where $\omega = pw(G)$. It could be sped up with pruning rules, and particularly a heuristic.</p>

CC BY-SA 3.0
2012-05-30T18:59:33.233Z
Wouaaaaaaaaahhhh !! How did you learn that it was added to Sage ? Nice to see people actually look what Sage's new features are :-)
Nathann Cohen
CC BY-SA 3.0
2012-05-30T19:01:27.157Z
By the way the module's documentation is just there, and explains how it all works : http://www.sagemath.org/doc/reference/sage/graphs/graph_decompositions/vertex_separation.html
Nathann Cohen
CC BY-SA 3.0
2012-05-31T21:18:39.823Z
Sorry to disappoint, but I'm not actually a SAGE user; Google found your patch contributing it. I would contribute to SAGE (I already use Cython), but I feel like it would be better to contribute to upstream projects (NetworkX?) where more people can make use of it.
Ralph Versteegen
CC BY-SA 3.0
2013-07-29T07:32:13.090Z
Well. NetworkX is not really "upstream" of Sage anymore, as it does not really use NetworkX much unless you ask for it. And being able to use other parts of maths, Cython and the interface with linear programming makes a difference too :-P
Nathann Cohen
CC BY-SA 3.0
2012-05-30T16:26:03.837Z
2012-06-01T08:29:57.523Z
2012-06-01T08:29:57.523Z
Ralph Versteegen
<p>Don't know about "an implementation" but check out</p>

<p>Computing Pathwidth Faster Than 2^n 
Karol Suchan and Yngve Villanger 
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009,Copenhagen, Denmark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.</p>

CC BY-SA 3.0
2011-07-12T15:43:03.150Z
2011-07-12T15:43:03.150Z
Andreas Björklund
<p>Hisao Tamaki recently devised an exact algorithm for directed pathwidth (WG 2011). There he refers to some successful practical application of his approach (ISCIT 2010), so I guess he also has an implementation of the algorithm.</p>

<p>Hisao Tamaki: A directed path-decomposition approach to exactly identifying attractors of boolean networks. International Symposium on Communications and Information Technologies (ISCIT 2010), pp. 844-849</p>

<p>Hisao Tamaki: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), LNCS 6986, pp. 331-342.</p>

CC BY-SA 3.0
2012-07-08T11:20:55.567Z
2012-07-08T11:20:55.567Z
Hermann Gruber
<p>I am looking for an implementation of an algorithm to compute the <a href="http://en.wikipedia.org/wiki/Path_decomposition">pathwidth</a> of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex separation number, or interval thickness of the graph. The algorithm does not have to be very fast; I want to run it on graphs of at most 20 vertices. I do require the algorithm to compute the pathwidth exactly, rather than giving an approximation.</p>

<p>I am aware that there are some implementations to compute the treewidth of a graph (a related concept) but have not been able to find any to compute the pathwidth. Any pointers are appreciated!</p>

<ds.algorithms><reference-request><graph-algorithms><implementation>
Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)
Bart Jansen
# Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)

(Asked by: username_0 on 2011-07-12)

I am looking for an implementation of an algorithm to compute the [pathwidth](http://en.wikipedia.org/wiki/Path_decomposition) of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex separation number, or interval thickness of the graph. The algorithm does not have to be very fast; I want to run it on graphs of at most 20 vertices. I do require the algorithm to compute the pathwidth exactly, rather than giving an approximation.

I am aware that there are some implementations to compute the treewidth of a graph (a related concept) but have not been able to find any to compute the pathwidth. Any pointers are appreciated!

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


---

## 3 answers

### Answer by username_1 on 2012-05-30. Score: 8 | Accepted answer

A simple DFS+DP implementation was added to SAGE 4.8 last year:
sage.graphs.graph\_decompositions.vertex\_separation.path\_decomposition

It's implemented in Cython (GNU GPL) [here](http://trac.sagemath.org/sage_trac/browser/sage/graphs/graph_decompositions/vertex_separation.pyx) and [here](http://trac.sagemath.org/sage_trac/browser/sage/graphs/graph_decompositions/fast_digraph.pyx). Very simple and short if you ignore everything nonessential. $O(n\omega 2^n)$ time where $\omega = pw(G)$. It could be sped up with pruning rules, and particularly a heuristic.

> **Comments:**
> **username_2**: Wouaaaaaaaaahhhh !! How did you learn that it was added to Sage ? Nice to see people actually look what Sage's new features are :-)  
> **username_2**: By the way the module's documentation is just there, and explains how it all works : http://www.sagemath.org/doc/reference/sage/graphs/graph_decompositions/vertex_separation.html  
> **username_1**: Sorry to disappoint, but I'm not actually a SAGE user; Google found your patch contributing it. I would contribute to SAGE (I already use Cython), but I feel like it would be better to contribute to upstream projects (NetworkX?) where more people can make use of it.  
> **username_2**: Well. NetworkX is not really "upstream" of Sage anymore, as it does not really use NetworkX much unless you ask for it. And being able to use other parts of maths, Cython and the interface with linear programming makes a difference too :-P  

---

### Answer by username_3 on 2011-07-12. Score: 8

Don't know about "an implementation" but check out

Computing Pathwidth Faster Than 2^n
Karol Suchan and Yngve Villanger
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009,Copenhagen, Denmark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.


---

### Answer by username_4 on 2012-07-08. Score: 2

Hisao Tamaki recently devised an exact algorithm for directed pathwidth (WG 2011). There he refers to some successful practical application of his approach (ISCIT 2010), so I guess he also has an implementation of the algorithm.

Hisao Tamaki: A directed path-decomposition approach to exactly identifying attractors of boolean networks. International Symposium on Communications and Information Technologies (ISCIT 2010), pp. 844-849

Hisao Tamaki: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), LNCS 6986, pp. 331-342.


---

