graphEmbeddings3D

Module AlgRealEmbeddings

class graphEmbeddings3D.algRealEmbeddings.AlgRealEmbeddings(graph_type, num_phi=20, num_theta=20, factor_second=4, choice_from_clusters='center', window=None, name=None, edges=None, num_sols=None, allowedNumberOfMissing=0, moreSamplingSubgraphs=False)

This class implements the sampling procedure for obtaining edge lengths with many real embeddings.

The predefined graphs given by graph_type can be found in graphEmbeddings3D.graphEmbedding.GraphEmbedding. Another option is to use graph_type`=’edges’ and specify `edges of the graph and the number of complex embeddings of the graph by num_sols. The graph must contain the triangle 1,2,3. In this case, the keys of a dictionary with edge lengths, when the function findMoreEmbeddings is called, must match edges.

num_phi and num_theta determine the number of samples of \(\varphi\) and \(\theta\) in the first phase of sampling. In the second phase, num_phi/factor_second and num_theta/factor_second values are sampled around the ones from the first phase with the highest number of real embeddings.

After sampling, edge lengths are selected from clusters by choice_from_clusters:

  • ‘center’: center of the \((\varphi,\theta)\) cluster
  • ‘closestToAverageLength’: average of lengths in cluster

name is used for temporary and results files.

For implementing a new graph, self._numAllSol must be set in the constructor to the maximal number of complex embeddings of the graph, and self._combinations contains all subgraphs suitable for sampling.

The parameter allowedNumberOfMissing indicates how many solutions can be lost in PHC computation without causing a recomputation.

If graph_type`=’edges’, then `moreSamplingSubgraphs indicates whether only subgraphs whose sampling preserves the coupler curve are used (False) or all that have necessary edges (True). Namely, whether deg(u)=4 or deg(u)>=4.

findMoreEmbeddings(starting_lengths, required_num=None, combinations=None, allowed_repetition=1)

Edge lengts with required_num real embeddings are searched by linear approach from starting_lengths, namely, subgraphs given by combinations are used one by one.

If required_num==None, then self._numAllSol is used. Similarly, if combinations==None, then self._combinations are used.

The parameter allowed_repetition determines, how many times can be the whole list combinations used without increase of the number of real embeddings.

Results are saved in ../results.

findMoreEmbeddings_tree(starting_lengths, required_num=None, onlyOne=True, combinations=None)

Edge lengts with required_num real embeddings are searched by tree approach from starting_lengths, namely, trying all combinations of subgraphs given by combinations.

If required_num==None, then self._numAllSol is used. Similarly, if combinations==None, then self._combinations are used.

If onlyOne is True, then the algorithm stops if the first edge lengths with required_num real embeddings are found. Otherwise, the whole tree is traversed (extremely long!!!).

Results are saved in ../results.

Module GraphEmbedding

class graphEmbeddings3D.graphEmbedding.GraphEmbedding(lengths, graph_type, tmpFileName=None, window=None, num_sols=None, allowedNumberOfMissing=0)

This class implements the computation of spatial embeddings for a graph \(G\) with edge lengths \(\mathbb{d}\)

Arbitrary minimally rigid graphs with vertices labeled by 1, …, N are supported:

  • use graph_type=’edges’
  • The edges are taken from the dict lengths.
  • The graph must contain the triangle 1,2,3.

Predefined graphs:

  • \(G_{16}\)
    • graph_type=’Max6vertices’
    • edges: {(1, 3), (5, 6), (2, 6), (2, 3), (3, 5), (1, 2), (4, 6), (1, 5), (4, 5), (1, 6), (3, 4), (2, 4)}
  • \(G_{48}\)
    • graph_type=’Max7vertices’
    • edges: {(2, 7), (4, 7), (1, 3), (4, 5), (1, 4), (5, 6), (2, 6), (1, 6), (3, 7), (1, 2), (6, 7), (5, 7), (1, 5), (2, 3), (3, 4)}
  • \(G_{32a}\)
    • graph_type=‘7vert32a’
    • edges: {(4, 7), (1, 3), (5, 6), (1, 4), (1, 6), (3, 7), (2, 5), (3, 5), (1, 2), (6, 7), (5, 7), (3, 6), (2, 3), (3, 4), (2, 4)}
  • \(G_{32b}\)
    • graph_type=‘7vert32b’
    • edges: {(2, 7), (4, 7), (2, 6), (4, 5), (1, 4), (5, 6), (1, 3), (2, 3), (3, 7), (2, 5), (1, 2), (6, 7), (1, 5), (3, 6), (3, 4)}
  • \(G_{24}\)
    • graph_type=‘7vert24’
    • edges: {(2, 7), (4, 7), (2, 6), (5, 6), (1, 4), (1, 3), (2, 3), (3, 7), (2, 5), (1, 2), (4, 6), (5, 7), (1, 5), (3, 6), (3, 4)}
  • \(G_{16a}\)
    • graph_type=‘7vert16a’
    • edges: {(4, 7), (1, 3), (5, 6), (1, 6), (3, 7), (2, 5), (3, 5), (1, 2), (4, 6), (5, 7), (3, 6), (1, 7), (2, 3), (3, 4), (2, 4)}
  • \(G_{16b}\)
    • graph_type=‘7vert16b’
    • edges: {(2, 7), (4, 7), (2, 6), (4, 5), (1, 4), (1, 3), (2, 3), (3, 7), (2, 5), (3, 5), (1, 2), (6, 7), (4, 6), (1, 5), (3, 6)}
  • \(G_{160}\)
    • graph_type=’Max8vertices’, or ‘Max8vertices_distSyst’ for using distance system instead of sphere equations (faster but often inaccurate)
    • edges: {(2, 7), (3, 2), (2, 6), (6, 8), (7, 8), (6, 1), (3, 1), (2, 8), (4, 7), (2, 1), (5, 8), (4, 3), (5, 1), (5, 4), (3, 7), (4, 1), (6, 5), (5, 7)}
  • \(G_{128}\)
    • graph_type=’Ring8vertices’
    • edges: {(1, 2), (2, 7), (5, 6), (1, 3), (6, 7), (6, 8), (4, 8), (4, 5), (2, 8), (7, 8), (1, 4), (3, 8), (1, 5), (1, 6), (1, 7), (2, 3), (3, 4), (5, 8)}

Inputs:

  • lengths is a dictionary with edge lengths of graph given by graph_type
  • tmpFileName is used for temporary files used during computations. If None, random hash is used.
  • num_sols must be specified if graph_type is ‘edges’. It is the number of complex embeddings of the graph.
  • allowedNumberOfMissing indicates how many solutions can be lost in PHC computation without causing a recomputation.
findEmbeddings(tolerance=1e-15, errorMsg=True, usePrev=True)

Compute embeddings of the graph compatible with the current edge lengths and fixed triangle and return them as dictionary {[‘real’]: listRealEmbeddings, [‘complex’]: listComplexEmbeddings}. Embeddings are considered real if the imaginary part of all coordinates is smaller than tolerance.

Package phcpy is used for the computation. If usePrev=True, then the solutions are tracked from ones from the previous call, if there was any.

getEdgeLength(u, v=None)

Return length of edge uv.

getEmbedding()

Return one of the real embeddings comaptible with the current edge lengths.

getEquations()

Return sphere equations of the graph corresponding to current edge lengths.

getLengths()

Return dictionary of edge lengths.

getPhiTheta(uvwpc)

Return angles \(\phi\) and \(\theta\) in the subgraph \((u,v,w,p,c)\) given by 5-tuple uvwpc.

setEdgeLength(Luv, u, v)

Set length of edge uv to Luv.

setLengths(lengths)

Set edge lengths to lengths.

setPhiTheta(uvwpc, phi, theta)

Set edge lengths so that the angles \(\phi\) and \(\theta\) in the subgraph \((u,v,w,p,c)\) given by 5-tuple uvwpc are phi and theta.

exception graphEmbeddings3D.graphEmbedding.TriangleInequalityError(errorMsg)

Exception raised if a tringle inequality is violated.

graphEmbeddings3D.graphEmbedding.getEdgeLengthsByEmbedding(graph_type, vert_coordinates, edges=[])

Return edge lengths for graph_type obtained by taking corresponding distances of vertices given by vert_coordinates.