Multitarget-tracker/src/Tracker/graph/GTL/src/topsort.cpp at master · gitleej/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
/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   topsort.cpp
//
//==========================================================================
// $Id: topsort.cpp,v 1.7 2001/11/07 13:58:12 pick Exp $

#include <GTL/topsort.h>

__GTL_BEGIN_NAMESPACE

//--------------------------------------------------------------------------
//   algorithm - interface
//--------------------------------------------------------------------------


void topsort::reset ()
{
    dfs::reset();
    acyclic = true;
    top_order.erase (top_order.begin(), top_order.end());;
}

int topsort::check (GTL::graph& G)
{
    return G.is_directed() ? GTL_OK : GTL_ERROR;
}


//--------------------------------------------------------------------------
//   Handler
//--------------------------------------------------------------------------


void topsort::init_handler (GTL::graph& G)
{
    top_numbers.init (G, 0);
    act_top_num = G.number_of_nodes();
}


void topsort::leave_handler (GTL::graph& /*G*/, GTL::node& n, GTL::node& /*f*/)
{
    top_numbers[n] = act_top_num;
    act_top_num--;
    top_order.push_front (n);
}


void topsort::old_adj_node_handler (GTL::graph& /*G*/, GTL::edge& /*adj*/, GTL::node& opp)
{
    if (top_numbers[opp] == 0) {
	acyclic = false;
    }
}

__GTL_END_NAMESPACE

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------