graphv

type AccessPath[Vertex any] interface {
	Common[Vertex]

	// AccessPath examines the path from the search root to the current vertex.
	//
	// Its parameter is the path from the search root to
	// the current vertex to examine.
	// path must be nonempty.
	//
	// It returns two indicators:
	//   found - to report whether the specified vertex is the search goal;
	//   cont - to report whether to continue searching.
	//
	// The search algorithm should exit immediately if cont is false.
	// In this case, the search result may be invalid.
	//
	// Sometimes it is also referred to as "visit".
	AccessPath(path []Vertex) (found, cont bool)
}

type AccessVertex[Vertex any] interface {
	Common[Vertex]

	// AccessVertex examines the specified vertex.
	//
	// It has two parameters:
	//   vertex - the vertex to examine;
	//   depth - the search depth from the root to the node.
	//
	// It returns two indicators:
	//   found - to report whether the specified vertex is the search goal;
	//   cont - to report whether to continue searching.
	//
	// The search algorithm should exit immediately if cont is false.
	// In this case, the search result may be invalid.
	//
	// Sometimes it is also referred to as "visit".
	AccessVertex(vertex Vertex, depth int) (found, cont bool)
}

type Common[Vertex any] interface {
	// Init initializes all states for a new search
	// with specified arguments args (e.g., set the search goal).
	//
	// It will be called once at the beginning of the search functions.
	Init(args ...any)

	// Root returns the vertex of the graph where the search algorithm start.
	//
	// It returns only one vertex because the search starts at
	// one specified vertex in most cases.
	// If there are multiple starting vertices, set the root to a dummy vertex
	// whose adjacent vertices are the starting vertices.
	Root() Vertex

	// Adjacency returns the adjacent vertices of the specified vertex
	// as an adjacency list.
	//
	// The first item in the list is accessed first.
	Adjacency(vertex Vertex) []Vertex

	// Discovered reports whether the specified vertex
	// has been examined by the method AccessVertex or AccessPath.
	//
	// Sometimes it is also referred to as "visited".
	//
	// It is typically implemented by using a hash table or
	// associating an attribute "discovered" to each vertex.
	//
	// If it is not necessary to record the vertices discovered,
	// or the graph is too big to record the vertices discovered,
	// just always return false.
	// In this case, the search algorithms may access one vertex
	// multiple times, and may even fall into an infinite loop.
	Discovered(vertex Vertex) bool
}

type IDSAccessPath[Vertex any] interface {
	AccessPath[Vertex]
	IDSSpecific[Vertex]
}

type IDSAccessVertex[Vertex any] interface {
	AccessVertex[Vertex]
	IDSSpecific[Vertex]
}

type IDSSpecific[Vertex any] interface {
	// ResetSearchState resets the search state for the next iteration.
	//
	// It will be called before each iteration in functions IDS and IDSPath,
	// except for the first iteration.
	//
	// Its implementation must reset all the vertices to undiscovered,
	// and can reset any other states associated with each iteration
	// in this method.
	ResetSearchState()
}