← Back to branch summary

~ubuntu-branches/debian/wheezy/abyss/wheezy

« back to all changes in this revision

Viewing changes to Graph/PopBubbles.h

  • Committer: Package Import Robot
  • Author(s): Shaun Jackman
  • Date: 2012-05-31 11:39:13 UTC
  • mfrom: (1.1.5)
  • Revision ID: package-import@ubuntu.com-20120531113913-39atrfritvjevhv6
Tags: 1.3.4-1
* New upstream release.
* debian/copyright: Add CityHash, which has an Expat license.
* debian/control: Bump Standards-Version to 3.9.3.1.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Graph/PopBubbles.h
32
32
void topologicalSort(const Graph& g, It it)
33
33
{
34
34
        using boost::default_color_type;
 
35
        using boost::property_map;
35
36
        using boost::vector_property_map;
36
 
        typedef vector_property_map<
37
 
                default_color_type, ContigNodeIndexMap> ColorMap;
 
37
        typedef typename property_map<Graph, vertex_index_t>::type
 
38
                VertexIndexMap;
 
39
        typedef vector_property_map<default_color_type, VertexIndexMap>
 
40
                ColorMap;
38
41
        depthFirstSearch(g, TopoVisitor<It>(it),
39
42
                        ColorMap(num_vertices(g)));
40
43
}
44
47
bool isBubble(const Graph& g, It first, It last)
45
48
{
46
49
        typedef typename graph_traits<Graph>::adjacency_iterator Ait;
 
50
        typedef typename graph_traits<Graph>::in_edge_iterator Iit;
47
51
        typedef typename graph_traits<Graph>::vertex_descriptor V;
48
52
        assert(last - first > 1);
49
53
        if (last - first == 2)
50
54
                return false; // unambiguous edge
51
 
        if (*first == ~last[-1])
 
55
        if (*first == get(vertex_complement, g, last[-1]))
52
56
                return false; // palindrome
53
57
        std::set<V> targets(first, first + 1);
54
58
        for (It it = first; it != last - 1; ++it) {
57
61
        }
58
62
        std::set<V> sources(last - 1, last);
59
63
        for (It it = first + 1; it != last; ++it) {
60
 
                std::pair<Ait, Ait> adj = adjacent_vertices(~*it, g);
61
 
                transform(adj.first, adj.second,
62
 
                                inserter(sources, sources.end()),
63
 
                                std::mem_fun_ref(&V::operator~));
 
64
                std::pair<Iit, Iit> adj = in_edges(*it, g);
 
65
                for (Iit eit = adj.first; eit != adj.second; ++eit)
 
66
                        sources.insert(source(*eit, g));
64
67
        }
65
68
        std::set<V> bubble(first, last);
66
69
        return sources == bubble && targets == bubble;
85
88
                if (sum < 2)
86
89
                        continue;
87
90
                if (opt::verbose > 3)
88
 
                        std::cerr << "* " << *first << '\n';
 
91
                        std::cerr << "* " << get(vertex_name, g, *first) << '\n';
89
92
                for (It it = first + 1; it != topo.end(); ++it) {
90
93
                        unsigned indeg = in_degree(*it, g);
91
94
                        unsigned outdeg = out_degree(*it, g);
92
95
                        sum -= indeg;
93
96
 
94
97
                        if (opt::verbose > 3)
95
 
                                std::cerr << *it << '\t' << indeg << '\t' << outdeg
 
98
                                std::cerr << get(vertex_name, g, *it)
 
99
                                        << '\t' << indeg << '\t' << outdeg
96
100
                                        << '\t' << sum
97
101
                                        << '\t' << sum + (int)outdeg << '\n';
98
102