<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>Constructor Overview -- a summary of the many ways of making graphs and hypergraphs</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_cover__Ideal.html">next</a> | <a href="_connected__Graph__Components.html">previous</a> | <a href="_cover__Ideal.html">forward</a> | <a href="_connected__Graph__Components.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<hr/>
<div><h1>Constructor Overview -- a summary of the many ways of making graphs and hypergraphs</h1>
<div><p>The following is separated into four sections:</p>
<ul><li>Basic Constructors</li>
<li>Converting Types</li>
<li>Special Graphs</li>
<li>Random (Hyper)Graphs</li>
</ul>
<h2>Basic Constructors</h2>
<p>The main way of constructing <a href="___Graph.html" title="a class for graphs">Graph</a> and <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> objects is to use the <a href="_graph.html" title="constructor for Graph">graph</a> and <a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph</a> methods. These methods are overriden to provide many ways of specifying edges.</p>
<p>For the purposes of the EdgeIdeals package, every graph and hypergraph is associated to a ring whose variables correspond to the vertices of the (hyper)graph. Thus, the most explicit way to make a graph or hypergraph is by <a href="_graph.html" title="constructor for Graph">graph(PolynomialRing,List)</a> and <a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph(PolynomialRing,List)</a>.The list parameter must contain edges which themselves are lists of variables in the ring.</p>
<table class="examples"><tr><td><pre>i1 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i2 : G = graph(R, {{x,y},{x,z},{y,z},{x,w}})
o2 = Graph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o2 : Graph</pre>
</td></tr>
<tr><td><pre>i3 : H = hyperGraph(R, {{x,y,z},{x,w}})
o3 = HyperGraph{edges => {{x, y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o3 : HyperGraph</pre>
</td></tr>
</table>
<p>Probably the most convenient way of specifying edges is as a list of monomials. Using the <a href="_graph.html" title="constructor for Graph">graph(List)</a> and <a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph(List)</a> methods implicitly defines the ring of the (hyper)graph to be the ring containing the monomials in the <a href="../../Macaulay2Doc/html/___List.html" title="the class of all lists -- {...}">List</a>. The following example gives the same hypergraphs as before.</p>
<table class="examples"><tr><td><pre>i4 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i5 : G = graph {x*y, x*z, y*z, x*w}
o5 = Graph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o5 : Graph</pre>
</td></tr>
<tr><td><pre>i6 : H = hyperGraph {x*y*z, x*w}
o6 = HyperGraph{edges => {{x, y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o6 : HyperGraph</pre>
</td></tr>
</table>
<p>The <a href="_graph.html" title="constructor for Graph">graph</a> and <a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph</a> constructors can also be used to make (hyper)graphs from square-free monomial ideals.The minimal generators of the ideal become the edges of the (hyper)graph. The ideal must be generated by quadratics if the <a href="_graph.html" title="constructor for Graph">graph</a> constructor is used.</p>
<table class="examples"><tr><td><pre>i7 : G = graph ideal(x*y, x*z, y*z, x*w)
o7 = Graph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o7 : Graph</pre>
</td></tr>
</table>
<h2>Converting Types</h2>
<p>In this section, we will see how to convert between <a href="../../SimplicialComplexes/html/___Simplicial__Complex.html" title="">SimplicialComplex</a>es and <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a>s, as well as between <a href="___Graph.html" title="a class for graphs">Graph</a>s and <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a>s.</p>
<p>The methods <a href="_simplicial__Complex__To__Hyper__Graph.html" title="makes a (hyper)graph from a simplicial complex">simplicialComplexToHyperGraph</a> and <a href="_hyper__Graph__To__Simplicial__Complex.html" title="makes a simplicial complex from a (hyper)graph">hyperGraphToSimplicialComplex</a> accomplish the former conversion in the following way. In <a href="_simplicial__Complex__To__Hyper__Graph.html" title="makes a (hyper)graph from a simplicial complex">simplicialComplexToHyperGraph</a> facets of the simplicial complex become the edges of the hypergraph, while in <a href="_hyper__Graph__To__Simplicial__Complex.html" title="makes a simplicial complex from a (hyper)graph">hyperGraphToSimplicialComplex</a> the edges of the hypergraph become the facets of the new simplicial complex.</p>
<table class="examples"><tr><td><pre>i8 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i9 : H = hyperGraph {x*y*z,x*w};</pre>
</td></tr>
<tr><td><pre>i10 : D = hyperGraphToSimplicialComplex H
o10 = | xw xyz |
o10 : SimplicialComplex</pre>
</td></tr>
<tr><td><pre>i11 : simplicialComplexToHyperGraph D
o11 = HyperGraph{edges => {{x, y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o11 : HyperGraph</pre>
</td></tr>
</table>
<p>The conversion of a graph into a hypergraph and vice versa use the constructors <a href="_graph.html" title="constructor for Graph">graph</a> and <a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph</a>. Any graph can be converted to a hyperGraph, but when a hyperGraph is converted into a graph, a check is run to ensure that the edges are all of size two. An error will be produced if this is not the case.</p>
<table class="examples"><tr><td><pre>i12 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i13 : G = graph {x*y, x*z, y*z, x*w};</pre>
</td></tr>
<tr><td><pre>i14 : H = hyperGraph G
o14 = HyperGraph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o14 : HyperGraph</pre>
</td></tr>
<tr><td><pre>i15 : graph H
o15 = Graph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o15 : Graph</pre>
</td></tr>
</table>
<p>Since the <a href="___Graph.html" title="a class for graphs">Graph</a> type is a subclass of <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a>, any method that takes a <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> will also work on <a href="___Graph.html" title="a class for graphs">Graph</a>s. So the conversion from graph to hypergraph is seldom needed; it is only needed when a method works differently on graphs than on hypergraphs (see <a href="_complement__Graph.html" title="returns the complement of a graph or hypergraph">complementGraph</a> for an example).</p>
<p>On the other hand, the conversion from hypergraph to graph is very important as many methods are only defined on graphs. In the following example, we use the <a href="_is__Chordal.html" title="determines if a graph is chordal">isChordal</a> method which only applies to graphs and hence necessitates a conversion of types.</p>
<table class="examples"><tr><td><pre>i16 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i17 : D = simplicialComplex {x*y, x*z, y*z, x*w};</pre>
</td></tr>
<tr><td><pre>i18 : H = simplicialComplexToHyperGraph D
o18 = HyperGraph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o18 : HyperGraph</pre>
</td></tr>
<tr><td><pre>i19 : G = graph H
o19 = Graph{edges => {{x, y}, {x, z}, {y, z}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o19 : Graph</pre>
</td></tr>
<tr><td><pre>i20 : isChordal G
o20 = true</pre>
</td></tr>
</table>
<h2>Special Graphs</h2>
<p>In addition to the more general constructors, there a number of methods which produce certain special graphs.</p>
<p><em>Cycles</em> can be constructed using <a href="_cycle.html" title="returns a graph cycle">cycle</a> which, depending on the parameters, uses all or some of the variables in the ring to define a graph cycle.</p>
<table class="examples"><tr><td><pre>i21 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i22 : cycle R
o22 = Graph{edges => {{x, y}, {y, z}, {z, w}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o22 : Graph</pre>
</td></tr>
<tr><td><pre>i23 : cycle(R,3)
o23 = Graph{edges => {{x, y}, {y, z}, {x, z}}}
ring => R
vertices => {x, y, z, w}
o23 : Graph</pre>
</td></tr>
<tr><td><pre>i24 : cycle {x,y,w}
o24 = Graph{edges => {{x, y}, {y, w}, {x, w}}}
ring => R
vertices => {x, y, z, w}
o24 : Graph</pre>
</td></tr>
</table>
<p><em>Anti-Cycles</em>, the graph complements of cycles, can be constructed using <a href="_anti__Cycle.html" title="returns a graph of an anticycle">antiCycle</a>, which takes parameters similar to those of <a href="_cycle.html" title="returns a graph cycle">cycle</a>.</p>
<table class="examples"><tr><td><pre>i25 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i26 : antiCycle R
o26 = Graph{edges => {{x, z}, {y, w}}}
ring => R
vertices => {x, y, z, w}
o26 : Graph</pre>
</td></tr>
</table>
<p><em>Complete graphs</em> can be constructed using <a href="_complete__Graph.html" title="returns a complete graph">completeGraph</a>, which defines a graph with every possible edge between a given set a vertices.</p>
<table class="examples"><tr><td><pre>i27 : R = QQ[x,y,z,w];</pre>
</td></tr>
<tr><td><pre>i28 : completeGraph R
o28 = Graph{edges => {{x, y}, {x, z}, {x, w}, {y, z}, {y, w}, {z, w}}}
ring => R
vertices => {x, y, z, w}
o28 : Graph</pre>
</td></tr>
<tr><td><pre>i29 : completeGraph(R,3)
o29 = Graph{edges => {{x, y}, {x, z}, {y, z}}}
ring => R
vertices => {x, y, z, w}
o29 : Graph</pre>
</td></tr>
<tr><td><pre>i30 : completeGraph {x,y,w}
o30 = Graph{edges => {{x, y}, {x, w}, {y, w}}}
ring => R
vertices => {x, y, z, w}
o30 : Graph</pre>
</td></tr>
</table>
<p><em>Complete multipartite graphs</em> can be constructed using <a href="_complete__Multi__Partite.html" title="returns a complete multipartite graph">completeMultiPartite</a>, which defines a graph with every possible edge between certain partitions of the vertices. See <a href="_complete__Multi__Partite.html" title="returns a complete multipartite graph">completeMultiPartite</a> for more details.</p>
<table class="examples"><tr><td><pre>i31 : R = QQ[a,b,x,y];</pre>
</td></tr>
<tr><td><pre>i32 : completeMultiPartite(R,2,2)
o32 = Graph{edges => {{a, x}, {a, y}, {b, x}, {b, y}}}
ring => R
vertices => {a, b, x, y}
o32 : Graph</pre>
</td></tr>
</table>
<h2>Random (Hyper)Graphs</h2>
<p>Three methods are provided for the construction of random (hyper)graphs.</p>
<ul><li><span><a href="_random__Graph.html" title="returns a random graph">randomGraph</a> -- returns a random graph</span></li>
<li><span><a href="_random__Uniform__Hyper__Graph.html" title="returns a random uniform hypergraph">randomUniformHyperGraph</a> -- returns a random uniform hypergraph</span></li>
<li><span><a href="_random__Hyper__Graph.html" title="returns a random hypergraph">randomHyperGraph</a> -- returns a random hypergraph</span></li>
</ul>
<p>Each method allows you to specify the number of edges desired. For the random hypergraph methods, the sizes of the edges must also be specified.</p>
<table class="examples"><tr><td><pre>i33 : R = QQ[x,y,z,u,v];</pre>
</td></tr>
<tr><td><pre>i34 : randomGraph(R,3)
o34 = Graph{edges => {{x, v}, {x, y}, {x, z}}}
ring => R
vertices => {x, y, z, u, v}
o34 : Graph</pre>
</td></tr>
<tr><td><pre>i35 : randomUniformHyperGraph(R,2,3)
o35 = HyperGraph{edges => {{z, u}, {y, z}, {x, z}}}
ring => R
vertices => {x, y, z, u, v}
o35 : HyperGraph</pre>
</td></tr>
<tr><td><pre>i36 : randomHyperGraph(R,{3,2,1})
o36 = HyperGraph{edges => {{x, v, z}, {y, z}, {u}}}
ring => R
vertices => {x, y, z, u, v}
o36 : HyperGraph</pre>
</td></tr>
</table>
<p>The <a href="_random__Hyper__Graph.html" title="returns a random hypergraph">randomHyperGraph</a> method is not guaranteed to return a hypergraph; sometimes it returns null. Please see the documentation of this method for more details.</p>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="___Extended_sp__Example.html" title="an extended example using EdgeIdeals">Extended Example</a> -- an extended example using EdgeIdeals</span></li>
<li><span><a href="___Graph.html" title="a class for graphs">Graph</a> -- a class for graphs</span></li>
<li><span><a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> -- a class for hypergraphs</span></li>
<li><span><a href="_graph.html" title="constructor for Graph">graph</a> -- constructor for Graph</span></li>
<li><span><a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph</a> -- constructor for HyperGraph</span></li>
<li><span><a href="_simplicial__Complex__To__Hyper__Graph.html" title="makes a (hyper)graph from a simplicial complex">simplicialComplexToHyperGraph</a> -- makes a (hyper)graph from a simplicial complex</span></li>
<li><span><a href="_hyper__Graph__To__Simplicial__Complex.html" title="makes a simplicial complex from a (hyper)graph">hyperGraphToSimplicialComplex</a> -- makes a simplicial complex from a (hyper)graph</span></li>
<li><span><a href="_cycle.html" title="returns a graph cycle">cycle</a> -- returns a graph cycle</span></li>
<li><span><a href="_anti__Cycle.html" title="returns a graph of an anticycle">antiCycle</a> -- returns a graph of an anticycle</span></li>
<li><span><a href="_complete__Graph.html" title="returns a complete graph">completeGraph</a> -- returns a complete graph</span></li>
<li><span><a href="_complete__Multi__Partite.html" title="returns a complete multipartite graph">completeMultiPartite</a> -- returns a complete multipartite graph</span></li>
<li><span><a href="_random__Graph.html" title="returns a random graph">randomGraph</a> -- returns a random graph</span></li>
<li><span><a href="_random__Uniform__Hyper__Graph.html" title="returns a random uniform hypergraph">randomUniformHyperGraph</a> -- returns a random uniform hypergraph</span></li>
<li><span><a href="_random__Hyper__Graph.html" title="returns a random hypergraph">randomHyperGraph</a> -- returns a random hypergraph</span></li>
</ul>
</div>
</div>
</body>
</html>
