Package moss

Class OverlapGraph

java.lang.Object
moss.OverlapGraph

public class OverlapGraph extends Object
Class to represent overlap graphs for embeddings.
Since:
2007.06.14
  • Constructor Summary

    Constructors
    Constructor
    Description
    Create a (empty) overlap graph with a default size.
    OverlapGraph(boolean harmful)
    Create a (empty) overlap graph with a default size.
    OverlapGraph(boolean harmful, int size)
    Create a (empty) overlap graph with a given size.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    Add an embedding to the overlap graph.
    void
    Clear an overlap graph (remove all embeddings).
    int
    Find the size of a maximum independent node set (MIS).
    int
    Find the size of a maximum independent node set (MIS).
    int
    Find the size of a maximum independent node set (MIS).
    int
    getMISSize(boolean greedy)
    Find the size of a maximum independent node set (MIS).
    boolean
    Check whether this is a harmful overlap graph.
    static void
    main(String[] args)
    Main function for testing some basic functionality.
    parse(Reader reader)
    Parse a graph description.
    int
    Get the size of the overlap graph (number of nodes).

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • OverlapGraph

      public OverlapGraph()
      Create a (empty) overlap graph with a default size.
      Since:
      2007.06.14 (Christian Borgelt)
    • OverlapGraph

      public OverlapGraph(boolean harmful)
      Create a (empty) overlap graph with a default size.
      Parameters:
      harmful - whether the graph is to be a harmful overlap graph
      Since:
      2007.06.14 (Christian Borgelt)
    • OverlapGraph

      public OverlapGraph(boolean harmful, int size)
      Create a (empty) overlap graph with a given size.
      Parameters:
      harmful - whether the graph is to be a harmful overlap graph
      size - the expected number of nodes
      Since:
      2007.06.14 (Christian Borgelt)
  • Method Details

    • isHarmful

      public boolean isHarmful()
      Check whether this is a harmful overlap graph.
      Returns:
      whether this is a harmful overlap graph
      Since:
      2007.06.14 (Christian Borgelt)
    • size

      public int size()
      Get the size of the overlap graph (number of nodes).
      Returns:
      the number of nodes of the overlap graph
      Since:
      2007.06.14 (Christian Borgelt)
    • clear

      public void clear()
      Clear an overlap graph (remove all embeddings).
      Since:
      2007.06.21 (Christian Borgelt)
    • add

      public void add(Embedding emb)
      Add an embedding to the overlap graph.

      The embedding is compared to all previously added embeddings and it is checked whether there is a (harmful) overlap with them. If there is an overlap, the nodes representing the embeddings are connected with an edge.

      Parameters:
      emb - the embedding to add
      Since:
      2007.06.14 (Christian Borgelt)
    • getMISGreedy

      public int getMISGreedy()
      Find the size of a maximum independent node set (MIS).

      This function uses a heuristic greedy algorithm that may yield a wrong result. However, as a tradeoff, it is considerably faster than the exact algorithm.

      The function selects in each step (one of) the node(s) with the smallest node degree, excludes its neighbors, and then selects nodes that became safe to select in the reduced overlap graph.

      Returns:
      the size of a maximum independent node set
      Since:
      2007.06.14 (Christian Borgelt)
      See Also:
    • getMISExact

      public int getMISExact()
      Find the size of a maximum independent node set (MIS).

      This function uses an exact algorithm based on a recursive node selection/exclusion scheme. It guarantees the optimal solution, but has exponential time complexity. In addition, it does not exploit all possible tricks, but is rather a fairly straightforward implementation of the basic search scheme.

      Returns:
      the size of a maximum independent node set
      Since:
      2007.06.14 (Christian Borgelt)
      See Also:
    • getMISSize

      public int getMISSize()
      Find the size of a maximum independent node set (MIS).
      Returns:
      the size of a maximum independent node set
      Since:
      2007.06.14 (Christian Borgelt)
      See Also:
    • getMISSize

      public int getMISSize(boolean greedy)
      Find the size of a maximum independent node set (MIS).

      The search is terminated as soon as an independent set of at least the minimum required size is found. In this case the returned value may be smaller than the actual MIS size, even if the exact algorithm is used.

      Parameters:
      greedy - whether to use the greedy algorithm
      Returns:
      the size of a maximum independent node set
      Since:
      2007.06.14 (Christian Borgelt)
    • parse

      public static OverlapGraph parse(Reader reader) throws IOException
      Parse a graph description.

      The graph is assumed to be given in ASCII DIMACS format.

      Parameters:
      reader - the reader to read from
      Returns:
      the parsed graph
      Throws:
      IOException - if parsing the graph failed
      Since:
      2007.06.18 (Christian Borgelt)
    • main

      public static void main(String[] args)
      Main function for testing some basic functionality.
      Parameters:
      args - the command line arguments
      Since:
      2007.06.15 (Christian Borgelt)