Converting between Graphs and Digraphs

Note that the two functions UnderlyingGraph and UnderlyingDigraph may also be used when one needs to get a copy of a graph \(G\) without \(G\)’s support and vertex/edge decorations.

OrientatedGraph(G): GrphUnd -> GrphDir

Given a graph \(G\), produce a digraph \(D\) whose vertex-set is the same as that of \(G\) and whose edge-set consists of the edges of \(G\), each given a direction. The edges of \(D\) are always directed from the lower numbered vertex to the higher numbered vertex. Thus, if \(G\) contains the edge \(\{ u,v\rbrace\), then \(D\) will have the edge \([u, v]\) if \(u < v\), otherwise the edge \([u, v]\). The support and vertex/edge decorations of \(G\) are not retained.

UnderlyingGraph(D): Grph -> GrphUnd

The underlying graph \(G\) of the graph \(D\); \(G\) has the same vertex-set as \(D\). If \(D\) is undirected, then \(G\) is a copy of \(D\) without \(D\)’s support and vertex/edge decorations. If \(D\) is directed, then two vertices \(u\) and \(v\) are adjacent in \(G\) if and only if, in \(D\), there is either an edge directed from \(u\) to \(v\) or from \(v\) to \(u\). The support and vertex/edge decorations of \(G\) are not retained.

UnderlyingDigraph(G): Grph -> GrphDir

The underlying digraph \(D\) of the graph \(G\); \(D\) has the same vertex-set as \(G\). If \(G\) is directed, then \(D\) is a copy of \(G\) without \(D\)’s support and vertex/edge decorations. If \(G\) is undirected, then if vertices \(u\) and \(v\) are adjacent in \(G\) then, in \(D\), there will be both an edge directed from \(u\) to \(v\) and an edge directed from \(v\) to \(u\). The support and vertex/edge decorations of \(G\) are not retained.