The Mixed Chinese Postman Problem is finding the minimum cost traversal of a mixed graph that covers each edge at least once. The problem is NP hard which was proved in 1976. My goal is to program a function that computes the MCPP optimum tour for a mixed graph in Mathematica.
I constructed a mixed graph paclet and submitted, updated, and documented the functions to the Paclet Repository.
I constructed a mixed graph paclet and submitted, updated, and documented the functions to the Paclet Repository.
Mixed Graph Paclet
Mixed Graph Paclet
Load the package and context:
In[]:=
PacletInstall["PeterBurbery/MixedGraphs"]
Out[]=
PacletObject
In[]:=
Needs["PeterBurbery`MixedGraphs`"]
A mixed graph has undirected and directed arcs . A mixed graph is the graph sum of an undirected graph and a digraph. A digraph is a contraction of the phrase directed graph. An edge is symmetric and can be traversed in both directions because it is undirected. An arc is directed and can be traversed in only one direction.
A graph, short for undirected graph most of the time, has undirected edges. A digraph, short for directed graph, has directed arcs.
A graph, short for undirected graph most of the time, has undirected edges. A digraph, short for directed graph, has directed arcs.
The function RandomMixedGraph constructs a graph with a certain number of nodes and edges and a value between 0 and 1 that determines what portion of the graph’s edges are directed arcs. 0 makes an undirected graph, 1 makes a digraph, and 0.68 makes a mix of an undirected graph and a digraph that is 0.68 directed, for example.
In[]:=
RandomMixedGraph[{20,54},0.68]
Out[]=
I can also construct lists of random mixed graphs:
Construct a list of 7 random mixed graphs:
In[]:=
RandomMixedGraph[{20,54},0.68,7]
Out[]=
,
,
,
,
,
,
I can also construct an array of graphs with specific dimensions:
Create an array of random mixed graphs with dimensions {2,3,5}
In[]:=
RandomMixedGraph[{20,54},0.68,{2,3,5},ImageSize->Tiny]
Out[]=
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
I created a function that converts a mixed graph into a digraph by replacing edges with pairs of arcs going in opposite directions:
In[]:=
=RandomMixedGraph[{20,54},0.68]
Out[]=
Convert the mixed graph to a digraph:
In[]:=
MixedGraphToDigraph[]
Out[]=
I also turn an undirected graph into a digraph with UndirectedGraphToMixedGraph by randomly replacing part of the edge set with directed arcs.
In[]:=
=RandomGraph[{20,54}]
Out[]=
In[]:=
UndirectedGraphToMixedGraph[,0.68]
Out[]=
I can also use graph distributions instead of nodes and edges in the graph specifications argument.
Construct a random mixed graph that follows the Barabasi-Albert graph distribution:
Construct a list of seven random mixed graphs that follows the Barabasi-Albert graph distribution:
Construct an 2 by 3 by 5 array of random mixed graphs that are modeled by the Barabasi-Albert graph distribution
I can also use options for the random mixed graph:
Construct a large mixed graph with the large graph plot theme based on the Barabasi-Albert graph distribution:
I can also created random mixed graphs with random weights:
Construct a random mixed graphs with random real weights
Construct a random mixed graph with random weights that are integers in between 1 and 7:
I can also generate lists and arrays of random weighted mixed graphs:
I can select the undirected edge set and the directed arc set of a mixed graph with MixedGraphUndirectedEdges and MixedGraphDirectedArcs, respectively:
I can also use a graph distribution:
Construct random mixed graphs with a graph distribution:
I can also specify options for the random weighted mixed graph:
Graph Properties and Data
Graph Properties and Data
I built a function GraphInformation that computes boolean properties for graphs:
Compute graph properties for the Petersen graph:
The function cannot evaluate if a mixed graph is Eulerian because the function EulerianGraphQ does not support mixed graphs. This is a topic of further research that I am working on.
TakeLargestGraphComponentBy selects the largest component in a graph based on an objective function such as EdgeCount.
Take the largest graph component by edge count:
Graphical Sequence
Graphical Sequence
The degree sequence of a graph can be computed with VertexDegree. I created a function GraphicalDegreeSequenceQ that evaluates if a sequence is graphical. One condition for a sequence to be graphical is for the sum to be even.
Compute if this random sequence is a graphical sequence;
The total is not even:
Evenness is a necessary but not a sufficient condition. A sequence can have an even sum and not be graphical.
I created two functions that function like RandomMixedGraph and RandomWeightedMixedGraph that assign names to the nodes:
I created a function to compute the convex hull of a graph based on a starting subset of the nodes:
Create a graph:
Find the convex hull starting with nodes 1, 2, and 9:
Eulerizing Graphs
Eulerizing Graphs
I created a function that Eulerizes unweighted undirected graphs and weighted undirected graphs.
In[]:=
Create a random graph
Take the largest connected component to ensure that the graph is connected
is not Eulerian
Make the graph Eulerian:
The output is now Eulerian
Eulerize a weighted undirected cost by minimizing the sum of added costs:
Eulerize the random weighted undirected graph:
Find the total cost of all the edges:
Verify the output is an Eulerian graph:
I can solve the mixed Chinese Postman Problem by Eulerizing a mixed graph. However, I have not fully figured this out yet.
My functions are built into a paclet named Mixed Graphs that can be loaded from the Paclet Repository. I will continue to update the paclet.