networkx / networkx-metis

NetworkX Addon to allow graph partitioning with METIS
Other
79 stars 21 forks source link

Rewrite test_metis.py to test exposed functions #44

Closed OrkoHunter closed 9 years ago

OrkoHunter commented 9 years ago

Fixes #26

I'm not sure whether it's the best testing method but I've used a nx.complete_graph(16) and tested the results against what I got on my computer.

As the results are generated by algorithms based on approximations, they depend upon the platform and compiler used.

OrkoHunter commented 9 years ago

For nxmetis.partition(G, 4)

msvc on Windows - (96, [[1, 2, 3, 9], [0, 4, 5, 6], [7, 8, 10, 15], [11, 12, 13, 14]])
gcc on Linux   -  (96, [[1, 2, 3, 10], [4, 5, 6, 7], [8, 9, 12, 14], [0, 11, 13, 15]])

For nxmetis.vertex_separator(G)

msvc on Windows - ([2, 4, 5, 6, 7, 9, 10], [0, 1, 3, 8, 11, 12, 13, 14, 15], []) 
gcc on Linux   -  ([1, 2, 4, 6, 7, 9, 13], [0, 3, 5, 8, 10, 11, 12, 14, 15], []) 
OrkoHunter commented 9 years ago

It appears that we are not the only one facing this problem.

http://stackoverflow.com/questions/31299159/metis-different-results-on-different-os http://stackoverflow.com/questions/29397370/getting-non-unique-results-from-metis-when-different-compiler-is-used

OrkoHunter commented 9 years ago

I think the good way here to test METIS should be that if it returns couples of nested lists or tuple (the way we expect) the tests should pass unless there is some error returned. Eventually we can't be sure for what METIS is going to return for a particular operation.

ysitu commented 9 years ago

It is true that we should tolerate variation in METIS output. But we should still verify the invariants. For example, when we do graph partitioning, we should verify that the returned partitions do not overlap.

OrkoHunter commented 9 years ago

I made some changes regarding the test-the-continuous-chains-from-partition. I'll try to finish it later today.

OrkoHunter commented 9 years ago

The new tests are ready for a review. Please ignore the lines commented. I'll remove the useless code before merging.

OrkoHunter commented 9 years ago

Last five comments addressed.

OrkoHunter commented 9 years ago

I've made the changes and rebased it because of #47. We can wait for a green tick on appveyor but that might take long because of the pending builds.