Class MDRk

  • All Implemented Interfaces:
    F

    public class MDRk
    extends MD
    Min Degree + Random k heuristic
    Since:
    01/01/2014
    Author:
    Jean-Guillaume Fages
    • Field Detail

      • k

        protected int k
      • iter

        protected int iter
    • Constructor Detail

      • MDRk

        public MDRk​(UndirectedGraph graph,
                    int k)
        Creates an instance of the Min Degree + Random k heuristic to compute independent sets on graph
        Parameters:
        graph - the grah
        k - number of random iterations
      • MDRk

        public MDRk​(UndirectedGraph graph)
        Creates an instance of the Min Degree + Random k heuristic to compute independent sets on graph
        Parameters:
        graph - the graph
    • Method Detail

      • prepare

        public void prepare()
        Description copied from interface: F
        Potentially performs some calculation before computing independent sets
        Specified by:
        prepare in interface F
        Overrides:
        prepare in class MD
      • computeMIS

        public void computeMIS()
        Description copied from interface: F
        Computes an Independent Set as large as possible, although it is not necessarily maximum
        Specified by:
        computeMIS in interface F
        Overrides:
        computeMIS in class MD
      • computeMISRk

        protected void computeMISRk()
      • hasNextMIS

        public boolean hasNextMIS()
        Specified by:
        hasNextMIS in interface F
        Overrides:
        hasNextMIS in class MD
        Returns:
        true iff the heuristic can compute another independent set