Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1110 > unrolled thread

Help with graph theory puzzle solution analysis

Back to article view | Back to comp.programming

Contents

  Help with graph theory puzzle solution analysis Andrew Tomazos <andrew@tomazos.com> - 2011-12-17 14:23 -0800
    Re: Help with graph theory puzzle solution analysis William Elliot <marsh@rdrop.com> - 2011-12-17 20:37 -0800
      Re: Help with graph theory puzzle solution analysis Wes Groleau <Groleau+news@FreeShell.org> - 2011-12-18 00:28 -0500
    Re: Help with graph theory puzzle solution analysis Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-12-17 22:56 -0600

#1110 — Help with graph theory puzzle solution analysis

I was involved in a programming competition recently and one of the
questions was approximately the following...

Let S(N) be the set of all graphs with N verticies and N-1 edges with
the following properties:
- undirected
- connected
- no loop edges (no edge has both ends on same vertex)
- no double edges (any pair of verticies have at most one edge
directly connecting them)

The number of edge ends joined to a vertex is called the vertex's
degree.

We are given an array of scores[] for each possible vertex degree.
(ie scores[k] is the score for a vertex of degree k.)

The score of a graph is the sum of the scores of all its verticies.

Given N and scores[], calculate the maximum possible score of all the
graphs in S(N).

One of the top rated programmers in the world wrote up a very similiar
solution to the following in less a minute...

int solve(int N, int scores[])
{
	int X[110][210];
	memset(X, 0xc0, sizeof(X)); // set X[a][b] all negative

	X[0][0] = 0;

	for (int i = 0; i < N; i++)
		for (int j = 0; j <= N * 2 - 2; j++)
			for (k = 1; k < N; k++)
			{
				int candidate = X[i][j] + scores[k];

				// if candidate is higher than X[i+1][j+k], overwrite it
				if (X[i+1][j+k] < candidate)
					X[i+1][j+k] = candidate;
			}

	return X[N][N*2-2];
}

Clearly they are using some kind of dynamic programming / memoization
technique - but I don't really understand it all.

Can anyone see what precisely X[a][b] holds?  Any what do i, j and k
represent?  What property of graphs are they using for the "optimal
substructure"?

Is this type of solution part of a general class of solutions?  and if
so can anyone recommend a good textbook or site that would cover it?

Thanks,
Andrew.

[toc] | [next] | [standalone]

#1111

On Sat, 17 Dec 2011, Andrew Tomazos wrote:

> I was involved in a programming competition recently and one of the
> questions was approximately the following...
>
> Let S(N) be the set of all graphs with N vertices and N-1 edges with
> the following properties:
> - undirected
> - connected
> - no loop edges (no edge has both ends on same vertex)
> - no double edges (any pair of vertices have at most one edge
> directly connecting them)
>
> The number of edge ends joined to a vertex is called the vertex's
> degree.
>
> We are given an array of scores[] for each possible vertex degree.
> (ie scores[k] is the score for a vertex of degree k.)
>
> The score of a graph is the sum of the scores of all its vertices.
>
> Given N and scores[], calculate the maximum possible score of all the
> graphs in S(N).
>
If both n and the scores are given, then the maximum and only possible 
score is the sum of the scores.  Is the problem to find the maximum score
of a simple (no loops, no double edges, no directed edges) connected graph 
of n-vertices?

The degree of a graph is two times the number of edges
and the maximum number of edges for a simple graph is
a complete simple graph which has n(n - 1)/2 edges.
Thus the maximum degree of a simple connected graph of n
vertices is n^2 - n.

> One of the top rated programmers in the world wrote up a very similar
> solution to the following in less a minute...
>
It appears to be recursive programming, ie a routine that repeatedly calls 
itself until an exit condition is meet.

> int solve(int N, int scores[])
> {
> 	int X[110][210];
> 	memset(X, 0xc0, sizeof(X)); // set X[a][b] all negative
>
> 	X[0][0] = 0;
>
> 	for (int i = 0; i < N; i++)
> 		for (int j = 0; j <= N * 2 - 2; j++)
> 			for (k = 1; k < N; k++)
> 			{
> 				int candidate = X[i][j] + scores[k];
>
> 				// if candidate is higher than X[i+1][j+k], overwrite it
> 				if (X[i+1][j+k] < candidate)
> 					X[i+1][j+k] = candidate;
> 			}
>
> 	return X[N][N*2-2];
> }
>
> Clearly they are using some kind of dynamic programming / memoization
> technique - but I don't really understand it all.
>
> Can anyone see what precisely X[a][b] holds?  Any what do i, j and k
> represent?  What property of graphs are they using for the "optimal
> substructure"?
>
> Is this type of solution part of a general class of solutions?  and if
> so can anyone recommend a good textbook or site that would cover it?
>
> Thanks,
> Andrew.
>

[toc] | [prev] | [next] | [standalone]

#1113

On 12-17-2011 23:37, William Elliot wrote:
> It appears to be recursive programming, ie a routine that repeatedly
> calls itself until an exit condition is meet.

I don't see a call to itself anywhere in it.
Do you mean that it is "unrolled" recursion?

-- 
Wes Groleau

   Be spontaneous … today
   http://Ideas.Lang-Learn.us/BlindDog?itemid=3984

[toc] | [prev] | [next] | [standalone]

#1112

On 12/17/2011 4:23 PM, Andrew Tomazos wrote:
> Can anyone see what precisely X[a][b] holds?  Any what do i, j and k
> represent?  What property of graphs are they using for the "optimal
> substructure"?

The best way to analyze this is to start by seeing the inner loop. Note 
that since k is the index to scores, it is obviously representing the 
degree of a node. In this case, we are comparing scores[k] + X[i][j] to 
X[i+1][j+k]. We're adding the degree to j (note that j goes from 0 to 
2*(N - 1), i.e., to twice the number of edges), so it seems natural to 
assume that X[a][b] refers to the best graph that has a nodes and a 
total "degree" of b.

What the algorithm is doing is building the graph one-by-one from 0 
nodes to N nodes. As it adds a node, it decides what the degree of that 
node should be; it accounts for the total score of the graph.

A side note is that we're effectively only keeping track of the graph by 
the list of node degrees used. This is sufficient, since every 
undirected graph of N - 1 edges must contain at least one tree. If we 
had a cycle in a graph, we could break the cycle and a tree at an edge 
each and piece the things together into a single connected component; 
rinse and repeat until the graph is reduced to a single tree.

In summary:
X[a][b] is the maximum score for a graph with a vertices and total 
degree b; i, j, and k iterate through number of vertices, total degree, 
and new degree respectively.

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web