#*************************************************************************#
# Copyright (C) 2013 Edinah K. Gnang #
# #
# Distributed under the terms of the GNU General Public License (GPL) #
# #
# This code is distributed in the hope that it will be useful, #
# but WITHOUT ANY WARRANTY; without even the implied warranty of #
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU #
# General Public License for more details. #
# #
# The full text of the GPL is available at: #
# #
# http://www.gnu.org/licenses/ #
#*************************************************************************#
r"""
C2.sage: ExpMath class Jan. 28, 2013
Every non-partisan combinatorial game can be describes abstractly as a desirected
graphs. The position are vertices, and there is a DIRECTED edge between vertex
v1 to v2, if it is a legal move. We represent a digraph as a List L. The vertices
are called 0, 1, ..., len(L)-1 and for i=0, 1, ..., len(L), L[i] is the set of
vertices for which there is a directed edge from i to the elemnts of the
corresponding set for example the graphs G = [[],[0],[0,1]] corresponds to the
graph on the vertices [0,1,2] and it edges are (1,0),(2,0),(2,1)
AUTHORS:
-- Edinah K. Gnang (Mon Jan 28 2013)
TODO:
-- Optimize the running time of the function is_cyclic by implementing a depth-first search routine
"""
def am(G):
"""
Expresses the adjacency matrix M corresponding to the graph G
M[i,j] = 1 (resp. 0) if j is ( is not )
in the list G[i]
sage:G = [[1],[2],[0]]
sage:am(G)
[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
"""
M = Matrix(ZZ,len(G),len(G),[0 for k in range((len(G))^2)])
for i in range(len(G)):
for j in range(len(G)):
if j in Set(G[i]):
M[i,j] = 1
return M
def is_cyclic(G):
"""
Inputs a directed graph (descibed as an list of list) and outputs True (resp. False) if
it has a cycle (if it contains no cycle)
sage: is_cyclic([[1],[2],[0]])
True
"""
# Obtaining the adjacency matrix
M = am(G)
# Initializing the temporary matrix
M1 = M
for i in range(len(G)):
if M1.trace() > 0:
return True
else :
M1 = M1*M
return False
def fGi(G,i):
"""
Inputs a directed graph G and an integer i in range(len(G))
and outputs 0 (resp. 1) if the vertex i is a losing (winning)
position
Incase the graph contains a cycle the function outputs -1
"""
if is_cyclic(G):
print "The Graph contains a cycle"
return -1
else:
M = G[i]
if G[i] == []:
return 0
elif Set([fGi(G,m) for m in M]) == Set([1]):
return 0
else :
return 1
def wl(G):
"""
Inputs a directed graph G representing a game and outputs a list of nops(G)
such that L[i] = 0 or 1 accorfing to whether position (vertex) i
is a loosing or a winning position
sage:G = [[1],[2],[0]]
sage:wl(G)
"""
return [fGi(G,i) for i in range(len(G))]
def rand_game(n, k):
"""
Inputs pos. integers n and k and ouputs a random digraph that has the property that out
of vertex i all the labels are less to i, and having as number of outgoing edges a number
between 2 and k
"""
L = [ list(Set([randint(0,j) for i in range(1,randint(2,k))])) for j in range(n)]
L.insert(0,[])
return L