lcz

682 Reputation

11 Badges

3 years, 220 days
changsha, China

MaplePrimes Activity


These are replies submitted by lcz

@Carl Love It would be nice if Mapleprimes could see the record of modifications, including deletions and flagged duplications, as Stack does.

@Carl Love I describe an equivalent question for this issue in the comments. But it is not clear to me yet:

  • For a fixed k, what is the algorithm complexity for finding all k-cliques of a given graph?

In any case it is necessary to provide a relatively efficient function to find all k-cliques in maple.

Edits: Algorithm to find cliques of a given size k【O(n^k) time complexity】 

But I cannot guarantee the authority of the information.

I think we can transform this set problem into a graph problem. 

We construct the corresponding graph as follows:

  • set each subset Ei as a vertex, and
  •  Ei is adjacent to Ej if and only if  Ei and Ej do not intersect.

This problem is then equivalent to finding all  cliques of size L of the graph

Unfortunately,  currently maple does not provide ready-made functions. As far as I know, IGraphM that is a Mathematica package for use in complex networks and graph theory research has this feature. I don't have too many ideas to implement IGCliques in maple yet.

S = {{{2, 3}, {2, 7}}, {{1, 3}, {2, 4}}, {{2, 4}, {2, 5}}, {{2, 
     6}, {1, 2}}};
G = RelationGraph[DisjointQ[#1, #2] &, List @@ S];
G1 = VertexReplace[G, Table[S[[i]] -> Subscript["S", i], {i, 4}]];
<< IGraphM`;
IGCliques[G1, {3}](*find all 3-cliques*)

{S1, S3, S4},  {S1, S2, S4}

 

It is found in [1] that there are 256 possible products of any two graphs using the adjacency and the non-adjacency relations of these graphs.  I think all these products can be handled with the function RelationGraph by Carl Love.  

sum(binomial(8, i),i=0..8)#Make a choice in each item, i.e., 2^8=256

[1] Barik, S., Bapat, R.B., Pati, S.: On the Laplacian spectra of product graphs. Appl. Anal. Discrete Math. 9, 39–58 (2015)

Out of these, four graph products namely, the Cartesian product (condition 1 or condition 7), the direct product (condition 3), the strong product (condition 1 or condition 3 or condition 7) and the lexicographic product (condition 1 or condition 3 or condition 5 or condition 7) are known as the standard graph products and have been studied by many researchers.

Here the conormal product is given by choosing the condition 1 or condition 3 or  condition 4 or  condition 5 or condition 7. It chooses “condition 4” more than the lexicographic product.

Therefore, the problems of computing products of two graphs in the future can be regarded as variants of the same problem on the mapleprimes, if not discussing the efficiency problem.

 

@vs140580 For your first problem:

You say in the post:

Give graph G1 and a graph G2  the problem is to extract maximum isomorphic copies of G1 from G2 such that it has no edge intersection maximum number is floor((number of edges of G2)/(number of edges of G1))...

 I wonder if you missed a full-stop in that sentence. Is it supposed to be:

Give graph G1 and a graph G2  the problem is to extract maximum isomorphic copies of G1 from G2 such that it has no edge intersection. Maximum number is floor((number of edges of G2)/(number of edges of G1))...

or:

Give graph G1 and a graph G2  the problem is to extract maximum isomorphic copies of G1 from G2 such that these isomorphic copies of G1 are edge-disjoint in G2 

 

I gave you an example, and please check if I understand correctly.

 

We can find at most three copies of G1 in G2 that are edges disjoint. Is "3" the answer you want?

I'm very interested in whether your C++ program can handle this example I'm talking about?

 

Can you give some examples for illustrating the subgraphs you are looking. I didn't catch your definition.

For example, you say:

  • it has no edge intersection maximum number is floor((number of edges of G2)/(number of edges of G1)) ..

What is edge intersection mximum number?

@Carl Love  Nice!  But where can we see Maple's improvements in some basic functions, such as "local" here? I checked the help documentation for  functions "proc" or "local" and there was no mention of improvements in maple 2022.

@vs140580 I downloaded your worksheet (the codes were contributed by Carl Love), it runs without any problem on my side. 

@Carl Love Thanks for informing that this is a extremely nonstandard numeric output format. Yes, as  tomleslie  said, this was entered manually by me, giving a bad example.

@tomleslie I just saw that cat might be able to do that.  I am so glad you have reminded me.

@tomleslie Thanks! What if the expression is derived from an intermediate derivation instead of the original input? If the expression is very long, I might not want to copy it again. I'd like to store it directly in my txt files.

@vs140580 I don't understand what you mean by that. 

You say:

  •  I need to see the vertex a big labels , edges how they are moving exactly in the graph more clearly which edge is exactly from which vertex to which after converting to pdf.

Do you mean to increase the size of the vertices and  thier labels ? The PDF generated by Gephi is a vector image, and you can resize  it without distortion.

F_0F_1_3.pdf

 

@vs140580 I am not familiar with the algorithmic problem of how to generate a connected planar graph. I am also a beginner in ogdf. So far I haven't learned how to build it locally (Windows).

I recently learned that python seems to provide the interface (https://pypi.org/project/ogdf-python/), but again,  it need source codes of ogdf to build it locally. (I haven't seen a detailed step by step process for building ogdf for windows).  But no matter how, you can click on the link  (ogdf-python) . Then enter the following code I wrote.

# uncomment if you didn't set this globally:
# %env OGDF_BUILD_DIR=~/ogdf/build-debug
from ogdf_python import ogdf, cppinclude
cppinclude("ogdf/basic/graph_generators/randomized.h")
cppinclude("ogdf/planarity/PlanarizationLayout.h")

G = ogdf.Graph()
ogdf.setSeed(1)
ogdf.randomPlanarConnectedGraph(G, 10, 15)
GA = ogdf.GraphAttributes(G, ogdf.GraphAttributes.all)
for n in G.nodes:
    GA.label[n] = "a%s" % n.index()

SL = ogdf.PlanarizationLayout()
SL.call(GA)
ogdf.GraphIO.drawSVG(GA, "sugiyama-simple.svg")
GA

As for how Maple calls it, I don't know yet. Maybe I'll learn it in the future.

ogdf is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing. It offers sophisticated algorithms and data structures to use within your own applications or scientific projects.  

see this :https://ogdf.github.io/doc/ogdf/group__graph-generators.html#gae9de58fd22ae2533f0d81d450d4bf985

randomPlanarConnectedGraph()

void ogdf::randomPlanarConnectedGraph ( Graph &  G,
    int  n,
    int  m 
  )    

Creates a random connected (simple) planar (embedded) graph.

Parameters
G is assigned the generated graph.
n is the number of nodes of the generated graph.
is the number of edges of the generated graph.
Note
n has a lower bound of 1, and m has a lower bound of n and an upper bound of \(3n-6\). The supplied values are adjusted if they are out of these bounds.
1 2 3 4 5 6 7 Last Page 1 of 12