## I want to get rid of unneccessary repetiton of cycles

I have a code that should read diameters of barrels from a txt file. If a barrel is smaller than the last one, smaller gets put inside bigger one. One package like that is lied on a stack. at the end, code should give out how many stacks we get and how many barrels were in a file. also sum of diameters.

If one number is repeated 3 times, we get 3 stack, if we have 5 repeating nmbers, then 5.
What can I do that I wouldnÂ´t have to write simillar blocks n times.

using System;
using System.Collections.Generic;
using System.IO;

namespace TaaviSimsonTest
{
class Program
{
static void Main(string() args)
{
{
int sum = 0;
string line = string.Empty;
List<int> numbersList = new List<int>();
{
int i = int.Parse(line);
sum += i;
}
int() numbersListArray = numbersList.ToArray();
int numberOfStacks = numbersListArray.Length;
//Max number of stacks equals to inital array length

Array.Sort(numbersListArray);       //Array is ascending orded
Array.Reverse(numbersListArray);    //Array in descending order

//Puts smaller barrels inside bigger. Decreases number of stacks.
List<int> repeatedBrarrelSizes = new List<int>();
for (int j = 0; j < (numbersListArray.Length - 1); j++)
{
if (numbersListArray(j) > numbersListArray(j + 1))
{
numberOfStacks--;
}
else if (numbersListArray(j) == numbersListArray(j + 1))
{
}
}
int() repeatedBarrelSizesArray = repeatedBrarrelSizes.ToArray();

//Repeats the cycle with repeating numbers
List<int> repeatedBarrelSizes2 = new List<int>();
for (int k = 0; k < (repeatedBarrelSizesArray.Length-1); k++)
{
if (repeatedBarrelSizesArray(k) > repeatedBarrelSizesArray(k+1))
{
numberOfStacks--;
}
else if (repeatedBarrelSizesArray(k) == repeatedBarrelSizesArray(k + 1))
{
}
}
int() repeatedBarrelSizes2Array = repeatedBarrelSizes2.ToArray();

//Repeats the cycle again, until no barrels left
List<int> repeatedBarrelSizes3 = new List<int>();
for (int k = 0; k < (repeatedBarrelSizes2Array.Length - 1); k++)
{
if (repeatedBarrelSizes2Array(k) > repeatedBarrelSizes2Array(k + 1))
{
numberOfStacks--;
}
else if (repeatedBarrelSizes2Array(k) == repeatedBarrelSizes2Array(k + 1))
{
}
}
int() repeatedBarrelSizes3Array = repeatedBarrelSizes3.ToArray();

foreach (int value in repeatedBarrelSizes3Array)
{
Console.WriteLine(value + " ");
}

Console.WriteLine("Sum: " + sum);
Console.WriteLine("Number of barrels: " + numbersListArray.Length);
Console.WriteLine("Stacks: " + numberOfStacks);
}
}
}
}


## graphs – Can Johnson’s algorithm for simple cycles be modified in order to find only cycles up to length L (but all of them)?

I have a question regarding Johnsonâ€™s algorithm for finding all simple cycles in a graph.

I was wondering it is possible to modify the algorithm in order to find only cycles up to a given length.

After having read into the algorithm, my approach would the following:

Assume I want only cycles up to length L.
Then, if the stack has reached height L, if the current node on top of the stack is not a neighbor of the starting node, I treat it as having no neighbors left, i.e. I remove it again from the stack.

I am not deep enough into network theory, however, to be sure that this modification still guarantees me finding all simple cycles (up to length L).

## chordless cycles and planarity in graphs

Let {C(G)} be the set of chordless cycles of a graph G. Compare the cycles pairwise. Let {V} represent the pairs which have exactly one vertex in common; and, let {P} represent those pairs which have a single continuous sequence of edges, ie, a path, in common. For a pair in {V},

In either type of conjunction, certain edge orderings on common vertices are required for planarity of G. Can the Kuratowski criteria for planarity be so determined?

## c++ – K-clustering algorithm using Kruskal MST with Disjoint Set in place to check for cycles

here below a working implementation that finds the minimal distance between k(set =4 below) clusters in a graph.
I have doubts mainly on the implementation of the Disjoint Set structure: instead of using STL containers, I went along with an array of pointers as data structure hosting the leader nodes, in order to have some practice with C-style pointers.

Here is the Graph structure:
Graph.h

// creates and manages a graph data structure
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED

#include <array>
#include <vector>
#include <list>
#include <fstream>
#include <string>
#include <iostream>

class Edge
{
public:
// constructors
Edge();
Edge(int, int, int);

std::array<int, 2> getNodes() const;
void setNodes(const int, const int);
int getCost() const;
void setCost(const int);
void swapNodes();
// a get() that allows writing:
int operator()(const int);

bool operator==(const Edge&) const;
bool operator!=(const Edge&) const;

private:
int node1, node2;       // nodes are just indices of the nodes in the graph
int cost;
};

class Node
{
friend class Graph;       // friendship needed by printing routine in Graph
public:
// constructors
Node();
Node(const Edge&);

int getLabel() const {return label;}
Edge getEdge(const int) const;
void setLabel(const int in) {label = in;}
int getScore() const {return score;}
void setScore(const int in) {score = in;}

std::list<Edge>::size_type size() const {return edges.size();}  // size of list 'edges'

// iterators
typedef std::list<Edge>::iterator iterator;
typedef std::list<Edge>::const_iterator const_iterator;
std::list<Edge>::iterator begin() {return edges.begin();}
std::list<Edge>::iterator end() {return edges.end();}
std::list<Edge>::const_iterator cbegin() const {return edges.begin();}
std::list<Edge>::const_iterator begin() const {return edges.begin();}
std::list<Edge>::const_iterator cend() const {return edges.end();}
std::list<Edge>::const_iterator end() const {return edges.end();}

// inserts group of edges to the end of a edges vector
std::list<Edge>::iterator insertEdges(const std::list<Edge>::iterator beg_in,
const std::list<Edge>::iterator end_in)
{
return edges.insert(end(), beg_in, end_in);
}
// erase node
std::list<Edge>::iterator erase(int);

bool operator==(const Node&) const;
bool operator!=(const Node&) const;

private:
int label;
std::list<Edge> edges;
int score;          // new, starts at 10000000, is equal to lowest cost Edge in 'edges'
};

class Graph
{
public:
Graph();
// constructor from txt file
Graph(const std::string&);

Node getNode(const int index) const {return nodes(index);}

std::vector<Node>::size_type size() {return nodes.size();}  // size of vector 'nodes'
std::vector<Node>::size_type size() const {return nodes.size();}  // size of vector 'nodes'
void output() const;      // prints graph
void output(const int) const;

// iterators
typedef std::vector<Node>::iterator iterator;
typedef std::vector<Node>::const_iterator const_iterator;
std::vector<Node>::iterator begin() {return nodes.begin();}
std::vector<Node>::iterator end() {return nodes.end();}
std::vector<Node>::const_iterator begin() const {return nodes.begin();}
std::vector<Node>::const_iterator end() const {return nodes.end();}

Node& operator()(const int index)
{
return nodes(index);
}

std::vector<Node>::iterator erase(const int index)
{
return nodes.erase(nodes.begin() + index);
}

private:
std::vector<Node> nodes;
};

bool compareCosts(const Edge&, const Edge&);
bool compareScores(const Node&, const Node&);
bool compareLabels(const Node&, const Node&);

#endif // GRAPH_H_INCLUDED


Graph.cpp:

#include <iostream>
#include <fstream>
#include <array>
#include <list>
#include <string>
#include <algorithm>
#include "Graph.h"

using std::array;       using std::ifstream;
using std::string;      using std::endl;
using std::cout;        using std::list;
using std::equal;

// Edge

// constructors
Edge::Edge():node1(0), node2(0), cost(0) {}
Edge::Edge(int node_1, int node_2, int len): node1(node_1), node2(node_2), cost(len) {}

array<int, 2> Edge::getNodes() const
{
array<int, 2> ret = {node1, node2};

return ret;
}

void Edge::setNodes(const int in1, const int in2)
{
node1 = in1;
node2 = in2;
}

int Edge::getCost() const
{
return cost;
}

void Edge::setCost(const int len)
{
cost = len;
}

void Edge::swapNodes()
{
node1 = node1 - node2;
node2 += node1;
node1 = node2 - node1;
}

// same as getNodes() above
int Edge::operator()(const int index)
{
if (index == 0) return node1;
else if (index == 1) return node2;
else {
try {throw;}
catch(...) {cout << "edge index must be either 0 or 1" << endl;}
return 1;
}
}

bool Edge::operator==(const Edge& rhs) const
{
if ( (node1 == rhs.getNodes()(0)) && (node2 == rhs.getNodes()(1)) && cost == rhs.getCost() )
return true;
else
return false;
}

bool Edge::operator!=(const Edge& rhs) const
{
if ( !(*this == rhs) )
return true;
else
return false;
}

// Node

//constructors
Node::Node(): label(0), edges(0), score(10000000) {}
Node::Node(const Edge& edg): label(edg.getNodes()(0)), edges(0), score(10000000)
{
edges.push_back(edg);
}

Edge Node::getEdge(const int index) const
{
Edge ret;
list<Edge>::const_iterator iter = edges.begin();

return *iter;
}

{
for (size_t i = 0; i != input.size(); i++)
{
edges.push_back(input(i));
}
}

list<Edge>::iterator Node::erase(int index)
{
list<Edge>::iterator iter = edges.begin();

return edges.erase(iter);
}

bool Node::operator==(const Node& rhs) const
{
return label == rhs.getLabel() && equal( edges.begin(), edges.end(), rhs.begin() );  // no need to equate scores
}

bool Node::operator!=(const Node& rhs) const
{
return !(*this == rhs);
}

// Graph

// constructors
Graph::Graph(): nodes(0) {}
Graph::Graph(const string& file_input): nodes(0)    // constructor from file
{
string filename(file_input + ".txt");
string line;
ifstream is;
is.open(filename);

int number_nodes; //, number_edges;
is >> number_nodes; // >> number_edges;
nodes.resize(number_nodes);  // reserve the Node vector of size 'number_nodes'

int node1, node2, cost;
while (is >> node1 >> node2 >> cost)
{
int nodes_array(2) = {node1, node2};
for (int& node_i : nodes_array) {
if (nodes(node_i - 1).size() == 1)
nodes(node_i - 1).setLabel(node_i);
}

Edge current_edge(node1, node2, cost);

if (node1 != node2) {
current_edge.swapNodes();
}
}

is.close();
}

// prints all input nodes
void Graph::output() const
{
for (size_t i = 0; i != nodes.size(); ++i)
{
cout << "Node " << nodes(i).getLabel() << ", size = " << nodes(i).edges.size() << "  with edges: ";
for (size_t j = 0; j != nodes(i).edges.size(); ++j)
{
int node_left = nodes(i).getEdge(j).getNodes()(0);
int node_right = nodes(i).getEdge(j).getNodes()(1);
int cost = nodes(i).getEdge(j).getCost();
cout << "(" << node_left << "-" << node_right << ", " << cost << ")   ";
}
cout << endl;
}
}

// prints 10 neighbours around picked node
void Graph::output(const int picked_node) const
{
for (int i = picked_node - 5; i != picked_node + 5; ++i)
{
cout << "Node " << nodes(i).getLabel() << ", with edges: ";
for (size_t j = 0; j != nodes(i).edges.size(); ++j)
{
int node_left = nodes(i).getEdge(j).getNodes()(0);
int node_right = nodes(i).getEdge(j).getNodes()(1);
int cost = nodes(i).getEdge(j).getCost();
int score = nodes(node_right - 1).getScore();
cout << "(" << node_left << "-" << node_right << ", " << cost << ", " << score << ")   ";
}
cout << endl;
}
}

bool compareCosts(const Edge& a, const Edge& b)
{
return a.getCost() < b.getCost();
}

bool compareScores(const Node& a, const Node& b)
{
return a.getScore() > b.getScore();
}

bool compareLabels(const Node& a, const Node& b)
{
return a.getLabel() > b.getLabel();
}


BFS implementation for Kruskal (alternative to Disjoint Set Kruskal implementation)

#ifndef BREADTHFIRSTSEARCH_H_INCLUDED

#include <limits>
#include "Graph.h"

int const infinity = std::numeric_limits<int>::infinity();

bool breadthFirstSearch(const Graph&, const int, const int);



#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>

using std::cout;    using std::endl;
using std::cin;     using std::find_if;
using std::vector;  using std::queue;
using std::map;

bool breadthFirstSearch(const Graph& G, const int start_node_label, const int target_node_label)
{
// define type for explored/unexplored Nodes
enum is_visited {not_visited, visited};
map<int, is_visited> node_is_visited;
for (Graph::const_iterator iter = G.begin(); iter != G.end(); ++iter)
node_is_visited(iter->getLabel()) = not_visited;

Graph::const_iterator start_node_iter =
find_if(G.begin(), G.end(), (=)(const Node& i){return i.getLabel() == start_node_label;});
if ( start_node_iter == G.end() )
return false;
node_is_visited(start_node_label) = visited;

Node next_node;
next_node = *start_node_iter;

// breadth-first algorithm runs based on queue structure
queue<Node> Q;
Q.push(next_node);

// BFS algorithm
while (Q.size() != 0) {     // out of main loop if all nodes searched->means no path is present
Node current_node = Q.front();
Node linked_node;       // variable hosting node on other end
for (size_t i = 0; i != current_node.size(); ++i) {     // explore nodes linked to current_node by an edge
find_if(G.begin(), G.end(), (=)(const Node& a){return a.getLabel() == linked_node_label;});
if ( is_linked_node_in_G != G.end() ) {    // check linked_node is in G
//                    cout << "current " << current_node.getLabel()       // for debug
//                         << " | path length = " << dist(linked_node_label) << endl;
if (linked_node_label == target_node_label)  // end search once target node is explored
return true;
}
} else {
if (linked_node_label == target_node_label)  // end search once target node is explored
return false;
}
}
Q.pop();
}

return false;
}


DisjointSet.h

#ifndef DISJOINTSET_H_INCLUDED
#define DISJOINTSET_H_INCLUDED

#include "Graph.h"

class DisjointSet
{
public:
DisjointSet(const size_t);
~DisjointSet();
DisjointSet& operator= (const DisjointSet&);

int find(const Node&);
void unionNodes(const Node&, const Node&);

private:
size_t size;        // graph size needed for allocation of pointer data members below
int* base;          // array of int each Node of the graph has its leader
int** leaders;      // array of pointers to int, allows to reassign leaders to Nodes after unions

int find_int(int);  // auxiliary to 'find' above

DisjointSet(const DisjointSet&);    // copy constructor forbidden
};

#endif // DISJOINTSET_H_INCLUDED


DisjointSet.cpp (here is where advice would be most appreciated)

// Union-find structure (lazy unions)
#include "DisjointSet.h"

DisjointSet::DisjointSet(size_t in): size(in), base(new int(in)), leaders(new int*(in))
{
for (size_t i = 1; i != in + 1; ++i) {
base(i - 1) = i;
leaders(i - 1) = &base(i - 1);
}
}

DisjointSet::~DisjointSet()
{
delete() base;
}

DisjointSet& DisjointSet::operator= (const DisjointSet& rhs)
{
if (this == &rhs)
return *this;       // make sure you aren't self-assigning
if (base != NULL) {
delete() leaders;     // get rid of the old data
delete() base;
}

// "copy constructor" from here
size = rhs.size;
base = new int(size);
base = rhs.base;
for (size_t i = 0; i != size; ++i)

return *this;
}

// auxiliary to find: implements the recursion
{

return parent;
}

// returns leader to input Node
int DisjointSet::find(const Node& input)
{
int parent( input.getLabel() );
if (input.getLabel() != *leaders(input.getLabel() - 1))

return parent;
}

// merges sets by assigning same leader (the lesser of the two Nodes)
void DisjointSet::unionNodes(const Node& a, const Node& b)
{
if (find(a) != find(b)) {
if (find(a) < find(b))
leaders(find(b) - 1) = &base(find(a) - 1);
else
leaders(find(a) - 1) = &base(find(b) - 1);
}
}


KruskalClustering.h

#ifndef KRUSKALCLUSTERING_H_INCLUDED
#define KRUSKALCLUSTERING_H_INCLUDED

#include <vector>
#include "Graph.h"
#include "DisjointSet.h"

int clusteringKruskalNaive(const Graph&, const std::vector<Edge>&, int);
int clusteringKruskalDisjointSet(const Graph& graph0, const std::vector<Edge>& edges, int);

#endif // KRUSKALCLUSTERING_H_INCLUDED


KruskalClustering.cpp

// Kruskal MST algorithm. Implementation specific to  (k=4)-clustering
// -naive (with breadth-first-search to check whether new edge creates a cycle); cost: O(#_edges * #_nodes)
// -and union-find implementations.  Cost: O(#_edges*log2(#_nodes))
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>        //std::find_if
#include "KruskalClustering.h"

using std::cout;            using std::endl;
using std::string;          using std::vector;
using std::find_if;

int clusteringKruskalNaive(const Graph& graph0, const vector<Edge>& edges, int k)
{
Graph T;    // Minimum Spanning Tree
vector<Edge>::const_iterator edges_iter = edges.begin();
int sum_costs(0), number_of_clusters( graph0.size() );  // keep track of overall cost of edges in T, and of clusters
while (number_of_clusters >= k) {

// find out if first node of edge is already in T
Graph::iterator is1_in_T = find_if(T.begin(), T.end(),
(=) (Node& a) {return a.getLabel() == graph0.getNode(edges_iter->getNodes()(0) - 1).getLabel();});
bool is1_in_T_flag;         // needed because T gets increased and thus invalidates iterator is1_in_T
Node* node_1 = new Node(*edges_iter); // no use of pointer here, it creates a new Node anyway, can't move Nodes to T
if ( is1_in_T == T.end() ) {      // node_1 not in T so we add it
number_of_clusters--;         // node_1 is not its own cluster any more
delete node_1;                // node_1 copied to T so ...
node_1 = &(T(T.size() - 1));  // ... it now points there
sum_costs += (*edges_iter).getCost();
is1_in_T_flag = false;
} else {                          // node_1 is in T already
delete node_1;                // if so, just update the pointer
node_1 = &(*is1_in_T);
is1_in_T_flag = true;
}

// perform BFS to check for cycles
bool check_cycles = breadthFirstSearch(T, edges_iter->getNodes()(0), edges_iter->getNodes()(1));

// create an identical edge, but with nodes positions swapped
Edge swapped_edge = *edges_iter;
swapped_edge.swapNodes();
// find out if second node of edge is already in T
Graph::iterator is2_in_T = find_if( T.begin(), T.end(),
(=) (Node& a) {return a.getLabel() == graph0.getNode(edges_iter->getNodes()(1) - 1).getLabel();});
// (either node1 or 2 not in T, or both, or both present but in different clusters of T)
if (!check_cycles) {         // if edges_iter creates no cycle when added to T
if (is1_in_T_flag){          // if node_1 was already present in T
sum_costs += (*edges_iter).getCost();
} else
number_of_clusters++;   // if node_1 not present, it means number_of_cl was decreased above ...

number_of_clusters--;       // ... and number_of_cl can decrease just by one, if adding an edge to T
if ( is2_in_T != T.end() )  // node_2 already in T: just update its list of edges
else {                      // node_2 not in T, so add it
Node node_2(swapped_edge);
}

} else {                        // cycle created by *edges_iter
if (!is1_in_T_flag)         // in case the cycle happened just after adding node_1:
}
if (number_of_clusters >= k)    // advance to next Edge if num_clusters > k
edges_iter++;

// debug
//        T.output();
//        cout << "next edge: (" << (*edges_iter).getNodes()(0) << "-"
//             << (*edges_iter).getNodes()(1) << ") " << endl;
//        cout << "clustering: " << number_of_clusters << endl;
}
cout << "Sum of MST lengths is: " << sum_costs << endl;

return (*edges_iter).getCost();
}

// same algorithm, implemented with Union-find structure
int clusteringKruskalDisjointSet(const Graph& graph0, const vector<Edge>& edges, int k)
{
DisjointSet disjoint_set_graph0( graph0.size() );       // create Union-find structure

Graph T;
vector<Edge>::const_iterator edges_iter = edges.begin();
int sum_costs(0), number_of_clusters( graph0.size() );

while ( number_of_clusters >= k ) {
// if nodes in Edge have not the same leader in the disjoint set, then no loop is created, and T can add the edge
if ( disjoint_set_graph0.find(graph0.getNode(edges_iter->getNodes()(0) - 1)) !=
disjoint_set_graph0.find(graph0.getNode(edges_iter->getNodes()(1) - 1)) ) {
sum_costs += (*edges_iter).getCost();
number_of_clusters--;               // no cycle created so the edge will be added to T

// look for node_1 in T
Graph::iterator is1_in_T = find_if(T.begin(), T.end(),
(=) (Node& a) {return a.getLabel() == graph0.getNode(edges_iter->getNodes()(0) - 1).getLabel();});
if ( is1_in_T == T.end() ) {   // if node_1 not in T add it
Node node1(*edges_iter);
} else                         // if node_1 already in T only add to it this edge

Edge swapped_edge = *edges_iter;
swapped_edge.swapNodes();
// look for node_2 in T
Graph::iterator is2_in_T = find_if(T.begin(), T.end(),
(=) (Node& a) {return a.getLabel() == graph0.getNode(edges_iter->getNodes()(1) - 1).getLabel();});
if ( is2_in_T == T.end() ) {     // same as for node_1
Node node2(swapped_edge);
} else

// merge the 2 nodes' sets: update their disjointed set leaders
disjoint_set_graph0.unionNodes( graph0.getNode(edges_iter->getNodes()(0) - 1),
graph0.getNode(edges_iter->getNodes()(1) - 1) );
}

if (number_of_clusters >= 4)
edges_iter++;
//debug
//        T.output();
//        cout << "next edge: (" << (*edges_iter).getNodes()(0) << "-"
//             << (*edges_iter).getNodes()(1) << ") " << endl;
//        cout << "clustering: " << number_of_clusters << endl;
//        for (size_t i = 0; i != graph0.size(); ++i)
//            cout << disjoint_set_graph0.get(i) << " ";
//        cout << endl;
}
cout << "Sum of MST lengths is: " << sum_costs << endl;

return (*edges_iter).getCost();
}


Lastly, main.cpp :

/* A max-spacing k-clustering program based on Kruskal MST algorithm.
The input file lists a complete graph with edge costs.
clusters k = 4 assumed.*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>        // std::sort;
#include "Graph.h"
#include "KruskalClustering.h"

using std::cout;                using std::endl;
using std::string;              using std::ifstream;
using std::vector;              using std::sort;

int main(int argc, char** argv)
{
cout << "Reading list of edges from input file ...n" << endl;

// read graph0 from input file
string filename(argv(1));

Graph graph0(filename);
//    graph0.output();   // debug
cout << endl;

// re-read input file and create a list of all edges in graph0
ifstream is(filename + ".txt");
int nodes_size;
is >> nodes_size;
vector<Edge> edges;
int node1, node2, cost;

while (is >> node1 >> node2 >> cost) {
Edge current_edge(node1, node2, cost);
edges.push_back(current_edge);
}
is.close();

// sort the edge list by increasing cost
cout << "Sorting edges ...n" << endl;
sort(edges.begin(), edges.end(), compareCosts);
//    for (vector<Edge>::iterator iter = edges.begin(); iter != edges.end(); ++iter)       // debug
//        cout << (*iter).getNodes()(0) << " " << (*iter).getNodes()(1) << "  " << (*iter).getCost() << endl;

cout << "Kruskal algorithm: Computing minimal distance between clusters when they are reduced to 4 ...n" << endl;

int k = 4;   // number of clusters desired

// pick implementation, comment the other
//int clustering_min_dist = clusteringKruskalNaive(graph0, edges, k);
int clustering_min_dist = clusteringKruskalDisjointSet(graph0, edges, k);

cout << "k = " << k << " clusters minimal distance is: " << clustering_min_dist << endl;

return 0;
}


## Set of cycles in directed graph

I have a directed graph. How to find in it some set of cycles that are pairwise
do not intersect, but cover the entire set of vertices, if a cycle from one vertex is not considered a cycle, but cycle of the two vertex is a cycle?

## algorithms – Minimum vertex cover and odd cycles

Suppose we have a graph $$G$$. Consider the minimum vertex cover problem of $$G$$ formulated as a linear programming problem, that is for each vertex $$v_{i}$$ we have the variable $$x_{i}$$, for each edge $$v_{i}v_{j}$$ we have the constraint $$x_{i}+x_{j}geq 1$$, for each variable we have $$0leq x_{i}leq 1$$ and we have the objective function $$min sumlimits_{1}^{n}{x_{i}}$$. We say such a linear programming problem LP. Note that it is NOT an integer linear programming problem.

We find a half integral optimal solution of LP that we say $$S_{hi}$$. For each variable $$x_{i}$$ that takes value 0 in $$S_{hi}$$, we add the constraint $$x_{i}=0$$ to LP.

For each odd cycle of $$G$$, add to LP the constraint $$x_{a}+x_{b}+x_{c}+…+x_{i}geq frac{1}{2}(k+1)$$ where $$x_{a},x_{b},x_{c},…,x_{i}$$ are the vertices of the cycle and $$k$$ is the number of vertices of the cycle. We find a new optimal solution of LP that we say $$S$$.

If $$x_{i}$$ is a variable that takes value $$0.5$$ in $$S_{hi}$$ and value $$gt 0.5$$ in $$S$$, can we say that there is at least a minimum vertex cover of $$G$$ that contains the vertex associated to $$x_{i}$$?

The idea behind the question: in an odd cycle $$c$$ with $$k$$ vertices, the number of vertices needed to cover the cycle is $$frac{1}{2}(k+1)$$, therefore for each odd cycle we add to LP the constraint $$x_{a}+x_{b}+x_{c}+…+x_{i}geq frac{1}{2}(k+1)$$. If in $$S_{hi}$$ the sum of the variables of $$c$$ is $$frac{k}{2}$$ (that is all the variables of $$c$$ take value $$frac{1}{2}$$), then in $$S$$ at least a variable $$x_{i}$$ of $$c$$ takes vale $$gt frac{1}{2}$$ and the vertex associated to $$x_{i}$$ belongs to at least a minimum vertex cover of the given graph.

## domain driven design – DDD – Object Life Cycles, Multiple Roots/Aggregates in a context, and Persistence

I have an application in which I’ve identified the need for an Authorization Context. There are some really basic invariants:

An action can only be performed in a system if a user if they have the associated function
Functions can be grouped into roles for easier management.
Role names must be unique so they aren’t confusing to a user
Users can’t have duplicate functions
Users can’t be in a role more than once

Functions are a pre-defined, immutable list which basically consist of a name and a description.
I get the feeling that these are value objects. Something like:

Function
--------
Name
Description


Role seems like it should be an entity, so it has an id, name, description, and list of functions

Role
----
Id
Name
Description
(Functions)


And a User, which can have functions or roles. (I’ve finally come to terms with a user being able to have different representations in different contexts, which is why I only need an Id here)

User
----
Id
(Functions)
(Roles)


First question: Is this even designed correctly? While I feel like the Functions could be value objects, the fact that they can be added and removed from a role or user make them feel like entities to me. Additionally I feel like the user and role only need references to the other entity Id’s, and not the entire objects, to satisfy the invariants.

Second problem: What is my Aggregate? My first inclination was that I would have an AuthorizationAggregate. That would have the list of FunctionValueObjects, and a list of currently defined roles. But that seems weird to me because the AuthorizationAggregate woudln’t have an ID of its own. And what do I do with the user? I don’t think holding a reference to every single user in the application when the aggregate is retrieved from the repository is a great idea, especially if all that’s taking place is a role being created. However, wouldn’t those users need to be updated in a role had a new function added (which is why I made the point earlier about only needed Ids).

So that leads me to think, do I have an AuthorizationRolesAggregate for the creation/modification/deletion of the Roles, and adding / removing functions from the roles?

Then do I have a separate AuthorizedUserAggregate for adding/removing roles and functions? I feel like this aggregate is from within the same Context, but the representations of the roles/functions may be different (just ids, for example). Also, when adding a role to a user, should I be taking a Role as the parameter for the AddRole method (eg: AddRole(Role role))? So should I be using a domain service here to pull the valid role from the AuthorizationRolesAggregate, and passing that to the AddRole method of the user?

3rd problem: This is more technical than theoretical, but what is the proper way for creating an aggregate. A static Create method on the Aggregate class? A create method on the repository? What about deleting an entity or an aggregate? In the above case, if I used the AuthorizationRolesAggregate to delete a role, what’s the best strategy for udpating all off the affected users? Raise a RoleDeleted domain event, and update N number AuthorizedUserAggregates to delete the associated role from the user becoming eventually consistent?

I think part of why I’m really struggling with this right now because right now it’s backed by a 3NF RDBMS, and I know that If I remove the role the next time I load an affected user, it will load properly without that associated role. However, that’s incredibly lazy, and doesn’t address any currently loaded members. I also know if I were to move to a document db, or event sourcing, that would not be the case.

I’m also fighting this idea that if I were to create a new role using the AuthorizationRolesAggregate, having to potentially check the entirety of the Aggregate (all of the loaded roles and their functions) when I go to persist the Aggregate. That again makes me think that’s not the right design.

Any pointers in the right direction would be very appreciated.

## co.combinatorics – Is there a bijective proof of an identity enumerating independent sets in cycles?

Let $$C_m$$ be the cycle with $$m$$ vertices, defined so that $$C_1$$ has a self-loop on its unique vertex. Let $$p_m$$ be the generating function enumerating the number of ways to choose $$k$$ vertices in $$C_m$$ so that no two are adjacent. Thus the coefficient of $$z^k$$ in $$p_m(z)$$ is the number of independent sets in $$C_m$$ of size $$k$$.

For instance, $$p_1(z) = 1$$, $$p_2(z) = 1+2z$$, $$p_3(z) = 1+3z$$, $$p_4(z) = 1+4z + 2z^2$$, $$p_5(z) = 1 + 5z+5z^2$$ and $$p_6(z) = 1 + 6z + 9z^2 + 2z^3$$. Set $$p_0 = 2$$.

It is not hard to show by algebraic arguments (related to the theory of Chebyshev polynomials) that if $$ell, m in mathbb{N}_0$$ with $$ell ge m$$ then

$$p_ell p_m = p_{ell+m} + (-1)^m z^{m} p_{ell-m}.$$

In particular, $$p_m^2 = p_{2m} + 2(-1)^m z^{m}$$, and so if $$k < m$$ then the coefficients of $$z^k$$ in $$p_m^2$$ and $$p_{2m}$$ are equal. I would like a bijective proof of this, or ideally, of the more general identity above.

Is there a bijective proof that if $$k < m$$ then the number of independent sets of size $$k$$ in the disjoint union $$C_m sqcup C_m$$ is equal to the number of independent sets of size $$k$$ in $$C_{2m}$$?

## discrete mathematics – can an Eulerian graph have exactly two cycles?

But avoid

• Make statements based on opinions; Support them with references or personal experiences.

Use MathJax to format equations. MathJax reference.

## Calculation of Rubiks $2 times 2 times 2$ permutation with cycles

The help of "PermutationGroup" shows a good example for the calculation of the permutations of a 3x3x3:

rot1 = Cycles[{{1, 3, 8, 6}, {2, 5, 7, 4}, {9, 48, 15, 12}, {10, 47,
16, 13}, {11, 46, 17, 14}}];
rot2 = Cycles[{{6, 15, 35, 26}, {7, 22, 34, 19}, {8, 30, 33, 11}, {12,
14, 29, 27}, {13, 21, 28, 20}}];
rot3 = Cycles[{{1, 12, 33, 41}, {4, 20, 36, 44}, {6, 27, 38, 46}, {9,
11, 26, 24}, {10, 19, 25, 18}}];
rot4 = Cycles[{{1, 24, 40, 17}, {2, 18, 39, 23}, {3, 9, 38, 32}, {41,
43, 48, 46}, {42, 45, 47, 44}}];
rot5 = Cycles[{{3, 43, 35, 14}, {5, 45, 37, 21}, {8, 48, 40, 29}, {15,
17, 32, 30}, {16, 23, 31, 22}}];
rot6 = Cycles[{{24, 27, 30, 43}, {25, 28, 31, 42}, {26, 29, 32,
41}, {33, 35, 40, 38}, {34, 37, 39, 36}}];
RubikGroup = PermutationGroup[{rot1, rot2, rot3, rot4, rot5, rot6}];


I want to calculate the permuations of a 2x2x2 cube like in the example above.
I created and wrote down a 2d 2x2x2 cube, which I think is the basic rotation cycle. But the permutations returned are far too many.
What am i missing

rot1 = Cycles[{{1, 2, 4, 3}, {5, 24, 9, 7}, {6, 23, 10, 8}}];
rot2 = Cycles[{{21, 22, 24, 23}, {1, 10, 20, 11}, {2, 16, 19, 5}}];
rot3 = Cycles[{{11, 5, 6, 12}, {1, 7, 19, 21}, {3, 13, 17, 23}}];
rot4 = Cycles[{{7, 8, 13, 14}, {3, 9, 18, 12}, {4, 15, 17, 6}}];
rot5 = Cycles[{{10, 16, 15, 9}, {2, 8, 18, 22}, {4, 14, 20, 24}}];
rot6 = Cycles[{{20, 19, 17, 18}, {16, 21, 12, 14}, {15, 22, 11, 13}}];
RubikGroup2x2x2 = PermutationGroup[{rot1, rot2, rot3, rot4, rot5, rot6}];
GroupOrder[RubikGroup2x2x2]


Out: 620.448.401.733.239.439.360.000

For a 2x2x2 cube, it should be 3,674,160.