Wolfram Cloud Document

ABSTRACT (original article): Driven by applications in the natural, social and computer sciences several algorithms have been proposed to enumerate all sets

X⊆V

of vertices of a graph

G=(V,E)

that induce a connected subgraph. We offer two algorithms for enumerating all

’s that induce (more exquisite) metric subgraphs. Specifically, the first algorithm, called AllMetricSets, generates these

’s in a compressed format. The second algorithm generates all (accessible) metric sets one-by-one but is provably output-polynomial. Mutatis mutandis the same holds for the convex sets

X⊆V

, where “convex” is a natural strengthening of “metric”. The Mathematica command BooleanConvert features prominently. CITATION (original article): Marcel Wild (2024), Compression with wildcards: All induced metric subgraphs, arXiv:2409.08363. https://doi.org/10.48550/arXiv.2409.08363

For random graphs gr all induced metric (or convex) subgraphs of cardinality

<=k

are produced. The algorithm is compared with an approach (called BConvert) that uses BooleanConvert. For details see my article (v2) in the arXiv : “Compression with wildcards: All metric induced subgraphs” .

Read in all the subroutines below, then follow the steps FIRST, ... SIXTH in this order (some steps not being mandatory)

FIRST (mandatory): Generate some random (or hand - typed) graph gr:

Choose number of vertices .

w=25;

Complement out exactly TWO of these THREE groups - of - lines in order to get a general graph, resp. tree, resp. GridGraph:

ka=90;(*choosenumberofedges(applicableonlyinthisgroup-of-lines)*)While[True,gr=RandomGraph[{w,ka},VertexLabels"Name"];If[ConnectedGraphQ[gr],Break[];];];(*While[True,GR=RandomGraph[{w,w+10},VertexLabels"Name"];gr=FindSpanningTree[GR];If[ConnectedGraphQ[gr],Break[];];];nl=Count[VertexDegree[gr],1];Print["so many leaves in the tree gr: ",nl];*)(*gr=GridGraph[{2,2,3,5},VertexLabels"Name"];(*makesuretheproductofthecomponentsequalsw*)*)

Visualization of gr

Out[]=

SECOND (A) (not mandatory): Count all (unbounded) connected and metric sets brute - force:

GDM=GraphDistanceMatrix[gr];Conn=Metr=0;Timing[Do[X=Subsets[Range[w],All,{i}][[1]];If[ConnectedGraphQ[Subgraph[gr,X]],Conn=Conn+1;If[IsItMetricQ[X],Metr=Metr+1;];];(*possiblycomplementthatlineout:*)If[Mod[i,20000]==333,Print[i," ",Conn," ",Metr];];,{i,2^w}];]Print["So many vertex-sets were connected: ",Conn];Print["So many vertex-sets were metric: ",Metr];

SECOND (B) (not mandatory): Estimate the numbers of connected, respectively metric sets of gr with cardinality <= k (based on 10000 random sets of vertices).

k=8;GDM=GraphDistanceMatrix[gr];ConnAmong10000=MetricAmong10000=0;SBC=Sum[Binomial[w,i],{i,0,k}];(*Print["SBC=",SBC];*)Timing[Do[RI=RandomInteger[{1,SBC}];X=Subsets[Range[w],k,{RI}][[1]];If[ConnectedGraphQ[Subgraph[gr,X]],ConnAmong10000=ConnAmong10000+1;If[IsItMetricQ[X],MetricAmong10000=MetricAmong10000+1;];];,{i,10000}];]Print["So many out of 10000 random k-bounded vertexsets were connected: ",ConnAmong10000];Print["So many out of 10000 random k-bounded vertexsets were metric: ",MetricAmong10000];

Out[]=

{4.65625,Null}

So many out of 10000 random k-bounded vertexsets were connected: 4184

So many out of 10000 random k-bounded vertexsets were metric: 261

THIRD (mandatory). Get the constraints (= superclauses, resp implications) necessary for the metric, respectively convex, subgraphs. Which of the two is decided at beginning with GeodesicallyConvexQ!

GDM=GraphDistanceMatrix[gr];GeodesicallyConvexQ=False;(*IfTrue,thenall(geodesically)convex,ifFalsethenallmetricsubgraphsaregenerated.Detailsinarticle*)Constraints={};Summe1=Summe2=h=0;(*hbecomesthenumberofconstraints,sointheendh=(wchoose2)-ka.*)Do[dist=GDM[[v1,v2]];If[v1<v2&&dist>1,premise={v1,v2};AltSubsets=GeodConvSubset={};Shortestv1v2=FindPath[gr,v1,v2,dist,All];Do[as=Complement[Shortestv1v2[[t]],premise];Summe2=Summe2+Length[as];AltSubsets=Append[AltSubsets,as];GeodConvSubset=Union[GeodConvSubset,as];,{t,Length[Shortestv1v2]}];If[GeodesicallyConvexQ,CS={premise,{GeodConvSubset}};,CS={premise,AltSubsets};];Summe1=Summe1+Length[AltSubsets];Constraints=Append[Constraints,CS];h=h+1;];,{v1,w},{v2,w}];Variablenmenge={};Clear[aa];Do[Variablenmenge=Append[Variablenmenge,aa[i]];traduit[aa[i]]=i;traduit[!aa[i]]=-i;,{i,w}];ConstraintsZuFormel;Print["The number of constraints is h=",h];If[!GeodesicallyConvexQ,Print["The average NUMBER of positive terms PER superclause is: ",N[Summe1/h]];Print["The average LENGTH of a positive term is: ",N[Summe2/Summe1]];,Print["Here the constraints are implications"];];

The number of constraints is h=210

The average NUMBER of positive terms PER superclause is: 2.97143

The average LENGTH of a positive term is: 1.31571

(*Notmandatory*)Do[Print[Constraints[[i]]];,{i,7}];

FORTH: OUR ALGORITHM (subroutines below must be read in)

In the article “our algorithm” is either AllMetricSets or AllConvexSets

FIFTH: BConvert (= terminology from article, Sec .6)

PART A:

PART B :

SIXTH: The alternative (usually slower) way of Sec . 6.3 .1 in article:

Part A : Click here in order to copy and paste the correct variables into f of Part B :

Part B:

Part C:

Subroutines to be read in beforehand, SEP 2024

This can sometimes be useful in TreatTopRow2:

This features newhaengig3, and so hopefully improves upon TreatToprow2:

Here the index of the next imposed constraint is calculated. The subroutine occurs in TreatTopRow2 :

This occurs in TreatTopRow3 but DOES NOT seem to improve newhaengig2 :

This occurs in newhaengig3 and uses parameters defined there :

This subroutine occurs in ImposePosTerms:

This subroutine occurs in TreatTopRow2 :

These subroutines translate our set - theoretic definition of the superclauses (which is necessary for Neuer Algorithmus) into a proper Boolean formula (which is necessary for our competitor BooleanConvert):

That occurs in ImposePosTermsBC:

This subroutine occurs in TreatTopRow2 and is an optional alternative (relying on BooleanConvert) to ImposePosTerms:

CITE THIS NOTEBOOK

Compression with wildcards: All induced metric subgraphs
by Marcel Wild
Wolfram Community, STAFF PICKS, October 30, 2024
https://community.wolfram.com/groups/-/m/t/3312008