"""xyzGraph.py
An xyz graph is the graph formed by a set of points in R^3 such that any
axis-parallel line intersects the set in zero or two points; we add an edge
for the two points on any nonempty line. These graphs include all bipartite
simple polyhedra, as well as some other nonplanar graphs; see
http://11011110.livejournal.com/tag/xyz+graphs for more.
We implement here an exponential-time algorithm for finding such
representations of an arbitrary graph, when they exist.
D. Eppstein, June 2006.
"""
from Graphs import isUndirected
from PartialOrder import TopologicalOrder
from StrongConnectivity import StronglyConnectedComponents
from Biconnectivity import stOrientation
import unittest
from collections import defaultdict
# 2to3 compatibility
try:
xrange
except:
xrange = range
def CubicMatchPartitions(G):
"""Partition a biconnected cubic graph G into three matchings.
Each matching is represented as a graph, in which G[v] is a list
of the three edges of G in the order of the three matchings.
This function generates a sequence of such representations.
"""
if not isUndirected(G):
raise ValueError("CubicMatchPartitions: graph is not undirected")
for v in G:
if len(G[v]) != 3:
raise ValueError("CubicMatchPartitions: graph is not cubic")
ST = stOrientation(G)
L = TopologicalOrder(ST)
for B in xrange(1<<(len(L)//2 - 1)):
# Here with a bitstring representing the sequence of choices
out = {}
pos = 0
for v in L:
source = [w for w in G[v] if w in out]
sourcepos = {}
adjlist = [None,None,None]
for w in source:
sourcepos[w] = [i for i in (0,1,2) if out[w][i]==v][0]
adjlist[sourcepos[w]] = w
usedpos = [sourcepos[w] for w in source]
if len(set(usedpos)) != len(usedpos):
# two edges in with same index, doesn't form matching
break
elif len(source) == 0:
# start vertex, choose one orientation
adjlist = list(ST[v])
elif len(source) == 1:
# two outgoing vertices, one incoming
avail = [i for i in (0,1,2) if i != usedpos[0]]
if B & (1<