Linear Arrangement Library

This library implements several algorithms to solve problems related to linear arrangements. For example, it implements algorithms that

• solve the Minimum Linear Arrangement Problem on trees under different constraints (no constraint, over bipartite, planar and projective arrangements),
• solve the Maximum Linear Arrangement Problem on trees under different constraints (no constraint, over bipartite, planar and projective arrangements),
• calculate the expectation and variance of the number of edge crossings and of the sum of the length of the edges under different constraints (such as projectivity and planarity),
• compute efficiently the number of edge crossings given a linear arrangement of a graph,
• and solve many other problems.

Some of the algorithms listed above are implemented for both general graphs and trees (the latter being more efficient). The library also provides functions for the generation of random/exhasutive labelled/unlabelled free/rooted trees. Besides, there's algorithms for the generation of arrangements under different constraints (such as projectivity and planarity). Users will also find utilities to process treebanks, and collection of treebanks.

For more information, visit LAL's official webpage. Do not forget to take a look at the guides!.

A word of caution The master branch of this repository may contain unstable code.

Installation of the library from binaries

We wrote different sets of instructions for installing LAL's compiled distribution files for

• Ubuntu. We do not currently maintain any official repository for any of the Linux distributions' package manager.
• Windows.

Installation of the library from sources

We wrote different sets of instructions for compiling and installing LAL from sources for

• Ubuntu.
• Windows.
• Mac OS.

Compile a program that uses LAL

See this file for instructions on how to compile and link a C++ program that uses LAL.

Author information

This library is the result of the joint effort of several people (in alphabetical order):

• Alemany-Puig, Lluís (see his webpage and his Research Gate profile).
• Esteban, Juan Luis (see his webpage and his Research Gate profile)
• Ferrer-i-Cancho, Ramon (see his webpage and his Research Gate profile).

Citing the library

In this library users will find implementations of papers written by the developers of LAL themselves, and implementations of algorithms devised by other researchers. This library is the result of great efforts put directly by the developers, and indirectly by other researchers. In an academic paper, please,

• cite the articles presenting LAL and the Zenodo repository that corresponds to the exact version of LAL that is used,
• acknowledge the effort made by other researchers by citing their papers in which they describe the algorithms implemented in this library. Such papers are cited in the C++ documentation and can be found easily in the doxygen documentation. In case a citation is lacking, or is just incorrect, do not hesitate to contact us to inform us about this issue. All the citations can be found in doxygen format here.

In order to cite the Linear Arrangement Library, please cite all papers presenting LAL (including, but not limited to the following list of papers):

• Lluı́s Alemany-Puig, Juan Luis Esteban, and Ramon Ferrer-i-Cancho. "The Linear Arrangement Library. A new tool for research on syntactic dependency structures". In: Proceedings of the Second Workshop on Quantitative Syntax (Quasy, SyntaxFest 2021). Sofia, Bulgaria: Association for Computational Linguistics, Dec. 2021, pp. 1–16. url: https://aclanthology.org/2021.quasy-1.1.

    @inproceedings{Alemany2021b,
    	title = {{The Linear Arrangement Library. A new tool for research on syntactic dependency structures}},
    	author = {{Alemany-Puig}, Llu\'{i}s and Esteban, {Juan Luis} and {Ferrer-i-Cancho}, Ramon},
    	arxivId = {2112.02512},
    	booktitle = {Proceedings of the Second Workshop on Quantitative Syntax (Quasy, SyntaxFest 2021)},
    	url = {https://aclanthology.org/2021.quasy-1.1},
    	month = {dec},
    	year = {2021},
    	address = {Sofia, Bulgaria},
    	publisher = {Association for Computational Linguistics},
    	pages = {1--16}
    }
  

In order to cite the corresponding Zenodo repository, please, refrain from using a non-stable release of LAL (main branch) for your research, and use a stable release instead. Contact us or visit the official webpage for help on how to proceed.

Documentation

The C++ documentation can be found online in the library's webpage. Alternatively, it can be generated in html format with doxygen. Simply issue the following command from the directory's root directory

$ cd /path/to/the/linear-arrangement-library
$ ./make_docs.sh