Function Repository Resource:

RandomMixedGraph

Source Notebook

Change an undirected graph into a mixed graph

Contributed by: Peter Burbery

ResourceFunction["RandomMixedGraph"][{n,m},frac]

creates a random graph with n vertices and m edges, with frac of these as directed edges and the rest undirected.

ResourceFunction["RandomMixedGraph"][{n,m},frac,spec]

creates a table of random graphs with dimensions given by spec.

Details

A mixed graph is one with both directed and undirected edges. ResourceFunction["RandomMixedGraph"] produces a mixed graph by making a random graph and converting a fraction of undirected edges into directed edges.

frac should be a number between 0 and 1 that determines the fraction of undirected edges which are coverted to directed edges. A frac value of 0 returns the original graph, while a frac value of 1 produces a fully-directed graph with randomly-oriented edges. A frac value of 0.5 would make approximately 50% of the edges directed.

Examples

Basic Examples (7)

Generate a random mixed graph with 20 nodes (vertices) and 48 edges, with a fraction of 0.75 arcs (edges):

In[1]:=

Out[1]=

Generate a graph with 0.5 directed edges:

In[2]:=

Out[2]=

Generate a list of random mixed graphs:

In[3]:=

Out[3]=

Generate an array of mixed graphs:

In[4]:=

Out[4]=

Generate a random spatial graph with 148 nodes and 0.68 directed edges:

In[5]:=

Out[5]=

Generate a list of random mixed graphs with the Barabasi-Albert graph distribution:

In[6]:=

Out[6]=

Generate a 2x3 array of random graphs based on PriceGraphDistribution:

In[7]:=

Out[7]=

Applications (10)

Make a big mixed graph:

In[8]:=

Out[8]=

Evaluate if a mixed graph has a Hamiltonian cycle:

In[9]:=

$\[ScriptCapitalG] = ResourceFunction["RandomMixedGraph"][{148, 403}, 0.68]$

Out[9]=

In[10]:=

$HamiltonianGraphQ[\[ScriptCapitalG]]$

Out[10]=

Find the graph union of two mixed graphs:

In[11]:=

Out[11]=

Make an indexed mixed graph:

In[12]:=

Out[12]=

Reverse the directed edges of a mixed graph:

In[13]:=

Out[13]=

Compute the graph product for various definitions for two mixed graphs:

In[14]:=

$\[ScriptCapitalG] = ResourceFunction["RandomMixedGraph"][{20, 54}, EulerGamma]$

Out[14]=

In[15]:=

$\[ScriptCapitalH] = ResourceFunction["RandomMixedGraph"][{20, 54}, EulerGamma]$

Out[15]=

The graphs can be very very big:

In[16]:=

$Table[GraphProduct[\[ScriptCapitalG], \[ScriptCapitalH], op, PlotLabel -> Style[op, 8]], {op, {"Cartesian", "Conormal", "Lexicographical", "Normal", "Rooted", "Tensor"}}]$

Out[16]=

Apply binary graph operations to two small mixed graphs:

In[17]:=

$\[ScriptCapitalG] = ResourceFunction["RandomMixedGraph"][{11, 29}, EulerGamma]$

Out[17]=

In[18]:=

$\[ScriptCapitalH] = ResourceFunction["RandomMixedGraph"][{11, 29}, EulerGamma]$

Out[18]=

In[19]:=

$AssociationThread[{"Boolean Graph Xor", "Boolean Graph Nand", "Graph Intersection", "Graph Union", "Graph Difference", "Graph Disjoint Union", "Cartesian Graph Product", "Conormal Graph Product", "Lexicographical Graph Product", "Normal Graph Product", "Rooted Graph Product", "Tensor Graph Product", "Graph Join", "Graph Sum"}, Map[(graphOperation |-> graphOperation[\[ScriptCapitalG], \[ScriptCapitalH]]), {BooleanGraph[Xor, ##] &, BooleanGraph[Nand, ##] &, GraphIntersection, GraphUnion, GraphDifference, GraphDisjointUnion, GraphProduct[##, "Cartesian"] &, GraphProduct[##, "Conormal"] &, GraphProduct[##, "Lexicographical"] &, GraphProduct[##, "Normal"] &, GraphProduct[##, "Rooted"] &, GraphProduct[##, "Tensor"] &, GraphJoin, GraphSum}]]$

Out[19]=

Compute unary graph operations on a large random mixed graph:

In[20]:=

$AssociationThread[{"Graph Power 2", "Graph Complement"}, Map[(graphOperation |-> graphOperation[\[ScriptCapitalG]]), {GraphPower[##, 2] &, GraphComplement}]]$