Create property-based tests for shortest paths algorithms

[pnevyk]

Create proptest tests for ShortestPaths using our graph generation strategies strategies. Test both algorithms (Dijkstra, Bellman-Ford). Use DebugGraph as the graph being generated because it provides very useful information in case of a failed assert.

What properties to test? One possibility is to implement a function for removing isolated vertices from a graph so that the tested graphs are connected. Then, For connected graphs after finishing an algorithm, it should be possible to reconstruct path and get distance from every vertex in the graph to the starting vertex. Also, the distances (not the paths, generally) should be equal as returned by Dijkstra and Bellman-Ford.

[pnevyk]

Update after #46:

• The proptests should look similarly to those for toposort

  gryf/src/algo/toposort.rs

  Lines 269 to 297 in 4518875

  	proptest! {
  	#[test]
  	#[cfg_attr(not(proptest), ignore = "compile with --cfg proptest")]
  	fn toposort_dfs_acyclic(graph in graph_directed(any::<()>(), any::<()>()).acyclic()) {
  	let toposort = TopoSort::on(&graph).with(Algo::Dfs).run();
  	assert_valid(toposort, &graph);
  	}
  	#[test]
  	#[cfg_attr(not(proptest), ignore = "compile with --cfg proptest")]
  	fn toposort_dfs_any(graph in graph_directed(any::<()>(), any::<()>())) {
  	let toposort = TopoSort::on(&graph).with(Algo::Dfs).run();
  	assert_valid(toposort, &graph);
  	}
  	#[test]
  	#[cfg_attr(not(proptest), ignore = "compile with --cfg proptest")]
  	fn toposort_kahn_acyclic(graph in graph_directed(any::<()>(), any::<()>()).acyclic()) {
  	let toposort = TopoSort::on(&graph).with(Algo::Kahn).run();
  	assert_valid(toposort, &graph);
  	}
  	#[test]
  	#[cfg_attr(not(proptest), ignore = "compile with --cfg proptest")]
  	fn toposort_kahn_any(graph in graph_directed(any::<()>(), any::<()>())) {
  	let toposort = TopoSort::on(&graph).with(Algo::Kahn).run();
  	assert_valid(toposort, &graph);
  	}
  	}

  .
• It is possible to request for generated graphs to be connected, but this feature is not implemented yet

  gryf/src/infra/proptest.rs

  Lines 322 to 327 in 4518875

  	if self.params.connected {
  	panic!("connected graphs are not supported yet");
  	// TODO: Identify all connected components and connect these
  	// components with new edges.
  	}

  (might be a part of this ticket).

[pnevyk]

In #64 I added proptests that at least check that the algorithms do not panic. But the properties mentioned in the original post in this issue should still be added.