lcz

620 Reputation

10 Badges

3 years, 89 days
changsha, China

MaplePrimes Activity


These are questions asked by lcz

I've been asking a similar question, but recently I used Mathematica to call these gadgets very succinctly, so I revisit the topic, and maybe Maple can do it as well, but I just didn't do it the right way.

  • nauty and Traces are programs for computing automorphism groups of graphs and digraphs. There is a small suite of programs called gtools included in the package. For example, geng can generate non-isomorphic graphs very quickly. 
  • plantri and fullgen are programs for generation of certain types of planar graph.

We note that binary executables of above two programs for Windows are not officially available. Fortunately, I recently compiled them by cygwin.  Of course, other operating systems can make it easier to use them. See attached two compressed files of compiled nauty and plantri programs for Windows.

The official websites of the two programs are listed below.

So, I found that Mathematica works very well for running these programs by Import. For example, the following two examples, one is to get all non-isomorphic 10-order 2-partite connected graph, the second example is to get all 14-order non-isomorphic  quadrilateral graphs (the planar graphs in which any face is 4-face).

glist10 = Import["!D:/nauty27r3/geng -c -b 10", "Graph6"]; // AbsoluteTiming
Length[glist10]

g14 = Import["!D:/plantri52/plantri 14 -q -g ", "Graph6"] // AbsoluteTiming

 

I tried maple's Import or ImportGraph functions, but both failed.

restart: 
with(GraphTheory):
L:=ImportGraph("!D:/nauty27r3/geng -c -b 10 -g",output=list):
L2:=Import("!D:/nauty27r3/geng -c -b 10 -g"):

Error, invalid input: GraphTheory:-ImportGraph uses a 2nd argument, format (of type {string, symbol}), which is missing
Error, (in Import) must specify format for this input

The problem seems to be not recognizing compilations symbols " !".  I don't know if Maple can do this like mathematica.

ImportGraph reads one or more graphs from a file. For a file containing multiple graphs, the supported formats are digraph6, graph6, and sparse6. I notice that one option is "output = graph or list, or iterator". However, in my programming with Maple, I was reminded several times that list is only good for a small amount of data.  

Although I can convert the list to an array using the convert function, the time spent in the conversion process needs to be considered.

restart: 
with(GraphTheory):
L:=ImportGraph("C:/Users/eul10c.g6", graph6, output=list):#31026 connected eulerian graphs on 10 vertices graphs and Change to your path here.
convert(L,Array) 

So does it make more sense to provide an "output=Array" as an output option?

eul10c.txt

The spectral radius  is maximum of the absolute values of the eigenvalues of the matrix A.  We can use the function SpectralRadius in Student package. But we noticed a sentence in the help document:

The output from this procedure will be as symbolic as computationally feasible. If the exact spectral radius of A is too time-consuming to compute, it may be computed numerically.

This means that SpectralRadius will evaluate the exact value when it can. Anyway, the internal evaluation process will take time. So for the sake of efficiency, we just want the numerical results of the spectral radius of a matrix. 


I tried to write the following function, but I feel that it is not very efficient, especially for solving characteristic polynomials and their roots.  I even feel that there is a way to find the spectral radius without taking the absolute value of all the eigenvalues and ordering them. 

Spectralradius := proc(A::Matrix)
 local Spectrum;
 Spectrum := sort(abs~([fsolve(LinearAlgebra:-
 CharacteristicPolynomial(A,x)=0,x )]),`>`);
 Spectrum[1]
end proc:

 

One example: In general, the matrices I encounter come from adjacency matrices of graphs, which are always real symmetric. So their eigenvalues are always real. But the Eigenvalues command very slow because it's always trying to get the exact value. So If we use Eigenvalues  to find all the eigenvalues and then sort them, it will be very slow.  Thus  I'm thinking about finding the numerical results.


 

with(LinearAlgebra):
with(GraphTheory):
G2:=Graph({{1,2},{2,3},{3,1},{3,4}}):
A2:=AdjacencyMatrix(G2):
Eigenvalues(A2);

Vector(4, {(1) = -1, (2) = (1/3)*(1+(3*I)*sqrt(111))^(1/3)+(10/3)/(1+(3*I)*sqrt(111))^(1/3)+1/3, (3) = -(1/6)*(1+(3*I)*sqrt(111))^(1/3)-(5/3)/(1+(3*I)*sqrt(111))^(1/3)+1/3+((1/2)*I)*sqrt(3)*((1/3)*(1+(3*I)*sqrt(111))^(1/3)-(10/3)/(1+(3*I)*sqrt(111))^(1/3)), (4) = -(1/6)*(1+(3*I)*sqrt(111))^(1/3)-(5/3)/(1+(3*I)*sqrt(111))^(1/3)+1/3-((1/2)*I)*sqrt(3)*((1/3)*(1+(3*I)*sqrt(111))^(1/3)-(10/3)/(1+(3*I)*sqrt(111))^(1/3))})

(1)

evalsN:=evalf(%);

Vector(4, {(1) = -1., (2) = 2.170086486-0.4000000000e-9*I, (3) = -1.481194304-0.5062177830e-9*I, (4) = .3111078169+0.7062177830e-9*I})

(2)

``

(3)

with(Student):
SpectralRadius(A2)

2.170086487

(4)

 

Maybe I need a way to find all the numerical eigenvalues of a real symmetric matrix not using  CharacteristicPolynomial or Eigenvalues.

Download zlc_1.mw

The IsSubgraphIsomorphic command accepts either two undirected graphs or two directed graphs as input.  It returns true if G1 is isomorphic to some subgraph of G2. The GraphTheory [IsSubgraphIsomorphic] command was introduced in Maple 2021.

If a graph T is isomorphic to some subgraph T' of  a graph GIsSubgraphIsomorphic(T,G)  will  return true. But there is no option to return T'. That makes it hard to check manually.

I've seen  IsSubgraphIsomorphic behaving strangely lately. I want to check whether K8-P6 contains K7-K3 as its subgraph.

T:=DeleteEdge(CompleteGraph(7),{{1,2},{2,3},{3,1}},inplace= false): 
G:=DeleteEdge(CompleteGraph(8),{{1,2},{2,3},{3,4},{4,5},{5,6}},inplace= false): 
IsSubgraphIsomorphic(T,G)

true

I think theoretically, the result of IsSubgraphIsomorphic is not correct. I also tested it from Mathematica, and it worked as I expected.

h = EdgeDelete[ CompleteGraph[7], {1 <-> 2, 2 <-> 3, 3 <-> 1}]; 
g = EdgeDelete[ CompleteGraph[8], {1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 6}]; 
IsomorphicSubgraphQ[h, g]

False

I wonder what went wrong.

 

PS: Subgraph isomorphism is a question I've asked before, and we can refer to the following links and code. https://www.mapleprimes.com/questions/226937-How-To--Test--A--Graph--Whether-Contains

with(GraphTheory):
with(combinat):
T:=DeleteEdge(CompleteGraph(7),{{1,2},{2,3},{3,1}},inplace= false): 
G:=DeleteEdge(CompleteGraph(8),{{1,2},{2,3},{3,4},{4,5},{5,6}},inplace=false): 
nE,nV := NumberOfEdges(T), NumberOfVertices(T):
# Produce all subgraphs of G which have the same number of edges and vertices as the "test" sub-graph T
U:=choose(Edges(G),nE): nops(%):
U1:=select(t -> (nops(`union`(t[]))=nV), U): nops(%):
gL:= Graph~(U1): nops(%):
ans:= [ seq
          ( `if`
            ( IsIsomorphic( T, gL[j] ),
              j,
              NULL
            ),
            j=1..numelems(gL)
          )
        ]:
if   numelems(ans)>0
then HighlightSubgraph( G, gL[ans[1]], edgestylesheet=[thickness=4, color="Red"]);
     DrawGraph(G, style=spring);
fi;

These codes are due to tomleslie  and  vv. According to above codes, it seems that there is something wrong with IsSubgraphIsomorphic too.

I want to generate several graphs  at the same time that can be dynamically adjusted.I tried to write the following code. But it seemed to keep overwriting the previous drawing of graphs in the list g. I only got the last graph K6.

with(GraphTheory):
g:=[seq(CompleteGraph(i),i=2..6)]:
DrawGraph~(g, layout = interactive, layoutoptions = [neutral_color = "pink", initial = spring])

I don't know how to generate  some graphs with dynamically modified layouts at once

1 2 3 4 5 6 7 Last Page 1 of 17