Skip to content
cRowdy - solver for variant of graph partitioning problem made for the CS170 Final Project. First place in Fall 2018 @ 53% of edges preserved.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
3rdparty/eigen3/Eigen
cmake_modules
data
include
CMakeLists.txt
LICENSE.md
README.md
config.hpp.in
graph.cpp
main.cpp
metissolver.cpp
problem.cpp
solutionfixer.cpp
spectralsolver.cpp
stdafx.cpp
stdafx.h
swappingoptimizer.cpp
util.cpp

README.md

cRowdy Solver

(c) Alex Yu (doriath) 2018

Overview

cRowdy is a solver for the CS170 final project, written in C++ 11.

cRowdy is lightweight and almost entirely written from ground-up. The only hard dependencies are the C++ STL and the Eigen linear algebra library, neither of which you will need to build or install separately. Moreover, the program works on essentially any system.

Build prerequisites

While the build process shouldn't be too difficult, if you run into any issues trying replicate my results, I would be happy to help.

Set up a modern C++ compiler

  • Note that I use some features from the C++ 11 standard, so very old compilers may not work (g++ 4.8+ is fine).
  • On most Linux distributions, g++ should be available from the default installation, so you shouldn't need to do anything.
    • Ubuntu (if not already installed): sudo apt-get -y install g++
  • On Mac OS X, installing developer tools will allow you to use clang/g++; entering g++ in terminal should prompt you to install the developer tools.
  • On Windows, you can either install Microsoft's Visual Studio (2015/2017) or MinGW g++. I recommend getting MSYS2.

Install CMake

Optional Stuff

  • Optional: build and install METIS: [http://glaros.dtc.umn.edu/gkhome/metis/metis/download]
    • METIS can be used for initialization (the METISSolver class) and it seems to improve results for some cases, but it is not required. By default cRowdy will use the in-house Spectral solver anyway.
    • If on Windows MSVC 14 (VS 2015), you can download binaries from me http://ocf.berkeley.edu/~sxyu/metis.zip or compile from https://github.com/jlblancoc/suitesparse-metis-for-windows
    • You may need to specify the directory where METIS was built/installed if Cmake fails to find them automatically. In that case, use cmake .. -DMETIS_INCLUDE_DIR="..." -DMETIS_LIB_DIR="..."
  • Very Optional: if you want to use your own version of Eigen 3, set -DEIGEN_DIR="your/path" in addition to other flags. I have included a copy of the Eigen library in the repo for convenience, so you don't have to do anything.
  • If you are interested in generating custom cases with real names from the census, copy the data folder into the build directory (not required)
    • Note that I have not really included a command to generate test cases. To do so, edit main.cpp and put something like:
      Problem prob;
      prob.k = 10;
      prob.s = 100;
      prob.random_students(500);
      Solution soln = prob.random_solution();
      prob.from_intended_solution(soln);
      return 0;
      just inside int main().

Build instructions

Configure and generate the build system

  • in the source directory (the one with CMakeLists.txt), run: mkdir build && cd build && cmake ..
    • If you are on Windows, you may need to choose a generator if CMake fails to detect it: cmake .. -G"Visual Studio 14 2015 Win64" to use Visual Studio 2015

Build the project

  • make sure you are still in the build directory and
    • On Linux/OS X/MinGW run make
    • For MSVC (Windows) you can double-click the solution file and build through Visual Studio
    • Alternatively, use CMake: cmake --build . --config=Release

Usage

Preparing input files

  • identify the binary output directory, where the crowdy output is located. cd to it (usually this should just be build, for Visual Studio this will be build/Release)
  • download the input files from Piazza and extract them to BIN_OUTPUT_DIR/all_inputs/*. The file paths should look like: BIN_OUTPUT_DIR/all_inputs/small/1/parameters.txt, etc.
  • if you also want to run on large cases, then also extract it to BIN_OUTPUT_DIR/all_inputs/all_large/*. The file paths should look like: BIN_OUTPUT_DIR/all_inputs/all_large/1/parameters.txt, etc.

Repro instructions

Make sure you are in the binary output directory (build or build/Release)

  • ./crowdy solve && ./crowdy optim
  • On one thread, expect the solver to take about 2-3 hours to run on all cases. On a hive computer (8-core) it finishes solving all cases in around 40 minutes. Be warned that since the program is parallelized, it will take up to 100% CPU time if it can, so the computer will become quite slow while it is running.
    • On a single run the solve only got average score 0.515-0.519. It will be beneficial to run the solver several times and take the better solution for each case (as I did for the actual submission) to achieve a better score. Also, consider using crowdy optim at least once afterwards to optimize solutions (this is much faster than solving).

General usage instructions

  • ./crowdy solve: use to run the solver on all cases. The solve command assumes that inputs are in ./all_inputs/*/*. Outputs will be written to ./all_outputs/*/*
  • ./crowdy metis: if you built with METIS, this extra command for using the METIS-initialized solver will be available as well
  • ./crowdy optim: used to optimize solutions using hill climbing after solving. I ran this continuously on a hive for several days to get optimal results
  • ./crowdy solve input_dir/: use cRowdy as a black-box solver
  • ./crowdy eval: use to get a score for all solutions, also reporting results per subset. Note that each of the above commands will also report the score when done
  • ./crowdy eval input_dir/ output_file.out: get a score for a particular solution or report it is invalid. Designed to work exactly like the provided scoring script
  • ./crowdy merge other_all_outputs_dir/: merge in solutions from another cRowdy instance. Inspects each test case and replaces solution if better.
  • There are some additional commands solve-subset, etc. You can run ./crowdy to see more information about them.

License

Apache 2.0.

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.