Multitarget-tracker/Tracker/graph/GTL/src/min_tree.cpp at master · KennisL/Multitarget-tracker · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   min_tree.cpp
//
//==========================================================================
// $Id: min_tree.cpp,v 1.4 2001/11/07 13:58:10 pick Exp $

#include <GTL/graph.h>
#include <stack>
#include <queue>
#include <GTL/min_tree.h>

__GTL_BEGIN_NAMESPACE

min_tree::min_tree () {
    is_set_distances = false;
    weight = 0;
}

int min_tree::check (graph& g) {
    if (g.is_directed()) return GTL_ERROR;
    else if (g.number_of_nodes() < 2) return GTL_ERROR;
    else if (!g.is_connected()) return GTL_ERROR;
    else if (!is_set_distances) return GTL_ERROR;
    else return GTL_OK;
}

void min_tree::set_distances (const edge_map<int>& dist) {
    this->dist = dist;
    is_set_distances = true;
}

std::set<edge> min_tree::get_min_tree() {
    return this->tree;
}

int min_tree::get_min_tree_length() {
    int sum;
	std::set<edge>::iterator tree_it;

    sum = 0;

    for (tree_it = tree.begin(); tree_it != tree.end(); tree_it++)
	sum += dist[*tree_it];

    return sum;
}

int min_tree::run (graph& g) {
	std::priority_queue <TSP_A_VALUE, std::vector<TSP_A_VALUE>, input_comp> node_distances;
    node::adj_edges_iterator adj_it, adj_end;
	std::set<node> tree_nodes;
	std::set<node>::iterator tree_it;
    edge curr;
    node new_node;
    graph::edge_iterator edge_it, edges_end;
    unsigned int number_of_nodes;
    int min_dist;


    // making out the start edge

    edge_it = g.edges_begin();
    edges_end = g.edges_end();

    curr = *edge_it;
    min_dist = dist[*edge_it];

    for (; edge_it != edges_end; edge_it++) {
	if (dist[*edge_it] < min_dist) {
	    curr = *edge_it;
	    min_dist = dist[*edge_it];
	}
    }

    tree.insert(curr);

    tree_nodes.insert(curr.source());
    tree_nodes.insert(curr.target());


    for (tree_it = tree_nodes.begin(); tree_it != tree_nodes.end(); tree_it++) {
	adj_it = tree_it->adj_edges_begin();
	adj_end = tree_it->adj_edges_end();

	for (; adj_it != adj_end; adj_it++) {
	    node_distances.push(TSP_A_VALUE(dist[*adj_it], adj_it));
	}
    }

    // create the min_tree

    number_of_nodes = g.number_of_nodes();

    while(tree.size() < number_of_nodes - 1) {
	curr = *((node_distances.top()).second);

	node_distances.pop();

	if (tree_nodes.find(curr.source()) != tree_nodes.end() &&
	    tree_nodes.find(curr.target()) != tree_nodes.end()) {
	} else {
	    tree.insert(curr);
	    weight += dist[curr];

	    if (tree_nodes.find(curr.source()) != tree_nodes.end()) {
		new_node = curr.target();
	    } else {
		new_node = curr.source();
	    }

	    tree_nodes.insert(new_node);

	    adj_it = new_node.adj_edges_begin();
	    adj_end = new_node.adj_edges_end();

	    for (; adj_it != adj_end; adj_it++) {
		node_distances.push(TSP_A_VALUE(dist[*adj_it], adj_it));
	    }
	}
    }

    return GTL_OK;
}

void min_tree::reset() {
    tree.erase (tree.begin(), tree.end());
    weight = 0;
}

__GTL_END_NAMESPACE