In[]:=
G=Graph[{a,b,c,d,e},{ab,ae,ad,ac,bc,ce,cd,de},VertexLabels->Automatic,EdgeWeight->Thread[{ab,ae,ad,ac,bc,ce,cd,de}->{1,1,1,2,1,1,1,1}],EdgeLabels->"EdgeWeight"]
Out[]=
In[]:=
MultiSet[g_?ConnectedGraphQ]:=Module[{firstToLast,lastToFirst},firstToLast=Graph[Fold[EdgeAdd[#1,DirectedEdge[First[#2],Last[#2]]]&,g,Cases[EdgeList[g],_UndirectedEdge]],EdgeWeight->Join[Values[AssociationMap[AnnotationValue[{g,#},EdgeWeight]&,Cases[EdgeList[g],_UndirectedEdge]]],AnnotationValue[{g,#},EdgeWeight]&/@EdgeList[g]]];lastToFirst=Graph[Fold[EdgeAdd[#1,DirectedEdge[Last[#2],First[#2]]]&,firstToLast,Cases[EdgeList[firstToLast],_UndirectedEdge]],EdgeWeight->Join[Values[AssociationMap[AnnotationValue[{firstToLast,#},EdgeWeight]&,Cases[EdgeList[firstToLast],_UndirectedEdge]]],AnnotationValue[{firstToLast,#},EdgeWeight]&/@EdgeList[firstToLast]]];Graph[Fold[EdgeAdd[#1,UndirectedEdge[Last[#2],First[#2]]]&,lastToFirst,Cases[EdgeList[lastToFirst],_UndirectedEdge]],EdgeWeight->Join[Values[AssociationMap[AnnotationValue[{lastToFirst,#},EdgeWeight]&,Cases[EdgeList[lastToFirst],_UndirectedEdge]]],AnnotationValue[{lastToFirst,#},EdgeWeight]&/@EdgeList[lastToFirst]],EdgeCapacityJoin[ConstantArray[∞,3EdgeCount[g]],ConstantArray[2,EdgeCount[g]]]]]
In[]:=
MultiSet[G]
Out[]=
In[]:=
FindMinimumCostFlow[MultiSet[G],{1,1,1,1,1}]
Out[]=
FindMinimumCostFlow
,{1,1,1,1,1}
In[]:=
(VertexInDegree[G,#]-VertexOutDegree[G,#])&/@VertexList[G]
Out[]=
{0,0,0,0,0}
In[]:=
RandomWeightedGraphTriangleInequality[vertices_,threshhold_]:=First@TakeLargestBy[ConnectedGraphComponents@Module[{randomGraph},randomGraph=RandomGraph[SpatialGraphDistribution[vertices,threshhold]];Graph[randomGraph,EdgeWeight->Thread[EdgeList[randomGraph]->(EuclideanDistance[AnnotationValue[{randomGraph,First[#]},VertexCoordinates],AnnotationValue[{randomGraph,Last[#]},VertexCoordinates]]&/@EdgeList[randomGraph])],EdgeLabels->"EdgeWeight",ImageSize->Full]],EdgeCount,1]
In[]:=
RandomWeightedGraphTriangleInequality[403,
-2.5

]
Out[]=
In[]:=
MixedGraph[g_,threshold_]:=Block[{replaceCount},replaceCount=Floor[thresholdEdgeCount[g]];Graph[Fold[EdgeAdd[EdgeDelete[#1,#2],First[#2]Last[#2]]&,g,RandomSample[EdgeList[g],replaceCount]],EdgeWeightThread[EdgeList[g]->(AnnotationValue[{g,#},EdgeWeight]&/@EdgeList[g])]]]
In[]:=
MixedGraph[G,.4]//InputForm
Out[]//InputForm=
Graph[{a, b, c, d, e}, {UndirectedEdge[a, b], UndirectedEdge[a, e], UndirectedEdge[a, c], UndirectedEdge[c, e], UndirectedEdge[c, d],
DirectedEdge[b, c], DirectedEdge[a, d], DirectedEdge[d, e]}, {EdgeLabels -> {EdgeWeight}, EdgeWeight -> {1, 1, 2, 1, 1, 1, 1, 1},
GraphLayout -> {Dimension -> 2}, VertexLabels -> {Automatic}}]

FindMinimumCostFlow

In[]:=
R=Graph[MixedGraph[RandomWeightedGraphTriangleInequality[54,
-1.5

],0.5]]
Out[]=