The edge connectivity of a connected graph G  is the minimum number of edges whose deletion from the graph G disconnects G. Below we are concerned with a particular kind of edge-cut.

• For a connected graph G=(V ,E), an edge set S ⊂ E is a restricted-edge-cut, if G−S is disconnected and every connected component of  G−S has at least 2 vertices. 

Clearly, a restricted-edge-cut is an edge cut with a special requirement.

• The restricted-edge-connectivity of G, denoted by κres(G), is defined as the cardinality of a minimum restricted-edge-cut.

For example, a graph g is as follows.

Clearly, its edge-connectivity is 1 since (0,3) or (0,4) is a edge cut of g. But we can find that  if we remove the edge (0,3), then "3" is a isolated vertex. Similarly, "4" is a isolated vertex if we remove  (0,4). It is not difficult to find g has exactly the two cut-edges (0,3) and (0,4).

Based on the definition of the restricted-edge-cuts, neither {(0,3)} nor  {(0,4)} are restricted-edge-cuts.  A minimum restricted-edge-cut is {(0,1),(0,2)} since every connected component of G-{(0,1),(0,2)} has  (at least) 2 vertices.

So  κres(g) is 2.  My problem is:

Given a graph G, how to calculate the restricted-edge-connectivity of  G?  Moreover, how to find a minimum restricted-edge-cut? 

A specific graph that I want to test is as follows. (it has 16 vertices and 56 edges.) I would like to calculate its restricted-edge-connectivity and find a minimum restricted-edge-cut. 

g:=ConvertGraph("O~tIID@wL~j`PbOqgLJ@p");
DrawGraph(g, stylesheet=[vertexborder=false,vertexpadding=15,edgecolor = "Black",
     vertexcolor="Black",edgethickness=2])

EdgeConnectivity(g) 

6

One option I came up with is to find all 6-edge subsets first. Test if they satisfy  the restricted condition (one by one). Then continue to increase to 7 or more. But this violent calculation may get stuck in the first step. That is, test all the minimum edge cut sets (Note that we will consider 32468436 edge-subsets!) I was referring to the efficiency aspect.  

with(Iterator):
C:=Combination(58,6):
K:=Edges(g):
#sub:=seq( K[[seq(c[]+1)]], c=C); # do not run this code since it has 32468436 members.

Any language is acceptable.( C or C++, Python. )

PS: Some time ago, I also asked a related question (but with some differences) on mathematica stack （Find all the minimum edge cuts of a graph）. Although Bob Hanlon  gave a reply, the actual result is not good.

Edits: The following literature gives a polynomial algorithm for computing the restricted-edge-connectivity of a given  graph. The heart of it is to computing the least cardinality of some  edge-pairs's edge separator. I'm stuck here.

• Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information processing letters, 1988, 27(4): 195-199.

How to implement this algorithm is my current concern.

I have the following expression:

q1:=2.800000000*10^(-30)*a+2.7800000000*10^(-29)*b+2.7800000000*10^(-31)+3.0*10^(-21)+2.*10^(-32)*c+3.*10^(-30)*d;

I saved it as a string, but the format seems to have changed.

q2:=convert(q1,string)

Can I output it as follows:

"2.800000000*10^(-30)*a+2.7800000000*10^(-29)*b+2.7800000000*10^(-31)+3.0*10^(-21)+2.*10^(-32)*c+3.*10^(-30)*d"

Recently, I tried to write a function to get the lexicographic product of two graphs.

• the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
• any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H.

I'm trying to write this function as defined after making sure it doesn't exist in maple. I saw a similar post by mathematica stack.

• https://mathematica.stackexchange.com/questions/173124/lexicographic-product-of-graphs

There are many answers in the post, the most interesting to me is the following code, which follows the definition of lexicographic product. 

lexicographicProduct[g1_?UndirectedGraphQ, g2_?UndirectedGraphQ, opt : OptionsPattern[]] := 
 RelationGraph[
   (* two nodes are connected if their corresponding nodes in the first graph are connected *)
   EdgeQ[g1, First[#1] \[UndirectedEdge] First[#2]] || 
   (* or their corresponding nodes in the first graph are the same and their corresponding nodes in the second graph are connected *)
   (First[#1] === First[#2] && EdgeQ[g2, Last[#1] \[UndirectedEdge] Last[#2]]) &,

   (* the vertices are the cartesian product of the two vertex sets *)
   Tuples[{VertexList[g1], VertexList[g2]}],

   (* also allow setting graph options *)
   opt
 ]

lexicographicProduct[CycleGraph[5], CycleGraph[3]]

It utilizes the  function RelationGraph in Mathematica. I feel that this function is generic in nature. So here I would ask maple if they had a similar function.

Function RelationGraph is to generate a graph based on data and a binary relation.

For example, using RelationGraph  I  can get easily  the k_th power G^k of an graph G which is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k.

Dis[g1_?UndirectedGraphQ, k_] := 
 RelationGraph[
  GraphDistance[g1, #1, #2] <= k && GraphDistance[g1, #1, #2] != 0 &, 
  VertexList[g1]]
Dis[PathGraph[Range[10]], 2]

If I use maple and do not use the built-in function GraphPower, I might deal with the following.

with(GraphTheory):
with(SpecialGraphs):
graphpower:=proc(G,k):
local choo,edge,vex,g;
 vex:=convert(Vertices(G),list);
 choo:= choose(vex, 2):
 g:= Graph(Vertices(G)):
 for edge in choo do 
     if Distance(G, edge[1], edge[2])<=k  then 
        AddEdge(g, convert(edge,set))
     fi;
  end do:
 return g;
end proc:
s:=graphpower(PathGraph(10),2);DrawGraph(s)

I believe if the RelationGraph function can be  implemented in maple, the function lexicographicProduct would be easier to obtain.

The problem comes from the link https://www.mapleprimes.com/questions/234398-Convert-Maple-Code-To-Python-#comment287424.

We know that when we compile a C or C ++ function, it generates an executable file.  Then we are free from source code.  For example. the function below returns a square matrix A where    "A[i, j]" is the distance from vertex i to vertex j in the graph G. My computer system is Windows.

// C Program for Floyd Warshall Algorithm
#include <stdio.h>

// Number of vertices in the graph
#define V 4

/* Define Infinite as a large enough
  value. This value will be used
  for vertices not connected to each other */
#define INF 99999

// A function to print the solution matrix
void printSolution(int dist[][V]);

// Solves the all-pairs shortest path
// problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V]) {
    /* dist[][] will be the output matrix
      that will finally have the shortest
      distances between every pair of vertices */
    int dist[V][V], i, j, k;

    /* Initialize the solution matrix
      same as input graph matrix. Or
       we can say the initial values of
       shortest distances are based
       on shortest paths considering no
       intermediate vertex. */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    /* Add all vertices one by one to
      the set of intermediate vertices.
      ---> Before start of an iteration, we
      have shortest distances between all
      pairs of vertices such that the shortest
      distances consider only the
      vertices in set {0, 1, 2, .. k-1} as
      intermediate vertices.
      ----> After the end of an iteration,
      vertex no. k is added to the set of
      intermediate vertices and the set
      becomes {0, 1, 2, .. k} */
    for (k = 0; k < V; k++) {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++) {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++) {
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // Print the shortest distance matrix
    printSolution(dist);
}

/* A utility function to print solution */
void printSolution(int dist[][V]) {
    printf ("The following matrix shows the shortest distances"
            " between every pair of vertices \n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

// driver program to test above function
int main() {
    /* Let us create the following weighted graph
            10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3           */
    int graph[V][V] = { {0,   5,  INF, 10},
        {INF, 0,   3, INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    };

    // Print the solution
    floydWarshall(graph);
    return 0;
}

The above functions will be packaged as the disall.exe , and then we will move them anywhere in my computer and run it in Powershell.  We don't have to deal with the source code unless we want to change it.

• https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/?ref=lbp

I mean can Maple do something like that?

with(GraphTheory);
G := Graph([1, 2, 3, 4, 5], {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}});
AllPairsDistance(G);

For exmaple, can I package the above code snippet into an exe file?

I  generated some graphs via maple and would like to put them in my paper. So I am going to convert the following worksheet to pdf.

with(GraphTheory):
Graphs:=[NonIsomorphicGraphs(6,8,output=graphs,outputform = graph)]:
num_g:=nops(Graphs):
num:=ceil((num_g)/5.):
M1:=Matrix (num,5,(i,j)->`if`((i-1)*5+j<=num_g, DrawGraph(Graphs[(i-1)*5+j],size=[250,250] ,overrideoptions ,showlabels=false,style=planar, stylesheet =  [
 vertexcolor     = orange
,vertexfontcolor = black
,vertexborder    = false
,edgethickness   = 0.6
,edgecolor       = MidnightBlue
,vertexshape     =  "circle"
,vertexfont      = [Arial, 4],
vertexthickness=5], caption = cat(H__,5*(i-1)+j),captionfont=["ROMAN",7]),plot(x = 0 .. 1, axes = none))):
DocumentTools:-Tabulate (M1[1..5,.. ],widthmode=percentage ,width=80 , exterior =all) :

But there was a problem with the exported pdf. There was some mosaic stuff at the vertices of all those graphs. It was strange. (I want to reduce the size of vertices of the graphs in order not to look crowded.)

• TST.mw
• TST.pdf

Only when I insert the option vertexpadding and set a large enough size  of vertex (for this example, we set vertexpadding=7),  it won't go wrong. However, in fact, we often need make vertice‘s size smaller , especially when there are more vertices.