improve documentation of input format

[mooreniemi]

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?

[hhirtz]

Hello, thank you for the detailed feedback! Those bindings are fairly low-level, and stay very close to the C library because I wanted to use them for benchmarks and also didn't thought people would come from python instead of C! xadj and adjncy do represent the raw CSR data (resp ROW_INDEX and COL_INDEX in the wikipedia page).

Of course, on searching I found that METIS had a pdf manual with the following explanation: [...] But I think this could be brought directly into the crate to help onboard new users. WDYT?

Sure, do you want to send a PR?

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

Sounds also good API wise, although there could be some issues with borrowing since metis::Graph<'a> doesn't own the graph... Maybe a GraphBuf type (kind of like PathBuf) could be of help?