Computational Tests for Solvability
view-graphs.sage contains code in Sage for verifying whether a viewing graph is solvable . A viewing graph is represented as an undirected "Graph" object in Sage. Such an object can be defined in different ways, for example as a list of edges:
G = Graph([(0,1),(1,2),(2,3),(3,0),(1,4),(4,5),(5,2)])
In an interactive notebook environment, the graph
G can be visualized with the command
1. Test for Non-Solvability
non_solving_check() can be used to prove that a graph is not solvable. Running
G is definitely not solvable, and
G is a "candidate" for being solvable (although even in this case it may still be possible for G to be not solvable: see Example 5 in ). The function runs the following tests (all
references are from ):
- Basic edge/vertex count (Theorem 1): returns
Trueif d(e,n) = 7e - 11n + 15<0, where e and n are respectively the number of edges and vertices of
- Bi-connected criterion (Proposition 3): returns
Gis not bi-connected, i.e., if it is possible to make the graph disconnected by removing one vertex.
- "Adjacent-valence" criterion (Proposition 2): returns
Gcontains two adjacent vertices of valence two.
- "d-condition" with vertices (Theorem 2): returns
Trueif there exists a subset of vertices of
Ginducing a subgraph
Hwith with e' edges and v' vertices and d(e',n')>d(e,n).
- "d-condition" with edges (Theorem 2): returns
Trueif there exists a subgraph
Hwith e' edges and v' vertices such that d(e',n')>d(e,n).
The last "d-condition" criterion is actually stronger than all the previous ones, but it is computationally more expensive.
2. Test for Solvability
move_completion() can be used to prove that a graph is solvable. Running
move_completion(G) returns a graph
K that is obtained from
G by applying the three "moves" from Theorem 3 in  cyclically, until no new move is possible. If the resulting graph
K is a complete graph (that can be verified with the command
G is solvable. Note that in special cases it may be possible that
K is not complete even though
G is solvable (see Examples 4 and 6 in ).
Running the function
move_completion() with the optional parameter
verbose set to
move_complection(G,verbose=True)) also prints a sequence of moves that produce
K starting from
3. Test for Finite-Solvability
degrees_of_freedom() can be used to verify whether or not a graph is finite solvable. The output of
degrees_of_freedom(G) is the dimension of the set T_G(c_1,...,c_n) defined in Section 4 of . This number is zero if and only if the graph is finite solvable. If this number is greater than zero, then the viewing graph generically identifies an infinite number of camera configurations. The dimensionality of T_G(c_1,...,c_n) is computed by verifying the rank of a matrix, corresponding to the linear compatibility equations described in Proposition 6 in  (after randomly fixing the camera pinholes).
 Matthew Trager, Brian Osserman, Jean Ponce: On Solvability of Viewing graphs, ECCV 2018 (https://arxiv.org/abs/1808.02856).