node connectivity of a mesh

Cplusc (457)
I asked this question before and I got some answers, but it's not working for me.
I have a list of triangle with its vertices like below,
triangle node0 node1 node2
1 2 4 6
2 2 6 5
3 1 3 4
4 1 4 2


as you see the whole mesh consists of 6 points. I want to make a vector of vector showing which nodes are connected together.
before this I did something like this,

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
 
		for (int i = 0; i < 100; i++)
	{
		counter[i] = 0;
	}

	for (size_t i = 0; i < triangle.size(); i++)
	{

		counter[node_0] = counter[node_0] + 1;
		node_connec[node_0][counter[node_0]] = node_0;
		counter[node_0] = counter[node_0] + 1;
		node_connec[node_0][counter[node_0]] = node_1;
		counter[node_0] = counter[node_0] + 1;
		node_connec[node_0][counter[node_0]] = node_2;

		counter[node_1] = counter[node_1];
		node_connec[node_1][counter[node_1]] = node_1;
		counter[node_1] = counter[node_1] + 1;
		node_connec[node_1][counter[node_1]] = node_2;
		counter[node_1] = counter[node_1] + 1;
		node_connec[node_1][counter[node_1]] = node_0;

		counter[node_2] = counter[node_2] + 1;
		node_connec[node_2][counter[node_2]] = node_2;
		counter[node_2] = counter[node_2] + 1;
		node_connec[node_2][counter[node_2]] = node_1;
		counter[node_2] = counter[node_2] + 1;
		node_connec[node_2][counter[node_2]] = node_0;
	}


it works for me, but after obtaining this matrix,I need to remove the zero elements from it, because for a big structure there will a lot of zero elements and saving that amount of unnecessary data would not be efficient.

I am searching for something to give me a vector of vector showing the node connectivity.
In this case it should be like this

1 2 6
1 2 3 5 6
2 3 4 5
3 4 5
2 3 4 5 6
1 2 5 6


This vector has been sorted in row major. first row shows the connected node to node 1, second row says which nodes are connected to node 2.
Last edited on
jonnin (11437)
You can google a few schemes for storing a sparse (mostly zero) matrix. Most matrix libraries have one already in place. That seems like overkill, though. There are different nifty ways but they boil down to having some sort of way to extract the info, eg convert the 2d to 1d and have int (location) and data (value) pairs is a simple method.

- you could also just do a vector<bool> where [0] = true means this thing is connected to the other thing's [0], [1] = true... etc very compact: it wastes the space for the zero, but now that is just a single bit, and one byte can hold all 6 possibly?

- you can use a map, location / value

and so on.

if you still want vector of vector it is just
vector<vector<int> > matrix;
and you can make a vector<int> with {1,2,6} and push that back or you can push an empty vector and do 1,2,6 one by one into the deeper dimension. Is something with that giving trouble?
Also, its often easier to just skip than to fix. Is there a way to simply NOT insert the zeros, so you don't have to remove them?
Last edited on
Cplusc (457)
The way I'm working with is csr format. But before that I need the connectivity of nodes. I don't get this part you said,
and you can make a vector<int> with {1,2,6} and push that back or you can push an empty vector and do 1,2,6 one by one into the deeper dimension. Is something with that giving trouble?
Could you please give mn an example. It's not in reality 6 points, it can be over one million tringle and nodes.
Last edited on
lastchance (6980)
The way I'm working with is csr format.


That doesn't look remotely like csr format.
Cplusc (457)
It is not csr yet. I get a 2d array (n_node*n_node), then I sort it out, then I remove zero and repeated element in each row and at the end I have a vector of vector and I get the row_ptr and col_ind for csr fomat. but I don't want to do this, it's not efficient. I just want to obtain this vector of vector by having each triangle vertices but I don't know how.
Last edited on
jonnin (11437)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <vector>
#include <iostream>

using namespace std;

int main()
{
   vector<vector< int> > test;
   vector<int> a{1,2,3};  //push back populated vectors. 
   vector<int> b{4,5,6,7,8};

   test.push_back(a);
   test.push_back(b);   
   cout << test[1][1] << endl;
   
   test.push_back(vector<int>{}); //push back empty vector
   test[2].push_back(9);  //add items to empty row (empty vector)
   cout << test[2][0];
	
}


performance: you will want to use reserve or construction to allocate the memory up front!
if you do not, every few push-backs will do a new pointer, copy old pointer into new one, delete old one operation.

where I stopped, its a non-square 2d construct shaped like this:
1,2,3
4,5,6,7,8
9

if you want to be cute you can put the 2d vector in a class and set up access so that if you go out of bounds it returns the (implied, sparse not saved) zeros, but the bounds checks cost you time... sounds like you prefer speed.
Last edited on
Cplusc (457)
Thanks for your answer, but it's doing the push back. My question is not about doing push back, I want to know how I can have a list of triangle with three vertices(in a mesh) and I obtain the node connectivity. and I want to have a vector of vector.

triangle node0 node1 node2
1  2  4  6
2  2  6  5
3  1  3  4
4  1  4  2


I want to get this

1 is connected to 1 2 6
2 is connected to 1 2 3 5 6
3 is connected to 2 3 4 5
4 is connected to 3 4 5
5 is connected to 2 3 4 5 6
6 is connected to 1 2 5 6


the above vector of vector shows each node is connected to which other node, this vector of vector is sorted in row major.
Last edited on
lastchance (6980)
I've no idea how your sample input gives your sample output (6 is only connected to 2, 4 and 5, for example) but this shows connections via sides of triangles.

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
 
#include <iostream>
#include <sstream>
#include <fstream>
#include <set>
#include <map>
using namespace std;

int main()
{
   map< int,set<int> > nodes;
// ifstream in( "data.txt" );
   istringstream in( "1 2 4 6\n"
                     "2 2 6 5\n"
                     "3 1 3 4\n"
                     "4 1 4 2\n" );   
   
   for( int dummy, a, b, c; in >> dummy >> a >> b >> c; )
   {
       nodes[a].insert( { b, c } );
       nodes[b].insert( { c, a } );
       nodes[c].insert( { a, b } );
   }
   
   for ( auto &s : nodes )
   {
      cout << s.first << " is connected to ";
      for ( auto n : s.second ) cout << n << ' ';
      cout << '\n';
   }
}


1 is connected to 2 3 4 
2 is connected to 1 4 5 6 
3 is connected to 1 4 
4 is connected to 1 2 3 6 
5 is connected to 2 6 
6 is connected to 2 4 5
Cplusc (457)
Thank you. If I want to this with a vector of vector instead of ifstream in or istringstream how is the syntax?
Last edited on
lastchance (6980)
resabzr wrote:
If I want to this with a vector of vector instead

I doubt that is a good thing to do. However, you could just copy it if you really wanted to (I'm assuming you don't need a node 0).
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
 
#include <iostream>
#include <sstream>
#include <fstream>
#include <set>
#include <map>
#include <vector>
using namespace std;

int main()
{
   map< int,set<int> > nodes;
// ifstream in( "data.txt" );
   istringstream in( "1 2 4 6\n"
                     "2 2 6 5\n"
                     "3 1 3 4\n"
                     "4 1 4 2\n" );   
   
   for( int dummy, a, b, c; in >> dummy >> a >> b >> c; )
   {
       nodes[a].insert( { b, c } );
       nodes[b].insert( { c, a } );
       nodes[c].insert( { a, b } );
   }
   
   vector<vector<int>> V(nodes.rbegin()->first+1);     // make space to number from 0 to the last node number
   for ( int i = 1; i < V.size(); i++ ) V[i] = vector<int>( nodes[i].begin(), nodes[i].end() );
   
   for ( int i = 1; i < V.size(); i++ )
   {
      cout << i << " is connected to ";
      for ( auto n : V[i] ) cout << n << ' ';
      cout << '\n';
   }
}


1 is connected to 2 3 4 
2 is connected to 1 4 5 6 
3 is connected to 1 4 
4 is connected to 1 2 3 6 
5 is connected to 2 6 
6 is connected to 2 4 5




resabzr wrote:
instead of ifstream in or istringstream

Look harder. I'm sure you'll work it out.
Cplusc (457)
I fixed it, thank you.

1
2
3
4
5
6
7
8
9
10
11
 
std::vector<std::vector<int> > vec;

		for (int i=0;i<vec.size();i++ )
		{
			size_t a =vec [i][0];
			size_t b =vec [i][1];
			size_t c =vec [i][2];
			nodes[a].insert({ b, c });
			nodes[b].insert({ c, a });
			nodes[c].insert({ a, b });
		}
jonnin (11437)
I have no idea how that is significantly different from what I said, but ok, glad you got it working :)
Cplusc (457)
Sorry, now I understand what you said at the beginning, I appreciate your time and answer.
Topic archived. No new replies allowed.