当前位置: 动力学知识库 > 问答 > 编程问答 >

c++ - Calculate sum of links of similar points

问题描述:

Suppose I have a set of 10000 points and they randomly connected to each other. For example let's take 10 points. And they connected like the picture-

Definition of Similar Points:

The points that has same number of links are called similar points. From the picture we can see-

Node 1 is connected with node [2] and [10]

Node 2 is connected with node [1},[3],[4],[5],[6],[7],[8]

Node 3 is connected with only node [2]

Node 4 is connected with only node [2]

Node 5 is connected with only node [2]

Node 6 is connected with only node [2]

Node 7 is connected with only node [2]

Node 8 is connected with node [2] and [9]

Node 9 is connected with only node [8]

Node 10 is connected with only node [1)

So according to the definition, Node- 3,4,5,6,7,9,10 are similar because each of them has only one link.

Again Node- 1 & 8 are similar because each of them has two links.

My Problem

Now I want to calculate the sum of the links of similar points. For example-

Node 1 has 8 are similar.

For node 1:

It is connected to Node 2 (which has 7 links)

And also connected to Node 10 (which has 1 link )

For node 8:

It is connected to Node 2 (which has 7 links)

And also connected to Node 9 (which has 1 link )

So for the group with two links, the number of total links should be= 7+1+7+1 =16.

Like this way I would like to calculate the total links for other similar points.

My Code

Here is my code. It gives the result for the total links for each of the points.

#include <cstdlib>

#include <cmath>

#include <fstream>

#include <iostream>

#include <vector>

using namespace std;

struct Node {

vector< int > links_to;

Node(void){};

Node(int first_link){

links_to.push_back(first_link);

};

};

class Links : public vector<Node> {

public:

void CreateLinks(int n,int m);

void OutputNodes();

};

int RandGenerate(int max) {

return int(drand48()*double(max));

}

void CreateRandom(int *nums,int m,int max) {

bool clear;

for(int i=0;i<m;i++) {

clear=true;

while(clear) {

clear=false;

nums[i]=RandGenerate(max);

for(int j=0;j<i;j++) {

if(nums[i]==nums[j]){

clear=true;break;

}

}

}

}

}

void Links::CreateLinks(int n,int m) {

clear();

for(int i=0;i<m;i++) {

push_back(Node());

}

int edge_targets[m],nums[m];

for(int i=0;i<m;i++) {

edge_targets[i]=i;

}

vector<int> repeated_nodes;

int source=m;

while(source<n) {

push_back(Node());

Node &node=*(end()-1);

for(int i=0;i<m;i++) {

node.links_to.push_back(edge_targets[i]);

at(edge_targets[i]).links_to.push_back(source);

repeated_nodes.push_back(edge_targets[i]);

repeated_nodes.push_back(source);

}

CreateRandom(nums,m,repeated_nodes.size());

for(int i=0;i<m;i++) {

edge_targets[i]=repeated_nodes[nums[i]];

}

source++;

}

}

void Links::OutputNodes() {

for(int i=0;i<size();i++){

cout<<endl;

for(int j=0;j<at(i).links_to.size();j++){

cout<<"Node "<<(i+1)<<" is connected with ["<<(at(i).links_to[j]+1)<<"]"<<endl;

}

cout<<"For Node: "<<(i+1)<<"\t"<<"Total links: "<<at(i).links_to.size()<<endl;

}

}

int main() {

srand48(46574621);

Links network;

network.CreateLinks(10,1); //(nodes,minimum value of link)

network.OutputNodes();

return 0;

}

Which generate the result like this-

Node 1 is connected with [2]

Node 1 is connected with [10]

For Node: 1 Total links: 2

Node 2 is connected with [1]

Node 2 is connected with [3]

Node 2 is connected with [4]

Node 2 is connected with [5]

Node 2 is connected with [6]

Node 2 is connected with [7]

Node 2 is connected with [8]

For Node: 2 Total links: 7

Node 3 is connected with [2]

For Node: 3 Total links: 1

Node 4 is connected with [2]

For Node: 4 Total links: 1 ... etc

I would like to add a function so that it groups the similar points and gives the output of the total links for each groups. How can I do that?

Updated in response to the answer of Pixelchemist

Let's say I store the data in a file name "MyLinks.txt" like this-

1 2

1 10

2 1

2 3

2 4

2 5

2 6

2 7

2 8...etc

And get the input from the file. Here is the code-

int main (void)

{

ifstream inputFile("MyLinks.txt");

double Temp[2];

Links links_object;

while (true) {

for (unsigned i = 0; i < 2; i++){

inputFile>>Temp[i];

}

for (size_t i(0u); i<10; ++i)

{

links_object.add(Node());

}

links_object.link_nodes(Temp[0], Temp[1]);

/*

links_object.link_nodes(0u, 9u);

links_object.link_nodes(1u, 2u);

links_object.link_nodes(1u, 3u);

links_object.link_nodes(1u, 4u);

links_object.link_nodes(1u, 5u);

links_object.link_nodes(1u, 6u);

links_object.link_nodes(1u, 7u);

links_object.link_nodes(7u, 8u);

*/

}

std::vector<size_t> linksum;

for (auto const & node : links_object.nodes())

{

size_t const linksum_index(node.links().size()-1u);

if (linksum.size() < node.links().size())

{

size_t const nls(node.links().size());

for (size_t i(linksum.size()); i<nls; ++i)

{

linksum.push_back(0u);

}

}

for (auto linked : node.links())

{

linksum[linksum_index] += linked->links().size();

}

}

for (size_t i(0u); i<linksum.size(); ++i)

{

std::cout << "Sum of secondary links with " << i+1;

std::cout << "-link nodes is: " << linksum[i] << std::endl;

}

}

Updated my code,store the results of 'connection' in a text file and trying to get the values from that. But now it gives me the segmentation fault. How can I fix it?

网友答案:

I would use a map. The number of links would be the key and its value would be a vector containing the IDs of nodes with that number of links.

typedef std::map<size_t,std::vector<size_t> SimilarNodeMap;

SimilarNodeMap myMap;

... // fill up the map

for (SimilarNodeMap::iterator it=mymap.begin(); it!=mymap.end(); ++it)
{
  std::cout << "Nodes with " it->first << " links: ";

  for ( size_t i = 0; i < second->size(); ++i )
  {
     std::cout << second->at(i) << std::endl;
  }
}
网友答案:

You can go through the nodes that are part of the "pair" and put them into a list. If there is an element you are trying to add that's already in the list don't add it.(e.x if statement check) Then after going through all the elements check the list size and that should be your links.

Correct me if this isn't what you are asking.

I'm sure there is a better way to do this. The complexity of this is O(n^2) time i believe.

网友答案:

I'd use a std::vector<size_t> where the index of the vector is the number of links of the respective node type.

You iterate over all of your nodes and increment the std::vector<size_t>-entry corresponding to the number of links of this node with the number of links of all nodes that are linked to the current one.

This code:

#include <vector>
#include <stdexcept>

class Node 
{
  std::vector< Node const * > m_links;
public:
  Node(void) { }
  void link_to (Node const &n) 
  { 
    m_links.push_back(&n); 
  }
  std::vector< Node const * > const & links (void) const 
  { 
    return m_links; 
  }
};

class Links
{
  std::vector<Node> m_nodes;
public:
  void add (Node const &node) { m_nodes.push_back(node); }
  void link_nodes (size_t node_a, size_t node_b)
  {
    size_t ns(m_nodes.size());
    if (node_a >= ns || node_b >= ns) 
    {
      throw std::logic_error("Requested invalid link.");
    }
    m_nodes[node_a].link_to(m_nodes[node_b]);
    m_nodes[node_b].link_to(m_nodes[node_a]);
  }
  std::vector<Node> const & nodes (void) const 
  { 
    return m_nodes; 
  }
};

int main (void)
{
  Links links_object;
  for (size_t i(0u); i<10; ++i)
  {
    links_object.add(Node());
  }

  links_object.link_nodes(0u, 1u);
  links_object.link_nodes(0u, 9u);
  links_object.link_nodes(1u, 2u);
  links_object.link_nodes(1u, 3u);
  links_object.link_nodes(1u, 4u);
  links_object.link_nodes(1u, 5u);
  links_object.link_nodes(1u, 6u);
  links_object.link_nodes(1u, 7u);
  links_object.link_nodes(7u, 8u);

  std::vector<size_t> linksum;
  for (auto const & node : links_object.nodes())
  {
    size_t const linksum_index(node.links().size()-1u);
    if (linksum.size() < node.links().size()) 
    {
      size_t const nls(node.links().size());
      for (size_t i(linksum.size()); i<nls; ++i) 
      {
        linksum.push_back(0u);
      }
    }
    for (auto linked : node.links())
    {
      linksum[linksum_index] += linked->links().size();
    }
  }

  for (size_t i(0u); i<linksum.size(); ++i)
  {
    std::cout << "Sum of secondary links with " << i+1;
    std::cout << "-link nodes is: " << linksum[i] << std::endl;
  }
}

Prints:

Sum of secondary links with 1-link nodes is: 39
Sum of secondary links with 2-link nodes is: 16
Sum of secondary links with 3-link nodes is: 0
Sum of secondary links with 4-link nodes is: 0
Sum of secondary links with 5-link nodes is: 0
Sum of secondary links with 6-link nodes is: 0
Sum of secondary links with 7-link nodes is: 9

You should get the idea.

网友答案:

You might iterate over all nodes and count. Pseudo code:

std::map<std::size_t, std::size_t> counter;
for each node
    ++counter[node.links().size]
分享给朋友:
您可能感兴趣的文章:
随机阅读: