Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithms Lab - Virtual Box

Algorithms Lab Technical Instructions & Frequently Asked Questions (FAQ)


General Information

For the Algolab, we use

This page is here to help you to get these technical details out of the way as quickly and painlessly as possible.


Algolab in the Computer Labs

The computer rooms CAB H56/H57 and HG E26.1 are equipped with the necessary software and are reserved for Algolab during the problem-of-the-week timeslot on Monday.

We recommend that you use the Fedora operating system on these machines. On those C++, BGL and CGAL should run fine and with recent versions.

The RedHat system on the machines in CAB also works, but the default boost packages are outdated. The recent ones (which are necessary for the MinCostMaxFlow implementations in BGL), are available but need to be activated. To activate them, execute this command in your terminal: scl enable rh-mongodb32 bash


Native setup on your own Machine

Linux

Just download the most recent g++, boost and cgal packages from your favorite package manager. On Ubuntu for instance, just run

sudo apt-get install build-essential libboost-all-dev libcgal-dev cmake cmake-data

Mac OS X / macOS

First install Xcode which includes a recent version of the LLVM C++ compiler. To install Boost and CGAL, we recommend homebrew which offers packages for both of them. To compile and link with the BGL, you need to provide the header path,

e.g. g++ yourcode.cpp -I /usr/local/opt/boost/include/ -o yourprogram

or you can just use the regular cgal_create_cmake script.

Windows

Getting everything to run with cygwin can be a pain. We recommend that you use our VirtualBox image, see below.


Algolab Virtualbox Instance

tl;dr: You can download a VirtualBox image with the libraries preinstalled here!

This tutorial is based on the virtual machine for the IFMP 2015 course by Christian Zingg (in German).

Preface

The goal of this virtual machine is to provide you with a hassle-free way to get started with the BGL and CGAL libraries for the Algorithms Lab.

We use Xubuntu as the operating system. A program called VirtualBox allows you to use it within your existing operating system. This guide is mostly for users of Windows and OS X. If you are using Linux, it's probably easier to just install the necessary packages for Algolab directly on your machine. But if you don't want to fill your machine with CGAL and Boost packages that you only need for the course, then this virtual machine (VM) might also be useful for you.

Important warning: Updating Xubuntu within the VM might lead to instabilities with VirtualBox. We recommend to just use the VM as it is.

Installation of VirtualBox

  1. Download the VirtualBox client for your operating system (called host operating system) and install it. (If you run into trouble, see the troubleshooting section below.)
    For the installation just follow the instructions of the assistant and consult the documentation on the download page if necessary.
  2. Download the file algolab.ova (~3.6 GB) and save it to your hard disk. Make sure that the file ending .ova is kept.
  3. In the next step, you have to import this file in the VirtualBox client. Fire up your VirtualBox client and choose "File -> Import Appliance..." in the menu. In the dialog, pick the location of algolab.ova. Press "Continue" to get to this screen:

    Import Dialog

    We recommend to keep everything as is, but if you want to use less or more working memory (RAM) for the guest system, you can change it here. Below 256 MB will be critical. We recommend to stick with the default of 1024 MB or only to increase it if your machine allows it.
    Then press "Import" and be patient until everything is copied.
    Comment: You can delete the file algolab.ova after the import.
  4. If the import was successful, then you should see the following:

    Shared Folder

    Before you start Xubuntu, we would like to setup a shared folder between the guest and the host operating system. This will allow you to easily share files between the two systems. First, create a new folder on your host operating system for this purpose, for instance on your Desktop. You can name it however you like, for instance vb_shared.
    Now go back to VirtualBox. Pick the entry algolab on the left and the click on the "Shared folders" title on the right (siehe Bild oben). You should see the following screen:

    Where to Press

    Press the "Add Shared Folder (Ins)" Symbol (green cross). This screen appears:

    Precise Name

    As "Folder Path" pick the folder that you just created on your machine (in our example vb_shared). As "Folder Name" you must absolutely have vb_shared, regardless of what you called the directory on your hard disk. Then press "OK" twice.
    As soon as you start Xubuntu this directory of your host system should be linked with the folder vb_shared on the desktop of Xubuntu.
  5. Now we are good to go! You can start your virtual machine.

    Credentials

    Username and password of the only account in the machine are both algolab. However, the system should log in automatically so you should only need it if you want to install additional software within the virtual machine.

Frequently Asked Questions (FAQ) / Troubleshooting

Quick Links

VirtualBox Installation

Importing the Virtual Machine into VirtualBox

If you get an error when importing the appliance which says that the "compressed image is corrupted", then something probably failed when downloading the file algolab.ova. In that case it should help if you just download algolab.ova again. If that does not help, try another browser or do it while connected at ETH.

Judge

Where can I submit?

You can either use the 'submit'-links for each task on the moodle, or you can click on the name of any problem on the overview page of the judge.

I can not access the documentation on the judge?

The documentation on the judge is only available from within the ETH network. If you see "Error 403 - You don't have permission to access /doc/ on this server.", please use ETH VPN.

C++ and STL

Run errors only on the judge

If you access your vector outside of its bounds, i.e. at V[V.size()], then many different things can happen. On your local machine, e.g. if it is running macOS, it might seem to run fine, your program reads a zero value and continues. On the judge however, your program most likely crashes and gets the verdict "RUN ERROR". Luckily, there is an easy way to locally check whether you run out of the bounds of any STL container: Just compile with the g++ flag -D_GLIBCXX_DEBUG. If you are using clang++ (default on macOS), then use -D_LIBCPP_DEBUG=0 instead.

Boost Graph Library (BGL)

Getting all of Boost to install and compile

If you are having trouble to get all the boost components installed on your system, there is an easy way out: The boost graph library (BGL) is header-only, so no installation is required. Just download the most recent version from the official website and link to it when compiling
g++ yourcode.cpp -I /path/to/your/boost/include/ -o yourprogram

Prim's Minimum Spanning Tree is buggy

If you are noticing buggy behavior of Prim's minimum spanning tree algorithm, then you should use a newer version of BGL. The version 1.54 was buggy.

Minimum Cost Maximum Flow algorithms are missing

If you are missing the cycle_canceling or the successive_shortest_path_nonnegative_weights algorithm, then your boost version is outdated. You need at least version 1.55.

No support for bundled properties

Bundled Properties could be nice to cleanup the template code in our graph definitions. Unfortunately, there is no obvious way on how to make them work with the flow algorithms that we need for the course, so we currently recommend that you do not use them.

Computational Geometry Algorithms Library (CGAL)

C++11 features and cmake

The cgal_create_cmake script that we recommend you to use for the CGAL problems does not compile with the C++11 flag, unless you are using a very recent CGAL version. This might cause weird compiler errors when your code uses C++11 features like auto or range-based for loops. This is how you can enable C++11 support in that case:

Exam

Can I bring my own keyboard?

No.

What material is available during the exam?

Everything on the documentation page of the AlgoLab judge (lecture slides, code templates, library manuals) is available during the exam. The moodle and your past submissions are NOT available. If you would like to propose some helpful scripts to all the students to be added here, please post it in the Moodle forum.

Further Help

If you still run into weird errors or you have any other questions, do not hesitate and ask in the Moodle forum. We are happy to help.