InstantForum.NET v2.9.0SQLServerCentralhttp://www.sqlservercentral.com/Forums/notifications@sqlservercentral.comWed, 22 May 2013 05:48:49 GMT20http://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxHere's my shot at finding the optimal covering vertices for the ski slope graph! It took about 6 minutes to run on my laptop, but I think it lists all optimal solutions. Comments scattered throughout explain it all.[code="sql"]CREATE TABLE #Grid(v1 SMALLINT NOT NULL, CHECK (v1 > 0), v2 SMALLINT NOT NULL, CHECK (v2 > 0), PRIMARY KEY (v1, v2), CHECK (v1 < v2));DECLARE @Edges INT ,@StartTime DATETIME = GETDATE();-- First let's convert the alphabetic vertices of the "ski slope" graph into SMALLINTsWITH SkiSlopeGraph (v1, v2) AS ( SELECT 'A', 'B' UNION ALL SELECT 'A', 'C' UNION ALL SELECT 'A', 'D' UNION ALL SELECT 'B', 'E' UNION ALL SELECT 'B', 'F' UNION ALL SELECT 'C', 'G' UNION ALL SELECT 'C', 'H' UNION ALL SELECT 'D', 'I' UNION ALL SELECT 'D', 'J' UNION ALL SELECT 'E', 'K' UNION ALL SELECT 'F', 'L' UNION ALL SELECT 'G', 'K' UNION ALL SELECT 'G', 'M' UNION ALL SELECT 'H', 'L' UNION ALL SELECT 'I', 'M' UNION ALL SELECT 'J', 'M' UNION ALL SELECT 'K', 'N' UNION ALL SELECT 'K', 'O' UNION ALL SELECT 'L', 'O' UNION ALL SELECT 'M', 'O' UNION ALL SELECT 'O', 'Q' UNION ALL SELECT 'Q', 'R' UNION ALL SELECT 'J', 'P' UNION ALL SELECT 'N', 'Q' UNION ALL SELECT 'N', 'R' UNION ALL SELECT 'P', 'S' UNION ALL SELECT 'P', 'T' UNION ALL SELECT 'Q', 'W' UNION ALL SELECT 'Q', 'U' UNION ALL SELECT 'R', 'U' UNION ALL SELECT 'R', 'V' UNION ALL SELECT 'S', 'V' UNION ALL SELECT 'S', 'R' UNION ALL SELECT 'T', 'V' UNION ALL SELECT 'T', 'Y' UNION ALL SELECT 'U', 'W' UNION ALL SELECT 'U', 'X' UNION ALL SELECT 'V', 'X' UNION ALL SELECT 'V', 'Y' UNION ALL SELECT 'X', 'W' UNION ALL SELECT 'W', 'Z' UNION ALL SELECT 'Y', 'Z')INSERT INTO #GridSELECT CASE WHEN v1 < v2 THEN CHARINDEX(v1, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ') ELSE CHARINDEX(v2, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ') END ,CASE WHEN v1 < v2 THEN CHARINDEX(v2, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ') ELSE CHARINDEX(v1, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ') ENDFROM SkiSlopeGraphSELECT @Edges = @@ROWCOUNT-- Now we count the number of unique vertices (=26)DECLARE @Nodes INT = (SELECT COUNT(*) FROM (SELECT v1 FROM #Grid UNION SELECT v2 FROM #Grid) a)-- And display some resultsSELECT Vertices=@Nodes ,VerticesWith1Edge=ISNULL(( SELECT COUNT(*) FROM ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a(v) GROUP BY v HAVING COUNT(v) = 1) a), 0) ,MaxDegree=( SELECT MAX(c) FROM ( SELECT v, c=COUNT(v) FROM (SELECT v1 FROM #Grid UNION ALL SELECT v2 FROM #Grid) a(v) GROUP BY v) a) ,MinDegree=( SELECT MIN(c) FROM ( SELECT v, c=COUNT(v) FROM (SELECT v1 FROM #Grid UNION ALL SELECT v2 FROM #Grid) a(v) GROUP BY v) a) ,Edges=@Edges ,[SetupTime(MSec)]=DATEDIFF(millisecond, @StartTime, GETDATE())SELECT @StartTime = GETDATE()-- Original solution begins here. The approach is to start by selecting the vertex that-- covers the most other vertices. Subsequent loops each select the next vertex that covers-- the most vertices from those that remain.DECLARE @Covers TABLE (v SMALLINT -- Covering vertice ,vn VARCHAR(8000)) -- Covered verticesWHILE EXISTS ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a (v) EXCEPT SELECT Item FROM @Covers CROSS APPLY DelimitedSplit8K(vn, ','))BEGIN ;WITH Counts AS ( SELECT v, n=COUNT(v) FROM ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a (v) WHERE v NOT IN ( SELECT Item FROM @Covers CROSS APPLY DelimitedSplit8K(vn, ','))) a GROUP BY v) INSERT INTO @Covers --OUTPUT INSERTED.* SELECT v, CAST(a.v AS VARCHAR(5)) + ( SELECT ',' + CASE WHEN v=v2 THEN CAST(v1 AS VARCHAR(5)) ELSE CAST(v2 AS VARCHAR(5)) END FROM #Grid b WHERE a.v = b.v1 OR a.v = b.v2 FOR XML PATH('')) FROM ( SELECT TOP 1 v FROM Counts ORDER BY n DESC, v ) aENDDECLARE @NoOfCoveringVertices INT = (SELECT COUNT(*) FROM @Covers) ,@VerticesCovered INT = ( SELECT COUNT(*) FROM ( SELECT Item FROM @Covers CROSS APPLY DelimitedSplit8K(vn, ',') GROUP BY Item) a) ,@OriginalSolution VARCHAR(8000) = STUFF(( SELECT ',' + RTRIM(v) FROM @Covers ORDER BY CAST(v AS INT) FOR XML PATH('')), 1, 1, '')-- Display some results for the solutionSELECT OriginalSolution=@OriginalSolution ,[SolnRunTime(MSec)]=DATEDIFF(millisecond, @StartTime, GETDATE()) ,VerticesCovered=@VerticesCovered ,NoOfCoveringVertices=@NoOfCoveringVertices ,PctOfVerticesToCover=CAST(100*@NoOfCoveringVertices/(1.*@Nodes) AS DECIMAL(8,2));DECLARE @PossibleOptimalSolutions TABLE (n SMALLINT, SolnNo INT, Soln VARCHAR(8000)); DECLARE @NoPossibleOptimalSolutions INTSELECT @StartTime = GETDATE();-- Now is where it starts to get fun.-- AllVertices simply is a list of all the vertices in the graph.-- UNIQUEnTuples is an rCTE described here: http://www.sqlservercentral.com/articles/sql+n-Tuples/89809/-- It actually uses a slightly performance-improved version late in the discussion thread.-- The rCTE generates all of the n-Tuple combinations up to 1 less than the number of covering-- vertices in the original solution.WITH AllVertices (v) AS ( SELECT v1 FROM #Grid UNION SELECT v2 FROM #Grid), UNIQUEnTuples (n, Tuples, ID) AS ( SELECT 1, CAST(v AS VARCHAR(8000)), v FROM AllVertices UNION ALL SELECT 1 + n.n, CAST(t.v AS VARCHAR(8000)) + ',' + n.Tuples, v FROM UNIQUEnTuples n CROSS APPLY ( SELECT v FROM AllVertices t WHERE t.v < n.ID) t WHERE n < @NoOfCoveringVertices - 1 )INSERT INTO @PossibleOptimalSolutionsSELECT n ,SolnNo=ROW_NUMBER() OVER (PARTITION BY n ORDER BY (SELECT NULL)) ,TuplesFROM UNIQUEnTuplesSELECT @NoPossibleOptimalSolutions=@@ROWCOUNT-- Display some statistics on the generated "potential" solutionsSELECT [No Of Possible "More" Optimal Solutions]=@NoPossibleOptimalSolutions ,[No of Possible Solns w-One Less Covering Vertex]=( SELECT COUNT(*) FROM @PossibleOptimalSolutions WHERE n = @NoOfCoveringVertices - 1) ,[Elapsed Time to Generate Them (MSec)]=DATEDIFF(millisecond, @StartTime, GETDATE())DECLARE @NoSolutions INT = -1SELECT @StartTime = GETDATE();DECLARE @Solutions TABLE (n INT, CoveringVertices VARCHAR(8000))INSERT INTO @SolutionsSELECT @NoOfCoveringVertices, @OriginalSolution-- Now is where it really gets fun. We must validate each of the possible solutions-- to identify any that yield a full cover.WHILE @NoSolutions <> 0BEGIN; WITH CoverVertices AS ( SELECT n, SolnNo, Soln, v=Item FROM @PossibleOptimalSolutions CROSS APPLY DelimitedSplit8K(Soln, ',') WHERE n = @NoOfCoveringVertices - 1), CoveredVertices AS ( SELECT n, SolnNo, Soln, CoverVertex=a.v, CoveredVertex=d.v ,m=ROW_NUMBER() OVER (PARTITION BY n, SolnNo, Soln, d.v ORDER BY (SELECT NULL)) FROM CoverVertices a OUTER APPLY (SELECT v2 FROM #Grid b WHERE a.v = b.v1) b OUTER APPLY (SELECT v1 FROM #Grid c WHERE a.v = c.v2) c CROSS APPLY (VALUES (a.v), (b.v2), (c.v1)) d(v) WHERE d.v IS NOT NULL) INSERT INTO @Solutions SELECT n, Soln FROM CoveredVertices WHERE m = 1 GROUP BY n, SolnNo, Soln HAVING COUNT(*) = @Nodes SELECT @NoSolutions = @@ROWCOUNT SELECT [Tuples Checked]=@NoOfCoveringVertices - 1 ,[Solutions Found]=@NoSolutions ,[Elapsed Time to Check Them (MSec)]=DATEDIFF(millisecond, @StartTime, GETDATE()) SELECT @StartTime = GETDATE(), @NoOfCoveringVertices=@NoOfCoveringVertices - 1END -- WHILE @NoSolutions <> 0-- No need to check further once no solutions are found because-- lower order Tuples will be subsets of the next higher order.-- Display all final solutions - lowest n is optimalSELECT NumberOfVertices=n, CoveringVerticesFROM @SolutionsORDER BY n, CoveringVerticesDROP TABLE #Grid[/code]It yields 29 solutions that contain 7 vertices each. There are no covering solutions with only 6 vertices (it checks). The solution with 8 vertices is what my original solution found and is used as the starting point.[code="plain"]NumberOfVertices CoveringVertices7 1,10,11,12,13,22,237 1,11,12,13,16,21,257 1,11,12,13,16,22,237 1,11,12,13,18,20,237 1,11,12,13,19,20,237 1,11,12,13,19,21,257 1,11,12,13,19,22,237 1,11,12,13,19,23,257 1,11,12,13,20,22,237 1,4,10,11,12,22,237 1,5,12,13,18,20,237 1,9,10,11,12,22,237 1,9,11,12,16,21,257 1,9,11,12,16,22,237 2,3,4,15,18,20,237 2,4,7,12,18,20,237 2,4,8,10,11,22,237 2,8,10,11,13,22,237 2,8,10,13,14,22,237 2,8,9,10,11,22,237 2,8,9,11,16,21,257 2,8,9,11,16,22,237 3,4,6,10,11,22,237 3,6,10,11,13,22,237 3,6,9,10,11,22,237 3,6,9,11,16,21,257 3,6,9,11,16,22,237 4,5,7,12,18,20,237 4,6,8,10,11,22,238 1,11,12,13,16,17,22,26[/code]Letters in the original graphic are mapped to numbers (A=1, B=2, ... Z=26).I don't think I'd want to run this on anything bigger than the 26 vertex graph though! The open question of course is can it be improved upon.Thu, 10 Jan 2013 21:26:29 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]dwain.c (1/10/2013)[/b][hr]BTW. I have an idea on how it might be possible to both prove whether or not the solution arrived at for the ski slope network is optimal, and if it's not to deliver an optimal solution. Working on that.Love this problem![/quote]Rats! Just when I had it working my laptop shut down, not once but twice, and I lost it!Grrrr!!!Thu, 10 Jan 2013 19:20:14 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/10/2013)[/b][hr]I guess you are referring to a tree. [/quote]Not exactly. Trees may be one type of graph that can be solved with it but there are others. If I have some time I'll post a graphic demo.[quote][b]Michael Meierruth (1/10/2013)[/b][hr]In fact, your single query doesn't extract anything for your ski slope data because it's not a tree.[/quote]Correct it would not as there are no "singly connected" vertices in the ski slope network.BTW. I have an idea on how it might be possible to both prove whether or not the solution arrived at for the ski slope network is optimal, and if it's not to deliver an optimal solution. Working on that.Love this problem!Thu, 10 Jan 2013 17:40:03 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxI guess you are referring to a tree.In fact, your single query doesn't extract anything for your ski slope data because it's not a tree.I'm going to dive into this thing as soon as I free myself from some work...Thu, 10 Jan 2013 07:09:58 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxOn the other hand, here is something to ponder upon.[code="sql"]CREATE TABLE #Grid(v1 SMALLINT NOT NULL CHECK (v1 > 0), v2 SMALLINT NOT NULL CHECK (v2 > 0), PRIMARY KEY (v1, v2), CHECK (v1 < v2));INSERT INTO #Grid (v1, v2)VALUES (1, 2), (1, 4), (2, 3), (2, 5), (2, 6); ;WITH SingleConnectedVertices AS ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a(v) GROUP BY v HAVING COUNT(v) = 1), CoveringVertices AS ( SELECT d.v1, d.v2 FROM SingleConnectedVertices a LEFT JOIN #Grid b ON v = b.v1 LEFT JOIN #Grid c ON v = c.v2 CROSS APPLY (VALUES (b.v2, b.v1),(c.v1, c.v2)) d(v1, v2) WHERE d.v1 IS NOT NULL)SELECT v1, CoveredVertices=CAST(v1 AS VARCHAR(5)) + ( SELECT ',' + CAST(v2 AS VARCHAR(5)) FROM CoveringVertices b WHERE a.v1 = b.v1 FOR XML PATH(''))FROM CoveringVertices aGROUP BY v1DROP TABLE #Grid[/code]Here we have a one statement query that delivers the optimal covering set for Joe's original graph. I believe it will deliver the optimal covering set when that set consists of only vertices that are incident to a vertex connected to the graph by a single edge.Unfortunately it is not a general solution. :-)Thu, 10 Jan 2013 06:04:14 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/10/2013)[/b][hr]In your opinion, can an optimal result be obtained with a single query?[/quote]My opinion is that the answer to this is no, because that I do not believe it can even be done with an rCTE. But then again if someone is able to do that, it may just win!Thu, 10 Jan 2013 04:35:52 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]CELKO (1/9/2013)[/b][hr][quote][b]Michael Meierruth (1/7/2013)[/b][hr]Celko,How about me proposing this as a problem in Beyond Relational's TSQL Challenges? There are some very sharp minds there that could come up with something interesting.[/quote]Sure! But again this is a known NP-complete problem.[/quote]Celko, Dwain,My idea of a challenge is to embrace this NP-complete concept whole-heartedly. Thus the result produced by sql must be optimal. Where I am still undecided is whether to restrict the solution to a single query starting with 'select' or 'with' or whether to allow a 'stored procedure' approach. In your opinion, can an optimal result be obtained with a single query?Where this then gets interesting is to discover the maximum number of vertices that can be handled in a reasonable amount of time by the best solution.Thu, 10 Jan 2013 01:34:54 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/9/2013)[/b][hr]In any case, with your data I will try and apply a replication strategy of the data to get a large number of vertices. This will give me an idea of the number of vertices needed such that performance starts to become an issue.[/quote]I was thinking about doing something like this too so I came up with this (already had something to get me started).[code="sql"]CREATE TABLE #Grid(v1 SMALLINT NOT NULL, CHECK (v1 > 0), v2 SMALLINT NOT NULL, CHECK (v2 > 0), PRIMARY KEY (v1, v2), CHECK (v1 < v2));DECLARE @Degree INT = 3 -- Roughly half of the actual graph's max degree ,@Nodes INT = 20 ,@Edges INT;WITH Nodes (node) AS ( SELECT TOP (@Nodes) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM sys.all_columns), Graph (Origin, Destination) AS ( SELECT CASE WHEN n1.node > n2.node THEN n2.node ELSE n1.node END ,CASE WHEN n1.node > n2.node THEN n1.node ELSE n2.node END FROM Nodes n1 CROSS APPLY ( SELECT TOP (@Degree) node=1 + ABS(CHECKSUM(NEWID())) % @Nodes FROM Nodes) n2)INSERT INTO #Grid (v1, v2)SELECT Origin, DestinationFROM ( SELECT Origin, Destination ,n=ROW_NUMBER() OVER (PARTITION BY Origin, Destination ORDER BY (SELECT NULL)) FROM Graph WHERE Origin <> Destination ) aWHERE n = 1SELECT @Edges = @@ROWCOUNTSELECT NoNodes=( SELECT MAX(DISTINCT v) FROM (SELECT v1 FROM #Grid UNION ALL SELECT v2 FROM #Grid) a(v)) ,MaxDegree=( SELECT MAX(c) FROM ( SELECT v, c=COUNT(v) FROM (SELECT v1 FROM #Grid UNION ALL SELECT v2 FROM #Grid) a(v) GROUP BY v) a) ,NoEdges=@EdgesDROP TABLE #Grid[/code]Wed, 09 Jan 2013 21:15:14 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxJoe,Let me ask another question as presumably you've researched this a bit more than me.Identifying the optimal covering vertices is NP-Complete. But is there a formula that utilizes knowledge of the number of vertices and the number of edges to identify the minimum number of vertices expected in an optimal solution?Wed, 09 Jan 2013 20:13:51 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxJoe, there is a bug in your code - not enough columns are defined here.[b]'Vertexes' has more columns than were specified in the column list[/b][b]IT IS VERY HARD TO DEBUG CODE IF IT WILL NOT PARSE[/b]CREATE VIEW Vertexes (v)ASSELECT v1, v_cover FROM GridUNIONSELECT v2, v_cover FROM Grid; You haven't said whether you will accept the use of UDF calls either.. it is very difficult to program a solution when you have not specified what technologies can be used. Are you expecting only ANSI features to be used?It is very difficult to solve a problem when you do not provide clear specifications.Please read any basic book on software engineering and specifications, and try again.:w00t:Wed, 09 Jan 2013 19:52:38 GMTJosh Ashwoodhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/7/2013)[/b][hr]Celko,How about me proposing this as a problem in Beyond Relational's TSQL Challenges? There are some very sharp minds there that could come up with something interesting.[/quote]Sure! But again this is a known NP-complete problem.Wed, 09 Jan 2013 18:19:56 GMTCELKOhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Greg Edwards-268690 (1/9/2013)[/b][hr]My neighbor did some similar - lighting for sports arenas.There were several additional variables - uniform light intensity, eliminate shadows, and placement to not blind the players. An additional constraint was using (for the most part) existing structure and catwalks for placement of light arrays. Choice of lights also became important - as initial cost could be higher, but the right fixtures could save tremendous amounts of energy and maintenance in just a few years.Unfortunately, he had a special program to do this, not that he was doing it in T-SQL.These ended up being pretty complex models, and took sometimes up to a day to run the calculations.Maybe after someone solves this, it gives an idea for round 2.Specs: Formally, a vertex cover of an undirecterd graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. Informally, you have a weird street map and want to put up security cameras at intersections (nodes) in such a way that no street (edge) is not under surveillance.[/quote]Greg,I thought about something like this. Indeed, putting a security camera at a vertex that has 5 edges might have a higher cost than at a vertex with only 2 edges. Now the objective function is different. You'd want to minimize the cost of the cover.Slightly different problem. The more parameters you add to it the more complicated it becomes. As if the base problem isn't complicated enough. :-PWed, 09 Jan 2013 17:50:49 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/9/2013)[/b][hr]dwain,You're right, the original version did not have DESC.I haven't analyzed your code. But is the objective of your code to find an optimal solution?In any case, with your data I will try and apply a replication strategy of the data to get a large number of vertices. This will give me an idea of the number of vertices needed such that performance starts to become an issue.[/quote]Michael,As Joe has pointed out, finding an optimal solution to the problem is NP-Complete, so I would not be so brash as to think I'm smart enough to develop in a very short time an algorithm that is capable of finding it. I just wanted to give it a try and to see if I could come up with a reasonably good solution.Wed, 09 Jan 2013 17:25:34 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxdwain,You're right, the original version did not have DESC.I haven't analyzed your code. But is the objective of your code to find an optimal solution?In any case, with your data I will try and apply a replication strategy of the data to get a large number of vertices. This will give me an idea of the number of vertices needed such that performance starts to become an issue.Wed, 09 Jan 2013 07:15:58 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxMy neighbor did some similar - lighting for sports arenas.There were several additional variables - uniform light intensity, eliminate shadows, and placement to not blind the players. An additional constraint was using (for the most part) existing structure and catwalks for placement of light arrays. Choice of lights also became important - as initial cost could be higher, but the right fixtures could save tremendous amounts of energy and maintenance in just a few years.Unfortunately, he had a special program to do this, not that he was doing it in T-SQL.These ended up being pretty complex models, and took sometimes up to a day to run the calculations.Maybe after someone solves this, it gives an idea for round 2.Specs: Formally, a vertex cover of an undirecterd graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. Informally, you have a weird street map and want to put up security cameras at intersections (nodes) in such a way that no street (edge) is not under surveillance.Wed, 09 Jan 2013 06:39:19 GMTGreg Edwards-268690http://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/9/2013)[/b][hr]Nice graph. It looks like ski slopes seen from high above.In any case, had to change your @Covers table declaration from v SMALLINT to v CHAR(1). No problem.But the solution I get is different from yours. How do you explain this?[code="other"]Q Q,N,O,R,U,WV V,R,S,T,X,YK K,E,G,N,OM M,G,I,J,OA A,B,C,DL L,F,H,OP P,J,S,TZ Z,W,Y[/code][/quote]I may have played around with the sort ordering near the end of the WHILE loop. Does yours look like this?[code="sql"] SELECT TOP 1 v FROM Counts ORDER BY n DESC, v DESC) a[/code]In the original version I don't think I had DESC on v. That could account for the difference. Interesting that it should be more optimal one way than the other. Wonder if that could be exploited in some way (assuming this is the issue).Wed, 09 Jan 2013 06:26:11 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxNice graph. It looks like ski slopes seen from high above.In any case, had to change your @Covers table declaration from v SMALLINT to v CHAR(1). No problem.But the solution I get is different from yours. How do you explain this?[code="other"]Q Q,N,O,R,U,WV V,R,S,T,X,YK K,E,G,N,OM M,G,I,J,OA A,B,C,DL L,F,H,OP P,J,S,TZ Z,W,Y[/code]Wed, 09 Jan 2013 05:05:32 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxHere's another network you can validate it on, assuming you want to manually calculate the optimal cover (from the 3rd article in my signature line).[IMG]http://i1252.photobucket.com/albums/hh569/dwaincamps/TransportationNetwork.jpg[/IMG]Here's the setup data (note where the CHECK constraint has been removed because originally this was designed as a directed graph so the vertex traversal can go from larger to smaller).[code="sql"]CREATE TABLE #Grid(v1 CHAR(1) NOT NULL, -- CHECK (v1 > 0), v2 CHAR(1) NOT NULL, -- CHECK (v2 > 0), PRIMARY KEY (v1, v2)--, --CHECK (v1 < v2));INSERT INTO #GridSELECT 'A', 'B'UNION ALL SELECT 'A', 'C'UNION ALL SELECT 'A', 'D'UNION ALL SELECT 'B', 'E'UNION ALL SELECT 'B', 'F'UNION ALL SELECT 'C', 'G'UNION ALL SELECT 'C', 'H'UNION ALL SELECT 'D', 'I'UNION ALL SELECT 'D', 'J'UNION ALL SELECT 'E', 'K'UNION ALL SELECT 'F', 'L'UNION ALL SELECT 'G', 'K'UNION ALL SELECT 'G', 'M'UNION ALL SELECT 'H', 'L'UNION ALL SELECT 'I', 'M'UNION ALL SELECT 'J', 'M'UNION ALL SELECT 'K', 'N'UNION ALL SELECT 'K', 'O'UNION ALL SELECT 'L', 'O'UNION ALL SELECT 'M', 'O' UNION ALL SELECT 'O', 'Q'UNION ALL SELECT 'Q', 'R'UNION ALL SELECT 'J', 'P'UNION ALL SELECT 'N', 'Q'UNION ALL SELECT 'N', 'R'UNION ALL SELECT 'P', 'S'UNION ALL SELECT 'P', 'T'UNION ALL SELECT 'Q', 'W'UNION ALL SELECT 'Q', 'U'UNION ALL SELECT 'R', 'U'UNION ALL SELECT 'R', 'V'UNION ALL SELECT 'S', 'V'UNION ALL SELECT 'S', 'R'UNION ALL SELECT 'T', 'V'UNION ALL SELECT 'T', 'Y'UNION ALL SELECT 'U', 'W'UNION ALL SELECT 'U', 'X'UNION ALL SELECT 'V', 'X'UNION ALL SELECT 'V', 'Y'UNION ALL SELECT 'X', 'W'UNION ALL SELECT 'W', 'Z'UNION ALL SELECT 'Y', 'Z'[/code]My solution should return these covers:[code="plain"]V V,R,S,T,X,YQ Q,N,O,R,U,WM M,G,I,J,OK K,E,G,N,OP P,J,S,TL L,F,H,OD D,A,I,JC C,A,G,HB B,A,E,FZ Z,W,Y[/code]Tue, 08 Jan 2013 17:50:45 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/8/2013)[/b][hr]Just looking at this sample data leads me to believe that a good approach is to select vertices with the most edges first.[/quote]Obviously I agree with this as that's the approach I used. :-DThere will probably be cases though, where this only leads to a good but suboptimal solution. It would be a factor of a "look ahead" to see if choosing the maximum coverage on this pass is worse than the final result of chossing a less-than-maximum coverage now, so as to arrive at a better solution down the line. Kinda like a chess game. The optimal next move is determined by the depth of look ahead. What looks like a great move at 2 levels of lookahead could lead to getting checkmated if you look ahead 4 moves.BTW. Thanks for validating diamondgm's solution (and mine). I was meaning to but didn't get around to it.Tue, 08 Jan 2013 17:32:36 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote]When I was playing around with adding the additional column into the table, I chose to make all the vertices be a CHAR data type instead of SMALLINT. The reason being is that you're not likely to perform math (or would you?) on the identifier of a vertex., [/quote]Agreed; I did numeric because the book I was using numbered the nodes, and fell into that notation. I cannot imagine any math on them.Tue, 08 Jan 2013 10:24:05 GMTCELKOhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]diamondgm (1/7/2013)[/b][hr]I've never seen this problem, so I'm not even sure if I am solving it correctly.This code is probably quite inefficient, but I THINK it solves the Min Cover problem?Scuze the messiness, I'm at work and did it in a rush :-P[/quote]diamondgm,For the arbitrary data below your code produces a solution with 11 vertices. Dwain's code produces a solution with 6 vertices (and which is correct). Thus, by definition, yours is not a min cover solution. Dwain's solution looks to be min cover (but still checking that).values (1,2),(2,3),(3,4),(4,15),(14,15),(4,9),(9,13),(9,10),(10,12),(10,11),(7,11),(7,8),(8,9),(6,7),(5,6),(5,8),(4,5)Just looking at this sample data leads me to believe that a good approach is to select vertices with the most edges first.Tue, 08 Jan 2013 06:48:19 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxFor a challenge like this the requirement would be to find the optimal solution(s).For the perfomance test a sufficiently large number of vertices would be used such that the cpu time would not exceed 60 seconds for the best solution. Any solution exceeding 5 minutes would be eliminated. To prevent 'cheating' there would be two performance tests, one for which the data is made public before hand and one where the data is not made public until the challenge has been closed.Tue, 08 Jan 2013 03:43:57 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]Michael Meierruth (1/7/2013)[/b][hr]Celko,How about me proposing this as a problem in Beyond Relational's TSQL Challenges? There are some very sharp minds there that could come up with something interesting.[/quote]I would be interested to know how you would judge such a competition. Speed is important but so is a "nearer optimal" solution.I've seen this in bin packing solutions, where you usually have to trade off speed for better bin utilization.Tue, 08 Jan 2013 02:56:27 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxI see two approaches:1. going from all vertices selected to a solution (top-down)2. going from no vertices selected to a solution (bottom-up)In both cases you will eventually run into a number of vertices where you will not arrive at a solution in a reasonable amount of time, i.e. you cannot traverse the full search tree. This is where you would need to apply an algorithm that uses a random approach and provides the best solution found within a given amount of time. It will not necessarily be the theoretically best solution.The random approach is divided into two (given N vertices):1. starting with K = N-1 generate all combinations K of N vertices and check for coverage; once a solution is found for given combination stop and decrease K by one and repeat; stop this when the number of combinations exceeds some threshold;2. generate K random vertices and check if it is a solution; if not then repeat; if yes then decrease K by 1 and repeat;Stop when exceeding a given time threshold.Now let me think about how to map this into an SQL approach...:w00t:Tue, 08 Jan 2013 02:37:43 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxJoe,When I was playing around with adding the additional column into the table, I chose to make all the vertices be a CHAR data type instead of SMALLINT. The reason being is that you're not likely to perform math (or would you?) on the identifier of a vertex.This also eliminates the need for the CASTs in the solution I did provide (presumably making it just a tad faster).Not sure why I couldn't get my version with the additional column to work. Well, actually it did work but it wasn't providing "as optimal" a solution as the solution I have posted using the TABLE VARIABLE. I'll probably try again at some point when I have some time, because even though it wasn't as optimal it was faster as I expected it might be.Mon, 07 Jan 2013 17:38:33 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote]I've never seen this problem, so I'm not even sure if I am solving it correctly. This code is probably quite inefficient, but I THINK it solves the Min Cover problem? [/quote]It is an NP-Complete problem. NOBODY has an efficient answer. I just thought it might be fun. I would add a bit more to my posting to get use some tools: [code="sql"]CREATE TABLE Grid(v1 SMALLINT NOT NULL CHECK (v1 > 0), v2 SMALLINT NOT NULL CHECK (v2 > 0), v_cover SMALLINT DEFAULT 0 NOT NULL,PRIMARY KEY (v1, v2), CHECK (v1 < v2));INSERT INTO Grid (v1, v2)VALUES (1, 2), (1, 4), (2, 3), (2, 5), (2, 6); CREATE VIEW Vertexes (v)ASSELECT v1, v_cover FROM GridUNIONSELECT v2, v_cover FROM Grid; CREATE VIEW Vertex_Degrees (v, degree)ASSELECT V.v, COUNT(*) AS degree FROM Grid AS G, Vertexes AS V WHERE V.v IN (G.v1, G.v2) GROUP BY V.v;[/code]If you make the vertex cover flag a SMALLINT, then we can play games with it. We probably use the degree for a greedy algorithms. Mon, 07 Jan 2013 12:51:54 GMTCELKOhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxCelko,How about me proposing this as a problem in Beyond Relational's TSQL Challenges? There are some very sharp minds there that could come up with something interesting.Mon, 07 Jan 2013 08:29:54 GMTMichael Meierruthhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxI've never seen this problem, so I'm not even sure if I am solving it correctly.This code is probably quite inefficient, but I THINK it solves the Min Cover problem?Scuze the messiness, I'm at work and did it in a rush :-P[code="sql"]USE tempdbGOIF OBJECT_ID('tempdb.dbo.Grid') IS NOT NULL DROP TABLE GridDECLARE @MinCover TABLE (Node INT)DECLARE @Node INTCREATE TABLE dbo.Grid( v1 INT ,v2 INT ,Processed BIT);INSERT INTO Grid (v1, v2, Processed)VALUES (1, 2, 0), (1, 4, 0), (2, 3, 0), (2, 5, 0), (2, 6, 0); WHILE EXISTS (SELECT * FROM Grid WHERE Processed = 0)BEGIN ;WITH NodeOcc AS ( SELECT Node = v1 FROM Grid UNION ALL SELECT v2 FROM Grid ) INSERT INTO @MinCover SELECT TOP 1 Node FROM NodeOcc WHERE Node NOT IN (SELECT Node FROM @MinCover) GROUP BY Node ORDER BY COUNT(*) DESC UPDATE G SET Processed = 1 FROM Grid G JOIN @MinCover NN ON G.v1 = NN.Node OR G.v2 = NN.NodeENDSELECT *FROM @MinCover[/code]Mon, 07 Jan 2013 05:06:13 GMTdiamondgmhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxSeems I couldn't get my second solution to work so I withdrew it.For now, I only have the one option for you, which I made a slight correction to above.Sun, 06 Jan 2013 23:47:24 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxMy apologies. Apparently I posted some buggy code!I have fixed the first solution. Now working on the second.Sun, 06 Jan 2013 20:35:46 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxOriginally my second solution... withdrawn because I couldn't get it working correctly.Sun, 06 Jan 2013 19:48:57 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]CELKO (1/6/2013)[/b][hr]I can offer on one my books at prize! I will send a rare UN-autographed copy so the winner can take it to B&N, claim they lost the sales slip and get cash! [/quote]I'll take one of the not-so-rare autographed ones as long as you pick up the shipping to Thailand. :-PSun, 06 Jan 2013 19:31:32 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote]Probably not an optimal solution but I think this will work. [/quote]No "probably" about it; this is an NP-complete problem so we know that the best we can do is to get some answer that looks better than the other ones we found in a reasonable time. [quote] Let the performance competition begin. :-D [/quote]I can offer on one my books at prize! I will send a rare UN-autographed copy so the winner can take it to B&N, claim they lost the sales slip and get cash! [quote] Could I alter your original table's structure? I'm thinking that if you add a "Covered" column the algorithm could be made more efficient by marking a vertex [sic: edge, not vertex] as covered once it is.[/quote]Sure; 80-95% of the work in SQL is in the DDL! There is a greedy algorithm that does this kind of marking; it is known to be between optimal and "twice optimal" set sizes. Sun, 06 Jan 2013 19:24:41 GMTCELKOhttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspx[quote][b]CELKO (1/5/2013)[/b][hr]{1, 2, 6} and {2, 4} are vertex covers. The second is the minimal cover. Can you prove it in SQL? How would you look for a cover? My first thought is grab random subset of (n) nodes and test them – brute force. [/quote]Instead of choosing a random subset of nodes, my loop solution selects the vertex remaining that has the most coverage.Sun, 06 Jan 2013 19:17:50 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxProbably not an optimal solution but I think this will work.[code="sql"]CREATE TABLE #Grid(v1 SMALLINT NOT NULL CHECK (v1 > 0), v2 SMALLINT NOT NULL CHECK (v2 > 0), PRIMARY KEY (v1, v2), CHECK (v1 < v2));INSERT INTO #Grid (v1, v2)VALUES (1, 2), (1, 4), (2, 3), (2, 5), (2, 6); DECLARE @Covers TABLE (v SMALLINT -- Covering vertex ,vn VARCHAR(8000)) -- Covered verticesWHILE EXISTS ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a (v) EXCEPT SELECT Item FROM @Covers CROSS APPLY DelimitedSplit8K(vn, ','))BEGINWHILE EXISTS ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a (v) EXCEPT SELECT Item FROM @Covers CROSS APPLY DelimitedSplit8K(vn, ','))BEGIN ;WITH Counts AS ( SELECT v, n=COUNT(v) FROM ( SELECT v FROM #Grid CROSS APPLY (VALUES (v1),(v2)) a (v) WHERE v NOT IN ( SELECT Item FROM @Covers CROSS APPLY DelimitedSplit8K(vn, ','))) a GROUP BY v) INSERT INTO @Covers --OUTPUT INSERTED.* SELECT v, CAST(a.v AS VARCHAR(5)) + ( SELECT ',' + CASE WHEN v=v2 THEN CAST(v1 AS VARCHAR(5)) ELSE CAST(v2 AS VARCHAR(5)) END FROM #Grid b WHERE a.v = b.v1 OR a.v = b.v2 FOR XML PATH('')) FROM ( SELECT TOP 1 v FROM Counts ORDER BY n DESC, v) aENDENDSELECT * FROM @CoversDROP TABLE #Grid[/code]Best I could do on short notice. :cool:Let the performance competition begin. :-DA question to you Joe. Could I alter your original table's structure? I'm thinking that if you add a "Covered" column the algorithm could be made more efficient by marking a vertex as covered once it is.Sun, 06 Jan 2013 18:23:00 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxLet's make that Wiki article a bit more accessible: [url]http://en.wikipedia.org/wiki/Vertex_covering[/url] while I work on it. :-DSun, 06 Jan 2013 17:29:46 GMTdwain.chttp://www.sqlservercentral.com/Forums/Topic1403293-392-1.aspxI have to do a book chapter on graph database. I already did “The Kevin Bacon” problem in SQL for a graph-base product company, so i wanted another one to demonstrate how these things work. The problem I picked is “Vertex covering” (http://en.wikipedia.org/wiki/Vertex_covering), which is known to be NP-complete and the best algorithms for it have an upper bound of twice the size. In short, it sounds easy but it is not. Anyone want to play with it in SQL? Specs: Formally, a vertex cover of an undirecterd graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. Informally, you have a weird street map and want to put up security cameras at intersections (nodes) in such a way that no street (edge) is not under surveillance. Here is a simple table and a simple five edge graph, taken from the Wikipedia article just referenced. CREATE TABLE Grid(v1 SMALLINT NOT NULL CHECK (v1 > 0), v2 SMALLINT NOT NULL CHECK (v2 > 0), PRIMARY KEY (v1, v2), CHECK (v1 < v2));INSERT INTO Grid (v1, v2)VALUES (1, 2), (1, 4), (2, 3), (2, 5), (2, 6); {1, 2, 6} and {2, 4} are vertex covers. The second is the minimal cover. Can you prove it in SQL? How would you look for a cover? My first thought is grab random subset of (n) nodes and test them – brute force. The obvious limitations are that [i]all[/i] the vertices is a cover but not minimal, and that the [i]empty set[/i] is not a cover until the graph is empty. Sat, 05 Jan 2013 16:13:16 GMTCELKO