#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/range/combine.hpp>
#include <boost/foreach.hpp>

#include <vector>
#include <algorithm>
#include <cmath>
#include <list>
#include <valarray>

#include <network.hpp>

struct EdgeProperties {
  unsigned index;
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeProperties> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::vertices_size_type VertexIndex;


template<class T>
bool is_shorter(const std::list<T> &, const std::list<T> &);

bool trivial(boost::detail::edge_desc_impl<boost::undirected_tag,unsigned long>);

std::list<std::pair<std::array<unsigned, 2>, std::list<unsigned>>> find_minimal_crack(const Graph &, const network &);