public class OverlapGraph
extends java.lang.Object
Constructor and Description |
---|
OverlapGraph()
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.
|
Modifier and Type | Method and Description |
---|---|
void |
add(Embedding emb)
Add an embedding to the overlap graph.
|
void |
clear()
Clear an overlap graph (remove all embeddings).
|
int |
getMISExact()
Find the size of a maximum independent node set (MIS).
|
int |
getMISGreedy()
Find the size of a maximum independent node set (MIS).
|
int |
getMISSize()
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 |
isHarmful()
Check whether this is a harmful overlap graph.
|
static void |
main(java.lang.String[] args)
Main function for testing some basic functionality.
|
static OverlapGraph |
parseGraph(java.io.Reader reader)
Parse a graph description.
|
int |
size()
Get the size of the overlap graph (number of nodes).
|
public OverlapGraph()
public OverlapGraph(boolean harmful)
harmful
- whether the graph is to be a harmful overlap graphpublic OverlapGraph(boolean harmful, int size)
harmful
- whether the graph is to be a harmful overlap graphsize
- the expected number of nodespublic boolean isHarmful()
public int size()
public void clear()
public void add(Embedding emb)
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.
emb
- the embedding to addpublic int getMISGreedy()
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.
getMISSize(boolean)
public int getMISExact()
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.
getMISSize(boolean)
public int getMISSize()
getMISSize(boolean)
public int getMISSize(boolean greedy)
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.
greedy
- whether to use the greedy algorithmpublic static OverlapGraph parseGraph(java.io.Reader reader) throws java.io.IOException
The graph is assumed to be given in ASCII DIMACS format.
reader
- the reader to read fromjava.io.IOException
public static void main(java.lang.String[] args)
args
- the command line arguments