Bolinas is a package for graph processing, developed at USC/ISI by Jacob Andreas, Daniel Bauer, David Chiang, Karl Moritz Hermann, Bevan Jones, and Kevin Knight. Bolinas follows in the footsteps of Carmel, a finite-state (string) transducer package written by Jonathan Graehl, and Tiburon, a tree transducer package written by Jonathan May.

Bolinas can process rooted, directed, cyclic, edge and node-labeled (hyper-)graphs. It is based on Synchronous Hyperedge Replacement Grammar (SHRG), a context free grammar formalism that works by repeatedly rewriting nonterminal hyperedges with larger graph fragments.

Please address inquiries about this software to Daniel Bauer or Kevin Knight


Given a Hyperedge Replacement Grammar (HRG) describing a possibly infinite set of graphs, Bolinas can test if an input graph is a member of this set and provide k-best derivations or a derivation forest as a regular tree grammar.

Bolinas supports graph-to-string, string-to-graph, graph-to-graph, and string-to-graph translation. It also supports translation from and into trees by representing them as hypergraphs. It can produce k-best derived graphs or strings.

Bolinas supports EM training of weights for HRGs and SHRGs given an input corpus of graphs, or pairs of graphs (or graph/string pairs).

Unlike Carmel, Bolinas does not implement intersection and composition, because HRG graph languages are not closed under these operations. This also means that the parser only accepts finite lists of graphs as input and not a set of graphs compactly defined by an HRG. Currently the package does also not implement cascading (application of a second HRG/SHRG to the output of a SHRG), which has to be set up by hand, running the tool multiple times.

Bolinas includes algorithms to extract SHRGs automatically from a collection of graphs and strings, specifically automatic alignment of strings to graphs and two different approaches to rule extraction.

Bolinas is written in Python 2.7, so it is easy to integrate Bolinas into your own project and it can run on a number of different platforms without requiring any changes.


You can read a tutorial (PDF) to help you get started with graph processing in Bolinas.

You can also get help on the command line (% ./bolinas --help) or (% python bolinas.py --help).

For in-depth information on the formalism, algorithms, and applications in NLP you can read several papers written by the developers and others.

Photo credit: Modified from "Bolinas, CA January 2009", by Flickr user cproppe, made available under the Creative Commons Attribution-NonCommercial 2.0 Generic license.

Last modified 2013-07-30 by Daniel Bauer.