@mmcdara Great. The most important thing is that you told me the objects of DrawGraph can be modified by ourselves. However, in Maple 2023, many errors and warnings are reported. I am not sure if it is due to the version update.

Download Customization_1_2023.mw

@mmcdara I apologize for my negligence, but my concern still has merit. Because the function ShortestPath selects one of shortest paths between two vertices, we need to consider that the following choices may cause problems. I would say that the success of your function depends on luck from ShortestPath.

If  ShortestPath(G,1,10) first selects the shortest path 1-2-7-10, and then removes vertices  "2" and "7", subsequently, we can find at most two vertex-disjoint paths between "1" and "10" (1-4-8-10,1-5-9-10).

I'm not sure if I misunderstood your function, but this situation is indeed concerning.

PS: Interestingly, I haven't found a counterexample yet that makes your function always fail. This implies that any shortest path will break two or more vertex-disjoint paths.

@Carl Love You are correct. The maximum flow between two vertices is equal to the maximum number of edge-disjoint paths (not  vertex-disjoint paths) between them.   I was mistaken in my previous statement. Your counterexample is correct.

So we can ask at least two questions:

How can we find edge-disjoint paths (resp. vertex-disjoint paths)  between two vertices with maximum size?

It seems that NetworkX in Python can achieve this and provides some algorithm suggestions.

• node_disjoint_paths

• edge_disjoint_paths

@mmcdara Your method gives me present a refreshing feeling. Before, I was always thinking about fully exploring the potential of the maximum network flow.

I'm a little worried that if the selection of the shortest path is inappropriate, we might not be able to find the maximum number of vertex disjoint paths. 

The following example confirms my concern that your method fails in this situation.

g:=Graph({{1,2},{1,3},{1,4},{1,5},{2,6},{3,7},{4,8},{5,9},{2,7},{6,10},{7,10},{8,10},{9,10}}):
vp := [[0,3],[-2,2],[-1,2],[1,2],[2,2],[-2,1],[-1,1],[1,1],[2,1],[0,0]];
SetVertexPositions(g, vp):
DrawGraph(g);
G := CopyGraph(g):
while IsConnected(G) do
  s := ShortestPath(G, 1, 7);
  c := s[2..-2]:
  G := DeleteVertex(G, c):
  print(s);
end do:

                           [1, 2, 7]

                           [1, 3, 7]

                        [1, 4, 8, 10, 7]

We found that there are four vertex-disjoint paths between "1" and "10" (1-2-6-10,1-3-7-10,1-4-8-10,1-5-9-10), while your method can only find three. The reason is that the first shortest path found [1, 2, 7, 10] was selected (which must be selected in your method).

@Carl Love It seems that this problem has not been solved yet. Because according to your code, the maximum flow between "1" and "4" is 6, so the minimum cut between "1" and "4" is also 6, which means there are 6 vertex-disjoint paths between edges (1,3) and (5,6) before contraction. But is this correct?

Sorry, I read it wrong. Nodes 5 and 6 are contracted into node 5, not node 4. I will try to continue with the calculation of restricted connectivity.

You seem to have asked a similar question before.

• https://www.mapleprimes.com/questions/230005-Longest-Distance-In-A-Graph-Via-Maple-Code

@acer Thanks! I use restart and it is fine now, maybe there was a problem loading the package. That's my problem.

@acer I'm sorry that I didn't present the problem as a whole. Your answer seems to not meet my requirements. What I'm looking for is the following

instead of your

There are still some objects that have not been replaced in your result, for example: )->} [->{ ]->}.

@acer I thought that  op([L1[1],L2[1]])  would pass L1[1] and L2[1]]  as a whole parameter to the function SubstituteAll  , but it seems that it is not the case. 

@acer 

I still have confusion. I have reviewed the documentation for  foldl and it should be able to recognize it. 

foldl(F, id, a, b, c, d)  

 F(F(F(F(id, a), b), c), d)

Or:

f:=(x,y)->sin(x+y);
foldl(f, a, 1, 2, 3, 4)

sin(sin(sin(sin(a + 1) + 2) + 3) + 4)

Why doesn't "SubstituteAll" work in particular?

Is this just a formality, like sursumCorda suggested, to first "uneval" it?

L1:= "()[]": L2:= "{}{}":
X:=(foldl(''SubstituteAll'',s,'op'([L1[1],L2[1]]),'op'([L1[2],L2[2]]),'op'([L1[3],L2[3]]),'op'([L1[4],L2[4]])));

X := 'SubstituteAll'('SubstituteAll'('SubstituteAll'('SubstituteAll'("[ (0, 1), (1, 2), (1, 10), (2, 3), (3, 4), (4, 5),\n(4, 9), (5, 6), (6, 7), (7, 8),(8, 9), (10, 11), (11, 12),\n(11, 16), (12, 13), (13, 14), (14, 15), (15, 16)]", op(["(", "{"])), op([")", "}"])), op(["[", "{"])), op(["]", "}"]))

@dharr I agree. Once we consider  minimality,  it seems that a minimal edge separator  is a minimal Cut, and the inverse  is also true.

@mmcdara Look at my comment. Do you think my explanation is incorrect?

@dharr I admit that the example I gave earlier was misleading due to being too specific. I'm very sorry.

I have a question about this part of the code  if nops(partition) <> 2 then return false end if. I'll give an example below to illustrate that there can still be more than two connected components if we remove a Cut edg.

g:=Graph({{1, 2}, {1, 3}, {1, 10}, {2, 3}, {3, 4}, {3, 10}, {4, 5}, {4, 6}, {6, 8}, {7, 8}, {7, 9}, {7, 11}, {7, 12}, {8, 9}, {10, 11}, {10, 12}, {11, 12}})

edg:={{1,10},{3,10},{3,4},{6,8},{7,11},{7,12}};# a Cut

But using your code,  it says that edg is  not a Cut.

 IsCut(g,edg)

false

Below is my inquiry on Computer Science Stack. Highheath  provided an algorithm that seems to be reliable.

• https://cs.stackexchange.com/questions/157731/how-to-determine-if-a-set-of-edges-is-an-edge-cut-of-a-graph

@Kitonum For the specific case where each division has same size: this is most concise code. But considering the versatility, the solutions provided by Carl Love and dharr are more attractive.

@Carl Love Thank you so much. Unfortunately, your code did not work on my computer. I suspect it may be due to P:=[3,3]. We expect to get 10 solutions, not 20, taking into account symmetrical solutions as one.

F := SetPartitionFixedSize([3, 3],compile = true);
Print(F, 'showrank')

1: 1 2 3 4 5 6 
 2: 1 2 4 3 5 6 
 3: 1 2 5 3 4 6 
 4: 1 2 6 3 4 5 
 5: 1 3 4 2 5 6 
 6: 1 3 5 2 4 6 
 7: 1 3 6 2 4 5 
 8: 1 4 5 2 3 6 
 9: 1 4 6 2 3 5 
10: 1 5 6 2 3 4