go to start Sol W13
|home |print view |recent changes |changed December 20, 2016 |
exact
|You are 54.81.139.56 <- set your identity!

Sections: Introductory Questions | Array dimension deduction | Managing Objects on the Heap | Shared Pointer to '''this''' | Reverse Echo | Example solution for topological sort. | Approach 1 – Three sets | Approach 2 – Topological sort |

Introductory Questions ^

Array dimension deduction ^

Which C++ mechanism can you use to deduce a dimension of an array passed as function parameter?

Managing Objects on the Heap ^

How do you create an instance of the default-constructible type Block on the heap?

std::make_unique<Block>();
std::make_shared<Block>();

How do you delete the instance created on the heap?

What problem arises if you have loops in your object structure and how do you solve this?

Shared Pointer to this ^

How can you access to a shared pointer from within the this object?

Reverse Echo ^

int main(int argc, char *argv[]){
	std::reverse_copy(argv+1, argv+argc, std::ostream_iterator<std::string>{std::cout,"\n"});
}

Example solution for topological sort. ^

We have two distinct approaches below to solve the given problem. Both solutions use the same module class and infrastructure for reading the data from an std::istream.

The module class satisfies the requirements for both approaches, thus it is a bit more complex than necessary for only one solution. Every module has a name (of type std::string), a set of successors and a set of predecessors. Successors in this context refer to modules the this-object is a dependency for, e.g. if the OO module is a requirement for the DB1 module, the DB1 module is in the successors of OO. Predecessors is the opposite direction, as it contains all modules that must have been attended as a prerequisite, e.g. if the OO module is a requirement for the DB1 module, the OO module is a predecessor of DB1. There is a further member variable earliest_semester, which contains the earliest semester the module can be taken with regard to all dependencies. This member variable will be used and updated in one of the approaches.

Important: As using std::shared_ptr for predecessors and successors alike might cause memory leaks as cyclic dependent modules would never be deleted, we use std::weak_ptr for the predecessors.

The module class is derived from std::enable_shared_from_this as we need to be able to create an std::shared_ptr for the this object in the add_predecessor() member function. Otherwise, we could not add a std::shared_ptr pointing to the this-object to the successors of the predecessor.

The function read_modules creates a module_catalog, which is a map with module names as keys and module pointers (std::shared_ptr) as values, from an input stream.

The function template values is just a convenience function to get all values stored in a map.

//module.h
#ifndef MODULE_H_
#define MODULE_H_

#include <algorithm>
#include <iosfwd>
#include <iterator>
#include <map>
#include <memory>
#include <string>
#include <vector>

struct module;

using module_ptr = std::shared_ptr<module>;
using modules = std::vector<module_ptr>;
using module_catalog = std::map<std::string, module_ptr>;

struct module : std::enable_shared_from_this<module> {
	explicit module(std::string const & name) : name {name}{};

	void add_predecessor(module_ptr predecessor) {
		std::weak_ptr<module> wp{predecessor};
		_predecessors.push_back(wp);
		predecessor->_successors.push_back(shared_from_this());
	}

	bool has_predecessor() const {
		return !_predecessors.empty();
	}

	void update_earliest_semester(unsigned newEarliestSemester) {
		earliest_semester = std::max(newEarliestSemester, earliest_semester);
	}

	unsigned get_earliest_semester() const {
		return earliest_semester;
	}

	modules successors() const {
		return _successors;
	}

	modules predecessors() {
		remove_expired_predecessors();
		modules predecessors_shared{_predecessors.size()};
		std::transform(std::begin(_predecessors), std::end(_predecessors), std::begin(predecessors_shared), [](module_weak_ptr m) {
			return m.lock();
		});
		return predecessors_shared;
	}

	std::string const name;
private:
	using module_weak_ptr = std::weak_ptr<module>;
	using module_back_references = std::vector<module_weak_ptr>;

	void remove_expired_predecessors() {
		auto removed_begin = std::remove_if(std::begin(_predecessors), std::end(_predecessors), [](module_weak_ptr m) {
			return m.expired();
		});
		_predecessors.erase(removed_begin, std::end(_predecessors));
	}

	unsigned earliest_semester{0};
	module_back_references _predecessors{};
	modules _successors{};

};


inline std::ostream & operator<<(std::ostream& out, module_ptr m) {
	out << m->name;
	return out;
}

module_catalog read_modules(std::istream & input);

template<typename M>
inline std::vector<typename M::mapped_type> values(M const& catalog) {
	std::vector<typename M::mapped_type> values{catalog.size()};
	std::transform(std::begin(catalog), std::end(catalog), std::begin(values),[](typename M::value_type const & pair){
		return pair.second;
	});
	return values;
}



#endif /* MODULE_H_ */

The implementation of the function read_modules reads the input line by line and adds a the module with all dependencies to the module catalog (add() function). The function get_module_ptr is a helper function that returns the std::shared_ptr for a module name and inserts new entries into the module catalog if necessary.

//module.cpp
#include "module.h"

#include <sstream>
#include <iterator>

namespace {

module_ptr get_module_ptr(std::string const & module_name, module_catalog & catalog) {
	if (catalog.count(module_name) == 0) {
		auto m = std::make_shared<module>(module_name);
		catalog[module_name] = m;
	}
	return catalog[module_name];
}

void add(module_catalog& catalog, std::string const & line) {
	std::stringstream line_stream{line};
	std::string module_name;
	line_stream >> module_name;
	auto module = get_module_ptr(module_name, catalog);
	std::for_each(std::istream_iterator<std::string>{line_stream}, std::istream_iterator<std::string>{}, [&](std::string const & module_name){
		auto dependency = get_module_ptr(module_name, catalog);
		module->add_predecessor(dependency);
	});
}

}

module_catalog read_modules(std::istream & input) {
	module_catalog catalog{};
	std::string line;
	while (getline(input, line)) {
		add(catalog, line);
	}
	return catalog;
}

Approach 1 – Three sets ^

The first approach is straight forward and works with three sets of modules that get iteratively updated:

The algorithm initializes the remaining_modules at the beginning with all modules from the module catalog. Then it copies all modules which have all prerequisites satisfied (depending on finished_modules) from the remaining_modules to the current_modules. These are all modules that can be taken in the current semester. They are printed on the output stream. Then all modules in current_modules are copied to finished_modules and removed from remaining_modules. These steps are repeated until there are no more remaining modules. (Beware of cycles – not considered here)

The function can_be_taken checks for a module whether it can be taken in the current semester given a set of already finished modules.

//semester.h
#ifndef SEMESTER_H_
#define SEMESTER_H_

#include <iosfwd>

void print_semester(std::istream& in, std::ostream& out);

#endif /* SEMESTER_H_ */

//semester.cpp
#include "semester.h"
#include "module.h"
#include <map>
#include <vector>
#include <memory>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <string>
#include <ostream>
#include <istream>

namespace {

template<typename ModItr>
bool can_be_taken(module_ptr module, ModItr accomplished_begin, ModItr accomplished_end) {
	auto predecessors = module->predecessors();
	return std::all_of(std::begin(predecessors), std::end(predecessors), [&](module_ptr m) {
		return std::find(accomplished_begin, accomplished_end, m) != accomplished_end;
	});
}

void print_plan(module_catalog const & catalog, std::ostream & out) {
	auto semester = 1u;
	modules finished_modules{};
	auto all_modules = values(catalog);
	modules remaining_modules{std::begin(all_modules), end(all_modules)};

	while (!remaining_modules.empty()) {
		out << semester << ": ";
		modules current_modules{};
		std::copy_if(std::begin(remaining_modules), std::end(remaining_modules), std::inserter(current_modules, std::begin(current_modules)), [&](module_ptr m){
			return can_be_taken(m, begin(finished_modules), end(finished_modules));
		});
		std::copy(std::begin(current_modules), std::end(current_modules), std::ostream_iterator<module_ptr>{out, " "});
		std::copy(std::begin(current_modules), std::end(current_modules), std::inserter(finished_modules, std::begin(finished_modules)));

		std::for_each(std::begin(current_modules), std::end(current_modules), [&](module_ptr m){
			remaining_modules.erase(std::remove(std::begin(remaining_modules), std::end(remaining_modules), m), std::end(remaining_modules));
		});

		semester++;
		out << "\n";
	}
}
}

void print_semester(std::istream& in, std::ostream& out) {
	auto catalog = read_modules(in);
	print_plan(catalog, out);
}

Approach 2 – Topological sort ^

The second approach is a bit smarter and exploits the topological order given by the direct acyclic module graph (hopefully, it is acyclic).

The reverse topological sort can be computed by a depth first post-order search, starting at the modules of the first semester. The function topological_order computes this list of modules. It starts from a given set of modules (those of the first semester) and walks recursively (function depth_first_search) through the module graph (successors of the module). Since our data structure is not a tree it is mandatory to keep the information whether a module (node) has already been visited in the depth first search. We keep track of that with the marked_modules map.

After we have the reverse topological sort we can just use this sequence once to update the earliest semester of all modules. The topological order guarantees that at the point we update the successors of a module the this-object has its final earliest semester value. All successors of the this-object are updated accordingly, which is the earliest semester for a successor is at least the earliest semester of the this-object + 1.

Eventually, just all modules that have the current earliest semester have to be copied to the output stream.

//semester_topological.h
#ifndef SEMESTER_TOPOLOGICAL_H_
#define SEMESTER_TOPOLOGICAL_H_

#include <iosfwd>

void print_semester_topological(std::istream& in, std::ostream& out);

#endif /* SEMESTER_TOPOLOGICAL_H_ */

//semester_topological.cpp
#include "semester_topological.h"
#include "module.h"

#include <algorithm>
#include <iterator>
#include <memory>
#include <sstream>
#include <unordered_map>
#include <utility>
#include <vector>


namespace {

void depth_first_search(module_ptr m, modules & topological_order, std::unordered_map<module_ptr, bool> & marked_modules) {
	marked_modules[m] = true;
	auto successors = m->successors();
	std::for_each(std::begin(successors), std::end(successors), [&](module_ptr s){
		if (!marked_modules[s]) {
			depth_first_search(s, topological_order, marked_modules);
		}
	});
	topological_order.push_back(m);
}

modules topological_order(modules const & initial_set, modules const & all_modules) {
	std::unordered_map<module_ptr, bool> marked_modules{all_modules.size()};
	std::for_each(std::begin(all_modules), std::end(all_modules), [&](module_ptr m){
		marked_modules[m] = false;
	});
	modules topological_order{};
	std::for_each(std::begin(initial_set), std::end(initial_set), [&](module_ptr m){
		if (!marked_modules[m]) {
			depth_first_search(m, topological_order, marked_modules);
		}
	});
	return topological_order;
}

void update_successors(module_ptr module) {
	auto successors = module->successors();
	std::for_each(std::begin(successors), std::end(successors), [&](module_ptr s){
		s->update_earliest_semester(module->get_earliest_semester() + 1);
	});
}

modules find_first_semester_modules(modules all_modules) {
	modules first_semester_modules{};
	std::for_each(std::begin(all_modules), std::end(all_modules), [&](module_ptr m){
		if(!m->has_predecessor()) {
			m->update_earliest_semester(1);
			first_semester_modules.push_back(m);
		}
	});
	return first_semester_modules;
}

void update_earliest_semester(module_catalog const & catalog) {
	auto all_modules = values(catalog);
	auto first_semester_modules = find_first_semester_modules(all_modules);
	auto complete_topological_order = topological_order(first_semester_modules, all_modules);
	std::for_each(std::rbegin(complete_topological_order), std::rend(complete_topological_order), [](module_ptr m) {
		update_successors(m);
	});
}

struct semester_comparator
{
    bool operator() ( module_ptr m, unsigned semester ) const
    {
        return m->get_earliest_semester() < semester;
    }

    bool operator() ( unsigned semester, module_ptr m ) const
    {
        return semester < m->get_earliest_semester();
    }
};

}


void print_semester_topological(std::istream& in, std::ostream& out) {
	auto catalog = read_modules(in);
	update_earliest_semester(catalog);
	auto modules = values(catalog);
	std::sort(std::begin(modules), std::end(modules), [](module_ptr lhs, module_ptr rhs) {
		return lhs->get_earliest_semester() < rhs->get_earliest_semester();
	});

	auto last_semester = (*std::rbegin(modules))->get_earliest_semester();
	for (auto semester = 1u; semester <= last_semester; semester++) {
		auto range = std::equal_range(std::begin(modules), std::end(modules), semester, semester_comparator{});
		out << semester << ": ";
		std::copy(range.first, range.second, std::ostream_iterator<module_ptr>{out, " "});
		out << "\n";
	}
}

Disclaimer: This is not neccessarily the best solution. If performance mattered there were more efficient ways for this calculation. But after all the idea behind this exerices was to practice std::shared_ptr and standard algorithms.


|home |print view |recent changes |changed December 20, 2016 |
exact
|You are 54.81.139.56 <- set your identity!

Sol W13
go to start