Core Graph Layer

Detailed Description

All graph algorithms used by Multi-State Mazes reside here. Some algorithms make random solution paths, while others help to build actual maze graphs.

Studying the Boost Graph Library will help greatly in understanding the implementations of these algorithms.


Classes

class  msmazes::DefaultRandomPathEdgePredicate
 The type of the default edge-checking predicate passed to the msmazes::makeRandomPaths() function template. More...
class  msmazes::DefaultCrossEdgeRemovalIntruder
 The type of the default intruder passed to the msmazes::removeCrossEdges() function template. More...

Functions

template<typename Graph>
bool msmazes::hasInEdges (typename boost::graph_traits< Graph >::vertex_descriptor target_v, const Graph &g)
 Returns true if the graph contains any incoming edges to target_v, false otherwise.
template<typename Graph>
void msmazes::removeInEdges (typename boost::graph_traits< Graph >::vertex_descriptor target_v, Graph &g)
 Removes all of target_v's incoming edges from the graph.
template<typename PredecessorMap, typename FrontInsertionSequence>
bool msmazes::makePath (typename boost::property_traits< PredecessorMap >::key_type source, typename boost::property_traits< PredecessorMap >::key_type target, const PredecessorMap p_map, FrontInsertionSequence &path)
 Stores the target vertex and its entire set of predecessors through the source vertex in the specified path container.
template<typename InputGraph, typename Vertex, typename Shuffler, typename OutputPredecessorMap, typename RandomPathEdgePredicate>
bool msmazes::makeRandomPaths (InputGraph &input_graph_arg, Vertex source_vertex_arg, Shuffler &shuffler_arg, OutputPredecessorMap output_predecessor_map_arg, RandomPathEdgePredicate visitor_arg)
 Outputs random paths from the graph to the predecessor map.
template<typename Params>
void msmazes::makeRandomPaths_with_named_params (Params &p)
 Packed-argument version of makeRandomPaths().
template<typename PathIterator, typename InputGraph, typename PredecessorMap, typename VertexIndexMap, typename VertexColorMap, typename VertexRankMap, typename Buffer, typename CrossEdgeRemovalIntruder>
void msmazes::removeCrossEdges (PathIterator path_begin, PathIterator path_end, InputGraph &g, PredecessorMap predecessor_map, VertexIndexMap index_map, VertexColorMap color_map, VertexRankMap rank_map, Buffer &Q, CrossEdgeRemovalIntruder &intruder)
 Converts the specified digraph to a maze with the specified solution path, using any specified utility maps.
template<typename Params>
void msmazes::removeCrossEdges_with_named_params (Params &p)
 Packed-argument version of removeCrossEdges().

Function Documentation

template<typename Graph>
bool hasInEdges (  typename boost::graph_traits< Graph >::vertex_descriptor  target_v,
const Graph &  g
) 
 

Returns true if the graph contains an edge e such that boost::target(e, g) == target_v, false otherwise.

Parameter Name Description Preconditions
target_v The vertex to check for incoming edges.
  • target_v must be a valid vertex descriptor in g.
g The graph containing target_v.
  • If the directed category of Graph is convertible to boost::directed_tag, then Graph must model the Adjacency Graph concept.

Returns:
true if any incoming edge exists, false otherwise.

template<typename Graph>
void removeInEdges (  typename boost::graph_traits< Graph >::vertex_descriptor  target_v,
Graph &  g
) 
 

Removes every edge e from g for which boost::target(e, g) == target_v.

Parameter Name Description Preconditions
target_v The vertex whose incoming edges are to be removed.
  • target_v must be a valid vertex descriptor in g.
g The graph containing target_v.

template<typename PredecessorMap, typename FrontInsertionSequence>
bool makePath (  typename boost::property_traits< PredecessorMap >::key_type  source,
typename boost::property_traits< PredecessorMap >::key_type  target,
const PredecessorMap  p_map,
FrontInsertionSequence &  path
)  [inline]
 

Attempts to extract a path from the input predecessor map, using the specified vertices as the path's endpoints, and store it in the specified container. Returns true if such a path exists, false otherwise.

Parameter Name Description Preconditions
source The start of the path.
  • source must be a valid key in p_map.
target The end of the path.
  • target must be a valid key in p_map.
p_map The input predecessor map.
  • PredecessorMap must model the Readable Property Map concept.
  • If vertex v has no predecessors, then boost::get(p_map, v) == v.
  • The key and value types are the same.
path The output container. FrontInsertionSequence must model the Front Insertion Sequence concept.

Returns:
true if source is a (distant) predecessor of target, false otherwise.

template<typename InputGraph, typename Vertex, typename Shuffler, typename OutputPredecessorMap, typename RandomPathEdgePredicate>
bool makeRandomPaths (  InputGraph &  input_graph_arg,
Vertex  source_vertex_arg,
Shuffler &  shuffler_arg,
OutputPredecessorMap  output_predecessor_map_arg,
RandomPathEdgePredicate  visitor_arg
) 
 

This algorithm creates random paths in the input graph, all from the specified source vertex, and places them in the output predecessor map. The implementation is based on an algorithm by James Gary Propp and David Bruce Wilson, located at http://dbwilson.com/ja/ja.ps.gz.ps on page 28. (See http://dbwilson.com/ja/ for output formats other than Postscript.)

The output predecessor map may form a forest instead of a tree; the implementation returns false in this case.

All programs using this function template must define BOOST_PARAMETER_MAX_ARITY as 5 or more.

Parameter Name Description Preconditions Default
input_graph_arg The input graph.
  • InputGraph must model the Bidirectional Graph concept.
  • boost::get(boost::vertex_index_t(), input_graph_arg) must return a valid vertex property map in input_graph_arg.
source_vertex_arg The root vertex of all the random paths.
  • Vertex must be the same as the vertex descriptor type of InputGraph.
  • source_vertex_arg must be a valid vertex descriptor in input_graph_arg.
shuffler_arg The random number generator used to help choose random predecessors for vertices.
output_predecessor_map_arg The output predecessor map.
  • The key and value types of OutputPredecessorMap must be the same as the vertex descriptor type of InputGraph.
visitor_arg A binary predicate functor that checks if an edge fulfills the caller-defined requirements for being part of a random path.
  • RandomPathEdgePredicate must model the Binary Predicate concept.
  • The member () operator must accept any edge descriptor in input_graph_arg as its first argument and a reference to input_graph_arg as its second argument.
DefaultRandomPathEdgePredicate()

Invariant:
Upon completion of the algorithm, the edges from boost::get(output_predecessor_map_arg, u) to u for all u in the input graph are in the random paths. If boost::get(output_predecessor_map_arg, u) == u, then u is either source_vertex_arg or a vertex that is not reachable from source_vertex_arg.

The example below shows how to output a number of random paths from the source vertex to a particular target vertex. 

     typedef boost::adjacency_list<>
             Graph;
     typedef boost::graph_traits<Graph>::vertex_descriptor
             Vertex;
     typedef std::map<Vertex,Vertex>
             VertexMap;
     typedef std::list<Vertex>
             Path;
     typedef boost::associative_property_map<VertexMap>
             PredecessorMap;
     typedef boost::random_number_generator<boost::mt19937,unsigned int>
             Shuffler;
     Graph g(24);  // Builds a graph with 24 vertices
     Vertex source_vertex = boost::vertex(0, g);
     Vertex target_vertex = boost::vertex(23, g);
     VertexMap v_map;
     PredecessorMap pred_map(v_map);
     std::list<Vertex> path;
     boost::mt19937 rng_engine;
     Shuffler shuffler(rng_engine);
     initGraph(g);  // Bunch of boost::add_edge() calls
     int num_runs = 5;  // Output five random paths
     while (num_runs > 0)
     {
         msmazes::makeRandomPaths(g, source_vertex, shuffler, pred_map);
         if (msmazes::makePath(source_vertex, target_vertex, pred_map, path))
         {
             // Process output path
             ...
             --num_runs;
         }
         path.clear();
     }

You can also pass the arguments by name. The following function call is equivalent to the one above: 

         msmazes::makeRandomPaths(
             msmazes::input_graph_arg = g
           , msmazes::source_vertex_arg = source_vertex
           , msmazes::shuffler_arg = shuffler
           , msmazes::output_predecessor_map_arg = pred_map
         );

Use the parameter table above to look up the parameter names.

template<typename Params>
void makeRandomPaths_with_named_params (  Params &  p  ) 
 

Outputs random paths from the graph to the predecessor map, both of which are named arguments in the specified Argument Pack object. See the makeRandomPaths() function documentation for acceptable parameters.

template<typename PathIterator, typename InputGraph, typename PredecessorMap, typename VertexIndexMap, typename VertexColorMap, typename VertexRankMap, typename Buffer, typename CrossEdgeRemovalIntruder>
void removeCrossEdges (  PathIterator  path_begin,
PathIterator  path_end,
InputGraph &  g,
PredecessorMap  predecessor_map,
VertexIndexMap  index_map,
VertexColorMap  color_map,
VertexRankMap  rank_map,
Buffer &  Q,
CrossEdgeRemovalIntruder &  intruder
) 
 

Removes cross-edges, with respect to the main path described by the range [path_begin_arg, path_end_arg) (not the predecessor map), from the graph, so that the main path is the only simple path (i.e. without cycles) between its end vertices.

All programs using this function template must define BOOST_PARAMETER_MAX_ARITY as 9 or more.

Parameter Name Description Preconditions Default
path_begin_arg The start of the main path.
  • PathIterator must model the Bidirectional Iterator concept.
  • The value type of PathIterator must be the same as the vertex descriptor type of InputGraph.
path_end_arg The past-the-end iterator indicating the end of the main path.
  • [path_begin_arg, path_end_arg) must be a valid range.
  • All elements in [path_begin_arg, path_end_arg) must be valid vertex descriptors in input_graph_arg.
input_graph_arg The input graph.
  • InputGraph must model the Vertex List Graph and Mutable Graph concepts.
  • The directed category type of InputGraph must be convertible to boost::directed_tag.
  • input_graph_arg must be strongly connected, i.e. boost::strong_components(input_graph_arg, component_map) == 1.
util_predecessor_map_arg A utility map used by the algorithm.
  • PredecessorMap must model the Read/Write Property Map concept.
  • The key and value types of PredecessorMap must be the same as the vertex descriptor type of InputGraph.
  • All elements in [path_begin_arg, path_end_arg) must be valid keys and values in util_predecessor_map_arg.
A boost::associative_property_map created from a std::map using the vertex descriptor type of InputGraph as both the key type and the value type.
util_index_map_arg A property map such that for each vertex v in input_graph_arg, boost::vertex( boost::get( util_index_map_arg, v), input_graph_arg) == v.
  • VertexIndexMap must model the Readable Property Map concept.
  • The key type of VertexIndexMap must be the same as the vertex descriptor type of InputGraph.
  • All elements in [path_begin_arg, path_end_arg) must be valid keys in util_index_map_arg.
boost::get(boost::vertex_index_t(), input_graph_arg)
util_color_map_arg A utility map used by the algorithm.
  • VertexColorMap must model the Read/Write Property Map concept.
  • VertexColorMap must be a valid parameter type for the boost::depth_first_visit function template.
  • The key type of VertexColorMap must be the same as the vertex descriptor type of InputGraph.
  • All elements in [path_begin_arg, path_end_arg) must be valid keys in util_color_map_arg.
A boost::iterator_property_map created from a std::vector, whose value type is the same as the value type of VertexColorMap and whose size is boost::num_vertices(input_graph_arg), and using util_index_map_arg for the index map.
util_rank_map_arg A utility map used by the algorithm. A boost::iterator_property_map created from a std::vector, whose value type is the same as the value type of VertexRankMap and whose size is boost::num_vertices(input_graph_arg), and using util_index_map_arg for the index map.
util_buffer_arg A buffer used during an underlying breadth-first traversal.
  • Buffer must model the Buffer concept.
  • The value type of Buffer must be the same as the vertex descriptor type of InputGraph.
A boost::queue whose value type is the same as vertex descriptor type of InputGraph.
intruder_arg An instance of a caller-defined class whose member functions are invoked at certain points in the algorithm.
  • CrossEdgeRemovalIntruder must implement the pathEdgeTemporarilyRemoved(), canRemoveCrossEdge(), and pathEdgeReinstated() member function templates.
  • The pathEdgeTemporarilyRemoved() member function template must accept any two valid vertex descriptors in input_graph_arg and a reference to input_graph_arg as actual arguments, in that order.
  • The canRemoveCrossEdge() and pathEdgeReinstated() member function templates must accept any valid edge descriptor in input_graph_arg and a reference to input_graph_arg as actual arguments, in that order.
  • The canRemoveCrossEdge() member function template must return a value of type bool.
DefaultCrossEdgeRemovalIntruder()

The example below illustrates the typical usage of this algorithm. 

     typedef boost::adjacency_list<>
             Graph;
     typedef boost::graph_traits<Graph>::vertex_descriptor
             Vertex;
     typedef std::map<Vertex,Vertex>
             VertexMap;
     typedef std::list<Vertex>
             Path;
     typedef boost::associative_property_map<VertexMap>
             PredecessorMap;
     typedef boost::random_number_generator<boost::mt19937,unsigned int>
             Shuffler;
     Graph g(24);  // Builds a graph with 24 vertices
     Vertex source_vertex = boost::vertex(0, g);
     Vertex target_vertex = boost::vertex(23, g);
     VertexMap v_map;
     PredecessorMap pred_map(v_map);
     std::list<Vertex> path;
     boost::mt19937 rng_engine;
     Shuffler shuffler(rng_engine);
     initGraph(g);  // Bunch of boost::add_edge() calls
     bool path_not_made = true;
     while (path_not_made)
     {
         path_not_made = false;
         msmazes::makeRandomPaths(g, source_vertex, shuffler, pred_map);
         if (msmazes::makePath(source_vertex, target_vertex, pred_map, path))
         {
             msmazes::removeCrossEdges(path.begin(), path.end(), g);
         }
         else
         {
             path_not_made = true;
             path.clear();
         }
     }

You can also pass the arguments by name. The following function call is equivalent to the one above: 

             msmazes::removeCrossEdges(
                 msmazes::path_begin_arg = path.begin()
               , msmazes::path_end_arg = path.end()
               , msmazes::input_graph_arg = g
             );

Use the parameter table above to look up the parameter names.

template<typename Params>
void removeCrossEdges_with_named_params (  Params &  p  ) 
 

Converts the digraph to a maze. The digraph is a named argument in the specified Argument Pack object. See the removeCrossEdges() function documentation for acceptable parameters.

Multi-State Mazes in C++ is hosted by SourceForge.net. Use the Table of Contents for navigation.