2
$\begingroup$

I have a graph and we can use FindMaximumFlow to find the maximum amount of pairings in such a graph. But I want to know the actual paths as well, not just the maximum amount of them.

For instance: In the documentation there is:

But what good is this to anyone, practically? Surely this HR manager person will actually have to pair up the particular person with a particular job. In other words, he wants a table of the paths not just the amount of them. For a small number like in this example, sure the paths are visible, but for a bigger one, good luck. Should I just construct my own tailored ford-fulkerson for this or is there something I am missing in FindMaximumFlow?

Thanks in advance. (For site mods: I cannot use either bipartite nor matching as tags due to low reputation, even though those are exactly the words to describe this.)

Improve this question
$\endgroup$
5
  • $\begingroup$ Did you have a look at optimumflowdata? $\endgroup$
    – Lou
    Commented May 5, 2022 at 20:26
  • $\begingroup$ If you are implying that the optimumflowdata object holds the flows then I do not know how to extract them, again, not sure what I am missing puu.sh/IYIFu/f2cb9b120e.png $\endgroup$
    – redivider
    Commented May 5, 2022 at 20:46
  • $\begingroup$ maxPairs["Properties"] will return a list of available properties, in your case, I think it's maxPairs["EdgeList"] that you're looking for. Also have a look at FindIndependentEdgeSet (specially Applications's section). $\endgroup$
    – Ben Izd
    Commented May 5, 2022 at 21:27
  • $\begingroup$ it is "EdgeList" actually, my bad I didnt notice it. $\endgroup$
    – redivider
    Commented May 5, 2022 at 22:12
  • $\begingroup$ Also you can use EdgeCount instead of Length[EdgeList[...]]. $\endgroup$
    – Ben Izd
    Commented May 6, 2022 at 6:31

1 Answer 1

Reset to default
1
$\begingroup$

It is indeed the "EdgeList" property of the optimumFlowData object! The problem is also I did this in a bad way by introducing a sink and a source (which gives me 3 times the paths) whereas I should've just used the vertexes only as in the documentation examples which made me think "EdgeList" is simply all the edges of the original graph.

    Clear[lists, graph, pP, pPi]
pP[x__] := (
  {x}[[1]] -> # & /@ Drop[{x}, 1]
  )
Clear[pPi]
pPi[x__] := (
  # -> Last [{x}] & /@ Drop[{x}, -1]
  )
lists := Join[
  pP[s1, m1, m2, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12, m13, 
   m15, m16, m17, m18, m19, m20, m21, m23, m24, m25, m26], 
  pP[m1, f1, f2, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, f16, 
   f17, f18, f19, f20, f21, f22, f23, f26, f34, f35, f36, f37, f28, 
   f29, f31, f33], 
  pP[m2, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, 
   f15, f16, f17, f19, f20, f21, f22, f23, f25, f26, f34, f35, f36, 
   f37, f28, f29, f38, f31, f33], 
  pP[m3, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, 
   f15, f16, f17, f18, f19, f20, f21, f22, f23, f25, f26, f34, f35, 
   f36, f37, f28, f20, f38, f31, f33], 
  pP[m4, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, 
   f15, f16, f17, f18, f19, f20, f21, f22, f23, f25, f26, f35, f36, 
   f37, f28, f29, f38, f31, f33], 
  pP[m5, f1, f2, f4, f5, f7, f8, f9, f10, f12, f14, f15, f16, f18, 
   f20, f21, f22, f23, f26, f34, f35, f36, f37, f28, f31, f33], 
  pP[m6, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, 
   f15, f16, f17, f18, f19, f20, f21, f22, f23, f25, f26, f34, f35, 
   f36, f37, f28, f29, f38, f31, f33], 
  pP[m7, f1, f3, f4, f5, f6, f7, f9, f10, f11, f12, f13, f14, f15, 
   f16, f17, f19, f20, f21, f22, f23, f24, f25, f26, f34, f35, f36, 
   f37, f28, f29, f38, f31, f32], 
  pP[m8, f1, f3, f4, f5, f6, f7, f9, f10, f11, f12, f13, f14, f15, 
   f16, f17, f19, f20, f21, f22, f23, f24, f25, f26, f35, f36, f37, 
   f28, f29, f38, f31, f32], 
  pP[m9, f1, f3, f4, f5, f6, f7, f9, f10, f11, f12, f13, f14, f15, 
   f16, f17, f19, f20, f21, f22, f23, f25, f26, f34, f35, f36, f37, 
   f28, f29, f38, f31], 
  pP[m10, f1, f2, f4, f5, f7, f8, f9, f10, f12, f14, f15, f16, f18, 
   f20, f21, f22, f23, f26, f34, f35, f36, f37, f28, f31, f33], 
  pP[m11, f1, f3, f4, f5, f6, f7, f9, f10, f11, f12, f13, f14, f15, 
   f16, f17, f19, f20, f21, f22, f23, f24, f25, f26, f34, f35, f36, 
   f37, f28, f29, f38, f31, f32], 
  pP[m12, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f12, f13, f14, f15,
    f16, f17, f18, f19, f20, f21, f22, f23, f25, f26, f34, f35, f36, 
   f28, f29, f38, f31, f33], 
  pP[m13, f1, f3, f4, f6, f7, f9, f10, f11, f12, f13, f14, f16, f17, 
   f19, f20, f22, f23, f24, f25, f35, f36, f37, f28, f29, f38, f31, 
   f32], pP[m15, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, 
   f13, f14, f15, f16, f16, f18, f19, f20, f21, f22, f23, f25, f26, 
   f35, f36, f37, f28, f29, f38, f31, f33], 
  pP[m16, f1, f2, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, f16, 
   f17, f18, f19, f20, f21, f22, f23, f26, f34, f35, f36, f37, f28, 
   f29, f31, f33], 
  pP[m17, f1, f2, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, f16, 
   f17, f18, f19, f20, f21, f22, f23, f26, f35, f36, f37, f28, f29, 
   f31, f33], 
  pP[m18, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14,
    f15, f16, f17, f18, f19, f20, f21, f22, f23, f25, f26, f34, f36, 
   f37, f28, f29, f38, f31, f33], 
  pP[m19, f1, f3, f4, f6, f7, f9, f10, f11, f12, f13, f14, f16, f17, 
   f19, f20, f22, f23, f24, f25, f35, f36, f37, f28, f29, f38, f31, 
   f32], pP[m20, f1, f3, f4, f5, f6, f7, f9, f10, f11, f12, f13, f14, 
   f15, f16, f17, f19, f20, f21, f22, f23, f25, f26, f34, f35, f36, 
   f37, f28, f29, f38, f31], 
  pP[m21, f1, f2, f4, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, 
   f16, f17, f18, f19, f20, f21, f22, f23, f26, f34, f35, f36, f37, 
   f28, f29, f31, f33], 
  pP[m23, f1, f2, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, f16, 
   f17, f18, f19, f20, f21, f22, f23, f26, f34, f35, f36, f37, f28, 
   f31, f33], 
  pP[m24, f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14,
    f15, f16, f17, f18, f19, f20, f21, f22, f23, f25, f26, f34, f35, 
   f36, f37, f28, f29, f38, f31, f33], 
  pP[m25, f1, f2, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, f16, 
   f17, f18, f19, f20, f21, f22, f23, f26, f34, f35, f36, f37, f28, 
   f29, f31, f33], 
  pP[m26, f1, f2, f4, f5, f7, f8, f9, f10, f12, f13, f14, f15, f16, 
   f17, f18, f19, f20, f21, f22, f23, f25, f26, f34, f35, f36, f37, 
   f28, f29, f31, f33], 
  pPi[f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, f13, f14, 
   f15, f16, f17, f18, f19, f20, f21, f22, f23, f24, f25, f26, f28, 
   f29, f31, f32, f33, f34, f35, f36, f37, f38, s2]]
graph = Graph[lists, VertexLabels -> "Name"]
maxPairs = 
 FindMaximumFlow[graph, s1, s2, "OptimumFlowData", 
  "EdgeCapacity" -> ConstantArray[1, Length[EdgeList[graph]]]]
maxPairs["FlowGraph"]
DeleteCases[
 DeleteCases[maxPairs["EdgeList"], 
  s1 \[DirectedEdge] _], _ \[DirectedEdge] s2]

Here is the output: output

Improve this answer
$\endgroup$
1
  • $\begingroup$ Please post your Mathematica code instead of only pictures. $\endgroup$
    – cvgmt
    Commented May 6, 2022 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.