-
Notifications
You must be signed in to change notification settings - Fork 4
/
BFSVisitorData.h
70 lines (60 loc) · 2.3 KB
/
BFSVisitorData.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//=======================================================================
// Copyright 2015 - 2020 Jeff Linahan
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#pragma once
#include "typedefs.h"
#include "BFSVert.h"
#include <vector>
struct BFSVisitorData
{
std::map<vertex_t, std::set<vertex_t>> children;
std::map<vertex_t, BFSVert> verts;
std::vector<edge_t> tree_edges;
uint num_levels;
Graph const* g;
vertex_t root;
BFSVisitorData(Graph const* g, vertex_t root);
explicit BFSVisitorData(BFSVisitorData const&) = default;
virtual ~BFSVisitorData() {};
void reset(Graph*);
bool is_tree_edge(edge_t) const;
uint edge_cost(edge_t, std::vector<vertex_t> const& cycle, Graph const&) const;
void print_costs () const;
void print_parents() const;
bool assert_data() const;
void examine_edge(edge_t e);
void examine_edge(edge_t e, GraphCR g) {};
bool in_cc(edge_t e) const;
std::vector<vertex_t> get_cycle(vertex_t v, vertex_t w, vertex_t ancestor) const;
edge_t arbitrary_nontree_edge(Graph const&) const;
bool assert_verts(GraphCR g) const;
std::vector<vertex_t> ancestors(vertex_t) const;
std::vector<vertex_t> get_cycle(vertex_t, vertex_t) const;
std::vector<vertex_t> get_cycle(edge_t e) const;
virtual void initialize_vertex (vertex_t v, GraphCR g) {};
virtual void discover_vertex (vertex_t v, GraphCR g) {};
virtual void examine_vertex (vertex_t v, GraphCR g) {};
virtual void finish_vertex (vertex_t v, GraphCR g) {};
virtual void black_target (edge_t, GraphCR g) {};
virtual void gray_target (edge_t, GraphCR g) {};
virtual void tree_target (edge_t, GraphCR g) {};
virtual void tree_edge (edge_t, GraphCR g) {};
virtual void non_tree_edge (edge_t, GraphCR g) {};
};
struct EdgeNotInVisitorData : std::exception
{
edge_t e;
Graph const* g;
EdgeNotInVisitorData(edge_t e, Graph const* g) : e(e), g(g) {}
};
bool on_cycle(vertex_t, std::vector<vertex_t> const& cycle, Graph const&);
bool on_cycle(edge_t, std::vector<vertex_t> const& cycle, Graph const&);
struct NoNontreeEdgeException
{
NoNontreeEdgeException(uint num_edges) : num_edges(num_edges) {}
uint num_edges;
};