function result = graph(n)
% given n, make an accessibility-matrix representation or something
% of G^n.
nodes = binaryCombinations(n);
revnodes = nodes(:,end:-1:1);
len = size(nodes,1);	% 2^n

valvec = (2.^(n-1:-1:0))';
vn = nodes*valvec;
vr = revnodes*valvec;

% classify each node into E, S, W, or A.
class = zeros(len,1)+'A';
class(binaryRowEqual(nodes, revnodes)) = 'S';
%class(logical(~sum(nodes ~= revnodes,2))) = 'S';
class(1) = 'E';
class(end) = 'E';

% Find class W (the "weird assymmetrics") -- only occurs
% in even n; otherwise the offender is symmetric.
if (~mod(n,2)), % if n is even...
	w = 1-mod(1:n,2);
	class(w*valvec+1) = 'W';
	class((1-w)*valvec+1) = 'W';
end

% find equivalence classes, and identify the representative
% (lexicographically smaller)
% addrId maps an address of a node to the same address (identity)
addrId = (1:len)';
% revEquiv maps an address of a node to the address of its reversal
for i=1:length(vr),
	revEquiv(i,1) = find(vn==vr(i));
end
rep = (addrId)<=revEquiv(addrId);
addrToRep = rep.*addrId + (~rep).*revEquiv;

% figure out where each G node can go (find its two outbound edges in Gn)
out0 = [nodes(:,2:end),zeros(len,1)];
addr0 = out0*valvec+1;
rep0 = addrToRep(addr0);

out1 = [nodes(:,2:end),ones(len,1)];
addr1 = out1*valvec+1;
rep1 = addrToRep(addr1);

repToAddr = find(rep);



% figure out all of the edges between representatives
edgeLabels = binaryCombinations(n+1);

% palindromes are always and the only loops,
% and we can (and must!) ignore them.
revEdgeLabels = edgeLabels(:,end:-1:1);
palindromeEdges = binaryRowEqual(edgeLabels, revEdgeLabels);

% any other edge is an edge between two equivalence classes (collapsed
% nodes). Select its direction based on where it's coming from or going to.
fromVert	= edgeLabels(:,1:end-1);
revFromVert	= fromVert(:,end:-1:1);
fromVal		= fromVert * valvec;
revFromVal	= revFromVert * valvec;
fromType	= -((fromVal<revFromVal)-(revFromVal<fromVal));
	% 1 means 'draw a head on this end'.
	% a head means 'arrives at top';
	% a tail means 'leaves from top'

toVert		= edgeLabels(:,2:end);
revToVert	= toVert(:,end:-1:1);
toVal		= toVert * valvec;
revToVal	= revToVert * valvec;
toType		= (toVal<revToVal)-(revToVal<toVal);

% fill in the edges where one end is a palindrome
fromType(fromType==0) = -toType(fromType==0);
toType(toType==0) = -fromType(toType==0);

x = [edgeLabels, palindromeEdges, fromVal, toVal, fromType, toType];
x(~palindromeEdges,:)
disagree = (fromType & toType) & (fromType == toType) & (~palindromeEdges);
disagrees = find(disagree);
x(disagrees,:)

% this only makes sense for non-disagreeing guys
shortEdges = [fromVal, toVal];
shortEdges(fromType==1,1:2) = shortEdges(fromType==1,2:-1:1);
shortEdges = shortEdges(~palindromeEdges,:);	% discard loops
shortEdges = addrToRep(shortEdges+1)-1;			% use representative names
shortEdges = unique(shortEdges,'rows');			% select the unique rows
shortEdges
find(class=='S')-1

return

% figure out where each G' node can go -- four possibilities.
% (actually two if node is symmetric.)
outEdges = [rep0, rep1, rep0(revEquiv), rep1(revEquiv)];

% eliminate loops
% count loops because I'm curious how many there are.
[outEdges,loop] = separateLoops(outEdges);	% kills self-loops
loop(find(~rep)) = 0; % loops only count if they're on a representative
numLoops = sum(loop);

degree = findDegree(outEdges);	% counts self-loops
[outEdges,degree]

nd4 = sum(degree(logical(rep))==4);
nd3 = sum(degree(logical(rep))==3);
nd1 = sum(degree(logical(rep))==1);
nn = sum(rep);
disp(sprintf('number of degree-1 nodes: %d', nd1));
disp(sprintf('number of degree-3 nodes: %d', nd3));
disp(sprintf('number of degree-4 nodes: %d', nd4));
disp(sprintf('number of nodes         : %d', nn));
disp(sprintf('fraction of degree-4 nodes: %6.3f', nd4/nn));

% the all-pair stuff is
% a little slow in that we compute over non-rep nodes,
% which always come out Inf.

% try to eliminate odd-degree nodes to get a eulerian tour
while 1,
% (this is where the code in bruteForce.m came from.)
% But it stunk, so the code below replaces it, exploiting a heuristic.
	degree = findDegree(outEdges);	% kills self-loops
	oddNodes = find(mod(degree,2)==1 & rep);
	if (length(oddNodes)==0),
		break;
	end
	% find an odd node with an odd nbr
	success = 0;
	for i=1:length(oddNodes),
		node = oddNodes(i);
		nbrs = outEdges(node,:);
		nbrs = nbrs(nbrs>0);
		nbrDegrees = degree(nbrs);
		oddNbri = find(mod(nbrDegrees,2)==1);
		if (length(oddNbri)>0),
			% yes, this guy has an odd nbr
			oddNbr = nbrs(oddNbri(1));
%			disp(sprintf('nodes %d and %d are 1 apart, cutting edge.', ...
%				node, oddNbr));
			outEdges = cutEdge(outEdges, node, oddNbr);
			% now go re-evaluate the graph
			success = 1;
			break;
		end
	end
	if (~success),
		if ((length(oddNodes)==2) & (mod(n,2)==0)),
			% okay, one pair left, 2 edges apart.
			n1 = oddNodes(1);
			n2 = oddNodes(2);
			[d,p] = dijkstra(outEdges, n1, oddNodes);
			% mask will make this really fast -- probably only two iterations.
			% what am I talking about? I'm using matlab! Since when have I
			% cared about fast?
			outEdges = cutPath(outEdges, n1, n2, p);
		else
			% hopefully we'll prove it can't happen!
			error('I have never seen this case happen before.');
		end
	end
end

% did the graph stay (basically) connected?
% [d,p] = dijkstra(outEdges, 2, []);
% disconnects = find((d==Inf) & (rep));
% disconnects

% hide any irrelevant nodes.
outEdges(find(~rep), :) = -1;
walk = eulerWalk(outEdges);

% the only "safe" loop to follow is the one at 0*.
% 
usableEdges = length(walk)-1;
	% -1 accounts for walk specified as vertices, and listing the
	% start and end vertex twice.
% by omitting the last two, we get handed cycles.
% by including them, we get a two-bit longer open path.

% % increment by one if the graph has a W node. (even n) (One was
% % counted in numLoops, but W's have two distinct self-loops.)
% NOOOO! don't follow loops, young Jedi!
% if (mod(n,2)==0),
% 	usableEdges = usableEdges+1;
% end

disp(sprintf('hay %d edges in walk and %d edges in loops', ...
	length(walk)-1, numLoops));
disp(sprintf('found a walk of length %d/%d (%d away)', ...
	usableEdges, 2^n, 2^n-usableEdges));
walk'
z_walk = nodes(walk,:)
out0(walk,:)
out1(walk,:)

% [addrId(find(rep)),outEdges(find(rep),:)]

spacecolumn = ones(size(class))*' ';
q = [char(nodes+'0'), char(class), char(rep*10+' '), ...
	spacecolumn,char(out0+'0'),spacecolumn,char(out1+'0')];
%char(class(find(degree==2)))'