English
资源说明：A C library and CLI for finding near-maximum weighted feedback arc sets
# Feedback Arc Set solver
This is a library + CLI for solving the following problem:
Given a non-negative nxn matrix W, find a permutation p of [0, n) that maximizes
sum_{p_i < p_j} W_ij
i.e. we regard W_ij as "the weight of evidence that i < j"
I would only give a fairly qualified recommendation in favour of it.
Features:
* It does a pretty good job. The test suite requires that it gets within 5% of the best known result on a variety of data, and it beats that with a comfortable margin.
* It's quite fast. For small numbers of items (<= 100) it completes in a few 100ms, going up to a few seconds for thousands of items.
* It's deterministic. Most of the best-of-breed algorithms for this problem are randomized. Empirically, this seems to produce consistently better scores than they do (but that may be errors in my implementation of them)
* It respects condorcet partitions. That is, if you partition the candidates into two sets A and B such that W_ab > W_ba for any a in A and b in B, it will always put everything in A first
* The result is locally optimal in the sense that no change which involves only moving a single element will improve the score
* Everything runs clean under valgrind with all test data
Downsides:
* The theoretical bounds on how bad the error can be are extremely weak to non-existent
* The performance is O(n^2) in the number of items, even when far fewer than O(n^2) comparisons are present.
* The API for the library is fairly poorly thought out at present.
* The command line interface is terribly rudimentary
All that being said, it appears to work and work reasonably well.
# Input format
The input to the solver is a sparse matrix format. It takes the form
n
i1 j1 x1
i2 j2 x2
...
where n is the number of dimensions and the i, j, x are triples with i, j integers with 0 <= i, j < n and x a float with x >= 0. This is interpreted as an nxn matrix with Aij = x.
The error messages on parsing failure are currently not very good. Sorry. I'll fix that at some point.
# Output format
The output is to stdout and looks like the following:
Score: 12.845055
Optimal ordering: 11 1 2 [7 3] 8 || [14 9 12] [10 13] [5 0] 4 6
The || indicates the presence of a condorcet partition at that point. A bracketed set of indices such as [7 3] indicates a tie where the order of the elements in the brackets does not matter.
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
