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)
        {
            using (TextReader reader = File.OpenText("C:\temp\andmed2"))
            {
                int sum = 0;
                string line = string.Empty;
                List<int> numbersList = new List<int>();
                while ((line = reader.ReadLine()) != null)   
                {
                    int i = int.Parse(line);    
                    sum += i;
                    numbersList.Add(int.Parse(line));
                }
                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))
                    {
                        repeatedBrarrelSizes.Add(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))
                    {
                        repeatedBarrelSizes2.Add(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))
                    {
                        repeatedBarrelSizes3.Add(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;}
    void addEdge(const Edge in) {edges.push_back(in);}
    void addManyEdges(const std::vector<Edge>);
    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);}
    void addNode(const Node in) {nodes.push_back(in);}

    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();
    advance(iter, index);

    return *iter;
}


void Node::addManyEdges(const vector<Edge> input)
{
    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();
    advance(iter, index);

    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);

        nodes(node1 - 1).addEdge(current_edge);
        if (node1 != node2) {
            current_edge.swapNodes();
            nodes(node2 - 1).addEdge(current_edge);
        }
    }

    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)
BreadthFirstSearch.h

#ifndef BREADTHFIRSTSEARCH_H_INCLUDED
#define BREADTHFIRSTSEARCH_H_INCLUDED

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

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

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

#endif // BREADTHFIRSTSEARCH_H_INCLUDED

BreadthFirstSearch.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#include "BreadthFirstSearch.h"

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
            int linked_node_label = current_node.getEdge(i).getNodes()(1);  
            Graph::const_iterator is_linked_node_in_G =
                       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
                linked_node = *is_linked_node_in_G; //G_tot.getNode(linked_node_label - 1);
                if (node_is_visited(linked_node_label) == not_visited) {    // check if linked_node is already in the queue
                    node_is_visited(linked_node_label) = visited;
                    Q.push(linked_node);                                    // if not, add it to the queue
//                    cout << "current " << current_node.getLabel()       // for debug
//                         << " | linked = " << linked_node_label + 1
//                         << " | 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&);

    int get(int index) {return *leaders(index);}

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;
    delete() leaders;
}


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);
    leaders = new int*(size);
    base = rhs.base;
    for (size_t i = 0; i != size; ++i)
        leaders(i) = &base(i);

    return *this;
}


// auxiliary to find: implements the recursion
int DisjointSet::find_int(int leader_pos)
{
    int parent(leader_pos);
    if (leader_pos != *leaders(leader_pos - 1))
        parent = find_int(*leaders(leader_pos - 1));

    return parent;
}


// returns leader to input Node
int DisjointSet::find(const Node& input)
{
    int parent( input.getLabel() );
    if (input.getLabel() != *leaders(input.getLabel() - 1))
        parent = find_int(*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 "BreadthFirstSearch.h"
#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
            T.addNode(*node_1);
            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
                (*node_1).addEdge(*edges_iter);       // just add new edge to node_1 list of edges
                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
                (*is2_in_T).addEdge(swapped_edge);
            else {                      // node_2 not in T, so add it
                Node node_2(swapped_edge);
                T.addNode(node_2);
            }

        } else {                        // cycle created by *edges_iter
            if (!is1_in_T_flag)         // in case the cycle happened just after adding node_1:
                (*is2_in_T).addEdge(swapped_edge);   // add edge to node_2, num_clusters already updated by 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);
                T.addNode(node1);
            } else                         // if node_1 already in T only add to it this edge
                (*is1_in_T).addEdge(*edges_iter);

            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);
                T.addNode(node2);
            } else
                (*is2_in_T).addEdge(swapped_edge);

            // 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;
} 

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?

Thank you for your reply to Mathematics Stack Exchange!

  • Please be sure answer the question. Provide details and share your research!

But avoid

  • Ask for help, clarify, or respond to other answers.
  • Make statements based on opinions; Support them with references or personal experiences.

Use MathJax to format equations. MathJax reference.

For more information, see our tips on writing great answers.

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:
3x3x3 cubes

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
2x2x2 cubes

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.