Class OverlapGraph
- Since:
- 2007.06.14
-
Constructor Summary
ConstructorsConstructorDescriptionCreate 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 TypeMethodDescriptionvoid
Add an embedding to the overlap graph.void
clear()
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 function for testing some basic functionality.static OverlapGraph
Parse a graph description.int
size()
Get the size of the overlap graph (number of nodes).
-
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 graphsize
- 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
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
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
Main function for testing some basic functionality.- Parameters:
args
- the command line arguments- Since:
- 2007.06.15 (Christian Borgelt)
-