API Documentation

class cliquematch.Graph

search_done

Whether the search has been completed (Readonly)

Type

bool

n_vertices

Number of vertices in the graph (Readonly)

Type

int

n_edges

Number of edges in the graph (Readonly)

Type

int

get_max_clique()

Finds a maximum clique in graph within the given bounds

Parameters

• lower_bound (int) – set a lower bound on the clique size. default is 1.

• upper_bound (int) – set an upper bound on the clique size. default is 65535.

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search). default is -1.

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound. default is True.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit. default is False.

Returns

the vertices in the maximum clique

Return type

list

Raises

RuntimeError – if the graph is empty or a clique could not be found

reset_search()

Reset the search space for get_max_clique.

Raises

RuntimeError – if the graph is empty

all_cliques(size)

Iterate through all cliques of a given size in the Graph.

Parameters

size (int) – size of a clique to search for.

Return type

CliqueIterator

Raises

RuntimeError – if the graph is empty

static from_file()

Constructs Graph instance from reading a Matrix Market file

Parameters

filename (str) –

Returns

the loaded Graph

Raises

RuntimeError – if the file could not be read

static from_edgelist()

Constructs Graph instance from the given edge list. Note that vertex indices must start from 1.

Parameters

• edgelist (numpy.ndarray) – shape (n,2)

• num_vertices (int) –

Returns

the loaded Graph

Raises

• RuntimeError – if any value in edgelist is greater than num_vertices

• RuntimeError – if value in edgelist is 0

static from_matrix()

Constructs Graph instance from the given boolean adjacency matrix

Parameters

adjmat (numpy.ndarray) – bool square matrix

Returns

the loaded Graph

Raises

RuntimeError – if adjmat is not square or the edges could not be constructed

static from_adjlist()

Constructs Graph instance from the given adjacency list. Note that the first element of the list must be an empty set, vertex indices start at 1.

Parameters

• num_vertices (int) –

• num_edges (int) –

• edges (list) – list of sets

Returns

the loaded Graph

Raises

RuntimeError – if first element in edges is nonempty, or there are invalid vertices/edges

to_file()

Exports Graph instance to a Matrix Market file

Parameters

filename (str) –

Raises

RuntimeError – if the file could not be opened, or if the graph is empty

to_edgelist()

Exports Graph instance to an edge list

Returns

(n,2) numpy.ndarray of edges

Raises

RuntimeError – if the graph is empty

to_matrix()

Exports Graph instance to a boolean matrix

Returns

square numpy.ndarray of bools

Raises

RuntimeError – if the graph is empty

to_adjlist()

Exports Graph instance to an adjacency list

Returns

list of sets

Raises

RuntimeError – if the graph is empty

class cliquematch.NWGraph

search_done

Whether the search has been completed (Readonly)

Type

bool

n_vertices

Number of vertices in the graph (Readonly)

Type

int

n_edges

Number of edges in the graph (Readonly)

Type

int

get_max_clique()

Finds a maximum clique in graph within the given bounds

Parameters

• lower_bound (float) – set a lower bound on the clique size. default is 1.

• upper_bound (float) – set an upper bound on the clique size. default is 65535.

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound. default is True.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

Returns

the vertices in the maximum clique

Return type

list

Raises

RuntimeError – if the graph is empty or a clique could not be found

reset_search()

Reset the search space for get_max_clique.

Raises

RuntimeError – if the graph is empty

all_cliques(size)

Iterate through all cliques of a given size in the NWGraph.

Parameters

size (float) – size of a clique to search for.

Return type

NWCliqueIterator

Raises

RuntimeError – if the graph is empty

get_clique_weight(clique)

Return the weight of the provided clique.

Parameters

clique (list) – a clique obtained via get_max_clique.

Return type

float

static from_edgelist()

Constructs NWGraph instance from the given edge list. Note that vertex indices must start from 1.

Parameters

• edgelist (numpy.ndarray) – shape (n,2)

• num_vertices (int) –

Returns

the loaded NWGraph

Raises

• RuntimeError – if any value in edgelist is greater than num_vertices

• RuntimeError – if value in edgelist is 0

static from_matrix()

Constructs NWGraph instance from the given boolean adjacency matrix

Parameters

adjmat (numpy.ndarray) – bool square matrix

Returns

the loaded NWGraph

Raises

RuntimeError – if adjmat is not square or the edges could not be constructed

static from_adjlist()

Constructs NWGraph instance from the given adjacency list. Note that the first element of the list must be an empty set, vertex indices start at 1.

Parameters

• num_vertices (int) –

• num_edges (int) –

• edges (list) – list of sets

Returns

the loaded NWGraph

Raises

RuntimeError – if first element in edges is nonempty, or there are invalid vertices/edges

to_edgelist()

Exports NWGraph instance to an edge list

Returns

(n,2) numpy.ndarray of edges

Raises

RuntimeError – if the graph is empty

to_matrix()

Exports NWGraph instance to a boolean matrix

Returns

square numpy.ndarray of bools

Raises

RuntimeError – if the graph is empty

to_adjlist()

Exports NWGraph instance to an adjacency list

Returns

list of sets

Raises

RuntimeError – if the graph is empty

class cliquematch.A2AGraph(set1, set2, d1=None, d2=None, is_d1_symmetric=True, is_d2_symmetric=True)

Correspondence Graph wrapper for array-to-array mappings.

S1

array elements are converted to numpy.float64

Type

numpy.ndarray

S2

array elements are converted to numpy.float64

Type

numpy.ndarray

d1

distance metric for elements in S1, defaults to Euclidean metric if None.

Type

callable (numpy.ndarray, int, int) -> float

d2

distance metric for elements in S2, defaults to Euclidean metric if None

Type

callable (numpy.ndarray, int, int) -> float

is_d1_symmetric

Type

bool

is_d2_symmetric

Type

bool

all_correspondences(size, return_indices=True)

Find all correspondences of a given size.

Parameters

• size (int) – size of the corresponding subsets.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Returns

a wrapped CorrespondenceIterator object, which yields correspondences as per return_indices.

Return type

_WrappedIterator

Raises

RuntimeError – if called before edges have been constructed

build_edges()

Build edges of the correspondence graph using distance metrics.

Checks d1 and d2 for defaults before passing to base class.

Raises

RuntimeError – if d1or d2 are invalid functions

Returns

True if construction was successful

Return type

bool

build_edges_with_condition(condition_func, use_cfunc_only)

Build edges of the correspondence graph using a given condition function.

Parameters

• condition_func (callable) – must take parameters corresponding to S1, int, int, S2, int, int, and return bool

• use_cfunc_only (bool) – if True, the distance metrics will not be used to filter out edges (slower)

Returns

True if construction was successful

Raises

RuntimeError – if d1, d2, or condition_func are invalid functions

get_correspondence(lower_bound=1, upper_bound=65535, time_limit=- 1.0, use_heuristic=True, use_dfs=True, continue_search=False, return_indices=True)

Get corresponding subsets between the S1 and S2. Calls get_max_clique internally.

Parameters

• lower_bound (int) – set a lower bound for the size

• upper_bound (int) – set an upper bound for the size

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search).

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Raises

• RuntimeError – if called before edges are constructed

• RuntimeError – if search parameters are invalid / clique is not found

• RuntimeError – if obtained correspondence is invalid

class cliquematch.L2LGraph(set1, set2, d1=None, d2=None, is_d1_symmetric=True, is_d2_symmetric=True)

Correspondence Graph wrapper for list-to-list mappings.

Any object can be passed for S1 and S2; the user is required to define how the elements are accessed.

S1

array elements are converted to numpy.float64

Type

object

S2

array elements are converted to numpy.float64

Type

object

d1

distance metric for elements in S1

Type

callable (list, int, int) -> float

d2

distance metric for elements in S2

Type

callable (list, int, int) -> float

is_d1_symmetric

Type

bool

is_d2_symmetric

Type

bool

all_correspondences(size, return_indices=True)

Find all correspondences of a given size.

Parameters

• size (int) – size of the corresponding subsets.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Returns

a wrapped CorrespondenceIterator object, which yields correspondences as per return_indices.

Return type

_WrappedIterator

Raises

RuntimeError – if called before edges have been constructed

build_edges()

Build edges of the correspondence graph using distance metrics.

Checks d1 and d2 for defaults before passing to base class.

Raises

RuntimeError – if d1or d2 are invalid functions

Returns

True if construction was successful

Return type

bool

build_edges_with_condition(condition_func, use_cfunc_only)

Build edges of the correspondence graph using a given condition function.

Parameters

• condition_func (callable) – must take parameters corresponding to S1, int, int, S2, int, int, and return bool

• use_cfunc_only (bool) – if True, the distance metrics will not be used to filter out edges (slower)

Returns

True if construction was successful

Raises

RuntimeError – if d1, d2, or condition_func are invalid functions

get_correspondence(lower_bound=1, upper_bound=65535, time_limit=- 1.0, use_heuristic=True, use_dfs=True, continue_search=False, return_indices=True)

Get corresponding subsets between the S1 and S2. Calls get_max_clique internally.

Parameters

• lower_bound (int) – set a lower bound for the size

• upper_bound (int) – set an upper bound for the size

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search).

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Raises

• RuntimeError – if called before edges are constructed

• RuntimeError – if search parameters are invalid / clique is not found

• RuntimeError – if obtained correspondence is invalid

class cliquematch.L2AGraph(set1, set2, d1=None, d2=None, is_d1_symmetric=True, is_d2_symmetric=True)

Correspondence Graph wrapper for list-to-array mappings.

Any general object can be passed for S1; the user is required to define how elements are accessed.

S1

Type

object

S2

array elements are converted to numpy.float64

Type

numpy.ndarray

d1

distance metric for elements in S1

Type

callable (list, int, int) -> float

d2

distance metric for elements in S2, defaults to Euclidean metric if None

Type

callable (numpy.ndarray, int, int) -> float

is_d1_symmetric

Type

bool

is_d2_symmetric

Type

bool

all_correspondences(size, return_indices=True)

Find all correspondences of a given size.

Parameters

• size (int) – size of the corresponding subsets.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Returns

a wrapped CorrespondenceIterator object, which yields correspondences as per return_indices.

Return type

_WrappedIterator

Raises

RuntimeError – if called before edges have been constructed

build_edges()

Build edges of the correspondence graph using distance metrics.

Checks d1 and d2 for defaults before passing to base class.

Raises

RuntimeError – if d1or d2 are invalid functions

Returns

True if construction was successful

Return type

bool

build_edges_with_condition(condition_func, use_cfunc_only)

Build edges of the correspondence graph using a given condition function.

Parameters

• condition_func (callable) – must take parameters corresponding to S1, int, int, S2, int, int, and return bool

• use_cfunc_only (bool) – if True, the distance metrics will not be used to filter out edges (slower)

Returns

True if construction was successful

Raises

RuntimeError – if d1, d2, or condition_func are invalid functions

get_correspondence(lower_bound=1, upper_bound=65535, time_limit=- 1.0, use_heuristic=True, use_dfs=True, continue_search=False, return_indices=True)

Get corresponding subsets between the S1 and S2. Calls get_max_clique internally.

Parameters

• lower_bound (int) – set a lower bound for the size

• upper_bound (int) – set an upper bound for the size

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search).

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Raises

• RuntimeError – if called before edges are constructed

• RuntimeError – if search parameters are invalid / clique is not found

• RuntimeError – if obtained correspondence is invalid

class cliquematch.A2LGraph(set1, set2, d1=None, d2=None, is_d1_symmetric=True, is_d2_symmetric=True)

Correspondence Graph wrapper for array-to-list mappings.

Any general object can be passed for S2; the user is required to define how elements are accessed.

S1

array elements are converted to numpy.float64

Type

numpy.ndarray

S2

Type

object

d1

distance metric for elements in S1, defaults to Euclidean metric if None

Type

callable (numpy.ndarray, int, int) -> float

d2

distance metric for elements in S2

Type

callable (list, int, int) -> float

is_d1_symmetric

Type

bool

is_d2_symmetric

Type

bool

all_correspondences(size, return_indices=True)

Find all correspondences of a given size.

Parameters

• size (int) – size of the corresponding subsets.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Returns

a wrapped CorrespondenceIterator object, which yields correspondences as per return_indices.

Return type

_WrappedIterator

Raises

RuntimeError – if called before edges have been constructed

build_edges()

Build edges of the correspondence graph using distance metrics.

Checks d1 and d2 for defaults before passing to base class.

Raises

RuntimeError – if d1or d2 are invalid functions

Returns

True if construction was successful

Return type

bool

build_edges_with_condition(condition_func, use_cfunc_only)

Build edges of the correspondence graph using a given condition function.

Parameters

• condition_func (callable) – must take parameters corresponding to S1, int, int, S2, int, int, and return bool

• use_cfunc_only (bool) – if True, the distance metrics will not be used to filter out edges (slower)

Returns

True if construction was successful

Raises

RuntimeError – if d1, d2, or condition_func are invalid functions

get_correspondence(lower_bound=1, upper_bound=65535, time_limit=- 1.0, use_heuristic=True, use_dfs=True, continue_search=False, return_indices=True)

Get corresponding subsets between the S1 and S2. Calls get_max_clique internally.

Parameters

• lower_bound (int) – set a lower bound for the size

• upper_bound (int) – set an upper bound for the size

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search).

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the elements

Raises

• RuntimeError – if called before edges are constructed

• RuntimeError – if search parameters are invalid / clique is not found

• RuntimeError – if obtained correspondence is invalid

class cliquematch.IsoGraph(set1, set2)

Correspondence graph for finding subgraph isomorphisms.

S1

Type

cliquematch.Graph

S2

Type

cliquematch.Graph

build_edges()

Build edges of the correspondence graph.

get_correspondence(lower_bound=1, upper_bound=65535, time_limit=- 1.0, use_heuristic=True, use_dfs=True, continue_search=False, return_indices=True)

Obtain the corresponding vertices in the subgraph isomorphism.

Parameters

• lower_bound (int) – set a lower bound for the size

• upper_bound (int) – set an upper bound for the size

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search).

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit.

• return_indices (bool) – if True return the vertices of the corresponding subgraphs, else return dicts for each corresponding subgraph and a dict mapping the vertices.

Raises

• RuntimeError – if called before edges are constructed

• RuntimeError – if search parameters are invalid / clique is not found

• RuntimeError – if obtained correspondence is invalid

all_correspondences(size, return_indices=True)

Find all correspondences of a given size.

Parameters

• size (int) – size of the corresponding subsets.

• return_indices (bool) – if True return the vertices of the corresponding subgraphs, else return dicts for each corresponding subgraph and a dict mapping the vertices.

Returns

a wrapped CorrespondenceIterator object, which yields correspondences as per return_indices.

Return type

_WrappedIterator

Raises

RuntimeError – if called before edges are constructed

class cliquematch.AlignGraph(set1, set2)

Correspondence graph for aligning images using obtained interest points.

Uses a mask-based filtering method as a conditon function during construction of the graph. Default Euclidean metrics are used as distance metrics.

S1

array elements are converted to numpy.float64

Type

numpy.ndarray

S2

array elements are converted to numpy.float64

Type

numpy.ndarray

build_edges_with_filter(control_points, filter_mask, percentage)

Uses control points and a binary mask to filter out invalid mappings and construct a correspondence graph.

Parameters

• control_points (numpy.ndarray) – control points to use in every alignment test

• filter_mask (numpy.ndarray) – a boolean mask showing valid regions in the target image

• percentage (float) – an alignment is valid if the number of control points that fall within the mask are greater than this value

get_correspondence(lower_bound=1, upper_bound=65535, time_limit=- 1.0, use_heuristic=True, use_dfs=True, continue_search=False, return_indices=True)

Find correspondence between the sets of points S1 and S2. Calls get_max_clique internally.

Parameters

• lower_bound (int) – set a lower bound for the size

• upper_bound (int) – set an upper bound for the size

• time_limit (float) – set a time limit for the search: a nonpositive value implies there is no time limit (use in conjunction with continue_search).

• use_heuristic (bool) – if True, use the heuristic-based search to obtain a large clique quickly. Good for obtaining an initial lower bound.

• use_dfs (bool) – if True, use the depth-first to obtain the clique. default is True.

• continue_search (bool) – set as True to continue a clique search interrupted by time_limit.

• return_indices (bool) – if True return the indices of the corresponding elements, else return the below dict

Returns

The two sets of corresponding points and the rotation/translation required to transform S1 to S2 (obtained via Kabsch Algorithm)

Return type

dict

Raises

• RuntimeError – if called before edges are constructed

• RuntimeError – if search parameters are invalid / clique is not found

• RuntimeError – if obtained correspondence is invalid

class cliquematch._WrappedIterator

Wrapper for a CorrespondenceIterator object to provide results as per return_indices. Satisfies the iter/next protocol.

class cliquematch.core.CliqueIterator

A class satisfying the iter/next protocol to produces cliques of a given size from a Graph.

class cliquematch.core.CorrespondenceIterator

A class satisfying the iter/next protocol to produces correspondences of a given size from a Graph.

class cliquematch.core.NWCliqueIterator

A class satisfying the iter/next protocol to produces cliques of a given weight from a NWGraph.