lcz

1009 Reputation

11 Badges

5 years, 258 days
changsha, China

MaplePrimes Activity


These are replies submitted by lcz

@Joe Riel  The author asks another question: 

and the graph in the question is  SoccerBallGraph. I I provided a solution based on  Moore–Penrose inverse of  Laplacian matrix of the graph. I am not a physics major, so I do not know the use of  Syrup package. I do not know how to solve  the resistance distance problem  of SoccerBallGraph by Syrup.

@Kitonum  Interesting, but could you prove that the summation in this problem must be in the form of a 3rd degree polynomial?

This is a good question, and perhaps mathematical induction can be tried. However, I suggest you can go to the mathematics stack to query the problem. There is more emphasis on mathematical proofs. If there is a relevant response, look forward to responding here.

@Carl Love Thanks for telling me. Following your suggestion, I added 1 to each element of the two-dimensional list, and the transformation was complete. 

with(GraphTheory):
glist:=[[1, 2, 3, 4, 5, 6], [0, 2, 3, 4, 7, 8],
 [0, 1, 3, 5, 7, 9], [0, 1, 2, 6, 8, 9],
 [0, 1, 5, 6, 7, 8], [0, 2, 4, 6, 7, 9], 
[0, 3, 4, 5, 8, 9], [1, 2, 4, 5, 8, 9], 
[1, 3, 4, 6, 7, 9], [2, 3, 5, 6, 7, 8]]
:
adjustlist_g:=Matrix(glist)+~1:#adjust 
G := Graph([$0..9],convert(adjustlist_g,listlist)):
DrawGraph(G)

 

 

@Carl Love  That's it, I understand 😀.  This representation of graph in maple does not seem to conform to the usual custom.

@Carl Love  Good! it's much faster than mine. But I test your code with the example below, they don't seem to be fast by contrast .

G:= GT:-LineGraph(GT:-CompleteGraph(20)): CountCliques(G, 3);
CodeTools:-Usage(CountCliques(G, 8));

The following code (using igraph) is super fast

from igraph import *
import time
g = Graph.Full(n=20)
g1=g.linegraph()
start = time.time()
numberk4=g1.cliques(min=8, max=8)
print(len(numberk4))
end = time.time()
print(end-start)

1511640

0.9485256671905518

I'm guessing  the  program for counting cliques  in igraph  is seriously optimised.

@tomleslie I think your suggestion is very correct.  All functions of graph theory included in maple are really unreal, With the research of graph theory, new algorithms or codes will always appear in each specific professional software package, and maple will always lag behind.

Ps:  Below is the code for python to call the igraph package. 

from igraph import *
g = Graph.Full(n=7)
g1=g.linegraph()
numberk4=g1.cliques(min=4, max=4)
print(len(numberk4))

105

We need to take advantage of their unique strengths.

@Carl Love You are right, anyway my code is incorrect. it sholud be  8->7 not 8->4.

 I was misled by the following  python codes found on the net.

PetersenGraph={
        
    1:[2, 5, 6], 
    2:[1, 3, 9], 
    3:[2, 4, 7],
    4:[3, 5, 10],
    5:[1, 4, 8], 
    6:[1, 7, 10],
    7:[3, 6, 8], 
    8:[5, 7, 9], 
    9:[2, 8, 10], 
    10:[4, 6, 9]
    }

def DFS(graph,s):       
    stack = []        
    stack.append(s)       
    seen = set()      
    seen.add(s)
    while (len(stack) > 0):
        vertex = stack.pop()     
        nodes = graph[vertex]     
        for w in nodes:
            if w not in seen:       
                stack.append(w)
                seen.add(w)
        print(vertex)
DFS(PetersenGraph,1)

1
6
10
9
8
4
3
7
5
2

 

NOTE: The  above non-recursive DFS code ( Doing it recursively, see tomleslie's

answer)   on many URLs is wrong, the correct version is at the URL below.

https://stackoverflow.com/questions/65806675/python-depth-first-search-non-recursive-approach

def Non_Recursive_dfs(graph, source):
    path = []
    stack = []
    stack.append(source)
    
    while stack:
        s = stack.pop()
        if s not in path:
            path.append(s)

        elif s in path:
            #leaf node
            continue
        for neighbour in graph[s]:
            stack.append(neighbour)
    
    return path
Non_Recursive_dfs(PetersenGraph,1)

 

[1, 6, 10, 9, 8, 7, 3, 4, 5, 2]

@Carl Love Cool! Indeed, there is something wrong with the code I wrote,

@Carl Love Thank you for informing me of this fact, although I don't quite know why a basic data structure  stack was dropped  and a similar structure  SimpleStack  was adopted in maple. 

@tomleslie Yes, only for spanning tree, it may not be necessary to write. The code of BFS or DFS is relatively basic, and in many problems,  we need them as a bridge.  

@vv In graph theory research, this kind of filtering behavior of  so many graphs is common. I'm not familiar with compiling, so I can only use Mathematica for now.  Would you have any more detailed suggestions? Thanks. Any suggestion would be very helpful. 

like this?

cp:=Compiler:-Compile(GraphTheory:-VertexConnectivity)

Error, (in subtype) too many levels of recursion

@tomleslie Hello, it's not empty, and the numbers of graphs with VertexConnectivity 6 are 6692.  I suppressed mathematica's output due to too many graphs.

L = Import[
  "C:/Users/asus/Desktop/op21new.g6"]; # Change this line
t = AbsoluteTiming[L1 = Select[L, VertexConnectivity[#] == 6 &];]
Length[L1]

6692

 

The calculation of vertex connectivity of graphs between between 11000 and 11100t ook only 0.10274 seconds, averaging 0.001 seconds per graph.

AbsoluteTiming[VertexConnectivity[#] & /@ L[[11000 ;; 11100]]]

{0.10274, {4, 4, 6, 4, 6, 4, 4, 6, 6, 6, 6, 6, 4, 4, 6, 6, 4, 4, 4, 6,
   6, 6, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 4, 4, 4, 6, 4, 
  6, 6, 6, 4, 4, 4, 6, 6, 4, 4, 6, 4, 4, 6, 4, 4, 4, 6, 4, 6, 6, 6, 6,
   6, 6, 6, 6, 6, 4, 4, 6, 6, 6, 4, 4, 4, 6, 4, 4, 4, 6, 4, 4, 4, 6, 
  6, 6, 6, 6, 6, 6, 4, 4, 6, 4, 6, 4, 4, 4}}

@acer    Matt C Anderson also replied unrelated answers to questions on  some other posts, very strange behavior.

@acer In your codes, I see this

ex2 := (a, expr)->(a) %* frontend(expand, [expr/a], _rest):

When I delete the option _rest.It also works.I haven't seen this plug-in in the help document, so I wonder what role _rest plays.

Even when I use it as a function alone, it shows an error,

expr := (cos(2*x) - sin(2*x)/(x^2*y) + 3*x*y)/cos(2*x);
frontend(expand, [expr]);
frontend(expand, [expr],_rest)

Error, invalid input: frontend expects its 3rd argument, f, to be of type list, but received _rest

First 6 7 8 9 10 11 12 Last Page 8 of 16