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
|
/* Copyright (c) 1997-2020
Ewgenij Gawrilow, Michael Joswig, and the polymake team
Technische Universität Berlin, Germany
https://polymake.org
This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version: http://www.gnu.org/licenses/gpl.txt.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
--------------------------------------------------------------------------------
*/
#ifndef POLYMAKE_GROUP_ORBITS_H
#define POLYMAKE_GROUP_ORBITS_H
#include <polymake/Array.h>
#include <polymake/Set.h>
#include <polymake/hash_set>
#include <polymake/Matrix.h>
#include <polymake/group/action.h>
#include <queue>
namespace polymake {
namespace group {
/*
* Computes the orbit of element, where the group is spanned by generators
*/
template<typename action_t, typename Perm, typename Element, typename Container=hash_set<Element>>
auto
orbit_impl(const Array<Perm>& generators,
const Element& element)
{
std::vector<action_t> g_actions; g_actions.reserve(generators.size());
for (const auto& g: generators)
g_actions.push_back(action_t(g));
Container orbit;
orbit.insert(element);
std::queue<Element> q;
q.push(element);
while (!q.empty()) {
const Element orbitElement = q.front();
q.pop();
for (const auto& a: g_actions) {
const Element next = a(orbitElement);
if (!orbit.collect(next)) {
q.push(next);
}
}
}
return orbit;
}
template<typename action_type, typename Perm, typename Element, typename Container=hash_set<Element>,
typename op_tag=typename pm::object_traits<Element>::generic_tag,
typename perm_tag=typename pm::object_traits<Perm>::generic_tag,
typename stores_ref=std::true_type>
auto
unordered_orbit(const Array<Perm>& generators,
const Element& element)
{
typedef pm::operations::group::action<Element&, action_type, Perm, op_tag, perm_tag, stores_ref> action_t;
return orbit_impl<action_t, Perm, Element, Container>(generators, element);
}
template<typename action_type, typename Perm, typename Element, typename Container=hash_set<Element>,
typename op_tag=typename pm::object_traits<Element>::generic_tag,
typename perm_tag=typename pm::object_traits<Perm>::generic_tag,
typename stores_ref=std::true_type>
auto
orbit(const Array<Perm>& generators,
const Element& element)
// ordered, for canonical representation
{
typedef pm::operations::group::action<Element&, action_type, Perm, op_tag, perm_tag, stores_ref> action_t;
return Set<Element>(entire(orbit_impl<action_t, Perm, Element, Container>(generators, element)));
}
namespace {
inline
Int next_not_in_set(const Set<Int>& the_set, Int initial_value)
{
if (!the_set.size() || initial_value >= *(the_set.rbegin())) return initial_value+1;
while(the_set.contains(++initial_value));
return initial_value;
}
}
/// Calculates a set of orbit representatives for a permutation action
template <typename GeneratorType>
Array<Int>
orbit_representatives(const Array<GeneratorType>& generators)
{
const Int degree = generators[0].size();
Set<Int> seen_elements;
std::vector<Int> reps;
Int rep = 0;
while (rep < degree) {
reps.push_back(rep);
seen_elements += orbit<on_elements, GeneratorType, Int, Set<Int>>(generators, rep);
rep = next_not_in_set(seen_elements, rep);
}
return Array<Int>{reps};
}
}
}
#endif
// Local Variables:
// mode:C++
// c-basic-offset:3
// indent-tabs-mode:nil
// End:
|
