Package com.jgalgo.alg.traversal

Interface NeighborSampler<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Superinterfaces:
RandomizedAlgorithm
All Known Subinterfaces:
NeighborSampler.Int
public interface NeighborSampler<V,E> extends RandomizedAlgorithm
Random neighbor sampler.

A neighbor sampler is a generic interface that implements a single method sample(Object) that samples a neighbor of a given vertex. Different implementations of the interface can sample neighbors uniformly or with a given weight function. The RandomWalkIter iterator is implemented using a neighbor sampler and use it in a specific way by sampling the neighbor of the last returned vertex.

Author:
Barak Ugav
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static interface 
    NeighborSampler.Int
    Random neighbor sampler for IntGraph.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> NeighborSampler<V,E>
    edgeUniform(Graph<V,E> g)
    Create a new sampler that samples neighbors according to a uniform distribution of the out edges of a vertex.
    static <V, E> NeighborSampler<V,E>
    edgeWeighted(Graph<V,E> g, WeightFunction<E> weights)
    Create a new sampler that samples neighbors according to a weighted distribution of the out edges of a vertex.
    Graph<V,E>
    graph()
    Get the graph this sampler is sampling from.
    E
    sample(V vertex)
    Sample a neighbor of the given vertex.

    Methods inherited from interface com.jgalgo.alg.common.RandomizedAlgorithm

    setSeed

  • Method Details

    • sample

      E sample(V vertex)
      Sample a neighbor of the given vertex.
      Parameters:
      vertex - the vertex to sample from
      Returns:
      the sampled neighbor, maybe be null if there are no neighbors or some other reason the implementation decides to return null (for example if some vertices are filtered out).
      Throws:
      NoSuchVertexException - if the vertex is not in the graph

    • graph

      Graph<V,E> graph()
      Get the graph this sampler is sampling from.
      Returns:
      the graph this sampler is sampling from

    • edgeUniform

      static <V, E> NeighborSampler<V,E> edgeUniform(Graph<V,E> g)
      Create a new sampler that samples neighbors according to a uniform distribution of the out edges of a vertex.

      Given a vertex in the graph, a random out-edge is sampled uniformly from the set of all out edges, and the other endpoint of the edge is returned. This has some implications:

      • If the graph contains parallel edges, the distribution will be different from a uniform distribution over the neighbors, as a neighbor with two edges will be sampled twice as often as a neighbor with only one edge.
      • If the graph contains self edges, the sampling can return the vertex itself.
      • If the graph is directed, neighbors connected with in-edges will not be sampled.
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph to sample from
      Returns:
      a new sampler that samples neighbors according to a uniform distribution of the out edges of a vertex

    • edgeWeighted

      static <V, E> NeighborSampler<V,E> edgeWeighted(Graph<V,E> g, WeightFunction<E> weights)
      Create a new sampler that samples neighbors according to a weighted distribution of the out edges of a vertex.

      Given a vertex in the graph, a random out-edge is sampled according to the weights of the edges, and the other endpoint of the edge is returned. Self edges are also considered in the sampling, along with parallel edges. Neighbors connected with in-edges will not be sampled.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph to sample from
      weights - the edge weight function
      Returns:
      a new sampler that samples neighbors according to a weighted distribution of the out edges of a vertex
      Throws:
      IllegalArgumentException - if any edge weight is negative