Graph Question

[Cell]

Hey guys,

I have a graph that I need to store and do some work on the nodes. The question I'm going to ask it pretty broad, and will most likely have many answers, in which case I will give more details.

What is the best way to store this graph? It has 9 nodes.

Thanks.

[EVOEx]

It depends on what algorithms you're going to use and whether there will be a lot of edges or only a few.

Usually, it's best to have an array of, in your case, 9 items. Every item here is an array of dynamic size. Let's say the index to the first array is A and then array[A][0] == B, then this means there is an edge from A to B. If it's a weighted graph, array[A][0] could be a structure with weight and B.

Another common, albeit less so, is to have a 2-dimensional array of 9 by 9 items, where array[A][B] is 1 (or the edge's weight) if there is an edge and 0 if there is no edge. This should be used for, for instance, floyd-warshall.

[nacho4d]

I would strongly recommend the use of a structure array.
If you are working with nodes it means that you have a tree right? ... Maybe the best way to do it is by creating a structure that has a pointer to the parent node structure and children nodes structure and offcourse the information about this node (weight, etc).

Using an 2d matrix (as is was suggested before) is also good but using pointers and structures is much more efficient when you work when nodes. (But it might be a little bit difficult also)

[EVOEx]

I would strongly recommend the use of a structure array.
If you are working with nodes it means that you have a tree right? ... Maybe the best way to do it is by creating a structure that has a pointer to the parent node structure and children nodes structure and offcourse the information about this node (weight, etc).

Using an 2d matrix (as is was suggested before) is also good but using pointers and structures is much more efficient when you work when nodes. (But it might be a little bit difficult also)

What would be wrong with something like this (note: C++, too lazy to write it in C):

int num_nodes;
cin >> num_nodes;

vector< vector<int> > edges(num_nodes);
for(int i = 0; i < num_nodes; i++) {
int a, b;
cin >> a >> b;
edges[a].push_back(b);
}

I've used this a lot and a lot of algorithms work perfectly using that.

[Snafuist]

The optimal representation depends on the algorithms that you want to use.

Example:
Assume you have a set of edges. If you want to find out whether this is a path from node a to node b, an incidence matrix or adjacency matrix are perfectly fine. If you want to find out whether this is the shortest path possible, a representation using structures with node pointers will be better suited.

So... look up incidence matrix and adjacency matrix. It allows node access in constant time (in contrast to the approach suggested above), maybe this is all you need. For more advanced algorithms to perform efficiently, you will probably need a representation using pointers.

What is your overall goal?

Greets,
Philip

[Cell]

My goal is that I am trying to create a two-way balanced partition. I am trying to figure out the minimum cutset, so I have chosen to use the Lin-Kernighan algorithm.

I have an algorithm in mind - however, I need to find a simple way to store each node.

The idea I've had thus far is to create a connection matrix which will show the vertices that connect each edge.

So, I have a 9x9 matrix. I was thinking of making each row a separate array. I can then search through each array to find the amount of internal & external connections, which is required by my algorithm.

Does this logic sound reasonable?

Thanks.

[Snafuist]

I'm not sure what you mean by "two-way balanced partition", but this may be due to my poor English skills. What is it?

Note that Lin-Kernighan uses heuristics. For a graph with 9 nodes, you may very well use an exact algorithm. For background knowledge about cuts, have a look at Menger's Theorem and its most important corollary, the Max-Flow-Min-Cut Theorem. There are about 27 million algorithms to compute cuts, maybe there are some that compute cuts which result in "two-way balanced partitions".

If I were you, I'd probably use brute force and see whether it's fast enough. Fancy algorithms are slow when n is small, and your n is most probably small.

Greets,
Philip

[Cell]

It's basically a balanced graph. I should mention that I had the number of nodes wrong - there are 10. So I'd need to produce 2 separate groups of 5 with the minimum amount of cuts to the vertices of my graph.

I see what you're saying about fancy algorithms - truth be told, I can look at this graph and see the solution. But this is for a course, and we were given a very small selection of algorithms to choose from. So I'm going with L-K.

The idea I had was something like this:

	
Node1[10] =  {edges..};  
Node2[10] =  {edges..}; 
.. ETC ...
Node10[10] =  {edges..};

And thus I can examine each node and the edges attached to it.

For example, in the L-K algorithm, there is a step where I need to look within my initial partitions and figure out the internal and external connections of each node. I would be able to easily do this now because of the way I have it set up.

What do you think?

I guess the reason for my post is that I have never implemented a complicated algorithm like this before and I do not want to shoot myself in the foot by oversimplifying how I enter the graph into my code.

[Snafuist]

It's not clear to me what you want to store in the Node*-arrays. I'd use integers and set NodeX[Y] to 0 if there's no edge between X and Y and 1 if there is. This is called an adjacency matrix (which actually stores the number of edges between two nodes, but I'm assuming that your edges are pairwise distinct and that two nodes are connected by at most one edge). This allows constant time checks for edges.

But there's no need to introduce ten names Node1, Node2, and so on; simply use a 2D array:

int graph[10][10];

Then graph[u][v] == 0 iff (u+1,v+1) is not an edge of your graph. You can use values != 0 to denote the state of an edge, e.g. edge is there, edge is temporarily removed, edge is permanently removed.

Note that if your graph is undirected, then graph[u][v] == graph[v][u], so you may use the upper half of the matrix for the graph and the lower half to store (temporary) results.

Also note that this approach is bad for large graphs, but for an exercise sheet, it will be fine.

Greets,
Philip

PS: for a more in-depth experience, read http://www.dcs.warwick.ac.uk/~harry/...on_journal.pdf. If you set the capacity of each edge to 1 and set k=2, then this algorithm computes a cut which partitions the graph into two subsets of equal size, whose cut is minimal. As far as I can understand, this is what you want to do.

[Cell]

Hey Snafuist, thanks for sticking with this thread.

It's not clear to me what you want to store in the Node*-arrays. I'd use integers and set NodeX[Y] to 0 if there's no edge between X and Y and 1 if there is. This is called an adjacency matrix (which actually stores the number of edges between two nodes, but I'm assuming that your edges are pairwise distinct and that two nodes are connected by at most one edge). This allows constant time checks for edges.

Yes, this is exactly the case. I am storing the edges as integers into something I was calling a 'connectivity matrix', which I believe is exactly what you are talking about.

I was calling each row of the adjacency matrix a node. I was doing this because the L-K algorithm requires that I figure out the internal and external connections for each node within their initial partition.

For example:

The first row of the adjacency matrix is the first Node in the graph:

A1[0, 0, 1, 0, 0, 1]

Now, the way this graph is initially split is that array positions 0, 1, and 2 are part of partition 1 and positions 3, 4, and 5 are part of partition 2.

So I search each row by partition, as it were - the first half and the second half.

For some reason, it just seems easier to me to do it in terms of rows. This is probably due to my inexperience in this area.

It seems to me that if I make this matrix a 2D array, I'd get swallowed up in the searching I need to do on each partition of each node (array).

Do you see what I'm saying?

But there's no need to introduce ten names Node1, Node2, and so on; simply use a 2D array:

int graph[10][10];

Then graph[u][v] == 0 iff (u+1,v+1) is not an edge of your graph. You can use values != 0 to denote the state of an edge, e.g. edge is there, edge is temporarily removed, edge is permanently removed.

Note that if your graph is undirected, then graph[u][v] == graph[v][u], so you may use the upper half of the matrix for the graph and the lower half to store (temporary) results.

I see what you are saying here. I am just worried about how I'd begin to search in the method I need to as I outlined above.

PS: for a more in-depth experience, read http://www.dcs.warwick.ac.uk/~harry/...on_journal.pdf. If you set the capacity of each edge to 1 and set k=2, then this algorithm computes a cut which partitions the graph into two subsets of equal size, whose cut is minimal. As far as I can understand, this is what you want to do.

Thanks for the article! I will read this tonight.