makeGraph: make a network graph representing a given puzzle
In shigono/rSlidePzl: Analyze sliding puzzles

Description Usage Arguments Value Examples

executes breadth-first search of all states which are reachable from the initial state. The exception is when it reach a state with satisfying goal conditions: it stop to search further from the state.

makeGraph(
  setting,
  state,
  goalcondition = NULL,
  initsize_states = 1e+06,
  initsize_transitions = 2e+06,
  max_depth = Inf,
  max_num_states = Inf,
  verbose = 1
)

`setting`	an object of 'slidepzl_setting' class. Setting of a puzzle.
`state`	an object of 'slidepzl_state' class. Initial state. It should be a valid state.
`goalcondition`	an object of 'slidepzl_state' class, or NULL. Conditions of goal. It should be a valid state if it is not NULL.
`initsize_states`	initial size of database of states. Execution of this function may slow down when more states are found than `initsize_states`.
`initsize_transitions`	initial size of database of transition. Execution of this function may slow down when more transition are found than `initsize_transitions`.
`max_depth`	max depth of states to search.
`max_num_states`	max number of states to find.
`verbose`	0:no message, 1:normal messages, 2:full messsages.

an object of 'igraph' class.

Vertexes and edges represents states and transition between states, respectively.

Include following information as attributes of vertexes:

name: character string, representing a state
depth: integer, representing depth of the state
status: 1:the initial state, 2:a state which is examined, 3:a state which is not examined, 4: a goal state

Include following information as attributes of edges:

name: which piece is moved to which direction. e.g. '11U' means a piece located at (1,1) in original state is moved up.

# make setting of a sliding puzzle
oSetting <- makeSetting(
  boardsize = c(3,3),
  piecesize = list(
    A = c(1, 1),
    B = c(1, 1),
    C = c(1, 1),
    D = c(1, 1),
    E = c(1, 1),
    F = c(1, 1),
    G = c(1, 1),
    H = c(1, 1)
  )
)
# make an initial state
oStart <- makeState(
  list(
    makePiece(type = "A", loc = c(1,1)),
    makePiece(type = "B", loc = c(2,2)),
    makePiece(type = "C", loc = c(1,2)),
    makePiece(type = "D", loc = c(2,1)),
    makePiece(type = "E", loc = c(2,3)),
    makePiece(type = "F", loc = c(3,3)),
    makePiece(type = "G", loc = c(3,1)),
    makePiece(type = "H", loc = c(3,2))
  )
)
stopifnot(isValidState(oStart, oSetting))

# define conditions of goal
oGoalCondition <- makeState(
  list(
    makePiece(type = "A", loc = c(1,1)),
    makePiece(type = "B", loc = c(1,2)),
    makePiece(type = "C", loc = c(1,3)),
    makePiece(type = "D", loc = c(2,1)),
    makePiece(type = "E", loc = c(2,2)),
    makePiece(type = "F", loc = c(2,3)),
    makePiece(type = "G", loc = c(3,1)),
    makePiece(type = "H", loc = c(3,2))
  )
)
stopifnot(isValidState(oGoalCondition, oSetting))

# analyse the puzzle and make a network graph of states
oGraph <- makeGraph(oSetting, oStart, oGoalCondition, max_depth = 5, verbose = 1)

# plot
set.seed(123)
plotGraph(oGraph, method = "GGally")

# show shortest pathes
lSolution <- getAllShortestPaths(oGraph)
print(lSolution$state)
print(lSolution$transition)