lihpc-computational-geometry / metis-rs Goto Github PK

I get an error on Linux when linking against some kind of .rlib from libmetris_sys gklib.o

,--eh-frame-hdr" "-Wl,-z,noexecstack" "-L" "/home/jms/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-o" "/home/jms/Projects/bevy/target/release/examples/meshlet-e26ebb2941c08c68" "-Wl,--gc-sections" "-pie" "-Wl,-z,relro,-z,now" "-Wl,-O1" "-Wl,--strip-debug" "-nodefaultlibs"
  = note: /usr/bin/ld: /home/jms/Projects/bevy/target/release/deps/libmetis_sys-5573fe5096f72fe6.rlib(f6cd32e89e94ec8c-gklib.o): relocation R_X86_64_32 against `.rodata' can not be used when making a PIE object; recompile with -fPIE
          /usr/bin/ld: failed to set dynamic section sizes: bad value
          collect2: error: ld returned 1 exit status

Hi,

I'm really excited to use metis-rs for my CFD code.

I think it would be amazing if a few small examples were given with the library for the part_dual and part_nodal methods, since they're the most used methods in metis, and users having access to some simple test cases will help them use the library correctly.

I will try to see if I can create the examples on my own. And if I'm successful, I will submit them for metis-rs.

Thanks!

Here are a few examples using Fortran interface to metis that give a small example mesh, and partition it:

1. https://ivan-pi.github.io/fmetis/sourcefile/test_partmeshnodal1.f90.html
2. https://ivan-pi.github.io/fmetis/sourcefile/test_partmeshnodal2.f90.html

Features should be purely additive, but here use-system and vendored are mutually exclusive.
Moreover, the logic with force-optimize-vendor is to enable vendored.

However, it seems that we can still end up with configurations enabling use-system and force-optimize-vendor (and thus vendored) at the same time (see #32).

Hi! Thanks so much for putting these bindings out there. As someone unfamiliar with METIS except pymetis, I find it a bit challenging to understand the documentation purely from Rust. Would you be open to some PRs to improve the documentation and examples?

For example, in the documentation I see the below, but I don't understand how to represent a graph as xadj and adjncy.

// Make a graph with two vertices and an edge between the two.
let xadj = &mut [0, 1, 2];
let adjncy = &mut [1, 0];

// Allocate the partition array which stores the partition of each vertex.
let mut part = [0, 0];

// There are one constraint and two parts.  The partitioning algorithm used
// is recursive bisection.  The k-way algorithm can also be used.
Graph::new(1, 2, xadj, adjncy)
    .part_recursive(&mut part)
    .unwrap();

// The two vertices are placed in different parts.
assert_ne!(part[0], part[1]);

I also see this example but couldn't use it to better infer.

Of course, on searching I found that METIS had a pdf manual with the following explanation:

5.5 Graph data structure
All of the graph partitioning and sparse matrix ordering routines in METIS take as input the adjacency structure of the
graph and the weights of the vertices and edges (if any).
The adjacency structure of the graph is stored using the compressed storage format (CSR). The CSR format is a
widely used scheme for storing sparse graphs. In this format the adjacency structure of a graph with n vertices and
m edges is represented using two arrays xadj and adjncy. The xadj array is of size n + 1 whereas the adjncy
array is of size 2m (this is because for each edge between vertices v and u we actually store both (v, u) and (u, v)).
The adjacency structure of the graph is stored as follows. Assuming that vertex numbering starts from 0 (C style),
then the adjacency list of vertex i is stored in array adjncy starting at index xadj[i] and ending at (but not
including) index xadj[i + 1] (i.e., adjncy[xadj[i]] through and including adjncy[xadj[i + 1]-1]). That
is, for each vertex i, its adjacency list is stored in consecutive locations in the array adjncy, and the array xadj
is used to point to where it begins and where it ends. Figure 3(b) illustrates the CSR format for the 15-vertex graph
shown in Figure 3(a).

But I think this could be brought directly into the crate to help onboard new users. WDYT?

Also it looks like petgraph and graph directly support a CSR type -- that could be brought into this crate optionally as well?

The problem

All partition functions in METIS will cause undefined behavior if given not well formed CSR graphs.

For example:

#[test]
fn segfault() {
    let adjncy = &mut [1, 9999];
    let xadj = &mut [0, 2];
    let part = &mut [0];
    Graph::new(1, 1, xadj, adjncy).part_recursive(part).unwrap();
}

This is expected as METIS does unchecked array indexing using values in adjncy in many places.

Because of this, the API is unsound and should be changed.

How can this be fixed

According to the Rust API Guidelines, the way to fix this and keep the signatures the same will be to add a validation function that checks every value of adjncy that it is less than xadj.len() - 1. The current implementations could be moved to an _unchecked version of the function.

impl Graph {
    fn new(...) -> Result<Graph> {
        Graph::validiate(...)?;
        unsafe { Graph::new_unchecked(...) }
    }
    unsafe fn new_unchecked(...) -> Graph {
        // current implemtation
        // maybe it includes existing asserts?
    }
}

// same process with Mesh

Hi,

I want to use metis in my rust application. It works great and your binding is very nice to use. Thank you for providing this.

Since some time one of the tests I made when learning the interface started to occasionally fail (Hence it is set to ignore).

thread 'experiments::metis_test::tests::test_convert_example' panicked at 'assertion failed: `(left == right)`
  left: `[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1]`,
 right: `[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0]`', src/experiments/metis_test.rs:81:9

Though, the unit tests uses the same data all the time it sometimes passes and sometimes not. The algorithm seems to produce different results inbetween runs.

I also noticed, that when I run my test suite on our HPC, the two tests in this module cause SIGSEGV errors from time to time.

I don't even know whether this is the right place to ask, but I thought I'll start at the very top of my stack trace 😬

We're relying on 06d4b31 for ourselves and would like to see a newly released version of this crate with that change included, would that be possible? Thanks 🙏

I was running into this with a graph I was passing to METIS. The part_kway function seems to take about 30 seconds, while the command line utility, built directly from the source, on the same graph takes less than a second.

I suspect it's missing some of the compile options or defines that a CMAKE-generated project is using. I will investigate.

I noticed that you distribute metis-rs under both Apache 2.0 and MIT. However, METIS FAQ states that you can distribute it under Apache 2.0. Just to be sure, I downloaded the sources, and it is only licensed under Apache 2.0.

Now I am not a lawyer.. perhaps it is okay to distribute bindings under different license. Regardless, distributing them under MIT is likely to confuse users who believe they can use the library-as-a-whole under MIT license.

Suggested changes:

• Remove LICENSE-MIT
• In Cargo.toml, change license = "MIT OR Apache-2.0" to license = "Apache-2.0"