graphalgs icon indicating copy to clipboard operation
graphalgs copied to clipboard

Refactor metric calculations

Open starovoid opened this issue 1 year ago • 1 comments

  1. Avoid .unwrap(). Where .unwrap() appears as a result of comparing distances, it may be necessary to impose additional restrictions on the types used.

  2. Add MetricCalculator type with methods

  • weighted(bool)
  • center()
  • diameter()
  • radius()
  • periphery()
  • eccentricity()

At now, each of the metric functions calculates a distance matrix at the beginning of its work. The MetricsCalculator will lazily calculate the distance matrix once, and then use it when calling metric methods. For a weighted graph, the distance matrix will be calculated using the Floyd-Warshall algorithm, for an unweighted graph, BFS will be used.

  1. Additionally, the MetricCalculator will have the
with_distance_mapping(mut self, distances: FnMut(G::NodeId, G::NodeId) -> FloatMeasure) -> Self

method, which allows you to specify the working distance map/matrix in advance. This can be useful if you already have a distance matrix and don't want to calculate it again.

  1. Add function
fn floyd_wharshall_distances(...) -> FnMut((G::NodeId, G::NodeID)) -> K,

for simple getting distance mapping.

  1. The currently available functions for finding metrics should remain unchanged, but they will call the MetricCalculator inside themselves.

P.s. I will be very glad to suggestions on how to further improve the API or optimize calculations.

starovoid avatar Nov 22 '24 15:11 starovoid

There is an idea to make BoundedMeasure the return type of all metric methods. This is the best interaction with all-shortest-path algorithms such as floyd_warshall, and for unweighted metrics we just add new builder weighted:

impl MetricsCalculator {
    pub fn unweighted(one: Fn() -> K) -> Self,

    pub fn weighted() -> Self
}

starovoid avatar Feb 01 '25 15:02 starovoid