alglib::graph Namespace Reference

Namespaces
	models

Classes
class	directed_graph
class	directed_graph< vertex_t, void, model >
class	edge_property
struct	edge_t
struct	edge_t< vertex_t, void >
class	undirected_graph
class	undirected_graph< vertex_t, void, model >
class	vertex_property

Functions
template<typename GraphType >
vertex_property< GraphType, typename GraphType::edge_type::attr_t >	bellman_ford (const GraphType &G, const typename GraphType::vertex_type source)
template<typename GraphType , typename OutputIter >
OutputIter	_single_bfs (const GraphType &G, const typename GraphType::vertex_type &start, vertex_property< GraphType, bool > &visited, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	single_bfs (const GraphType &G, const typename GraphType::vertex_type &start, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	bfs (const GraphType &G, const typename GraphType::vertex_type &start, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	bfs (const GraphType &G, OutputIter dest)
template<typename GraphType >
vertex_property< GraphType, int >	connected_components (const GraphType &G)
template<typename GraphType , typename OutputIter >
OutputIter	_single_preorder_dfs (const GraphType &G, const typename GraphType::vertex_type &start, vertex_property< GraphType, bool > &visited, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	single_preorder_dfs (const GraphType &G, const typename GraphType::vertex_type &start, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	_single_postorder_dfs (const GraphType &G, const typename GraphType::vertex_type &start, vertex_property< GraphType, bool > &visited, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	single_postorder_dfs (const GraphType &G, const typename GraphType::vertex_type &start, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	preorder_dfs (const GraphType &G, const typename GraphType::vertex_type start, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	preorder_dfs (const GraphType &G, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	postorder_dfs (const GraphType &G, const typename GraphType::vertex_type start, OutputIter dest)
template<typename GraphType , typename OutputIter >
OutputIter	postorder_dfs (const GraphType &G, OutputIter dest)
template<typename vertex_t , typename attr_t >
std::ostream &	operator<< (std::ostream &out, const edge_t< vertex_t, attr_t > &e)
template<typename vertex_t , typename attr_t >
edge_t< vertex_t, attr_t >	make_edge (vertex_t from, vertex_t to, attr_t attribute)
template<typename GraphType , typename OutputIter >
OutputIter	topological_order (const GraphType &G, OutputIter dest)

Function Documentation

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::_single_bfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		vertex_property< GraphType, bool > &	visited,
		OutputIter	dest
	)

                                        {    
    
    typedef typename GraphType::vertex_type vertex_type;

    /* Maintains a list of unexplored vertices in order of their distance
     * from the start vertex */
    std::queue<vertex_type> frontier;

    /* Put `start` in the queue to start the bfs from */
    frontier.push(start);
    
    while(!frontier.empty()) {
        vertex_type inspect = frontier.front();
        frontier.pop();
        visited[inspect] = true;

        /* Put it into the output stream before inspection */
        *dest++ = inspect;

        for(auto it = G.avbegin(inspect); it != G.avend(inspect); it++)
            if(!visited(*it))
                frontier.push(*it);
    }
    return dest;
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::_single_postorder_dfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		vertex_property< GraphType, bool > &	visited,
		OutputIter	dest
	)

                                                  {
    visited[start] = true;
    for(auto it = G.avbegin(start); it != G.avend(start); it++)
        if(!visited(*it))
            dest = _single_postorder_dfs(G, *it, visited, dest);
    *dest++ = start;  // Put it on the output stream
    return dest;
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::_single_preorder_dfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		vertex_property< GraphType, bool > &	visited,
		OutputIter	dest
	)

                                                 {
    *dest++ = start;  // Put it on the output stream
    visited[start] = true;

    /* Explore adjacent vertices */
    for(auto it = G.avbegin(start); it != G.avend(start); it++)
        if(!visited(*it))
            dest = _single_preorder_dfs(G, *it, visited, dest);

    return dest;
}

template<typename GraphType >

vertex_property<GraphType, typename GraphType::edge_type::attr_t> alglib::graph::bellman_ford	(	const GraphType &	G,
		const typename GraphType::vertex_type source
	)

                                                         {

}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::bfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		OutputIter	dest
	)

                                {
    
    /* visited property initialized with false for each vertex */
    vertex_property<GraphType, bool> visited(G, false);

    /* do the bfs of the start vertex first */
    dest = _single_bfs(G, start, visited, dest);

    /* then others if they are not visited */
    for(auto it = G.vbegin(); it != G.vend(); it++)
        if(!visited(*it))
            dest = _single_bfs(G, *it, visited, dest);

    return dest;
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::bfs	(	const GraphType &	G,
		OutputIter	dest
	)

                                                    {
    return bfs(G, *G.vbegin(), dest);
}

template<typename GraphType >

vertex_property<GraphType, int> alglib::graph::connected_components

(

const GraphType &

G

)

                                                                         {
    /* initialize each property with -1, indicating its component has not been ascertained */
    vertex_property<GraphType, int> component_id(G, -1);

    /* start labelling component id with 1 */
    int next_component_id = 1;

    for(auto it = G.vbegin(); it != G.vend(); it++) {
        /* for every vertex which is not assigned a component id */
        if(component_id(*it) == -1) {
            std::vector<typename GraphType::vertex_type> component;
            single_preorder_dfs(G, *it, back_inserter(component));

            /* set the component_id of each of the vertices in component */
            for(auto vertex : component)
                if(component_id(vertex) == -1)
                    component_id[vertex] = next_component_id;

            next_component_id++;
        }
    }
    return component_id;
};

template<typename vertex_t , typename attr_t >

edge_t<vertex_t, attr_t> alglib::graph::make_edge	(	vertex_t	from,
		vertex_t	to,
		attr_t	attribute
	)

                                                     {
    return edge_t<vertex_t, attr_t>(from, to, attribute);
}

template<typename vertex_t , typename attr_t >

std::ostream& alglib::graph::operator<<	(	std::ostream &	out,
		const edge_t< vertex_t, attr_t > &	e
	)

                                                                           {

    out << "(from: " << e.from << ", to: " << e.to
        << ", attr: " << e.attribute << ")";
    return out;
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::postorder_dfs	(	const GraphType &	G,
		const typename GraphType::vertex_type start	,
		OutputIter	dest
	)

                                          {

    /* visited property on G, each initialized with false */
    vertex_property<GraphType, bool> visited(G, false);

    /* do a dfs on the start vertex first */
    dest = _single_postorder_dfs(G, start, visited, dest);

    /* check all the vertices and perform dfs on the unvisited ones */
    for(auto it = G.vbegin(); it != G.vend(); it++)
        if(!visited(*it))
            dest = _single_postorder_dfs(G, *it, visited, dest);

    return dest;
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::postorder_dfs	(	const GraphType &	G,
		OutputIter	dest
	)

                                                              {
    return postorder_dfs(G, *G.vbegin(), dest);
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::preorder_dfs	(	const GraphType &	G,
		const typename GraphType::vertex_type start	,
		OutputIter	dest
	)

                                         {

    /* visited property, initialized with false for each vertex */
    vertex_property<GraphType, bool> visited(G, false);

    /* do a dfs on the start vertex first */
    dest = _single_preorder_dfs(G, start, visited, dest);

    /* check all the vertices and perform dfs on the unvisited ones */
    for(auto it = G.vbegin(); it != G.vend(); it++)
        if(!visited(*it))
            dest = _single_preorder_dfs(G, *it, visited, dest);

    return dest;
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::preorder_dfs	(	const GraphType &	G,
		OutputIter	dest
	)

                                                             {
    return preorder_dfs(G, *G.vbegin(), dest);
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::single_bfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		OutputIter	dest
	)

                                       {    
    return _single_bfs(G, start, vertex_property<GraphType, bool>(G, false), dest);
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::single_postorder_dfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		OutputIter	dest
	)

                                                {
    vertex_property<GraphType, bool> visited(G, false);
    return _single_postorder_dfs(G, start, visited, dest);
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::single_preorder_dfs	(	const GraphType &	G,
		const typename GraphType::vertex_type & start	,
		OutputIter	dest
	)

                                                {
    vertex_property<GraphType, bool> visited(G, false);
    return _single_preorder_dfs(G, start, visited, dest);
}

template<typename GraphType , typename OutputIter >

OutputIter alglib::graph::topological_order	(	const GraphType &	G,
		OutputIter	dest
	)

                                                                  {
    return postorder_dfs(G, dest);
}