#ifndef GRAPH_COVERAGE_H_

#define GRAPH_COVERAGE_H_

#include "edge.h"

#include <list>

#include <utility>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/graph_utility.hpp>

///////////////////////////////////////////////////////////////////////////////////////////////////

class graph_coverage

{

{

/*--------------------------------------------------------------------------------------------*/

void edges_list_from_path(const std::list<size_t>& path, std::list<edge_id>* out)

{

if(path.empty())

return;

std::list<size_t>::const_iterator path_it = path.begin();

std::list<size_t>::const_iterator path_end = path.end();

size_t current_vertex = *path_it;

++path_it;

while(path_it != path_end)

{

size_t next_vertex = *path_it;

out->push_back( edge_id(current_vertex, next_vertex) );

current_vertex = next_vertex;

++path_it;

}

}

/*--------------------------------------------------------------------------------------------*/

}

/////////////////////////////////////////////////////////////////////////////////////////////////////

size_t graph_coverage::aditional_coverage_for_path(std::list<size_t> path) const

{

std::list<edge_id> edges_of_path;

utils::edges_list_from_path(path, &edges_of_path);

size_t coverage = 0;

BOOST_FOREACH(const edge_id& edge_of_path, edges_of_path)

{

coverage_map::const_iterator it = m_covered_edges.find(edge_of_path);

assert(it != m_covered_edges.end());

if(! it->second)

{// edge not covered yet

++coverage;

}

}

return coverage;

}

/*-------------------------------------------------------------------------------------------------*/

bool graph_coverage::fully_covered() const

{

bool result = true;

BOOST_FOREACH(const coverage_map::value_type& edge_coverage, m_covered_edges)

{// Cover all edges in graph

result = result && edge_coverage.second;

}

return result;

}

/*-------------------------------------------------------------------------------------------------*/

void graph_coverage::add_coverage_for_path(const std::list<size_t>& path)

{

std::list<edge_id> edges_of_path;

utils::edges_list_from_path(path, &edges_of_path);

BOOST_FOREACH(const edge_id& edge_of_path, edges_of_path)

{// Cover all edges from path

m_covered_edges[edge_of_path] = true;

}

}

/*-------------------------------------------------------------------------------------------------*/

main.cpp

{

template<typename T>

std::istream& operator >> (std::istream& in, std::pair<T, T>& p )

{

in >> p.first >> p.second;

return in;

}

}

typedef boost::adjacency_list

<

boost::listS,

boost::vecS,

boost::directedS

>

Graph;

/////////////////////////////////////////////////////////////////////////

template<typename T>

void read_values_in_set(std::istream& input, size_t values_count, std::set<T>* result)

{

typename std::istream_iterator<T> in_it(input);

typename std::istream_iterator<T> in_end;

for(size_t i = 0; i < values_count; ++i)

{

assert(in_it != in_end);

typename std::pair<std::set<T>::iterator, bool> insert_result = result->insert(*in_it);

assert(insert_result.second);

if(i < values_count - 1)

{

++in_it;

}

}

}

/*------------------------------------------------------------------------*/

void output_test(const std::list<size_t>& path_accumulator, std::ostream& output)

{

output << "{";

std::list<size_t>::const_iterator end = path_accumulator.end();

for(std::list<size_t>::const_iterator it = path_accumulator.begin(); it != end;)

{

const size_t val = *it;

++it;

output << val;

if(it != end)

{

output << " -> ";

}

}

output << "}" << std::endl;

}

/*------------------------------------------------------------------------*/

void save_to_collection(const std::list<size_t>& path, std::list<std::list<size_t> >& pathes_collection)

{

pathes_collection.push_back(path);

}

/*------------------------------------------------------------------------*/

template<

typename BoostAdjacencyList,

typename VertexDescriptor

>

void trace_graph(const BoostAdjacencyList& graph,

const VertexDescriptor& current_vertex,

const std::set<size_t>& final_vertices,

std::list<size_t>& path_accumulator,

std::vector<int>& visits_count_vector,

std::list<std::list<size_t> >& pathes_collection)

{

const size_t vertex_index = current_vertex;

if(final_vertices.find(vertex_index) != final_vertices.end())

{// Reached final vertex

path_accumulator.push_back(vertex_index);

save_to_collection(path_accumulator, pathes_collection);

path_accumulator.pop_back();

return;

}

if(out_degree(current_vertex, graph) == 0)

{// No out edges

return;

}

assert(visits_count_vector[vertex_index] <= 2);

if( visits_count_vector[vertex_index] == 2 )

{

return;

}

++visits_count_vector[vertex_index];

path_accumulator.push_back(vertex_index);

typename std::pair<BoostAdjacencyList::out_edge_iterator, BoostAdjacencyList::out_edge_iterator> out_edges_range = boost::out_edges(current_vertex, graph);

while(out_edges_range.first != out_edges_range.second)

{

VertexDescriptor next_vertex = boost::target(*out_edges_range.first, graph);

trace_graph(graph, next_vertex, final_vertices, path_accumulator, visits_count_vector, pathes_collection);

++out_edges_range.first;

}

path_accumulator.pop_back();

--visits_count_vector[vertex_index];

assert(visits_count_vector[vertex_index] >= 0);

}

/*------------------------------------------------------------------------*/

void read_case(Graph& states_graph, std::set<size_t>& final_states)

{

size_t vertices_count = 0;

std::cin >> vertices_count;

assert(vertices_count > 0);

size_t final_vertices_count = 0;

std::cin >> final_vertices_count;

assert(final_vertices_count > 0);

assert(vertices_count > final_vertices_count);

read_values_in_set(std::cin, final_vertices_count, &final_states);

std::istream_iterator<std::pair<size_t, size_t> > cin_edge_it(std::cin);

std::istream_iterator<std::pair<size_t, size_t> > cin_edge_end;

Graph graph(cin_edge_it, cin_edge_end, vertices_count);

std::swap(states_graph, graph);

} алгоритм тестування програмне забезпечення

/*------------------------------------------------------------------------*/

void generate_all_tests(const Graph& states_graph, const std::set<size_t>& final_states, std::list<std::list<size_t> >& tests_collection)

{

std::list<size_t> path_accumulator;

std::vector<int> visits_count_vector(boost::num_vertices(states_graph), 0);

trace_graph(states_graph, boost::vertex(0, states_graph), final_states, path_accumulator, visits_count_vector, tests_collection);

}

/*------------------------------------------------------------------------*/

void choose_best_tests(const size_t M, const double P, // <- algorithm parameters

const Graph& states_graph,

const size_t states_count,

std::list<std::list<size_t> >& tests_collection,

std::list<std::list<size_t> >& best_tests)

{

graph_coverage test_coverage(states_graph);

do

{

std::list<std::list<size_t> >::iterator tests_it = tests_collection.begin();

std::list<std::list<size_t> >::iterator tests_end = tests_collection.end();

const std::list<size_t>* best_test_ptr = &(tests_collection.front());

size_t best_test_length = best_test_ptr->size();

size_t best_test_coverage = test_coverage.aditional_coverage_for_path(*best_test_ptr);

BOOST_FOREACH(const std::list<size_t>& current_test, tests_collection)

{

const size_t current_test_coverage = test_coverage.aditional_coverage_for_path(current_test);

const size_t current_test_length = current_test.size();

if((current_test_length > M) && (best_test_length <= M))

{

continue;

}

if( ((current_test_length <= M) && (best_test_length <= M))

&& (best_test_coverage > current_test_coverage) )

{

continue;

}

if( (best_test_coverage >= current_test_coverage)

&& (best_test_length < current_test_length) )

{

continue;

}

if( (best_test_coverage > current_test_coverage)

&& (best_test_length <= current_test_length) )

{

continue;

}

if( double(best_test_length - current_test_length)*P

< double(best_test_coverage - current_test_coverage) )

{

continue;

}

best_test_ptr = &current_test;

best_test_length = current_test_length;

best_test_coverage = current_test_coverage;

}

best_tests.push_back(*best_test_ptr);

test_coverage.add_coverage_for_path(*best_test_ptr);

}

while(!test_coverage.fully_covered() && !tests_collection.empty());

}

/*------------------------------------------------------------------------*/

/////////////////////////////////////////////////////////////////////////

/*Формат воода:

<Количество вершин>

<Количество конечных вершин> <Конечная вершина> [<Конечная вершина> ... ]

<Входная вершина ребра 1> <Выходная вершина ребра 1>

<Входная вершина ребра 2> <Выходная вершина ребра 2>

...

<Входная вершина ребра n> <Выходная вершина ребра n>

*/

int main(const int argc, const char* argv[])

{

size_t M = 0;

double P = 0;

if(argc != 3)

{

std::cout << "Usage : " << argv[0] << " <desired test length M> <length-to-coverage coefficient P>" << std::endl;

return 0;

}

else

{

M = boost::lexical_cast<size_t>(argv[1]);

P = boost::lexical_cast<double>(argv[2]);

}

Graph states_graph;

std::set<size_t> final_states;

read_case(states_graph, final_states);

std::list<std::list<size_t> > tests_collection;

generate_all_tests(states_graph, final_states, tests_collection);

std::list<std::list<size_t> > best_tests;

choose_best_tests(M, P, states_graph, boost::num_vertices(states_graph), tests_collection, best_tests);

std::cout << "Best tests:" << std::endl;

BOOST_FOREACH( const std::list<size_t>& test, best_tests)

{

output_test(test, std::cout);

}

return 0;

}

/*------------------------------------------------------------------------*/

Размещено на Allbest.ru