Graph Question

This is a discussion on Graph Question within the C Programming forums, part of the General Programming Boards category; Hey guys, I have a graph that I need to store and do some work on the nodes. The question ...

  1. #1
    PhysicistTurnedProgrammer Cell's Avatar
    Join Date
    Jan 2009
    Location
    New Jersey
    Posts
    72

    Graph Question

    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.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.

  3. #3
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126

    Wink Structures

    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)
    Mac OS 10.6 Snow Leopard : Darwin

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by nacho4d View Post
    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):
    Code:
    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.

  5. #5
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  6. #6
    PhysicistTurnedProgrammer Cell's Avatar
    Join Date
    Jan 2009
    Location
    New Jersey
    Posts
    72
    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.

  7. #7
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  8. #8
    PhysicistTurnedProgrammer Cell's Avatar
    Join Date
    Jan 2009
    Location
    New Jersey
    Posts
    72
    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:

    Code:
    	
    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.

  9. #9
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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:

    Code:
    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.
    Last edited by Snafuist; 03-19-2009 at 04:28 PM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  10. #10
    PhysicistTurnedProgrammer Cell's Avatar
    Join Date
    Jan 2009
    Location
    New Jersey
    Posts
    72
    Hey Snafuist, thanks for sticking with this thread.

    Quote Originally Posted by Snafuist View Post
    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?


    Quote Originally Posted by Snafuist View Post
    But there's no need to introduce ten names Node1, Node2, and so on; simply use a 2D array:

    Code:
    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.

    Quote Originally Posted by Snafuist View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 01:14 PM
  2. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 10:47 PM
  4. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 04:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21