Class MeshStatistics

java.lang.Object
Jcg.util.MeshStatistics
public class MeshStatistics extends Object
This class provides methods for computing mesh statistics (average degree, diameter, ...).
Author:
Luca Castelli Aleardi (Ecole Polytechnique, 2019-2025)

  • Field Details

    • mesh

      Polyhedron_3 mesh
      Input mesh (half-edge representation)

    • precision

      private int precision

    • verbosity

      public int verbosity

    • eccentricity

      public int[] eccentricity

  • Constructor Details

  • Method Details

    • sizeVertices

      public int sizeVertices()
      Return the number of nodes of the graph

    • statsVertexDegree

      public double statsVertexDegree(int degree)
      Compute the proportion of vertices having a given degree.
      Parameters:
      degree - of a vertex
      Returns:
      the proportion of vertices having a given 'degree'

    • getVertexDegreeDistribution

      public double[] getVertexDegreeDistribution()
      Return the vertex degree distribution, up to degree 'max'

    • meshStatisticsToString

      public String meshStatisticsToString(int maxDegree, boolean sepTriangles, int verbosity)
      Return a String storing some mesh statistics:
      -) minimum and maximum vertex degree
      -) the vertex degree distribution, up to degree 'max'
      -) number of separating triangles, if needed
      Parameters:
      verbosity - if verbosity>0 show the heading line

    • headingToString

      public static String headingToString(int max, boolean separatingTriangles)
      Return a the heading:
      n e genus type minDeg maxDeg avgDev deg2 deg3 ... sepTri sepTri%

    • getVertexDegrees

      public static int[] getVertexDegrees(Polyhedron_3 tri)
      Return the vertex degree sequence (int[] array)

      Warning: the runtime complexity is not optimal (iterating over edges could be slightly faster)
      Returns:
      an array of size N, storing the vertex degree sequence

    • getVertexDegreeSequence

      public double[] getVertexDegreeSequence()
      Return the vertex degree sequence (double[] array)
      Returns:
      an array of doubles of size N, storing the vertex degree sequence

    • getVertexDegreeEntropy

      public double getVertexDegreeEntropy()
      Return the entropy of the vertex degree sequence
      Returns:
      the entropy of the vertex degree sequence

    • averageDegree

      public double averageDegree()
      Return the average degree of the graph

    • numberConnectedComponents

      public int numberConnectedComponents()
      Return the number of connected components of the graph

    • type

      public String type()
      Get the type of the mesh: triangle, quad, polygonal

    • computeAllDistancesFromVertex

      public int computeAllDistancesFromVertex(Vertex v)
      Compute, from each vertex, the (graph) distance to vertex v It performs a BFS visit of the entire mesh starting from vertex v

      Remark: the vertices are assumed to have an index, between 0..n-1

      Parameters:
      v - the starting vertex
      Returns:
      an array containing the (integer) distances from vertex v

    • approximatedDiameter

      public int approximatedDiameter(int seeds)
      Compute an approximation of the diameter using a small set of random seed vertices

      Remark: the vertices are assumed to have an index, between 0..n-1

      Parameters:
      mesh - input polyhedral mesh
      Returns:
      the approximated diameter

    • diameter

      public int diameter()
      Compute the exact diameter with brute force (slow)

      Remark: the vertices are assumed to have an index, between 0..n-1

      Returns:
      the exact diameter

    • bruteForceEccentricity

      public void bruteForceEccentricity()
      Compute the exact diameter with brute force

      Warning: this method can be slow for large meshes (>10k vertices)

      Remark: the vertices are assumed to have an index, between 0..n-1

    • getRadiusAndDiameter

      public int[] getRadiusAndDiameter()
      Return the 'radius' and 'diameter' of the graph

    • getAverageVertexGap

      public double getAverageVertexGap()
      Return the average vertex gap (as defined in Barik et al.).
      The gap of an edge (u, v) is the absolute value |u-v|.

      Reference: Vertex Reordering for Real-World Graphs and Applications: An Empirical Evaluation (Barik et al. 2020)
      Returns:
      the average vertex gap (over all edges)

    • getAverageVertexGap

      public double getAverageVertexGap(int[] pi)
      Return the average vertex gap (profile) of a mesh whose vertices have been permuted according to a given permutation 'pi' of [0...n-1].
      Remark: vertex 'u' has number pi(u) in the permuted graph.
      The gap of an edge (u, v) is the absolute value |pi(u)-pi(v)|.

      Reference: Vertex Reordering for Real-World Graphs and Applications: An Empirical Evaluation (Barik et al. 2020)
      Parameters:
      pi - the input vertex permutation
      Returns:
      the average vertex gap (over all edges) for a permuted mesh

    • vertexBandwidth

      public int vertexBandwidth(Vertex v)
      Return the vertex bandwidth of a vertex v.
      The bandwidth is the maximal gap between vertex 'v' and its neighbors.
      Parameters:
      v - a vertex in a polygonal mesh

    • getAverageBandwidth

      public double getAverageBandwidth()
      Return the average vertex bandwidth.
      Parameters:
      v - a vertex in a polygonal mesh

    • approx

      public static double approx(double x, int prec)