66 lines
1.2 KiB
C++
66 lines
1.2 KiB
C++
|
|
||
|
|
#include <knotkit.h>
|
||
|
|
|
||
|
|
static bool
|
||
|
|
find_cycle_1 (map<unsigned, int> &cycle, const directed_multigraph &bg,
|
||
|
|
set<unsigned> edges,
|
||
|
|
unsigned f,
|
||
|
|
unsigned e, unsigned e_to)
|
||
|
|
{
|
||
|
|
for (set_const_iter<unsigned> i = edges; i; i ++)
|
||
|
|
{
|
||
|
|
if (i.val () == e)
|
||
|
|
continue;
|
||
|
|
|
||
|
|
if (bg.edge_from[i.val ()] == e_to)
|
||
|
|
{
|
||
|
|
if (i.val () == f)
|
||
|
|
return 1;
|
||
|
|
|
||
|
|
cycle.push (i.val (), 1);
|
||
|
|
if (find_cycle_1 (cycle, bg, edges, f,
|
||
|
|
i.val (), bg.edge_to[i.val ()]))
|
||
|
|
return 1;
|
||
|
|
|
||
|
|
cycle.yank (i.val ());
|
||
|
|
}
|
||
|
|
else if (bg.edge_to[i.val ()] == e_to)
|
||
|
|
{
|
||
|
|
if (i.val () == f)
|
||
|
|
return 1;
|
||
|
|
|
||
|
|
cycle.push (i.val (), -1);
|
||
|
|
if (find_cycle_1 (cycle, bg, edges, f,
|
||
|
|
i.val (), bg.edge_from[i.val ()]))
|
||
|
|
return 1;
|
||
|
|
|
||
|
|
cycle.yank (i.val ());
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
map<unsigned, int>
|
||
|
|
find_cycle (const directed_multigraph &bg,
|
||
|
|
set<unsigned> edges,
|
||
|
|
unsigned f, unsigned f_to)
|
||
|
|
{
|
||
|
|
map<unsigned, int> cycle;
|
||
|
|
|
||
|
|
if (bg.edge_to[f] == f_to)
|
||
|
|
cycle.push (f, 1);
|
||
|
|
else
|
||
|
|
{
|
||
|
|
assert (bg.edge_from[f] == f_to);
|
||
|
|
cycle.push (f, -1);
|
||
|
|
}
|
||
|
|
|
||
|
|
bool b = find_cycle_1 (cycle, bg, edges, f,
|
||
|
|
f, f_to);
|
||
|
|
assert (b);
|
||
|
|
|
||
|
|
return cycle;
|
||
|
|
}
|
||
|
|
|