## 1009 Reputation

5 years, 174 days
changsha, China

## In Maple 2023, many errors and warnings ...

@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.

 > restart:
 > interface(version)
 (1)
 > with(GraphTheory): with(plots):
 > G := Digraph({[1, 2], [2, 3], [3, 4], [4, 1]}):
 > dg := DrawGraph(G):
 > print~([op(dg)]):
 (2)

CHANGING EDGES

 > # The last POLYGONS structures describe each edges with its arrow. # # If you want to change the style and position of any arrow you can do this. MoveArrow := proc(edge, pc, angle, length, closed, col)   local f, dx, dy, alpha, beta1, beta2, head, end1, end2, arrow, style:   f      := (dx, dy) -> piecewise(dx >= 0, arctan(dy/dx), Pi+arctan(dy/dx)):   dx, dy := (op(1, edge)[2] -~ op(1, edge)[1])[];   alpha  := f(dx, dy);   beta1  := alpha-angle;   beta2  := alpha+angle;   head   := op(1, edge)[1]*~pc +~ op(1, edge)[2]*~(1-pc):   end1   := head -~ length *~ [cos, sin](beta1):   end2   := head -~ length *~ [cos, sin](beta2):   style  := remove(type, [op(edge)], list)[]:   if closed then     arrow := [end1, head, end2, end1]:    #return POLYGONS([op(1, edge)[], ListTools:-Reverse(op(1, edge))[]], style),    #       POLYGONS(arrow, COLOR(RGB, op(ColorTools:-NameToRGB24(col))))     return POLYGONS(arrow, COLOR(RGB, op(ColorTools:-NameToRGB24(col)))),            POLYGONS([op(1, edge)[], ListTools:-Reverse(op(1, edge))[]], style)   else     arrow  := [end1, head], [head, end2]:     return POLYGONS(op(1, edge), arrow, style)   end if: end proc: NV     := numelems(Vertices(G)): NE     := numelems(Edges(G)): pol    := select(has, [op(dg)], POLYGONS): edges  := pol[-NE..-1]: others := pol[1], remove(has, [op(dg)], POLYGONS)[]: cols     :=["Red", "Cyan","Yellow", "Magenta"]: pos      := [0.4, 0.3, 0.4, 0.3]: NewEdges := seq(MoveArrow(edges[n], pos[n], Pi/12, 0.1, true, cols[n]), n=1..NE): display(PLOT(others, NewEdges), axes=none)

CHANGING VERTICES

 > centers   := map(n -> Statistics:-Mean(convert(op(n, others[1]), Matrix)), [\$1..NV]): diameters := map(n -> abs~(op(n, others[1])[1] -~ centers[n]), [\$1..NV]):
 > ChangeVertex := proc(shape, c, d, theta, col)   local fig, n:   if shape = "disk" then     fig := display(plottools:-disk([0, 0], d[1], color=col));   elif shape = "ellipse" then     fig := display(plottools:-ellipse([0, 0], entries(d, nolist), color=col, filled=true))   elif shape[1] = "P" then     n   := parse(shape[2..-1]):     fig := display(polygonplot([seq([cos(2*Pi*i/n), sin(2*Pi*i/n)], i = 1..n)], color=col)):     fig := plottools:-scale(fig, entries(d, nolist))   end if;   plottools:-translate(plottools:-rotate(fig, theta), entries(c, nolist)); end proc:
 > # shapes := {"disk", "ellipse", ...) (see plottools) #           or "Pn" where n is an integer >= 3 NewDiameters := map(d -> d*~[2, 1], diameters): rotations    := (Pi/NV)*~[\$1..NV]: shapes       := ["disk", "ellipse", "P4", "P7"]: display(   seq(ChangeVertex(shapes[n], centers[n], NewDiameters[n], rotations[n], "Chartreuse"), n=1..NV)   , PLOT(others[2..-1], NewEdges)   , axes=none   , scaling=constrained )
 >

## Depending on luck from ShortestPath?...

@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.

## You are correct....

@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 are paths that only share their first and last nodes. The number of node independent paths between two nodes is equal to their local node connectivity.

This is a flow based implementation of node disjoint paths. We compute the maximum flow between source and target on an auxiliary directed network. The saturated edges in the residual network after running the maximum flow algorithm correspond to node disjoint paths between source and target in the original network. This function handles both directed and undirected graphs, and can use all flow algorithms from NetworkX flow package.
Edge disjoint paths are paths that do not share any edge. The number of edge disjoint paths between source and target is equal to their edge connectivity.

This is a flow based implementation of edge disjoint paths. We compute the maximum flow between source and target on an auxiliary directed network. The saturated edges in the residual network after running the maximum flow algorithm correspond to edge disjoint paths between source and target in the original network. This function handles both directed and undirected graphs, and can use all flow algorithms from NetworkX flow package.

## A counterexample...

@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).

## I'm sorry to bother you since I feel tha...

@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.

## a similar question before...

You seem to have asked a similar question before.

## Thanks!...

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

## a slight 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

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

## Thanks!...

@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.

## confusion...

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(["]", "}"]))

## I vote up....

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

## a slight problem...

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

## a question...

@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.

## Nice!...

@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.

## a slight problem...

@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

 1 2 3 4 5 6 7 Last Page 3 of 16
﻿