Creating a directed weighted graph by using a database

Given a database in matrix format:

SeedRandom[6]; mat = RandomInteger[5, {27, 30}]; mat[[1, All]] = {"", a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2,     c3, c4, c5, d1, d2, d3, d4, d5, afd1, afd2, bfd1, bfd2, cfd1, cfd2,    dfd1, dfd2, TD}; mat[[All, 1]] = {"", a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2,     c3, c4, c5, d1, d2, d3, d4, d5, aT, bT, cT, dT, VA, TS}; 

Each row and column has a name, e.g., a1, a2, .... Suppose the following operations on mat.

  1. Drop the columns {a1, a3, b1, b2, c4, c5, d2, d5} and the rows with the same names.
  2. Create a weighted directed graph using the columns {a2, a4, a5, b3, b4, b5, c1, c2, c3, d1, d3, d4} and the rows with the same names.

My question is not about the operations referred to in [1] and [2]. I like to know how to keep the linkage between a string vertex name and a numeric vertex name. String names for the list in [2] are {a2, a4, a5, b3, b4, b5, c1, c2, c3, d1, d3, d4} and the associated numeric names are {2, 4, 5, 8, 9, 10, 11, 12, 13, 16, 18, 19}.

Because my original matrix is large, with the operation in item [1], I lose the linkage between numeric and string names, which I need in later stages of output formatting. For example, I can easily find Cliques with numeric vertex names but I need to know the string names linked to the numeric vertices.

Any suggestion?

A graph database suitable for analyzing a heap snapshot?

It looks like recommendation questions aren’t explicitly OT, so here goes:

I’m working on some tooling for analyzing a dump of the heap of a running program. The dump is just a list of nodes with associated metadata and references to other nodes (possibly-cyclical).

I don’t have any experience with graph databases, and I’m wondering if I would save myself a lot of time by building tooling around a graph DB. So I’m looking for recommendations and pointers to resources, and advice.

Some specific questions:

  • are there any graph databases that have functionality built in for computing a dominator tree? (googling this didn’t seem to get any results)
  • are there any DBs that have tooling for visualizing a huge graph?

How to add the weights to the transition graph of a Markov chain?

The following working program uses Graph and Markov Chain

P = {{1/2, 1/2, 0, 0}, {1/2, 1/2, 0, 0}, {1/4, 1/4, 1/4, 1/4}, {0, 0,     0, 1}}; proc = DiscreteMarkovProcess[3, P]; Graph[proc, GraphStyle -> "DiagramBlue",   EdgeLabels ->    With[{sm = MarkovProcessProperties[proc, "TransitionMatrix"]},     Flatten@Table[DirectedEdge[i, j] -> sm[[i, j]], {i, 2}, {j, 2}]]]  sm = MarkovProcessProperties[proc, "TransitionMatrix"] sm == P 

Since I couldn’t make it work for larger matrices, I clarified in the last two lines that sm is just P. But, if I try to replace sm by P in the first part, all hell breaks loose. So, I tried copy paste changing just P to a larger matrix, but this does not work. Why?

P = {{0, 1/4, 1/2, 1/4, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 1/3, 0, 2/3,      0}, {0, 0, 0, 0, 0, 1},    {0, 0, 1/4, 0, 3/4, 0}, {1/4, 0, 0, 0, 3/4, 0}}; P // MatrixForm proc = DiscreteMarkovProcess[1, P]; Graph[proc,   EdgeLabels ->    With[{sm = MarkovProcessProperties[proc, "TransitionMatrix"]},     Flatten@Table[DirectedEdge[i, j] -> sm[[i, j]], {i, 6}, {j, 6}]]] 

Weird looking ListDensityPlot graph

I am trying to use the following set of data to plot a 3D graph.

data = {{0.1`, -200, 2.47349`}, {0.1`, -180, 2.34881`}, {0.1`, -160,     2.215`}, {0.1`, -140, 2.08`}, {0.1`, -120, 1.93`}, {0.1`, -100,     1.84`}, {0.1`, -80, 1.69`}, {0.1`, -60, 1.53`}, {0.1`, -40,     1.46`}, {0.1`, -20, 1.19`}, {0.1`, 0, 1.62`}, {0.2`, -200,     2.46`}, {0.2`, -180, 2.163`}, {0.2`, -160, 1.95`}, {0.2`, -140,     1.73`}, {0.2`, -120, 1.52`}, {0.2`, -100, 1.36`}, {0.2`, -80,     1.12`}, {0.2`, -60, 0.9078`}, {0.2`, -40, 0.82`}, {0.2`, -20,     0.83`}, {0.2`, 0, 0.948`}, {0.3`, -200, 2.097`}, {0.3`, -180,     1.853`}, {0.3`, -160, 1.53`}, {0.3`, -140, 1.295`}, {0.3`, -120,     1.062`}, {0.3`, -100, 0.875`}, {0.3`, -80, 0.6164`}, {0.3`, -60,     0.4163`}, {0.3`, -40, 0.254`}, {0.3`, -20, 0.196`}, {0.3`, 0,     0.323`}, {0.4`, -200, 1.74`}, {0.4`, -180, 1.42`}, {0.4`, -160,     1.174`}, {0.4`, -140, 0.936`}, {0.4`, -120, 0.749`}, {0.4`, -100,     0.503`}, {0.4`, -80,     0.2565`}, {0.4`, -55, -0.0507`}, {0.4`, -35, -0.2962`}, {0.4`, \ -20, -0.264`}, {0.4`, 0, -0.133`}, {0.5`, -190, 1.3452`}, {0.5`, -170,     1.0393`}, {0.5`, -160, 0.92`}, {0.5`, -140, 0.736`}, {0.5`, -120,     0.45`}, {0.5`, -90,     0.1056`}, {0.5`, -70, -0.1159`}, {0.5`, -50, -0.32422`}, {0.5`, \ -40, -0.419`}, {0.5`, -20, -0.573`}, {0.5`, 0, -0.43`}, {0.6`, -200,     1.183`}, {0.6`, -180, 1.006`}, {0.6`, -170, 0.888`}, {0.6`, -150,     0.653`}, {0.6`, -130, 0.42`}, {0.6`, -100,     0.074`}, {0.6`, -80, -0.149`}, {0.6`, -50, -0.475`}, {0.6`, -40, \ -0.613`}, {0.6`, -10, -0.772`}, {0.6`, 0, -0.6`}, {0.7`, -200,     1.19`}, {0.7`, -165, 0.776`}, {0.7`, -160, 0.717`}, {0.7`, -130,     0.365`}, {0.7`, -110, 0.162`}, {0.7`, -100,     0.0176`}, {0.7`, -70, -0.315`}, {0.7`, -60, -0.432`}, {0.7`, -40, \ -0.672`}, {0.7`, -20, -0.8212`}, {0.7`, 0, -0.66`}, {0, -200,     1.937`}, {0, -180, 1.937`}, {0, -160, 1.937`}, {0, -140,     1.937`}, {0, -120, 1.937`}, {0, -100, 1.937`}, {0, -80,     1.937`}, {0, -60, 1.937`}, {0, -40, 1.937`}, {0, -20, 1.937`}, {0,     0, 1.937`}, {0.7855`, -200, 1.2206`}, {0.7855`, -170,     0.865`}, {0.7855`, -160, 0.745`}, {0.7855`, -140,     0.507`}, {0.7855`, -130, 0.388`}, {0.7855`, -110,     0.152`}, {0.7855`, -80, -0.195`}, {0.7855`, -50, -0.534`}, \ {0.7855`, -40, -0.666`}, {0.7855`, -10, -0.897`}, {0.7855`,     0, -0.609`}, {"", "", ""}, {0.15`, -180, 2.37`}, {"", "",     ""}, {0.15`, -140, 1.93433`}, {0.15`, -120, 1.7464`}, {0.15`, -100,     1.61726`}, {0.15`, -80, 1.41843`}, {"", "", ""}, {"", "",     ""}, {"", "", ""}, {0.15`, 0, 1.29525`}, {0.25`, -200,     2.20387`}, {"", "", ""}, {0.25`, -160, 1.73875`}, {"", "",     ""}, {0.25`, -120, 1.34535`}, {0.25`, -100, 1.10704`}, {0.25`, -80,     0.852466`}, {"", "", ""}, {0.25`, -40, 0.518832`}, {"", "",     ""}, {0.25`, 0, 0.616489`}, {0.05`, -200, 2.17447`}, {0.05`, -180,     2.15766`}, {"", "", ""}, {"", "", ""}, {"", "", ""}, {"", "",     ""}, {0.05`, -80, 1.8539`}, {0.05`, -60, 1.78145`}, {"", "",     ""}, {0.05`, -20, 1.771`}, {0.05`, 0, 1.85024`}}  

However, the final graph is weird (the mesh) enter image description here

It does not work when I increase the InterpolationOrder, and it does not work when I increase the number of data points. What is the problem here? Thank you so much.

Purging SP getting deadlocked with App…Not able to completed understand Deadlock Graph

We have a stored procedure which purges old data. On regular basis, it is getting deadlocked with application stored procedure. Below is the deadlock graph:

Deadlock Graph

Deadlock XML:

<deadlock>   <victim-list>    <victimProcess id="process1a780008c8"/>   </victim-list>   <process-list>    <process id="process1a780008c8" taskpriority="0" logused="1604" waitresource="KEY: 8:72065847945068544 (862c7d05dafc)" waittime="1477" ownerId="4649107786" transactionname="batch_archive" lasttranstarted="2020-12-18T22:05:16.377" XDES="0x27495e1c40" lockMode="U" schedulerid="6" kpid="7560" status="suspended" spid="1049" sbid="0" ecid="4" priority="0" trancount="0" lastbatchstarted="2020-12-18T22:05:01.070" lastbatchcompleted="2020-12-18T22:05:01.070" lastattention="1900-01-01T00:00:00.070" clientapp="SQLAgent - TSQL JobStep (Job 0xAC6E654BCA73184DA4769BFB133908A1 : Step 2)" hostname="SERVER_NAME" hostpid="4024" isolationlevel="read committed (2)" xactid="4649107786" currentdb="6" currentdbname="DB_NAME" lockTimeout="4294967295" clientoption1="673316896" clientoption2="128056">     <executionStack>      <frame procname="DB_NAME.dbo.PURGE_SP_NAME" line="674" stmtstart="45158" stmtend="45440" sqlhandle="0x03000600119b6e78797169003dab000001000000000000000000000000000000000000000000000000000000">  delete from DBNAME..TABLE_NAME with(rowlock) where email_id in      (select email_id from ARCHIVAL_BATCH    </frame>      <frame procname="adhoc" line="6" stmtstart="166" stmtend="566" sqlhandle="0x010006002208560560621cea2000000000000000000000000000000000000000000000000000000000000000">  EXEC @return_value = [dbo].[PURGE_SP_NAME]    @arch_mon_crit = 93,    @batch_size = 3,    @po_sql_code = @po_sql_code OUTPUT,    @po_sql_msg = @po_sql_msg OUTPU    </frame>     </executionStack>     <inputbuf>    DECLARE @return_value int,    @po_sql_code int,    @po_sql_msg nvarchar(2000)    EXEC @return_value = [dbo].[PURGE_SP_NAME]    @arch_mon_crit = 93,    @batch_size = 3,    @po_sql_code = @po_sql_code OUTPUT,    @po_sql_msg = @po_sql_msg OUTPUT    SELECT @po_sql_code as N&apos;@po_sql_code&apos;,    @po_sql_msg as N&apos;@po_sql_msg&apos;    SELECT &apos;Return Value&apos; = @return_value       </inputbuf>    </process>    <process id="process1a93ff7c28" taskpriority="0" logused="10000" waittime="1457" schedulerid="1" kpid="5312" status="suspended" spid="1049" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2020-12-18T22:05:01.070" lastbatchcompleted="2020-12-18T22:05:01.070" lastattention="1900-01-01T00:00:00.070" clientapp="SQLAgent - TSQL JobStep (Job 0xAC6E654BCA73184DA4769BFB133908A1 : Step 2)" hostname="SERVER_NAME" hostpid="4024" loginname="DOMAIN\SQL_SRVC_ACCOUNT" isolationlevel="read committed (2)" xactid="4649107786" currentdb="6" currentdbname="DB_NAME" lockTimeout="4294967295" clientoption1="673316896" clientoption2="128056">     <executionStack>      <frame procname="DB_NAME.dbo.PURGE_SP_NAME" line="674" stmtstart="45158" stmtend="45440" sqlhandle="0x03000600119b6e78797169003dab000001000000000000000000000000000000000000000000000000000000">  delete from DBNAME..TABLE_NAME with(rowlock) where email_id in      (select email_id from ARCHIVAL_BATCH    </frame>      <frame procname="adhoc" line="6" stmtstart="166" stmtend="566" sqlhandle="0x010006002208560560621cea2000000000000000000000000000000000000000000000000000000000000000">  EXEC @return_value = [dbo].[PURGE_SP_NAME]    @arch_mon_crit = 93,    @batch_size = 3,    @po_sql_code = @po_sql_code OUTPUT,    @po_sql_msg = @po_sql_msg OUTPU    </frame>     </executionStack>     <inputbuf>    DECLARE @return_value int,    @po_sql_code int,    @po_sql_msg nvarchar(2000)    EXEC @return_value = [dbo].[PURGE_SP_NAME]    @arch_mon_crit = 93,    @batch_size = 3,    @po_sql_code = @po_sql_code OUTPUT,    @po_sql_msg = @po_sql_msg OUTPUT    SELECT @po_sql_code as N&apos;@po_sql_code&apos;,    @po_sql_msg as N&apos;@po_sql_msg&apos;    SELECT &apos;Return Value&apos; = @return_value       </inputbuf>    </process>    <process id="process1a78191468" taskpriority="0" logused="21516" waitresource="OBJECT: 8:1761441349:4 " waittime="3632" ownerId="4649111643" transactionname="user_transaction" lasttranstarted="2020-12-18T22:05:19.960" XDES="0x208e1d4400" lockMode="IX" schedulerid="5" kpid="7936" status="suspended" spid="332" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2020-12-18T22:05:19.963" lastbatchcompleted="2020-12-18T22:05:19.547" lastattention="1900-01-01T00:00:00.547" clientapp="rx-process_jpid[8344]" hostname="APP_SERVER_NAME" hostpid="0" loginname="DOMAIN\SQL_SRVC_ACCOUNT" isolationlevel="read committed (2)" xactid="4649111643" currentdb="8" currentdbname="DBNAME" lockTimeout="4294967295" clientoption1="673185824" clientoption2="128056">     <executionStack>      <frame procname="DBNAME.dbo.APP_SERVER_NAME1" line="99" stmtstart="3616" stmtend="3868" sqlhandle="0x0300080011c5170b94ab5e01b0a8000001000000000000000000000000000000000000000000000000000000">  INSERT INTO TABLE_NAME_alt ( email_id ,activity_id ,text_content ) VALUES ( @p_email_id ,@p_activity_id ,@p_text_content    </frame>      <frame procname="DBNAME.dbo.APP_SERVER_NAME" line="301" stmtstart="14314" stmtend="15014" sqlhandle="0x0300080012f6881b97ab5e01b0a8000001000000000000000000000000000000000000000000000000000000">  EXEC @v_ret_value = APP_SERVER_NAME1 @p_email_id , @p_activity_id , @p_alias_id , @p_subject , @p_email_date , @p_email_size , @p_num_attachments , @p_charset , @p_message_id , @p_from_email_address , @p_recv_email_address , @p_delete_flag , @p_header , @p_content , @p_content_type , @p_text_content , @v_sql_code OUTPUT , @v_sql_message OUTPU    </frame>      <frame procname="adhoc" line="1" stmtstart="1204" stmtend="1900" sqlhandle="0x0100080051e7691ef0b8d2062300000000000000000000000000000000000000000000000000000000000000">  EXEC @P0 = APP_SP_NAME   @P1  ,  @P2  ,  @P3  ,  @P4  ,  @P5  ,  @P6  ,  @P7  ,  @P8  ,  @P9  ,  @P10  ,  @P11  , &apos;n&apos; , @P12  ,  @P13  ,  @P14  ,  @P15  ,  @P16  ,  @P17  ,  @P18  ,  @P19  ,  @P20 OUT  ,  @P21  ,  @P22  ,  @P23  ,  @P24  ,  @P25  ,  @P26  ,  @P27  ,  @P28  ,  @P29  ,  @P30  ,  @P31  ,  @P32  ,  @P33 OUT  ,  @P34 OU    </frame>      <frame procname="unknown" line="1" sqlhandle="0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000">  unknown    </frame>     </executionStack>     <inputbuf>  (@P0 decimal(38,4) OUTPUT,@P1 bigint,@P2 bigint,@P3 nvarchar(4000),@P4 datetime2,@P5 int,@P6 int,@P7 nvarchar(4000),@P8 nvarchar(4000),@P9 nvarchar(4000),@P10 nvarchar(4000),@P11 nvarchar(4000),@P12 nvarchar(4000),@P13 nvarchar(max),@P14 nvarchar(4000),@P15 nvarchar(4000),@P16 nvarchar(4000),@P17 nvarchar(4000),@P18 nvarchar(4000),@P19 nvarchar(4000),@P20 decimal(38,4) OUTPUT,@P21 int,@P22 int,@P23 bigint,@P24 bigint,@P25 nvarchar(4000),@P26 bigint,@P27 datetime2,@P28 int,@P29 nvarchar(4000),@P30 nvarchar(4000),@P31 nvarchar(4000),@P32 bigint,@P33 decimal(38,4) OUTPUT,@P34 nvarchar(4000) OUTPUT)EXEC @P0 = APP_SP_NAME   @P1  ,  @P2  ,  @P3  ,  @P4  ,  @P5  ,  @P6  ,  @P7  ,  @P8  ,  @P9  ,  @P10  ,  @P11  , &apos;n&apos; , @P12  ,  @P13  ,  @P14  ,  @P15  ,  @P16  ,  @P17  ,  @P18  ,  @P19  ,  @P20 OUT  ,  @P21  ,  @P22  ,  @P23  ,  @P24  ,  @P25  ,  @P26  ,  @P27  ,  @P28  ,  @P29  ,  @P30  ,  @P31  ,  @P32  ,  @P33 OUT  ,  @P34 OUT                                                                           </inputbuf>    </process>   </process-list>   <resource-list>    <keylock hobtid="72065847945068544" dbid="8" objectname="DBNAME.dbo.TABLE_NAME" indexname="TABLE_NAME_IDX" id="lock271c759a00" mode="X" associatedObjectId="72065847945068544">     <owner-list>      <owner id="process1a78191468" mode="X"/>     </owner-list>     <waiter-list>      <waiter id="process1a780008c8" mode="U" requestType="wait"/>     </waiter-list>    </keylock>    <exchangeEvent id="Pipe1d4b680400" WaitType="e_waitPipeGetRow" waiterType="Coordinator" nodeId="12" tid="0" ownerActivity="sentData" waiterActivity="needMoreData" merging="false" spilling="false" waitingToClose="false">     <owner-list>      <owner id="process1a780008c8"/>     </owner-list>     <waiter-list>      <waiter id="process1a93ff7c28"/>     </waiter-list>    </exchangeEvent>    <objectlock lockPartition="4" objid="1761441349" subresource="FULL" dbid="8" objectname="DBNAME.dbo.TABLE_NAME_ALT" id="lock23febd7300" mode="X" associatedObjectId="1761441349">     <owner-list>      <owner id="process1a93ff7c28" mode="X"/>     </owner-list>     <waiter-list>      <waiter id="process1a78191468" mode="IX" requestType="wait"/>     </waiter-list>    </objectlock>   </resource-list>  </deadlock>  

I have just started troubleshooting to fix deadlock. I am not able to get few things in above deadlock graph:

  1. Our Purging SP is a single SP which runs as one transaction, then why we are seeing two processes for it.
  2. What is exchange event? From where it came?
  3. At what level locks are being taken? Row, Page or table?
  4. How to proceed further?

Any help would be appreciated.

NOTE: 1. We are deleting less records batch wise in purging SP.
2. I have removed the actual SP and table Names with Aliases.

Efficiently determining the K shortest paths in a graph

My goal is to efficiently find the $ k$ shortest paths between a source and a destination in an undirected graph. I implemented two solutions of this problem myself, but, as I am very interesting in efficiency, was wondering if there might be a more efficient solution to this problem.

The first solution is based on Yen’s algorithm (https://en.wikipedia.org/wiki/Yen%27s_algorithm):

yen[graph_, source_, destination_, k_] :=    Module[{a, b, gtemp, spurnode, roothpath, sp, roothminusspur,      double, WAmatrix, dirgraph},    a = {FindShortestPath[graph, source, destination]};    b = {};    Do[     Do[      gtemp = graph;      roothpath = a[[-1]][[1 ;; i + 1]];      roothminusspur = Drop[roothpath, -1];      double =        Table[If[         a[[l]][[1 ;; Min[i + 1, Length[a[[l]]]]]] == roothpath,          a[[l]][[i + 1]] \[UndirectedEdge] a[[l]][[i + 2]], {}], {l, 1,          Length[a]}];      gtemp = EdgeDelete[gtemp, Union[Flatten@double]];      gtemp = VertexDelete[gtemp, roothminusspur];      sp = FindShortestPath[gtemp, roothpath[[-1]], destination];      If[Length[sp] > 0,        AppendTo[        b, {GraphDistance[gtemp, roothpath[[-1]], destination],          Flatten@{roothminusspur, sp}}]];      , {i, 0, Length[a[[-1]]] - 2}];     If[Length[b] == 0, Break[],       b = SortBy[Union[b], First];      AppendTo[a, b[[1]][[2]]];      b = Drop[b, 1]];     , {j, 1, k - 1}];    Return[a]    ]; 

The second solution is a bit ugly and can be arbitrary slow, but works quite well on graphs that have a lot of arcs and the weights between these arcs do not differ that much. The idea is to use the build-in FindPath function of Mathematica and increase the costs, until you have indeed found $ k$ or more paths. If you have found more than $ k$ paths, you delete the paths with the most costs:

nmatrix = WeightedAdjacencyMatrix[graph]; maxcosts = Total[nmatrix, 2]; costs = GraphDistance[graph, source, destination]; Do[  paths = FindPath[graph, source, destination, costs + l, All];  If[Length[paths] >= k, costest = costs + l - 1; Break[]],   {l, 0, Round[maxcosts - costs]}]; If[Length[paths] > k,   defpaths = FindPath[graph, source, destination, costest, All];  possiblepaths = Complement[paths, defpaths];  costpaths =    Table[Sum[     nmatrix[[possiblepaths[[j]][[i]]]][[possiblepaths[[j]][[i +           1]]]], {i, Length[possiblepaths[[j]]] - 1}], {j,      Length[possiblepaths]}];  paths = Join[defpaths,     possiblepaths[[Ordering[costpaths][[1 ;; k - Length[defpaths]]]]]];  ]; 

Any hints/suggestions for speed-up techniques or more elegant solutions are more than welcome 🙂

How to mark a point on a graph?

So I’m obtaining the following graph:

graphicDelayZOOM =   LogLinearPlot[GroupDelay /. w -> 2 \[Pi] f, {f, 10, 3000},    PlotRange -> {{100, 3000}, {0.000116, 0.0001201}},    PlotPoints -> 200,    PlotStyle -> {{AbsoluteThickness[1.5], RGBColor[1, 0, 0]}},    GridLines -> Automatic, FrameLabel -> {"f(Hz)", "time"},    Frame -> True, BaseStyle -> {FontFamily -> "Times", FontSize -> 12}] 

enter image description here

Now I want to display the point f1=2000, GroupDelay(f1). Is there any easy way to do it?

Custom layered graph layout

I’d like to write a program to draw a graph taking as an input the size of the layers and the edges of the graph. e.g. For edges={} and Layers={3,3,5,1} I’d expect something like this

I’ve used this code to generate the plot but (i) of course I’m just using the ‘trick’ of coloring the edges the same as the background just to put the vertices where I want them – which it’s computationally expensive to do, especially for bigger numbers of vertices, and (ii) I don’t really know how to specify the edges now.

Layers = {3, 3, 5, 1} // Sort[#, Greater] &; Graph[CompleteGraph[Total[Layers], EdgeStyle -> White], VertexSize -> Large, GraphLayout -> {"MultipartiteEmbedding", "VertexPartition" -> Layers}] 

Then, my question reduces to: (i) Is there a better way to force the size of the layers, and (ii) how to specify the edges within this new layout.