This is Graphs.info, produced by Macaulay2, version 1.20

Graphs
******

Authors
=======

  * Jack Burkart <jburkar1@nd.edu>
  * David Cook II (see http://ux1.eiu.edu/~dwcook/ ) <dcook.math@gmail.com>
  * Caroline Jansen <cjansen@alumni.nd.edu>
  * Amelia Taylor <originalbrickhouse@gmail.com>
  * Augustine O'Keefe <aokeefe@tulane.edu>
  * Contributors of note: Carlos Amendola, Alex Diaz, Luis David Garcia Puente,
    Roser Homs Pons, Olga Kuznetsova,  Shaowei Lin, Sonja Mapes, Harshit J
    Motwani, Mike Stillman, Doug Torrance

Version
=======

This documentation describes version 0.3.4 of Graphs.

Source code
===========

The source code from which this documentation is derived is in the file
Graphs.m2 (see common/share/Macaulay2/Graphs.m2 ).

Exports
=======

  * Types
      * Digraph
      * Graph
      * SortedDigraph -- hashtable used in topSort
  * Functions and commands
      * addEdge -- A method for adding edges to a graph
      * "addEdges'" -- see addEdge, -- A method for adding edges
        to a graph
      * addVertex -- A method for adding a set of vertices to
        a graph
      * "addVertices" -- see addVertex, -- A method for adding
        a set of vertices to a graph
      * adjacencyMatrix -- Returns the adjacency matrix
        of a Graph or Digraph
      * barbellGraph -- Returns the barbell graph
      * barycenter -- Returns the barycenter of a grah
      * BFS (missing documentation)
      * bipartiteColoring -- Returns a coloring of a
        bipartite graph
      * breadthFirstSearch -- runs a breadth first
        search on the digraph starting at a specified node and returns a list
        of the vertices in the order they were discovered
      * cartesianProduct -- Computes the cartesian
        product of two graphs
      * center -- Returns the center of a graph
      * children -- returns the children of a vertex of a
        digraph
      * chromaticNumber -- Computes the chromatic
        number of a graph
      * circularLadder -- Returns a circular ladder
        graph
      * cliqueComplex -- Returns the clique complex of a
        graph
      * cliqueNumber -- Returns the clique number of a
        graph
      * closedNeighborhood -- Returns the closed
        neighborhood of a vertex of a graph
      * clusteringCoefficient -- a method for
        computing the clustering coefficient of a Graph
      * cocktailParty -- Returns a cocktail party graph
      * complementGraph -- Returns the complement of a
        graph
      * completeGraph -- Constructs a complete graph
      * completeMultipartiteGraph, --
        constructs a complete multipartite graph
      * coverIdeal -- Returns the vertex cover ideal of a
        graph
      * criticalEdges -- Finds the critical edges of a
        graph
      * crownGraph -- Returns a crown graph
      * cycleGraph -- Constructs a cycle graph
      * degeneracy -- Computes the degeneracy of a graph
      * degreeCentrality -- Returns the
        degreeCentrality of a vertex of a graph
      * degreeIn -- returns the "in-degree" of a vertex in a
        digraph
      * degreeMatrix -- Returns the degree matrix of a
        graph
      * degreeOut -- returns the "out-degree" of a vertex in
        a digraph
      * degreeSequence -- the degree sequence of a graph
      * deleteEdges -- Deletes a list of edges from a graph
      * deleteVertex -- a method for deleting the vertex
        of a graph
      * deleteVertices -- Deletes specified vertices
        from a digraph or graph
      * density -- computes the density of a graph
      * depthFirstSearch -- runs a depth first search
        on the digraph or digraph and returns the discovery time and finishing
        time for each vertex in the digraph
      * descendants -- returns the descendants of a digraph
      * descendents (missing documentation)
      * DFS (missing documentation)
      * digraph -- Constructs a digraph
      * digraphTranspose -- returns the transpose of a
        Digraph
      * "tensorProduct" -- see directProduct, -- Computes
        the direct product of two graphs
      * disjointUnion -- Returns the disjoint union of a
        list of graphs.
      * displayGraph -- displays a digraph or graph using
        Graphviz
      * distance -- Computes the distance between two
        vertexSet in a graph
      * distanceMatrix -- Computes the distance matrix
        of a digraph
      * doubleStar -- returns a double star graph
      * eccentricity -- Returns the eccentricity of a
        vertex of a graph
      * edgeConnectivity -- computes the edge
        connectivity of a graph
      * edgeCuts -- returns the edge cuts of a graph
      * edgeIdeal -- returns the edge ideal of a graph
      * edges -- Returns the edges of a digraph or graph
      * expansion -- returns the expansion of a graph
      * findPaths -- finds all the paths in a digraph of a
        given length starting at a given vertex
      * floydWarshall -- runs the Floyd-Warshall
        algorithm on a digraph to determine the minimum distance from one
        vertex to another in the digraph
      * "foreFathers" -- see forefathers, -- returns the
        forefathers of a digraph
      * forefathers -- returns the forefathers of a digraph
      * friendshipGraph -- Returns a friendship Graph
      * generalizedPetersenGraph -- Returns a
        generalized petersen graph
      * girth -- A method for computing the girth of a graph
      * graph -- Constructs a simple graph
      * graphComposition -- A method for composing two
        graphs
      * graphLibrary -- constructs a graph of a type
        specified in the string input
      * graphPower -- constructs a graph raised to a power
      * hasEulerianTrail -- determines whether a graph
        or a digraph has an Eulerian trail
      * hasOddHole -- checks whether a graph has a odd hole
      * incidenceMatrix -- computes the incidence
        matrix of a graph
      * independenceComplex -- constructs the
        independence complex of a graph
      * independenceNumber -- computes the
        independence number of a graph
      * indexLabelGraph -- Relabels the vertices of a
        graph or digraph according to their indices, indexed from 0.
      * inducedSubgraph -- A method for finding the
        induced subgraph of any Graph or Digraph
      * isBipartite -- determines whether a graph is
        bipartite
      * isChordal -- checks whether a graph is chordal
      * isCM -- determines if a graph is Cohen-Macaulay
      * isConnected -- determines whether a graph is
        connected
      * isCyclic -- determines whether a graph is cyclic
      * isEulerian -- determines if a graph or digraph is
        Eulerian
      * isForest -- determines whether a graph is a forest
      * isLeaf -- determines whether a vertex is a leaf
      * isPerfect -- checks whether a graph is perfect
      * isReachable -- checks if a vertex u is reachable
        from a vertex v
      * isRegular -- determines whether a graph is regular
      * isRigid -- checks if a graph is rigid
      * isSimple -- checks if a graph is simple
      * isSink -- determines if a vertex of a digraph is a sink
        or not
      * isSource -- determines if a vertex of a digraph is a
        source or not
      * isStronglyConnected -- checks if a digraph
        is strongly connected
      * isTree -- determines whether a graph is a tree
      * isWeaklyConnected -- checks if a digraph is
        weakly connected
      * kneserGraph -- constructs a kneser graph of
        specified size
      * ladderGraph -- Returns a ladder graph
      * laplacianMatrix -- Returns the laplacian matrix
        of a graph
      * leaves -- lists the leaves of a tree graph
      * lexicographicProduct (missing documentation)
      * lineGraph -- Returns the line graph of an undirected
        graph
      * lollipopGraph -- constructs a lollipop graph
      * lowestCommonAncestors -- determines the
        lowest common ancestors between two vertexSet
      * minimalDegree -- computes the minimal degree of a
        graph
      * minimalVertexCuts -- finds the minimal vertex
        cuts of a graph
      * monomialGraph -- Returns a monomial graph
      * neighbors -- returns the neighbors of a vertex in a
        graph
      * nondescendants -- returns the nondescendants of
        a vertex of a digraph
      * nondescendents (missing documentation)
      * nonneighbors -- returns the non-neighbors of a
        vertex in a graph
      * numberOfComponents -- computes the number of
        connected components of a graph
      * numberOfTriangles -- counts how many
        subtriangles are present in a graph
      * parents -- returns the parents of a vertex on a digraph
      * pathGraph -- A method that makes a path graph
      * prismGraph (missing documentation)
      * radius -- Returns the radius of a graph
      * rattleGraph -- Returns a rattle graph
      * reachable -- Returns the vertices reachable in a
        digraph from a given collection of vertices
      * reindexBy -- reindexes the vertices according to the
        input ordering.
      * removeNodes (missing documentation)
      * reverseBreadthFirstSearch -- runs a
        reverse breadth first search on the digraph and returns a list of the
        vertexSet in the order they were discovered
      * showTikZ -- Writes a string of TikZ syntax that can be
        pasted into a .tex file to display G
      * sinks -- returns the sinks of a digraph
      * sources -- returns the sources of a digraph
      * spanningForest -- constructs a spanning forest
        of a graph
      * spectrum -- Returns the spectrum of a graph
      * starGraph -- Returns a star graph
      * strongProduct -- a method for taking the strong
        product of two graphs
      * thresholdGraph -- A method that generates a
        threshold graph from a binary list
      * topologicalSort -- outputs a list of vertices
        in a topologically sorted order of a DAG.
      * topSort -- outputs a hashtable containing original
        digraph, new digraph with vertices topologically sorted and a map from
        vertices of original digraph to new digraph.
      * underlyingGraph -- Returns the underlying graph
        of a digraph
      * vertexConnectivity -- computes the vertex
        connectivity of a graph
      * vertexCoverNumber -- returns the vertex cover
        number of a graph
      * vertexCovers -- returns a list of the minimal
        vertex covers of a graph
      * vertexCuts -- lists all the vertex cuts of a graph
      * vertexMultiplication
      * vertexSet -- Returns the vertices of a graph or
        digraph
      * wheelGraph -- Constructs a wheel graph
      * windmillGraph -- Constructs a windmill graph
      * writeDotFile -- Writes a graph to a dot file with
        a specified filename
  * Methods
      * "addEdge(Digraph,Set)" -- see addEdge, -- A method for
        adding edges to a graph
      * "addEdges'(Digraph,List)" -- see addEdge, -- A method
        for adding edges to a graph
      * "addVertex(Digraph,Thing)" -- see addVertex, -- A
        method for adding a set of vertices to a graph
      * "addVertices(Digraph,List)" -- see addVertex, -- A
        method for adding a set of vertices to a graph
      * "adjacencyMatrix(Digraph)" -- see adjacencyMatrix,
        -- Returns the adjacency matrix of a Graph or Digraph
      * "barbellGraph(ZZ)" -- see barbellGraph, -- Returns
        the barbell graph
      * "barycenter(Graph)" -- see barycenter, -- Returns the
        barycenter of a grah
      * "bipartiteColoring(Graph)" -- see bipartiteColoring,
        -- Returns a coloring of a bipartite graph
      * "breadthFirstSearch(Digraph,Thing)" -- see breadthFirstSearch,
        -- runs a breadth first search on the digraph
        starting at a specified node and returns a list of the vertices in the
        order they were discovered
      * "cartesianProduct(Graph,Graph)" -- see cartesianProduct,
        -- Computes the cartesian product of two graphs
      * "center(Graph)" -- see center, -- Returns the center of a
        graph
      * "children(Digraph,Thing)" -- see children, -- returns
        the children of a vertex of a digraph
      * "chromaticNumber(Graph)" -- see chromaticNumber,
        -- Computes the chromatic number of a graph
      * "circularLadder(ZZ)" -- see circularLadder, --
        Returns a circular ladder graph
      * "cliqueComplex(Graph)" -- see cliqueComplex, --
        Returns the clique complex of a graph
      * "cliqueNumber(Graph)" -- see cliqueNumber, --
        Returns the clique number of a graph
      * "closedNeighborhood(Graph,Thing)" -- see closedNeighborhood,
        -- Returns the closed neighborhood of a vertex of a
        graph
      * "clusteringCoefficient(Graph)" -- see clusteringCoefficient,
        -- a method for computing the clustering
        coefficient of a Graph
      * "clusteringCoefficient(Graph,Thing)" -- see
        clusteringCoefficient, -- a method for computing
        the clustering coefficient of a Graph
      * "cocktailParty(ZZ)" -- see cocktailParty, --
        Returns a cocktail party graph
      * "complementGraph(Graph)" -- see complementGraph,
        -- Returns the complement of a graph
      * "completeGraph(ZZ)" -- see completeGraph, --
        Constructs a complete graph
      * "completeMultipartiteGraph(List)" -- see
        completeMultipartiteGraph, -- constructs a
        complete multipartite graph
      * connectedComponents(Graph), --
        Computes the connected components of a graph
      * "coverIdeal(Graph)" -- see coverIdeal, -- Returns the
        vertex cover ideal of a graph
      * "criticalEdges(Graph)" -- see criticalEdges, --
        Finds the critical edges of a graph
      * "crownGraph(ZZ)" -- see crownGraph, -- Returns a
        crown graph
      * "cycleGraph(ZZ)" -- see cycleGraph, -- Constructs a
        cycle graph
      * "degeneracy(Graph)" -- see degeneracy, -- Computes
        the degeneracy of a graph
      * degree(Digraph,Thing) -- returns
        the degree of a vertex in a digraph
      * "degreeCentrality(Graph,Thing)" -- see degreeCentrality,
        -- Returns the degreeCentrality of a vertex of a
        graph
      * "degreeIn(Digraph,Thing)" -- see degreeIn, -- returns
        the "in-degree" of a vertex in a digraph
      * "degreeMatrix(Digraph)" -- see degreeMatrix, --
        Returns the degree matrix of a graph
      * "degreeOut(Digraph,Thing)" -- see degreeOut, --
        returns the "out-degree" of a vertex in a digraph
      * "degreeSequence(Graph)" -- see degreeSequence, --
        the degree sequence of a graph
      * "deleteEdges(Graph,List)" -- see deleteEdges, --
        Deletes a list of edges from a graph
      * "deleteVertex(Graph,Thing)" -- see deleteVertex, --
        a method for deleting the vertex of a graph
      * "deleteVertices(Digraph,List)" -- see deleteVertices,
        -- Deletes specified vertices from a digraph or graph
      * "density(Graph)" -- see density, -- computes the density
        of a graph
      * "depthFirstSearch(Digraph)" -- see depthFirstSearch,
        -- runs a depth first search on the digraph or
        digraph and returns the discovery time and finishing time for each
        vertex in the digraph
      * "descendants(Digraph,Thing)" -- see descendants, --
        returns the descendants of a digraph
      * diameter(Graph) -- Computes the diameter of
        a graph
      * "digraph(HashTable)" -- see digraph, -- Constructs a
        digraph
      * "digraph(List)" -- see digraph, -- Constructs a digraph
      * "digraph(List,List)" -- see digraph, -- Constructs a
        digraph
      * "digraph(List,Matrix)" -- see digraph, -- Constructs a
        digraph
      * "digraph(Matrix)" -- see digraph, -- Constructs a
        digraph
      * "digraphTranspose(Digraph)" -- see digraphTranspose,
        -- returns the transpose of a Digraph
      * "directProduct(Graph,Graph)" -- see directProduct,
        -- Computes the direct product of two graphs
      * "disjointUnion(List)" -- see disjointUnion, --
        Returns the disjoint union of a list of graphs.
      * "displayGraph(Digraph)" -- see displayGraph, --
        displays a digraph or graph using Graphviz
      * "displayGraph(String,Digraph)" -- see displayGraph,
        -- displays a digraph or graph using Graphviz
      * "displayGraph(String,String,Digraph)" -- see displayGraph,
        -- displays a digraph or graph using Graphviz
      * "distance(Digraph,Thing,Thing)" -- see distance, --
        Computes the distance between two vertexSet in a graph
      * "distanceMatrix(Digraph)" -- see distanceMatrix,
        -- Computes the distance matrix of a digraph
      * "doubleStar(ZZ,ZZ)" -- see doubleStar, -- returns a
        double star graph
      * "eccentricity(Graph,Thing)" -- see eccentricity, --
        Returns the eccentricity of a vertex of a graph
      * "edgeConnectivity(Graph)" -- see edgeConnectivity,
        -- computes the edge connectivity of a graph
      * "edgeCuts(Graph)" -- see edgeCuts, -- returns the edge
        cuts of a graph
      * "edgeIdeal(Graph)" -- see edgeIdeal, -- returns the
        edge ideal of a graph
      * "edges(Digraph)" -- see edges, -- Returns the edges of a
        digraph or graph
      * "edges(Graph)" -- see edges, -- Returns the edges of a
        digraph or graph
      * "expansion(Graph)" -- see expansion, -- returns the
        expansion of a graph
      * "findPaths(Digraph,Thing,ZZ)" -- see findPaths, --
        finds all the paths in a digraph of a given length starting at a given
        vertex
      * "floydWarshall(Digraph)" -- see floydWarshall, --
        runs the Floyd-Warshall algorithm on a digraph to determine the minimum
        distance from one vertex to another in the digraph
      * "forefathers(Digraph,Thing)" -- see forefathers, --
        returns the forefathers of a digraph
      * "friendshipGraph(ZZ)" -- see friendshipGraph, --
        Returns a friendship Graph
      * "generalizedPetersenGraph(ZZ,ZZ)" -- see
        generalizedPetersenGraph, -- Returns a
        generalized petersen graph
      * "girth(Graph)" -- see girth, -- A method for computing the
        girth of a graph
      * "graph(HashTable)" -- see graph, -- Constructs a simple
        graph
      * "graph(List)" -- see graph, -- Constructs a simple graph
      * "graph(List,List)" -- see graph, -- Constructs a simple
        graph
      * "graph(List,Matrix)" -- see graph, -- Constructs a simple
        graph
      * "graph(Matrix)" -- see graph, -- Constructs a simple graph
      * graph(Digraph) -- Returns the legacy G#graph
        hash table
      * "graphComposition(Graph,Graph)" -- see graphComposition,
        -- A method for composing two graphs
      * "graphLibrary(String)" -- see graphLibrary, --
        constructs a graph of a type specified in the string input
      * "graphPower(Graph,ZZ)" -- see graphPower, --
        constructs a graph raised to a power
      * "hasEulerianTrail(Digraph)" -- see hasEulerianTrail,
        -- determines whether a graph or a digraph has an
        Eulerian trail
      * "hasEulerianTrail(Graph)" -- see hasEulerianTrail,
        -- determines whether a graph or a digraph has an
        Eulerian trail
      * "hasOddHole(Graph)" -- see hasOddHole, -- checks
        whether a graph has a odd hole
      * html(Digraph) -- Create an .svg
        representation of a graph or digraph
      * "incidenceMatrix(Graph)" -- see incidenceMatrix,
        -- computes the incidence matrix of a graph
      * "independenceComplex(Graph)" -- see independenceComplex,
        -- constructs the independence complex of a graph
      * "independenceNumber(Graph)" -- see independenceNumber,
        -- computes the independence number of a graph
      * "indexLabelGraph(Digraph)" -- see indexLabelGraph,
        -- Relabels the vertices of a graph or digraph
        according to their indices, indexed from 0.
      * "indexLabelGraph(Graph)" -- see indexLabelGraph,
        -- Relabels the vertices of a graph or digraph according to their
        indices, indexed from 0.
      * "inducedSubgraph(Digraph,List)" -- see inducedSubgraph,
        -- A method for finding the induced subgraph of any
        Graph or Digraph
      * "inducedSubgraph(Graph,List)" -- see inducedSubgraph,
        -- A method for finding the induced subgraph of any
        Graph or Digraph
      * "isBipartite(Graph)" -- see isBipartite, --
        determines whether a graph is bipartite
      * "isChordal(Graph)" -- see isChordal, -- checks whether
        a graph is chordal
      * "isCM(Graph)" -- see isCM, -- determines if a graph is
        Cohen-Macaulay
      * "isConnected(Graph)" -- see isConnected, --
        determines whether a graph is connected
      * "isCyclic(Graph)" -- see isCyclic, -- determines
        whether a graph is cyclic
      * isCyclic(Digraph) -- determines whether a
        digraph is cyclic
      * "isEulerian(Digraph)" -- see isEulerian, --
        determines if a graph or digraph is Eulerian
      * "isEulerian(Graph)" -- see isEulerian, -- determines
        if a graph or digraph is Eulerian
      * "isForest(Graph)" -- see isForest, -- determines
        whether a graph is a forest
      * "isLeaf(Graph,Thing)" -- see isLeaf, -- determines
        whether a vertex is a leaf
      * "isPerfect(Graph)" -- see isPerfect, -- checks whether
        a graph is perfect
      * "isReachable(Digraph,Thing,Thing)" -- see isReachable,
        -- checks if a vertex u is reachable from a vertex v
      * "isRegular(Graph)" -- see isRegular, -- determines
        whether a graph is regular
      * "isRigid(Graph)" -- see isRigid, -- checks if a graph is
        rigid
      * "isSimple(Graph)" -- see isSimple, -- checks if a graph
        is simple
      * "isSink(Digraph,Thing)" -- see isSink, -- determines if a
        vertex of a digraph is a sink or not
      * "isSource(Digraph,Thing)" -- see isSource, --
        determines if a vertex of a digraph is a source or not
      * "isStronglyConnected(Digraph)" -- see isStronglyConnected,
        -- checks if a digraph is strongly connected
      * "isTree(Graph)" -- see isTree, -- determines whether a
        graph is a tree
      * "isWeaklyConnected(Digraph)" -- see isWeaklyConnected,
        -- checks if a digraph is weakly connected
      * "kneserGraph(ZZ,ZZ)" -- see kneserGraph, --
        constructs a kneser graph of specified size
      * "ladderGraph(ZZ)" -- see ladderGraph, -- Returns a
        ladder graph
      * "laplacianMatrix(Graph)" -- see laplacianMatrix,
        -- Returns the laplacian matrix of a graph
      * "leaves(Graph)" -- see leaves, -- lists the leaves of a
        tree graph
      * "lineGraph(Graph)" -- see lineGraph, -- Returns the
        line graph of an undirected graph
      * "lollipopGraph(ZZ,ZZ)" -- see lollipopGraph, --
        constructs a lollipop graph
      * "lowestCommonAncestors(Digraph,Thing,Thing)" -- see
        lowestCommonAncestors, -- determines the lowest
        common ancestors between two vertexSet
      * "minimalDegree(Graph)" -- see minimalDegree, --
        computes the minimal degree of a graph
      * "minimalVertexCuts(Graph)" -- see minimalVertexCuts,
        -- finds the minimal vertex cuts of a graph
      * "monomialGraph(MonomialIdeal,ZZ)" -- see monomialGraph,
        -- Returns a monomial graph
      * "neighbors(Graph,Thing)" -- see neighbors, -- returns
        the neighbors of a vertex in a graph
      * "nondescendants(Digraph,Thing)" -- see nondescendants,
        -- returns the nondescendants of a vertex of a digraph
      * "nonneighbors(Graph,Thing)" -- see nonneighbors, --
        returns the non-neighbors of a vertex in a graph
      * "numberOfComponents(Graph)" -- see numberOfComponents,
        -- computes the number of connected components of a
        graph
      * "numberOfTriangles(Graph)" -- see numberOfTriangles,
        -- counts how many subtriangles are present in a
        graph
      * "parents(Digraph,Thing)" -- see parents, -- returns the
        parents of a vertex on a digraph
      * "pathGraph(ZZ)" -- see pathGraph, -- A method that
        makes a path graph
      * "radius(Graph)" -- see radius, -- Returns the radius of a
        graph
      * "rattleGraph(ZZ,ZZ)" -- see rattleGraph, -- Returns
        a rattle graph
      * "reachable(Digraph,List)" -- see reachable, -- Returns
        the vertices reachable in a digraph from a given collection of vertices
      * "reachable(Digraph,Set)" -- see reachable, -- Returns
        the vertices reachable in a digraph from a given collection of vertices
      * "reindexBy(Digraph,String)" -- see reindexBy, --
        reindexes the vertices according to the input ordering.
      * "reindexBy(Graph,String)" -- see reindexBy, --
        reindexes the vertices according to the input ordering.
      * "reverseBreadthFirstSearch(Digraph,Thing)" -- see
        reverseBreadthFirstSearch, -- runs a reverse
        breadth first search on the digraph and returns a list of the vertexSet
        in the order they were discovered
      * "showTikZ(Digraph)" -- see showTikZ, -- Writes a string
        of TikZ syntax that can be pasted into a .tex file to display G
      * "sinks(Digraph)" -- see sinks, -- returns the sinks of a
        digraph
      * "sources(Digraph)" -- see sources, -- returns the
        sources of a digraph
      * "spanningForest(Graph)" -- see spanningForest, --
        constructs a spanning forest of a graph
      * "spectrum(Graph)" -- see spectrum, -- Returns the
        spectrum of a graph
      * "starGraph(ZZ)" -- see starGraph, -- Returns a star
        graph
      * "strongProduct(Graph,Graph)" -- see strongProduct,
        -- a method for taking the strong product of two graphs
      * "thresholdGraph(List)" -- see thresholdGraph, --
        A method that generates a threshold graph from a binary list
      * "topologicalSort(Digraph)" -- see topologicalSort,
        -- outputs a list of vertices in a topologically
        sorted order of a DAG.
      * "topologicalSort(Digraph,String)" -- see topologicalSort,
        -- outputs a list of vertices in a topologically
        sorted order of a DAG.
      * "topSort(Digraph)" -- see topSort, -- outputs a
        hashtable containing original digraph, new digraph with vertices
        topologically sorted and a map from vertices of original digraph to new
        digraph.
      * "topSort(Digraph,String)" -- see topSort, -- outputs a
        hashtable containing original digraph, new digraph with vertices
        topologically sorted and a map from vertices of original digraph to new
        digraph.
      * "underlyingGraph(Digraph)" -- see underlyingGraph,
        -- Returns the underlying graph of a digraph
      * "vertexConnectivity(Graph)" -- see vertexConnectivity,
        -- computes the vertex connectivity of a graph
      * "vertexCoverNumber(Graph)" -- see vertexCoverNumber,
        -- returns the vertex cover number of a graph
      * "vertexCovers(Graph)" -- see vertexCovers, --
        returns a list of the minimal vertex covers of a graph
      * "vertexCuts(Graph)" -- see vertexCuts, -- lists all
        the vertex cuts of a graph
      * "vertexMultiplication(Graph,Thing,Thing)" -- see
        vertexMultiplication,
      * "vertexSet(Digraph)" -- see vertexSet, -- Returns the
        vertices of a graph or digraph
      * "vertices(Digraph)" -- see vertexSet, -- Returns the
        vertices of a graph or digraph
      * "wheelGraph(ZZ)" -- see wheelGraph, -- Constructs a
        wheel graph
      * "windmillGraph(ZZ,ZZ)" -- see windmillGraph, --
        Constructs a windmill graph
      * "writeDotFile(String,Digraph)" -- see writeDotFile,
        -- Writes a graph to a dot file with a specified filename
      * "writeDotFile(String,Graph)" -- see writeDotFile,
        -- Writes a graph to a dot file with a specified filename
  * Symbols
      * discoveryTime (missing documentation)
      * finishingTime (missing documentation)
      * "EntryMode" -- see graph, -- Constructs a simple graph
      * newDigraph -- key used in the output of topSort
      * simpleGraph (missing documentation)
      * Singletons (missing documentation)

For the programmer
==================

The object Graphs, is a package (Macaulay2Doc).

addEdge -- A method for adding edges to a graph
***********************************************

Synopsis
========

  * Usage:
        H = addEdges' (G, L)
        H = addEdge (G, S)
  * Inputs:
      * G, a graph,
      * L, a list (Macaulay2Doc), This List should be composed of
        other Lists, just as one would input an edge set
      * S, a set (Macaulay2Doc), This is used when only one edge
        needs to be used via addEdge
  * Outputs:
      * H, a graph, The Graph with the new edge

Description
===========

This method will take in a Graph and a List of new edges, and output a graph
with these new edges along with the previous edges.

+------------------------------------+
|i1 : H = cycleGraph 4;              |
+------------------------------------+
|i2 : G = addEdge(H, set {0,2})      |
|                                    |
|o2 = Graph{0 => {1, 2, 3}}          |
|           1 => {0, 2}              |
|           2 => {0, 1, 3}           |
|           3 => {0, 2}              |
|                                    |
|o2 : Graph                          |
+------------------------------------+
|i3 : G = addEdges'(H, {{0,2},{3,1}})|
|                                    |
|o3 = Graph{0 => {1, 2, 3}}          |
|           1 => {0, 2, 3}           |
|           2 => {0, 1, 3}           |
|           3 => {0, 1, 2}           |
|                                    |
|o3 : Graph                          |
+------------------------------------+

See also
========

  * addVertices -- A method for adding a set of vertices to a
    graph

Ways to use addEdge :
=====================

  * "addEdge(Digraph,Set)"

For the programmer
==================

The object addEdge, is a method function (Macaulay2Doc).

addVertex -- A method for adding a set of vertices to a graph
*************************************************************

Synopsis
========

  * Usage:
        H = addVertex (G, v)
        H = addVertices (G, L)
  * Inputs:
      * G, a graph,
      * L, a list (Macaulay2Doc), list of the names of the new
        vertices
      * v, a thing (Macaulay2Doc), name of the new vertex
  * Outputs:
      * H, a graph, This is the graph with the additional
        vertices specified in L

Description
===========

This method will add vertices (as singletons) to any already present graph.
Note that if you add a vertex that is already in the vertex set of the input
graph, that vertex will be ignored.

+--------------------------------+
|i1 : G = completeGraph 4        |
|                                |
|o1 = Graph{0 => {1, 2, 3}}      |
|           1 => {0, 2, 3}       |
|           2 => {0, 1, 3}       |
|           3 => {0, 1, 2}       |
|                                |
|o1 : Graph                      |
+--------------------------------+
|i2 : H = addVertices(G, {3,4,5})|
|                                |
|o2 = Graph{0 => {1, 2, 3}}      |
|           1 => {0, 2, 3}       |
|           2 => {0, 1, 3}       |
|           3 => {0, 1, 2}       |
|           4 => {}              |
|           5 => {}              |
|                                |
|o2 : Graph                      |
+--------------------------------+

See also
========

  * addEdges' -- A method for adding edges to a graph

Ways to use addVertex :
=======================

  * "addVertex(Digraph,Thing)"

For the programmer
==================

The object addVertex, is a method function (Macaulay2Doc).

adjacencyMatrix -- Returns the adjacency matrix of a Graph or Digraph
*********************************************************************

Synopsis
========

  * Usage:
        A = adjacencyMatrix D
        A = adjacencyMatrix G
  * Inputs:
      * D, a digraph,
      * G, a graph,
  * Outputs:
      * A, a matrix (Macaulay2Doc),

Description
===========

The adjacency matrix is the n by n matrix (where n is the number of vertices in
graph/digraph G) with rows and columns indexed by the vertices of G. Entry
A_(u,v) is 1 if and only if {u,v} is an edge of G and 0 otherwise. It is easy
to observe that if we just use a simple graph G, then its adjacency matrix must
be symmetric, but if we use a digraph, then it is not necessarily symmetric.

+---------------------------------------------------------------+
|i1 : D = digraph({{1,2},{2,3},{3,4},{4,3}},EntryMode=>"edges");|
+---------------------------------------------------------------+
|i2 : adjacencyMatrix D                                         |
|                                                               |
|o2 = | 0 1 0 0 |                                               |
|     | 0 0 1 0 |                                               |
|     | 0 0 0 1 |                                               |
|     | 0 0 1 0 |                                               |
|                                                               |
|              4        4                                       |
|o2 : Matrix ZZ  <--- ZZ                                        |
+---------------------------------------------------------------+
|i3 : G = graph({1,2,3,4}, {{1,2},{2,3},{3,4},{4,3}})           |
|                                                               |
|o3 = Graph{1 => {2}   }                                        |
|           2 => {1, 3}                                         |
|           3 => {2, 4}                                         |
|           4 => {3}                                            |
|                                                               |
|o3 : Graph                                                     |
+---------------------------------------------------------------+
|i4 : adjacencyMatrix G                                         |
|                                                               |
|o4 = | 0 1 0 0 |                                               |
|     | 1 0 1 0 |                                               |
|     | 0 1 0 1 |                                               |
|     | 0 0 1 0 |                                               |
|                                                               |
|              4        4                                       |
|o4 : Matrix ZZ  <--- ZZ                                        |
+---------------------------------------------------------------+

See also
========

  * degreeMatrix -- Returns the degree matrix of a graph
  * laplacianMatrix -- Returns the laplacian matrix of
    a graph

Ways to use adjacencyMatrix :
=============================

  * "adjacencyMatrix(Digraph)"

For the programmer
==================

The object adjacencyMatrix, is a method function (Macaulay2Doc).

barbellGraph -- Returns the barbell graph
*****************************************

Synopsis
========

  * Usage:
        G = barbellGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph, The barbell graph

Description
===========

The barbell graph corresponding to an integer n is formed by the disjoint union
of two complete graphs on n vertices joined together by exactly on edge
connecting these complete graphs.

+-------------------------------------+
|i1 : G = barbellGraph 6              |
|                                     |
|o1 = Graph{0 => {1, 2, 3, 4, 5}     }|
|           1 => {0, 2, 3, 4, 5}      |
|           2 => {0, 1, 3, 4, 5}      |
|           3 => {0, 1, 2, 4, 5}      |
|           4 => {0, 1, 2, 3, 5}      |
|           5 => {0, 1, 2, 3, 4, 6}   |
|           6 => {5, 7, 8, 9, 10, 11} |
|           7 => {6, 8, 9, 10, 11}    |
|           8 => {6, 7, 9, 10, 11}    |
|           9 => {6, 7, 8, 10, 11}    |
|           10 => {6, 7, 8, 9, 11}    |
|           11 => {6, 7, 8, 9, 10}    |
|                                     |
|o1 : Graph                           |
+-------------------------------------+

Ways to use barbellGraph :
==========================

  * "barbellGraph(ZZ)"

For the programmer
==================

The object barbellGraph, is a method function (Macaulay2Doc).

barycenter -- Returns the barycenter of a grah
**********************************************

Synopsis
========

  * Usage:
        H = barycenter G
  * Inputs:
      * G, a graph,
  * Outputs:
      * H, a graph, The barycenter of G

Description
===========

The barycenter of a graph is the subgraph induced by all the vertices with
eccentricity equal to the graph's radius, in other words, it is the subgraph
induced by the center of a graph.

+--------------------------------+
|i1 : barycenter pathGraph 6     |
|                                |
|o1 = Graph{2 => {3}}            |
|           3 => {2}             |
|                                |
|o1 : Graph                      |
+--------------------------------+
|i2 : barycenter completeGraph 6 |
|                                |
|o2 = Graph{0 => {1, 2, 3, 4, 5}}|
|           1 => {0, 2, 3, 4, 5} |
|           2 => {0, 1, 3, 4, 5} |
|           3 => {0, 1, 2, 4, 5} |
|           4 => {0, 1, 2, 3, 5} |
|           5 => {0, 1, 2, 3, 4} |
|                                |
|o2 : Graph                      |
+--------------------------------+

See also
========

  * center -- Returns the center of a graph

Ways to use barycenter :
========================

  * "barycenter(Graph)"

For the programmer
==================

The object barycenter, is a method function (Macaulay2Doc).

BFS
***

Ways to use breadthFirstSearch :
================================

  * "breadthFirstSearch(Digraph,Thing)" -- see breadthFirstSearch,
    -- runs a breadth first search on the digraph starting
    at a specified node and returns a list of the vertices in the order they
    were discovered

For the programmer
==================

The object BFS (missing documentation) is a method function (Macaulay2Doc).

bipartiteColoring -- Returns a coloring of a bipartite graph
************************************************************

Synopsis
========

  * Usage:
        coloring = bipartiteColoring G
  * Inputs:
      * G, a graph,
  * Outputs:
      * coloring, a list (Macaulay2Doc), a coloring of bipartite
        graph G

Description
===========

A graph is bipartite if it has a chromatic number less than or equal to 2.
This method colors the graph two colors. In other words, it partitions the
graph into two sets such that there is no edge connecting any vertex within
each set.

+-------------------------------------------------------------------+
|i1 : G = graph({{0,1},{1,2},{2,4},{3,4},{4,5}},EntryMode=>"edges");|
+-------------------------------------------------------------------+
|i2 : bipartiteColoring G                                           |
|                                                                   |
|o2 = {{0, 2, 3, 5}, {1, 4}}                                        |
|                                                                   |
|o2 : List                                                          |
+-------------------------------------------------------------------+

See also
========

  * isBipartite -- determines whether a graph is bipartite

Ways to use bipartiteColoring :
===============================

  * "bipartiteColoring(Graph)"

For the programmer
==================

The object bipartiteColoring, is a method function (Macaulay2Doc).

breadthFirstSearch -- runs a breadth first search on the digraph starting at a specified node and returns a list of the vertices in the order they were discovered
******************************************************************************************************************************************************************

Synopsis
========

  * Usage:
        bfs = breadthFirstSearch(D,v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc),
  * Outputs:
      * bfs, a list (Macaulay2Doc), A list of the vertices of D in
        order discovered by the breadth first search

Description
===========

A breadth first search begins the search at the specified vertex of a digraph,
followed by that vertex's children (or in the case of an undirected graph, its
neighbors), followed by     their children (or neighbors), etc, until all the
descendants are exhausted, and returns a list, such that the list's index
number indicates the     depth level of the vertex, of lists of the vertices in
order searched.

+----------------------------------------------------------------------+
|i1 : D = digraph ({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges");|
+----------------------------------------------------------------------+
|i2 : bfs = breadthFirstSearch(D,0)                                    |
|                                                                      |
|o2 = {{0}, {1, 2}, {3}, {4}}                                          |
|                                                                      |
|o2 : List                                                             |
+----------------------------------------------------------------------+
|i3 : G = cycleGraph 6                                                 |
|                                                                      |
|o3 = Graph{0 => {1, 5}}                                               |
|           1 => {0, 2}                                                |
|           2 => {1, 3}                                                |
|           3 => {2, 4}                                                |
|           4 => {3, 5}                                                |
|           5 => {0, 4}                                                |
|                                                                      |
|o3 : Graph                                                            |
+----------------------------------------------------------------------+
|i4 : bfs = breadthFirstSearch(G,3)                                    |
|                                                                      |
|o4 = {{3}, {4, 2}, {5, 1}, {0}}                                       |
|                                                                      |
|o4 : List                                                             |
+----------------------------------------------------------------------+

See also
========

  * reverseBreadthFirstSearch -- runs a
    reverse breadth first search on the digraph and returns a list of the
    vertexSet in the order they were discovered
  * depthFirstSearch -- runs a depth first search on
    the digraph or digraph and returns the discovery time and finishing time
    for each vertex in the digraph
  * topologicalSort -- outputs a list of vertices in a
    topologically sorted order of a DAG.

Ways to use breadthFirstSearch :
================================

  * "breadthFirstSearch(Digraph,Thing)"

For the programmer
==================

The object breadthFirstSearch, is a method function (Macaulay2Doc).

cartesianProduct -- Computes the cartesian product of two graphs
****************************************************************

Synopsis
========

  * Usage:
        F = cartesianProduct(G,H)
  * Inputs:
      * G, a graph,
      * H, a graph,
  * Outputs:
      * F, a graph, The Cartesian Product of G and H

Description
===========

This method will take in any two graphs and output the cartesian product of the
two graphs. The vertex set of this new graph is the cartesian product of the
vertex sets of the two input graphs.  The keys for each vertex will be output
as a sequence. Any two vertices (u,u') and (v,v') are adjacent in the cartesian
product of G and H if and only if either u = v and u' is adjacent with v' in H,
or u' = v' and u is adjacent with v in G.

+----------------------------------------------+
|i1 : G = graph({1,2},{{1,2}});                |
+----------------------------------------------+
|i2 : H = graph({3,4,5},{{3,4},{4,5}});        |
+----------------------------------------------+
|i3 : G' = cartesianProduct(G,H)               |
|                                              |
|o3 = Graph{(1, 3) => {(2, 3), (1, 4)}        }|
|           (1, 4) => {(1, 3), (2, 4), (1, 5)} |
|           (1, 5) => {(2, 5), (1, 4)}         |
|           (2, 3) => {(1, 3), (2, 4)}         |
|           (2, 4) => {(2, 5), (2, 3), (1, 4)} |
|           (2, 5) => {(2, 4), (1, 5)}         |
|                                              |
|o3 : Graph                                    |
+----------------------------------------------+

See also
========

  * strongProduct -- a method for taking the strong
    product of two graphs
  * directProduct (Polyhedra) -- computes the direct
    product of two convex objects
  * graphComposition -- A method for composing two
    graphs

Ways to use cartesianProduct :
==============================

  * "cartesianProduct(Graph,Graph)"

For the programmer
==================

The object cartesianProduct, is a method function (Macaulay2Doc).

center -- Returns the center of a graph
***************************************

Synopsis
========

  * Usage:
        L = center G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a list (Macaulay2Doc), This is a list of the vertices of
        G that form the center of G

Description
===========

The center of a graph G is defined to be the set of all vertices of G such that
the eccentricity of the vertex is equal to the graph's radius. This list often
will contain 1 member, for example, path graphs on with an odd amount of
vertices.  It can also contain all the vertices (such as complete graphs).

+-------------------------------+
|i1 : center graphLibrary "dart"|
|                               |
|o1 = {2}                       |
|                               |
|o1 : List                      |
+-------------------------------+

See also
========

  * barycenter -- Returns the barycenter of a grah
  * eccentricity -- Returns the eccentricity of a vertex
    of a graph
  * radius -- Returns the radius of a graph

Ways to use center :
====================

  * "center(Graph)"

For the programmer
==================

The object center, is a method function (Macaulay2Doc).

children -- returns the children of a vertex of a digraph
*********************************************************

Synopsis
========

  * Usage:
        C = children (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), the vertex that we want to find
        the children of
  * Outputs:
      * C, a set (Macaulay2Doc), a set of the children of v

Description
===========

The children of v are the all the vertices u such that {v,u} is in the edge set
of the digraph D. So the children of a vertex v are exactly those vertices on a
directed graph that v points to.

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : children(D, b)                                     |
|                                                        |
|o2 = set {c, d}                                         |
|                                                        |
|o2 : Set                                                |
+--------------------------------------------------------+

See also
========

  * descendants -- returns the descendants of a digraph

Ways to use children :
======================

  * "children(Digraph,Thing)"

For the programmer
==================

The object children, is a method function (Macaulay2Doc).

chromaticNumber -- Computes the chromatic number of a graph
***********************************************************

Synopsis
========

  * Usage:
        chi = chromaticNumber G
  * Inputs:
      * G, a graph,
  * Outputs:
      * chi, an integer (Macaulay2Doc), The chromatic number of G

Description
===========

The chromatic number of G is chi(G) = min{k | there exists a k-coloring of G}.
A k-coloring of G is a partition into k sets of vertices such that in each of
these sets, none of the members form edges with each other.

+----------------------+
|i1 : G = cycleGraph 5;|
+----------------------+
|i2 : chromaticNumber G|
|                      |
|o2 = 3                |
+----------------------+

See also
========

  * independenceNumber -- computes the independence
    number of a graph

Ways to use chromaticNumber :
=============================

  * "chromaticNumber(Graph)"

For the programmer
==================

The object chromaticNumber, is a method function (Macaulay2Doc).

circularLadder -- Returns a circular ladder graph
*************************************************

Synopsis
========

  * Usage:
        G = circularLadder n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph, The circular ladder graph

Description
===========

The circular ladder graph corresponding to an integer n is a ladder of size n
with two extra edges that connect the each top vertex with its respective
bottom vertex. This creates two cycles, one inside and the other outside, that
are connected by edges.

+--------------------------+
|i1 : G = circularLadder 5 |
|                          |
|o1 = Graph{0 => {1, 4, 5}}|
|           1 => {0, 2, 6} |
|           2 => {1, 3, 7} |
|           3 => {2, 4, 8} |
|           4 => {0, 3, 9} |
|           5 => {0, 6, 9} |
|           6 => {1, 5, 7} |
|           7 => {2, 6, 8} |
|           8 => {3, 7, 9} |
|           9 => {4, 5, 8} |
|                          |
|o1 : Graph                |
+--------------------------+

See also
========

  * ladderGraph -- Returns a ladder graph

Ways to use circularLadder :
============================

  * "circularLadder(ZZ)"

For the programmer
==================

The object circularLadder, is a method function (Macaulay2Doc).

cliqueComplex -- Returns the clique complex of a graph
******************************************************

Synopsis
========

  * Usage:
        clG = cliqueComplex G
  * Inputs:
      * G, a graph,
  * Outputs:
      * clG, an abstract simplicial complex (SimplicialComplexes),
        The clique complex of G

Description
===========

The clique complex of a graph G is the set of all cliques of G.

+--------------------------------------------------------------+
|i1 : G = graph(toList(1..4),{{1, 2}, {1, 3}, {2, 3}, {3, 4}});|
+--------------------------------------------------------------+
|i2 : cliqueComplex G                                          |
|                                                              |
|o2 = simplicialComplex | x_3x_4 x_1x_2x_3 |                   |
|                                                              |
|o2 : SimplicialComplex                                        |
+--------------------------------------------------------------+

See also
========

  * independenceComplex -- constructs the
    independence complex of a graph
  * cliqueNumber -- Returns the clique number of a graph

Ways to use cliqueComplex :
===========================

  * "cliqueComplex(Graph)"

For the programmer
==================

The object cliqueComplex, is a method function (Macaulay2Doc).

cliqueNumber -- Returns the clique number of a graph
****************************************************

Synopsis
========

  * Usage:
        omega = cliqueComplex G
  * Inputs:
      * G, a graph,
  * Outputs:
      * omega, an integer (Macaulay2Doc), the clique number of G

Description
===========

The clique number is the maximum number of vertices comprising a clique in G. A
clique in a graph G is a set of vertices such that all the the vertices are
mutually adjacent (they are all connected to each other).

+--------------------------------------------------------------------+
|i1 : G = graph({{1, 2}, {1, 3}, {2, 3}, {3, 4}},EntryMode=>"edges");|
+--------------------------------------------------------------------+
|i2 : cliqueNumber G                                                 |
|                                                                    |
|o2 = 3                                                              |
+--------------------------------------------------------------------+

See also
========

  * independenceNumber -- computes the independence
    number of a graph
  * cliqueComplex -- Returns the clique complex of a
    graph

Ways to use cliqueNumber :
==========================

  * "cliqueNumber(Graph)"

For the programmer
==================

The object cliqueNumber, is a method function (Macaulay2Doc).

closedNeighborhood -- Returns the closed neighborhood of a vertex of a graph
****************************************************************************

Synopsis
========

  * Usage:
        N = closedNeighborhood(G,v)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc),
  * Outputs:
      * N, a list (Macaulay2Doc), The closed neighborhood of vertex
        v in graph G

Description
===========

The closed neighborhood of a vertex v just the union of the open neighborhood
(or neighbors) of v and the vertex v itself

+----------------------------+
|i1 : G = cycleGraph 4;      |
+----------------------------+
|i2 : closedNeighborhood(G,2)|
|                            |
|o2 = set {1, 2, 3}          |
|                            |
|o2 : Set                    |
+----------------------------+

See also
========

  * neighbors -- returns the neighbors of a vertex in a graph

Ways to use closedNeighborhood :
================================

  * "closedNeighborhood(Graph,Thing)"

For the programmer
==================

The object closedNeighborhood, is a method function (Macaulay2Doc).

clusteringCoefficient -- a method for computing the clustering coefficient of a Graph
*************************************************************************************

Synopsis
========

  * Usage:
        c = clusteringCoefficient(G, v)
        g = clusteringCoefficient(G)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc), v should be a member of the
        vertex set of G
  * Outputs:
      * c, an integer (Macaulay2Doc), The local clustering
        coefficient for G relative to v.
      * g, an integer (Macaulay2Doc), The global clustering
        coefficient for G.

Description
===========

The clustering coefficient is a measure of the degree to which nodes in a graph
tend to cluster together. The global clustering coefficient gives an overall
indication of the interconnectedness of the graph. The local clustering
coefficient gives an indication of how embedded a single vertex is in the
graph.

+------------------------------------------+
|i1 : clusteringCoefficient cycleGraph 4   |
|                                          |
|o1 = 0                                    |
|                                          |
|o1 : QQ                                   |
+------------------------------------------+
|i2 : clusteringCoefficient completeGraph 4|
|                                          |
|o2 = 1                                    |
|                                          |
|o2 : QQ                                   |
+------------------------------------------+

Ways to use clusteringCoefficient :
===================================

  * "clusteringCoefficient(Graph)"
  * "clusteringCoefficient(Graph,Thing)"

For the programmer
==================

The object clusteringCoefficient, is a
method function (Macaulay2Doc).

cocktailParty -- Returns a cocktail party graph
***********************************************

Synopsis
========

  * Usage:
        G = cocktailParty n
  * Inputs:
      * n, an integer (Macaulay2Doc), The number of vertices on each
        side; there will be 2*n total vertices
  * Outputs:
      * G, a graph, The cocktail party graph

Description
===========

The cocktail party graph with respect to an integer n is a graph with 2*n
vertices. Its edge set is formed by taking a disjoint union of n path graphs on
2 vertices and taking its complement, yielding an edge set of every possible
edge except for those that were initially adjacent on the ladder.

+-----------------------------------+
|i1 : cocktailParty 4               |
|                                   |
|o1 = Graph{0 => {1, 2, 3, 5, 6, 7}}|
|           1 => {0, 2, 3, 4, 6, 7} |
|           2 => {0, 1, 3, 4, 5, 7} |
|           3 => {0, 1, 2, 4, 5, 6} |
|           4 => {1, 2, 3, 5, 6, 7} |
|           5 => {0, 2, 3, 4, 6, 7} |
|           6 => {0, 1, 3, 4, 5, 7} |
|           7 => {0, 1, 2, 4, 5, 6} |
|                                   |
|o1 : Graph                         |
+-----------------------------------+

Ways to use cocktailParty :
===========================

  * "cocktailParty(ZZ)"

For the programmer
==================

The object cocktailParty, is a method function (Macaulay2Doc).

complementGraph -- Returns the complement of a graph
****************************************************

Synopsis
========

  * Usage:
        G' = complementGraph G
  * Inputs:
      * G, a graph,
  * Outputs:
      * G', a graph, The complement graph of G

Description
===========

The complement graph of a graph G is the graph G^c where any two vertcies are
adjacent in G^c iff they are not adjacent in G. The original vertex set is
preserved, only the edges are changed.

+-----------------------+
|i1 : G = cycleGraph 4  |
|                       |
|o1 = Graph{0 => {1, 3}}|
|           1 => {0, 2} |
|           2 => {1, 3} |
|           3 => {0, 2} |
|                       |
|o1 : Graph             |
+-----------------------+
|i2 : complementGraph G |
|                       |
|o2 = Graph{0 => {2}}   |
|           1 => {3}    |
|           2 => {0}    |
|           3 => {1}    |
|                       |
|o2 : Graph             |
+-----------------------+

Ways to use complementGraph :
=============================

  * "complementGraph(Graph)"

For the programmer
==================

The object complementGraph, is a method function (Macaulay2Doc).

completeGraph -- Constructs a complete graph
********************************************

Synopsis
========

  * Usage:
        K = completeGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * K, a graph, The complete graph with n vertices

Description
===========

A complete graph on n vertices is a graph in which all the vertices are
adjacent to each other.

+-----------------------------+
|i1 : K = completeGraph 5     |
|                             |
|o1 = Graph{0 => {1, 2, 3, 4}}|
|           1 => {0, 2, 3, 4} |
|           2 => {0, 1, 3, 4} |
|           3 => {0, 1, 2, 4} |
|           4 => {0, 1, 2, 3} |
|                             |
|o1 : Graph                   |
+-----------------------------+

Ways to use completeGraph :
===========================

  * "completeGraph(ZZ)"

For the programmer
==================

The object completeGraph, is a method function (Macaulay2Doc).

completeMultipartiteGraph -- constructs a complete multipartite graph
*********************************************************************

Synopsis
========

  * Usage:
        G = completeMultipartiteGraph P
  * Inputs:
      * P, a list (Macaulay2Doc), if P has k elements, the graph is
        k-partite. P_i determines how many vertices are in each partite group
  * Outputs:
      * G, a graph, a complete multipartite graph

Description
===========

A complete multipartite graph is a graph that is first and foremost
multi-partite. That is, the vertex set of a complete multipartite graph can be
partitioned into k sets such that within each set, none of the vertices are
connected by an edge.  The second condition is that each vertex is connected to
ever vertex except for those in its partition so that it is "almost" a complete
graph. For programming this graph, the input is a list P. The length of the
list P will be the number of groups of vertices. For example, in a complete
bipartite graph, the length of the list would be 2. The entry P_i will
determine how many vertices are in each partition; necisarrily, we see that the
entries of the list must be positive integers.

+------------------------------------------+
|i1 : G = completeMultipartiteGraph {1,2,3}|
|                                          |
|o1 = Graph{0 => {1, 2, 3, 4, 5}}          |
|           1 => {0, 3, 4, 5}              |
|           2 => {0, 3, 4, 5}              |
|           3 => {0, 1, 2}                 |
|           4 => {0, 1, 2}                 |
|           5 => {0, 1, 2}                 |
|                                          |
|o1 : Graph                                |
+------------------------------------------+

Ways to use completeMultipartiteGraph :
=======================================

  * "completeMultipartiteGraph(List)"

For the programmer
==================

The object completeMultipartiteGraph, is a
method function (Macaulay2Doc).

connectedComponents(Graph) -- Computes the connected components of a graph
**************************************************************************

Synopsis
========

  * Function: connectedComponents (SimplicialComplexes),
  * Usage:
        C = connectedComponents G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a list (Macaulay2Doc), The list of connected components
        of G

Description
===========

A connected component is a list of vertices of a graph that are connected, in
other words there exists a path of edges between any two vertices in the
component.

+-------------------------------------------------------+
|i1 : G = graph(toList(1..8),{{1,2},{2,3},{3,4},{5,6}});|
+-------------------------------------------------------+
|i2 : connectedComponents G                             |
|                                                       |
|o2 = {{1, 2, 3, 4}, {5, 6}, {7}, {8}}                  |
|                                                       |
|o2 : List                                              |
+-------------------------------------------------------+

See also
========

  * isConnected -- determines whether a graph is connected
  * numberOfComponents -- computes the number of
    connected components of a graph

Ways to use this method:
========================

  * connectedComponents(Graph), --
    Computes the connected components of a graph

coverIdeal -- Returns the vertex cover ideal of a graph
*******************************************************

Synopsis
========

  * Usage:
        J = coverIdeal G
  * Inputs:
      * G, a graph,
  * Outputs:
      * J, an ideal (Macaulay2Doc), The vertex cover ideal of a
        graph G

Description
===========

The vertex cover ideal of a graph G is the ideal generated by (m_s | s in [n]
is a vertex cover of G), where m_s = product_(i in S)(x_i)

+--------------------------------------------------------------------+
|i1 : G = graph({{1, 2}, {1, 3}, {2, 3}, {3, 4}},EntryMode=>"edges");|
+--------------------------------------------------------------------+
|i2 : coverIdeal G                                                   |
|                                                                    |
|o2 = monomialIdeal (x x , x x , x x x )                             |
|                     1 3   2 3   1 2 4                              |
|                                                                    |
|o2 : MonomialIdeal of QQ[x ..x ]                                    |
|                          1   4                                     |
+--------------------------------------------------------------------+

See also
========

  * edgeIdeal -- returns the edge ideal of a graph
  * vertexCovers -- returns a list of the minimal vertex
    covers of a graph
  * vertexCoverNumber -- returns the vertex cover
    number of a graph

Ways to use coverIdeal :
========================

  * "coverIdeal(Graph)"

For the programmer
==================

The object coverIdeal, is a method function (Macaulay2Doc).

criticalEdges -- Finds the critical edges of a graph
****************************************************

Synopsis
========

  * Usage:
        C = criticalEdges G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a list (Macaulay2Doc), the critical edges of G

Description
===========

A critical edge is an edge such that the removal of the edge from the graph
increases the graph's independence number.

+-----------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1},{3,4},{4,1},{4,2},{4,5}},EntryMode=>"edges |
|-----------------------------------------------------------------------------|
|");                                                                          |
+-----------------------------------------------------------------------------+
|i2 : criticalEdges G                                                         |
|                                                                             |
|o2 = {set {1, 2}, set {1, 3}, set {2, 3}}                                    |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * independenceNumber -- computes the independence
    number of a graph

Ways to use criticalEdges :
===========================

  * "criticalEdges(Graph)"

For the programmer
==================

The object criticalEdges, is a method function (Macaulay2Doc).

crownGraph -- Returns a crown graph
***********************************

Synopsis
========

  * Usage:
        G = crownGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc), The number of vertices on each
        side; there will be 2*n total vertices
  * Outputs:
      * G, a graph,

Description
===========

The crown graph with respect to n is a type of bipartite graph. More
specifically, it is the complement of the ladder graph with respect to n.

+--------------------------+
|i1 : crownGraph 4         |
|                          |
|o1 = Graph{0 => {5, 6, 7}}|
|           1 => {4, 6, 7} |
|           2 => {4, 5, 7} |
|           3 => {4, 5, 6} |
|           4 => {1, 2, 3} |
|           5 => {0, 2, 3} |
|           6 => {0, 1, 3} |
|           7 => {0, 1, 2} |
|                          |
|o1 : Graph                |
+--------------------------+

See also
========

  * ladderGraph -- Returns a ladder graph

Ways to use crownGraph :
========================

  * "crownGraph(ZZ)"

For the programmer
==================

The object crownGraph, is a method function (Macaulay2Doc).

cycleGraph -- Constructs a cycle graph
**************************************

Synopsis
========

  * Usage:
        C = cycleGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * C, a graph, The cycle graph with n vertices

Description
===========

A cycle graph is a graph on n vertices in which all the vertices are in a
closed chain of edges.

+-----------------------+
|i1 : C = cycleGraph 5  |
|                       |
|o1 = Graph{0 => {1, 4}}|
|           1 => {0, 2} |
|           2 => {1, 3} |
|           3 => {2, 4} |
|           4 => {0, 3} |
|                       |
|o1 : Graph             |
+-----------------------+

Ways to use cycleGraph :
========================

  * "cycleGraph(ZZ)"

For the programmer
==================

The object cycleGraph, is a method function (Macaulay2Doc).

degeneracy -- Computes the degeneracy of a graph
************************************************

Synopsis
========

  * Usage:
        d = degeneracy G
  * Inputs:
      * G, a graph,
  * Outputs:
      * d, an integer (Macaulay2Doc),

Description
===========

The degeneracy of a graph is the maximum degree of all vertices in any subgraph
of G.  This is essentially equivalent to the coloring number of G, which is the
least number k such that there exists an ordering of the vertices of G in which
each vertex has less than k neighbors earlier in the ordering.  The coloring
number is equal to the degeneracy plus one.

+--------------------------+
|i1 : G = completeGraph 10;|
+--------------------------+
|i2 : degeneracy G         |
|                          |
|o2 = 9                    |
+--------------------------+

Ways to use degeneracy :
========================

  * "degeneracy(Graph)"

For the programmer
==================

The object degeneracy, is a method function (Macaulay2Doc).

degree(Digraph,Thing) -- returns the degree of a vertex in a digraph
********************************************************************

Synopsis
========

  * Function: degree (Macaulay2Doc),
  * Usage:
        x = degree(D,v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), a vertex in the graph/digraph
  * Outputs:
      * x, an integer (Macaulay2Doc),

Description
===========

In a simple graph, the degree of a vertex is the number of neighbors of the
vertex. In a digraph, we define the degree of a vertex to be the number of
elements in the unique union of the parents and children of the vertex.

+------------------------------------------------------------+
|i1 : D = digraph({1,2,3,4},{{1,2},{2,3},{3,4},{4,2},{2,4}});|
+------------------------------------------------------------+
|i2 : degree(D, 3)                                           |
|                                                            |
|o2 = 2                                                      |
+------------------------------------------------------------+
|i3 : degree(D, 2)                                           |
|                                                            |
|o3 = 3                                                      |
+------------------------------------------------------------+

See also
========

  * neighbors -- returns the neighbors of a vertex in a graph
  * parents -- returns the parents of a vertex on a digraph
  * children -- returns the children of a vertex of a digraph

Ways to use this method:
========================

  * degree(Digraph,Thing) -- returns the
    degree of a vertex in a digraph

degreeCentrality -- Returns the degreeCentrality of a vertex of a graph
***********************************************************************

Synopsis
========

  * Usage:
        x = degreeCentrality (G, v)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc), v must be a vertex of G
  * Outputs:
      * x, a real number (Macaulay2Doc), x is a real number between 0
        and 1

Description
===========

The degreeCentrality of a vertex of a graph is the degree of a vertex divided
by 2 times the number of edges of the graph.  Intuitively, this number will
give a measure of how "central" a vertex is in a graph. In other words, if a
vertex has a relatively high degreeCentrality, it is connected to more
vertexSet than other vertexSet of G, so it is more central or a bottleneck in
the graph. Note that the sum of the degree centralities must be 1.

+-----------------------------------------------------------------------------+
|i1 : L = apply(vertexSet pathGraph 5, i -> degreeCentrality (pathGraph 5, i))|
|                                                                             |
|      1  1  1  1  1                                                          |
|o1 = {-, -, -, -, -}                                                         |
|      8  4  4  4  8                                                          |
|                                                                             |
|o1 : List                                                                    |
+-----------------------------------------------------------------------------+
|i2 : sum L                                                                   |
|                                                                             |
|o2 = 1                                                                       |
|                                                                             |
|o2 : QQ                                                                      |
+-----------------------------------------------------------------------------+

See also
========

  * center -- Returns the center of a graph
  * distance -- Computes the distance between two vertexSet in
    a graph
  * degree (Macaulay2Doc)

Ways to use degreeCentrality :
==============================

  * "degreeCentrality(Graph,Thing)"

For the programmer
==================

The object degreeCentrality, is a method function (Macaulay2Doc).

degreeIn -- returns the "in-degree" of a vertex in a digraph
************************************************************

Synopsis
========

  * Usage:
        x = degreeIn (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), a vertex of D
  * Outputs:
      * x, an integer (Macaulay2Doc),

Description
===========

In a directed graph, we define the degree into a vertex or the "in-degree" of a
vertex to be the number of parents of that vertex. Intuitively, this give the
number of edges that point into the vertex.

+------------------------------------------------------+
|i1 : D = digraph({1,2,3,4},{{1,2},{2,3},{3,4},{4,2}});|
+------------------------------------------------------+
|i2 : degreeIn(D, 2)                                   |
|                                                      |
|o2 = 2                                                |
+------------------------------------------------------+

See also
========

  * degree (Macaulay2Doc)
  * degreeOut -- returns the "out-degree" of a vertex in a
    digraph
  * parents -- returns the parents of a vertex on a digraph

Ways to use degreeIn :
======================

  * "degreeIn(Digraph,Thing)"

For the programmer
==================

The object degreeIn, is a method function (Macaulay2Doc).

degreeMatrix -- Returns the degree matrix of a graph
****************************************************

Synopsis
========

  * Usage:
        D = degreeMatrix G
  * Inputs:
      * G, a graph,
  * Outputs:
      * D, a matrix (Macaulay2Doc), The degree matrix of graph G

Description
===========

The degree matrix is the n by n diagonal matrix (where n is the number of
vertices in the vertex set of the graph G) indexed by the vertices of G where
A_(u,u) is the degree of vertex u. The degree of a vertex u is the number of
edges such that {u,v} is an edge for any v also in the vertex set. This matrix
is always diagonal.

+------------------------------------------------------------+
|i1 : G = graph({1,2,3,4,5},{{1,2},{2,3},{3,4},{3,5},{4,5}});|
+------------------------------------------------------------+
|i2 : degreeMatrix G                                         |
|                                                            |
|o2 = | 1 0 0 0 0 |                                          |
|     | 0 2 0 0 0 |                                          |
|     | 0 0 3 0 0 |                                          |
|     | 0 0 0 2 0 |                                          |
|     | 0 0 0 0 2 |                                          |
|                                                            |
|              5        5                                    |
|o2 : Matrix ZZ  <--- ZZ                                     |
+------------------------------------------------------------+

See also
========

  * adjacencyMatrix -- Returns the adjacency matrix of
    a Graph or Digraph
  * laplacianMatrix -- Returns the laplacian matrix of
    a graph
  * degree (Macaulay2Doc)

Ways to use degreeMatrix :
==========================

  * "degreeMatrix(Digraph)"

For the programmer
==================

The object degreeMatrix, is a method function (Macaulay2Doc).

degreeOut -- returns the "out-degree" of a vertex in a digraph
**************************************************************

Synopsis
========

  * Usage:
        x = degreeIn (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), a vertex of D
  * Outputs:
      * x, an integer (Macaulay2Doc),

Description
===========

In a directed graph, we define the degree out of a vertex or the "out-degree"
of a vertex to be the number of children of that vertex. Intuitively, this give
the number of edges pointing out of a vertex to another vertex.

+------------------------------------------------------+
|i1 : D = digraph({1,2,3,4},{{1,2},{2,3},{3,4},{4,2}});|
+------------------------------------------------------+
|i2 : degreeOut(D, 2)                                  |
|                                                      |
|o2 = 1                                                |
+------------------------------------------------------+

See also
========

  * degree (Macaulay2Doc)
  * degreeIn -- returns the "in-degree" of a vertex in a
    digraph
  * children -- returns the children of a vertex of a digraph

Ways to use degreeOut :
=======================

  * "degreeOut(Digraph,Thing)"

For the programmer
==================

The object degreeOut, is a method function (Macaulay2Doc).

degreeSequence -- the degree sequence of a graph
************************************************

Synopsis
========

  * Usage:
        degreeSequence G
  * Inputs:
      * G, a graph,
  * Outputs:
      * a list (Macaulay2Doc), the degree sequence of G;

Description
===========

The degree sequence of a graph is the list of the degrees of its vertices
sorted in nonincreasing order.

+-------------------------------+
|i1 : degreeSequence pathGraph 5|
|                               |
|o1 = {2, 2, 2, 1, 1}           |
|                               |
|o1 : List                      |
+-------------------------------+

Ways to use degreeSequence :
============================

  * "degreeSequence(Graph)"

For the programmer
==================

The object degreeSequence, is a method function (Macaulay2Doc).

deleteEdges -- Deletes a list of edges from a graph
***************************************************

Synopsis
========

  * Usage:
        G' = deleteEdges(G,E)
  * Inputs:
      * G, a graph,
      * E, a list (Macaulay2Doc),
  * Outputs:
      * G', a graph, the graph resulting from deleting edges in
        list E from graph G

Description
===========

This method deletes the specified edges from the graph, but preserves the
original vertex set of the graph, and outputs the adjusted graph.

+---------------------------------------+
|i1 : G = cycleGraph 10;                |
+---------------------------------------+
|i2 : deleteEdges(G,{{1,2},{3,4},{7,8}})|
|                                       |
|o2 = Graph{0 => {1, 9}}                |
|           1 => {0}                    |
|           2 => {3}                    |
|           3 => {2}                    |
|           4 => {5}                    |
|           5 => {4, 6}                 |
|           6 => {5, 7}                 |
|           7 => {6}                    |
|           8 => {9}                    |
|           9 => {0, 8}                 |
|                                       |
|o2 : Graph                             |
+---------------------------------------+

See also
========

  * deleteVertices -- Deletes specified vertices from a
    digraph or graph
  * deleteVertex -- a method for deleting the vertex of a
    graph

Ways to use deleteEdges :
=========================

  * "deleteEdges(Graph,List)"
  * deleteEdges(Digraph,List) (missing documentation)

For the programmer
==================

The object deleteEdges, is a method function (Macaulay2Doc).

deleteVertex -- a method for deleting the vertex of a graph
***********************************************************

Synopsis
========

  * Usage:
        H = deleteVertex(G, v)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc), v should be a member of the
        vertex set of G
  * Outputs:
      * H, a graph, The graph with the vertex v and any edges
        touching it

Description
===========

This is a method that takes in any graph and outputs this graph minus one
specified vertex. This will also remove any edge that contained this vertex as
one of its entries.

+----------------------------+
|i1 : G = cycleGraph 4;      |
+----------------------------+
|i2 : G' = deleteVertex(G,1);|
+----------------------------+

See also
========

  * inducedSubgraph -- A method for finding the induced
    subgraph of any Graph or Digraph
  * deleteVertices -- Deletes specified vertices from a
    digraph or graph
  * deleteEdges -- Deletes a list of edges from a graph

Ways to use deleteVertex :
==========================

  * "deleteVertex(Graph,Thing)"
  * deleteVertex(Digraph,Thing) (missing documentation)

For the programmer
==================

The object deleteVertex, is a method function (Macaulay2Doc).

deleteVertices -- Deletes specified vertices from a digraph or graph
********************************************************************

Synopsis
========

  * Usage:
        G' = deleteVertices(G,L)
  * Inputs:
      * G, a digraph,
      * L, a list (Macaulay2Doc),
  * Outputs:
      * G', a digraph, Graph with vertices in list L and their
        incident edges deleted.

Description
===========

Removes specified list of vertices and their incident edges from a graph or
digraph.

+------------------------------------------------+
|i1 : G = graph({1,2,3,4,5},{{1,3},{3,4},{4,5}});|
+------------------------------------------------+
|i2 : L = {1,2};                                 |
+------------------------------------------------+
|i3 : deleteVertices(G,L)                        |
|                                                |
|o3 = Graph{3 => {4}   }                         |
|           4 => {3, 5}                          |
|           5 => {4}                             |
|                                                |
|o3 : Graph                                      |
+------------------------------------------------+

See also
========

  * deleteVertex -- a method for deleting the vertex of a
    graph
  * inducedSubgraph -- A method for finding the induced
    subgraph of any Graph or Digraph
  * deleteEdges -- Deletes a list of edges from a graph

Ways to use deleteVertices :
============================

  * "deleteVertices(Digraph,List)"

For the programmer
==================

The object deleteVertices, is a method function (Macaulay2Doc).

density -- computes the density of a graph
******************************************

Synopsis
========

  * Usage:
        d = density G
  * Inputs:
      * G, a graph,
  * Outputs:
      * d, a rational number (Macaulay2Doc), the density of G

Description
===========

A dense graph has a high edge to vertex ratio, whereas a sparse graph has a low
edge to vertex ratio.  Density is equal to 2*|E| divided by |V|*(|V|-1).  A
complete graph has density 1; the minimal density of any graph is 0.

+-------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{4,2},{1,4}},EntryMode=>"edges");|
+-------------------------------------------------------------------+
|i2 : density G                                                     |
|                                                                   |
|     5                                                             |
|o2 = -                                                             |
|     6                                                             |
|                                                                   |
|o2 : QQ                                                            |
+-------------------------------------------------------------------+

See also
========

  * degreeCentrality -- Returns the degreeCentrality
    of a vertex of a graph

Ways to use density :
=====================

  * "density(Graph)"

For the programmer
==================

The object density, is a method function (Macaulay2Doc).

depthFirstSearch -- runs a depth first search on the digraph or digraph and returns the discovery time and finishing time for each vertex in the digraph
********************************************************************************************************************************************************

Synopsis
========

  * Usage:
        dfs = depthFirstSearch D
        dfs = depthFirstSearch G
  * Inputs:
      * D, a digraph,
      * G, a graph,
  * Outputs:
      * dfs, a hash table (Macaulay2Doc), A hash table with
        keys discoveryTime and finishingTime, whose values are hash tables
        containing for each vertex the discovery time and finishing time,
        respectively.

Description
===========

A depth first search begins at the first vertex of a graph as a root and
searches as far as possible along one branch from that root before backtracking
to the next branch to the right. Discovery time denotes the order in which the
vertex was searched first; finishing time denotes the time in which the
vertex's descendents were all finished.

+-----------------------------------------------------------------------------+
|i1 : D = digraph ({{0,1},{1,3},{1,4},{4,7},{4,8},{0,2},{2,5},{2,6}},EntryMode|
|                                                                             |
|o1 = Digraph{0 => {1, 2}}                                                    |
|             1 => {3, 4}                                                     |
|             2 => {5, 6}                                                     |
|             3 => {}                                                         |
|             4 => {7, 8}                                                     |
|             5 => {}                                                         |
|             6 => {}                                                         |
|             7 => {}                                                         |
|             8 => {}                                                         |
|                                                                             |
|o1 : Digraph                                                                 |
|-----------------------------------------------------------------------------|
|=>"edges")                                                                   |
+-----------------------------------------------------------------------------+
|i2 : dfs = depthFirstSearch D                                                |
|                                                                             |
|o2 = HashTable{discoveryTime => HashTable{0 => 1 }}                          |
|                                          1 => 2                             |
|                                          2 => 12                            |
|                                          3 => 9                             |
|                                          4 => 3                             |
|                                          5 => 13                            |
|                                          6 => 15                            |
|                                          7 => 6                             |
|                                          8 => 4                             |
|               finishingTime => HashTable{0 => 18}                           |
|                                          1 => 11                            |
|                                          2 => 17                            |
|                                          3 => 10                            |
|                                          4 => 8                             |
|                                          5 => 14                            |
|                                          6 => 16                            |
|                                          7 => 7                             |
|                                          8 => 5                             |
|                                                                             |
|o2 : HashTable                                                               |
+-----------------------------------------------------------------------------+
|i3 : G = cycleGraph 6                                                        |
|                                                                             |
|o3 = Graph{0 => {1, 5}}                                                      |
|           1 => {0, 2}                                                       |
|           2 => {1, 3}                                                       |
|           3 => {2, 4}                                                       |
|           4 => {3, 5}                                                       |
|           5 => {0, 4}                                                       |
|                                                                             |
|o3 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i4 : dfs = depthFirstSearch G                                                |
|                                                                             |
|o4 = HashTable{discoveryTime => HashTable{0 => 1 }}                          |
|                                          1 => 10                            |
|                                          2 => 5                             |
|                                          3 => 4                             |
|                                          4 => 3                             |
|                                          5 => 2                             |
|               finishingTime => HashTable{0 => 12}                           |
|                                          1 => 11                            |
|                                          2 => 6                             |
|                                          3 => 7                             |
|                                          4 => 8                             |
|                                          5 => 9                             |
|                                                                             |
|o4 : HashTable                                                               |
+-----------------------------------------------------------------------------+

See also
========

  * breadthFirstSearch -- runs a breadth first
    search on the digraph starting at a specified node and returns a list of
    the vertices in the order they were discovered
  * topologicalSort -- outputs a list of vertices in a
    topologically sorted order of a DAG.

Ways to use depthFirstSearch :
==============================

  * "depthFirstSearch(Digraph)"

For the programmer
==================

The object depthFirstSearch, is a method function (Macaulay2Doc).

descendants -- returns the descendants of a digraph
***************************************************

Synopsis
========

  * Usage:
        L = descendants (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), a vertex of the digraph
  * Outputs:
      * L, a set (Macaulay2Doc), a set of all the descendants of v

Description
===========

The descendants of a directed graph are all the vertexSet u of D such that u is
reachable from v. Another way to more intuitively see what the descendants are
is to see the descandants of a vertex v can be found by first taking the
children of v. Then if you take the children of each of the children, and
continue the process until the list stops growing, this will form all the
descandants of v.

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : descendants (D, a)                                 |
|                                                        |
|o2 = set {a, b, c, d}                                   |
|                                                        |
|o2 : Set                                                |
+--------------------------------------------------------+

See also
========

  * children -- returns the children of a vertex of a digraph
  * isReachable -- checks if a vertex u is reachable from a
    vertex v
  * nondescendants -- returns the nondescendants of a
    vertex of a digraph

Ways to use descendants :
=========================

  * "descendants(Digraph,Thing)"

For the programmer
==================

The object descendants, is a method function (Macaulay2Doc).

descendents
***********

Ways to use descendants :
=========================

  * "descendants(Digraph,Thing)" -- see descendants, --
    returns the descendants of a digraph

For the programmer
==================

The object descendents (missing documentation) is a method function (Macaulay2Doc).

DFS
***

Ways to use depthFirstSearch :
==============================

  * "depthFirstSearch(Digraph)" -- see depthFirstSearch,
    -- runs a depth first search on the digraph or digraph
    and returns the discovery time and finishing time for each vertex in the
    digraph

For the programmer
==================

The object DFS (missing documentation) is a method function (Macaulay2Doc).

diameter(Graph) -- Computes the diameter of a graph
***************************************************

Synopsis
========

  * Function: diameter (Macaulay2Doc),
  * Usage:
        d = diameter G
  * Inputs:
      * G, a graph,
  * Outputs:
      * d, an integer (Macaulay2Doc), The diameter of G

Description
===========

The diameter of a graph is the maximum of the distances between all the
vertexSet of G.  If the graph is not connected, the diameter is infinity.

+-------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4}},EntryMode=>"edges");|
+-------------------------------------------------------+
|i2 : d = diameter G                                    |
|                                                       |
|o2 = 3                                                 |
+-------------------------------------------------------+
|i3 : G = graph({1,2,3,4},{{2,3},{3,4}});               |
+-------------------------------------------------------+
|i4 : d = diameter G                                    |
|                                                       |
|o4 = infinity                                          |
|                                                       |
|o4 : InfiniteNumber                                    |
+-------------------------------------------------------+

See also
========

  * distance -- Computes the distance between two vertexSet in
    a graph
  * distanceMatrix -- Computes the distance matrix of a
    digraph

Ways to use this method:
========================

  * diameter(Graph) -- Computes the diameter of a
    graph

Digraph
*******

Types of digraph :
==================

  * Graph

Functions and methods returning a digraph :
===========================================

  * "addEdges'(Digraph,List)" -- see addEdge, -- A method for
    adding edges to a graph
  * "addVertex(Digraph,Thing)" -- see addVertex, -- A method
    for adding a set of vertices to a graph
  * deleteVertex(Digraph,Thing) (missing documentation)
  * "deleteVertices(Digraph,List)" -- see deleteVertices,
    -- Deletes specified vertices from a digraph or graph
  * "digraph(HashTable)" -- see digraph, -- Constructs a digraph
  * "digraph(List)" -- see digraph, -- Constructs a digraph
  * "digraph(List,List)" -- see digraph, -- Constructs a digraph
  * "digraph(List,Matrix)" -- see digraph, -- Constructs a
    digraph
  * "digraph(Matrix)" -- see digraph, -- Constructs a digraph
  * "digraphTranspose(Digraph)" -- see digraphTranspose,
    -- returns the transpose of a Digraph
  * "indexLabelGraph(Digraph)" -- see indexLabelGraph,
    -- Relabels the vertices of a graph or digraph according to their indices,
    indexed from 0.
  * "inducedSubgraph(Digraph,List)" -- see inducedSubgraph,
    -- A method for finding the induced subgraph of any Graph
    or Digraph
  * "reindexBy(Digraph,String)" -- see reindexBy, -- reindexes
    the vertices according to the input ordering.

Methods that use a digraph :
============================

  * "addEdge(Digraph,Set)" -- see addEdge, -- A method for
    adding edges to a graph
  * "addVertices(Digraph,List)" -- see addVertex, -- A method
    for adding a set of vertices to a graph
  * "adjacencyMatrix(Digraph)" -- see adjacencyMatrix,
    -- Returns the adjacency matrix of a Graph or Digraph
  * "breadthFirstSearch(Digraph,Thing)" -- see breadthFirstSearch,
    -- runs a breadth first search on the digraph starting
    at a specified node and returns a list of the vertices in the order they
    were discovered
  * "children(Digraph,Thing)" -- see children, -- returns the
    children of a vertex of a digraph
  * degree(Digraph,Thing) -- returns the
    degree of a vertex in a digraph
  * "degreeIn(Digraph,Thing)" -- see degreeIn, -- returns the
    "in-degree" of a vertex in a digraph
  * "degreeMatrix(Digraph)" -- see degreeMatrix, -- Returns
    the degree matrix of a graph
  * "degreeOut(Digraph,Thing)" -- see degreeOut, -- returns
    the "out-degree" of a vertex in a digraph
  * deleteEdges(Digraph,List) (missing documentation)
  * "depthFirstSearch(Digraph)" -- see depthFirstSearch,
    -- runs a depth first search on the digraph or digraph
    and returns the discovery time and finishing time for each vertex in the
    digraph
  * "descendants(Digraph,Thing)" -- see descendants, --
    returns the descendants of a digraph
  * Digraph _ List (missing documentation)
  * Digraph _ ZZ (missing documentation)
  * Digraph _* (missing documentation)
  * "displayGraph(Digraph)" -- see displayGraph, --
    displays a digraph or graph using Graphviz
  * "displayGraph(String,Digraph)" -- see displayGraph, --
    displays a digraph or graph using Graphviz
  * "displayGraph(String,String,Digraph)" -- see displayGraph,
    -- displays a digraph or graph using Graphviz
  * "distance(Digraph,Thing,Thing)" -- see distance, --
    Computes the distance between two vertexSet in a graph
  * distance(Digraph,Thing) (missing documentation)
  * "distanceMatrix(Digraph)" -- see distanceMatrix, --
    Computes the distance matrix of a digraph
  * "edges(Digraph)" -- see edges, -- Returns the edges of a
    digraph or graph
  * "findPaths(Digraph,Thing,ZZ)" -- see findPaths, -- finds
    all the paths in a digraph of a given length starting at a given vertex
  * "floydWarshall(Digraph)" -- see floydWarshall, -- runs
    the Floyd-Warshall algorithm on a digraph to determine the minimum distance
    from one vertex to another in the digraph
  * "forefathers(Digraph,Thing)" -- see forefathers, --
    returns the forefathers of a digraph
  * graph(Digraph) -- Returns the legacy G#graph
    hash table
  * "hasEulerianTrail(Digraph)" -- see hasEulerianTrail,
    -- determines whether a graph or a digraph has an
    Eulerian trail
  * html(Digraph) -- Create an .svg representation of
    a graph or digraph
  * isCyclic(Digraph) -- determines whether a
    digraph is cyclic
  * "isEulerian(Digraph)" -- see isEulerian, -- determines if
    a graph or digraph is Eulerian
  * "isReachable(Digraph,Thing,Thing)" -- see isReachable,
    -- checks if a vertex u is reachable from a vertex v
  * "isSink(Digraph,Thing)" -- see isSink, -- determines if a
    vertex of a digraph is a sink or not
  * "isSource(Digraph,Thing)" -- see isSource, -- determines if
    a vertex of a digraph is a source or not
  * "isStronglyConnected(Digraph)" -- see isStronglyConnected,
    -- checks if a digraph is strongly connected
  * "isWeaklyConnected(Digraph)" -- see isWeaklyConnected,
    -- checks if a digraph is weakly connected
  * "lowestCommonAncestors(Digraph,Thing,Thing)" -- see
    lowestCommonAncestors, -- determines the lowest
    common ancestors between two vertexSet
  * net(Digraph) (missing documentation)
  * "nondescendants(Digraph,Thing)" -- see nondescendants,
    -- returns the nondescendants of a vertex of a digraph
  * "parents(Digraph,Thing)" -- see parents, -- returns the
    parents of a vertex on a digraph
  * "reachable(Digraph,List)" -- see reachable, -- Returns the
    vertices reachable in a digraph from a given collection of vertices
  * "reachable(Digraph,Set)" -- see reachable, -- Returns the
    vertices reachable in a digraph from a given collection of vertices
  * "reverseBreadthFirstSearch(Digraph,Thing)" -- see
    reverseBreadthFirstSearch, -- runs a reverse
    breadth first search on the digraph and returns a list of the vertexSet in
    the order they were discovered
  * "showTikZ(Digraph)" -- see showTikZ, -- Writes a string of
    TikZ syntax that can be pasted into a .tex file to display G
  * "sinks(Digraph)" -- see sinks, -- returns the sinks of a
    digraph
  * "sources(Digraph)" -- see sources, -- returns the sources of
    a digraph
  * "topologicalSort(Digraph)" -- see topologicalSort,
    -- outputs a list of vertices in a topologically sorted order of a DAG.
  * "topologicalSort(Digraph,String)" -- see topologicalSort,
    -- outputs a list of vertices in a topologically sorted
    order of a DAG.
  * "topSort(Digraph)" -- see topSort, -- outputs a hashtable
    containing original digraph, new digraph with vertices topologically sorted
    and a map from vertices of original digraph to new digraph.
  * "topSort(Digraph,String)" -- see topSort, -- outputs a
    hashtable containing original digraph, new digraph with vertices
    topologically sorted and a map from vertices of original digraph to new
    digraph.
  * toString(Digraph) (missing documentation)
  * "underlyingGraph(Digraph)" -- see underlyingGraph,
    -- Returns the underlying graph of a digraph
  * "vertexSet(Digraph)" -- see vertexSet, -- Returns the
    vertices of a graph or digraph
  * "vertices(Digraph)" -- see vertexSet, -- Returns the
    vertices of a graph or digraph
  * "writeDotFile(String,Digraph)" -- see writeDotFile, --
    Writes a graph to a dot file with a specified filename

For the programmer
==================

The object Digraph, is a type (Macaulay2Doc), with
ancestor classes HashTable (Macaulay2Doc), < Thing (Macaulay2Doc).

digraph -- Constructs a digraph
*******************************

Synopsis
========

  * Usage:
        G = digraph E
        G = digraph H
        G = digraph (V, E)
        G = digraph (V, A)
        G = digraph A
  * Inputs:
      * E, a list (Macaulay2Doc), Denotes an edge list (a list of
        ordered pair lists)
      * V, a list (Macaulay2Doc), Denotes a vertex list
      * H, a hash table (Macaulay2Doc),
      * A, a matrix (Macaulay2Doc), Denotes an adjacency matrix
  * Optional inputs (Macaulay2Doc),:
      * EntryMode (missing documentation) => ..., default value "auto", null
      * Singletons (missing documentation) => ..., default value null, null
  * Outputs:
      * G, a digraph,

Description
===========

A digraph is a set of vertices connected by directed edges. Unlike the case
with simple graphs, {u,v} being an edge does not imply that {v,u} is also an
edge. Notably, this allows for non-symmetric adjacency matrices.

+-----------------------------------------------------------------------------+
|i1 : G = digraph ({{1,2},{2,1},{3,1}}, EntryMode => "edges")                 |
|                                                                             |
|o1 = Digraph{1 => {2}}                                                       |
|             2 => {1}                                                        |
|             3 => {1}                                                        |
|                                                                             |
|o1 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i2 : G = digraph hashTable{1 => {2}, 3 => {4}, 5 => {6}}                     |
|                                                                             |
|o2 = Digraph{1 => {2}}                                                       |
|             2 => {}                                                         |
|             3 => {4}                                                        |
|             4 => {}                                                         |
|             5 => {6}                                                        |
|             6 => {}                                                         |
|                                                                             |
|o2 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i3 : G = digraph ({{a,{b,c,d,e}}, {b,{d,e}}, {e,{a}}}, EntryMode =>          |
|                                                                             |
|o3 = Digraph{a => {e, b, c, d}}                                              |
|             b => {e, d}                                                     |
|             c => {}                                                         |
|             d => {}                                                         |
|             e => {a}                                                        |
|                                                                             |
|o3 : Digraph                                                                 |
|-----------------------------------------------------------------------------|
|"neighbors")                                                                 |
+-----------------------------------------------------------------------------+
|i4 : G = digraph ({x,y,z}, matrix {{0,1,1},{0,0,1},{0,1,0}})                 |
|                                                                             |
|o4 = Digraph{x => {y, z}}                                                    |
|             y => {z}                                                        |
|             z => {y}                                                        |
|                                                                             |
|o4 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i5 : G = digraph matrix {{0,1,1},{0,0,1},{0,1,0}}                            |
|                                                                             |
|o5 = Digraph{0 => {1, 2}}                                                    |
|             1 => {2}                                                        |
|             2 => {1}                                                        |
|                                                                             |
|o5 : Digraph                                                                 |
+-----------------------------------------------------------------------------+

See also
========

  * graph -- Constructs a simple graph

Ways to use digraph :
=====================

  * "digraph(HashTable)"
  * "digraph(List)"
  * "digraph(List,List)"
  * "digraph(List,Matrix)"
  * "digraph(Matrix)"

For the programmer
==================

The object digraph, is a method function with options (Macaulay2Doc).

digraphTranspose -- returns the transpose of a Digraph
******************************************************

Synopsis
========

  * Usage:
        G = digraphTranspose D
  * Inputs:
      * D, a digraph,
  * Outputs:
      * G, a digraph, the transpose digraph of D

Description
===========

The transpose of a digraph D is the graph formed by taking every edge (u,v) in
D and changing it to (v,u). Intuitively, it reverses the direction of all the
edges while keeping the same vertex set.  One can also view the transpose in
terms of adjacency matrices, where the adjacency matrix of the transpose of D
is the transpose of the adjacency matrix of D. In this way, we quickly see that
the transpose of a transpose digraph is the original digraph, and that this
operator is trivial for simple graphs since they have symmetric matrices.

+---------------------------------------------------------------------------+
|i1 : D = digraph ({{1,2},{2,3},{3,4},{4,1},{1,3},{4,2}},EntryMode=>"edges")|
|                                                                           |
|o1 = Digraph{1 => {2, 3}}                                                  |
|             2 => {3}                                                      |
|             3 => {4}                                                      |
|             4 => {1, 2}                                                   |
|                                                                           |
|o1 : Digraph                                                               |
+---------------------------------------------------------------------------+
|i2 : D' = digraphTranspose D                                               |
|                                                                           |
|o2 = Digraph{1 => {4}   }                                                  |
|             2 => {1, 4}                                                   |
|             3 => {1, 2}                                                   |
|             4 => {3}                                                      |
|                                                                           |
|o2 : Digraph                                                               |
+---------------------------------------------------------------------------+
|i3 : D'' = digraphTranspose D'                                             |
|                                                                           |
|o3 = Digraph{1 => {2, 3}}                                                  |
|             2 => {3}                                                      |
|             3 => {4}                                                      |
|             4 => {1, 2}                                                   |
|                                                                           |
|o3 : Digraph                                                               |
+---------------------------------------------------------------------------+

Ways to use digraphTranspose :
==============================

  * "digraphTranspose(Digraph)"

For the programmer
==================

The object digraphTranspose, is a method function (Macaulay2Doc).

directProduct -- Computes the direct product of two graphs
**********************************************************

Synopsis
========

  * Usage:
        F = directProduct(G,H)
  * Inputs:
      * G, a graph,
      * H, a graph,
  * Outputs:
      * F, a graph, The Direct Product of G and H

Description
===========

This method will take in any two graphs and output the direct product of these
two graphs. The vertex set of the direct product of G and H is the cartesian
product of G and H's vertex sets. The keys for each vertex will be output as a
sequence to represent this.  Any two vertices (u,u') and (v,v') form an edge in
the direct product of G and G if and only if u' is adjacent with v' and u is
adjacent with v in the original graphs.

+--------------------------------------+
|i1 : G = graph({1,2},{{1,2}});        |
+--------------------------------------+
|i2 : H = graph({3,4,5},{{3,4},{4,5}});|
+--------------------------------------+
|i3 : G'= directProduct(G,H)           |
|                                      |
|o3 = Graph{(1, 3) => {(2, 4)}        }|
|           (1, 4) => {(2, 5), (2, 3)} |
|           (1, 5) => {(2, 4)}         |
|           (2, 3) => {(1, 4)}         |
|           (2, 4) => {(1, 3), (1, 5)} |
|           (2, 5) => {(1, 4)}         |
|                                      |
|o3 : Graph                            |
+--------------------------------------+

See also
========

  * graphComposition -- A method for composing two
    graphs
  * strongProduct -- a method for taking the strong
    product of two graphs
  * cartesianProduct -- Computes the cartesian product
    of two graphs

Ways to use directProduct :
===========================

  * "directProduct(Graph,Graph)"
  * directProduct(Cone,Cone) (Polyhedra),
    -- computes the direct product of polyhedra and cones
  * "directProduct(Cone,Polyhedron)" -- see directProduct(Cone,Cone) (Polyhedra),
    -- computes the direct product
    of polyhedra and cones
  * "directProduct(Polyhedron,Cone)" -- see directProduct(Cone,Cone) (Polyhedra),
    -- computes the direct product
    of polyhedra and cones
  * "directProduct(Polyhedron,Polyhedron)" -- see
    directProduct(Cone,Cone) (Polyhedra), --
    computes the direct product of polyhedra and cones
  * directProduct(Fan,Fan) (Polyhedra), --
    computes the direct product of two fans

For the programmer
==================

The object directProduct (Polyhedra), is a method function (Macaulay2Doc).

discoveryTime
*************

For the programmer
==================

The object discoveryTime (missing documentation) is a symbol (Macaulay2Doc).

disjointUnion -- Returns the disjoint union of a list of graphs.
****************************************************************

Synopsis
========

  * Usage:
        G = disjointUnion L
  * Inputs:
      * L, a list (Macaulay2Doc),
  * Outputs:
      * G, a graph, The disjoint union of the graphs in list L

Description
===========

The disjoint union of a list of graphs is the graph constructed from the unions
of their respective vertex sets and edge sets. By default, the vertex set of
the union will be listed as sequences.

+-------------------------------------------------+
|i1 : A = graph({{1,2},{2,3}},EntryMode=>"edges");|
+-------------------------------------------------+
|i2 : B = graph({1,2,3,4,5},{{1,2},{4,5}});       |
+-------------------------------------------------+
|i3 : disjointUnion {A,B}                         |
|                                                 |
|o3 = Graph{{1, 0} => {{2, 0}}        }           |
|           {1, 1} => {{2, 1}}                    |
|           {2, 0} => {{1, 0}, {3, 0}}            |
|           {2, 1} => {{1, 1}}                    |
|           {3, 0} => {{2, 0}}                    |
|           {3, 1} => {}                          |
|           {4, 1} => {{5, 1}}                    |
|           {5, 1} => {{4, 1}}                    |
|                                                 |
|o3 : Graph                                       |
+-------------------------------------------------+

Ways to use disjointUnion :
===========================

  * "disjointUnion(List)"

For the programmer
==================

The object disjointUnion, is a method function (Macaulay2Doc).

displayGraph -- displays a digraph or graph using Graphviz
**********************************************************

Synopsis
========

  * Usage:
        displayGraph(dotFileName,jpgFileName,G)
        displayGraph(dotFileName,G)
        displayGraph G
  * Inputs:
      * G, a digraph,
      * dotFileName, a string (Macaulay2Doc),
      * jpgFileName, a string (Macaulay2Doc),

Description
===========

Displays a digraph or graph using Graphviz

See also
========

  * showTikZ -- Writes a string of TikZ syntax that can be
    pasted into a .tex file to display G
  * writeDotFile -- Writes a graph to a dot file with a
    specified filename

Ways to use displayGraph :
==========================

  * "displayGraph(Digraph)"
  * "displayGraph(String,Digraph)"
  * "displayGraph(String,String,Digraph)"

For the programmer
==================

The object displayGraph, is a method function (Macaulay2Doc).

distance -- Computes the distance between two vertexSet in a graph
******************************************************************

Synopsis
========

  * Usage:
        d = distance(G,v,u)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc),
      * u, a thing (Macaulay2Doc),
  * Outputs:
      * d, an integer (Macaulay2Doc), The distance between vertexSet
        v and u

Description
===========

The distance between two vertexSet is calculated as the number of edges in the
shortest path between the two vertexSet.  If the two vertexSet are not
connected, the distance between them is infinity by convention.

+-------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4}},EntryMode=>"edges");|
+-------------------------------------------------------+
|i2 : d = distance (G,1,4)                              |
|                                                       |
|o2 = 3                                                 |
+-------------------------------------------------------+
|i3 : G = graph({1,2,3,4},{{2,3},{3,4}});               |
+-------------------------------------------------------+
|i4 : d = distance(G, 1, 4)                             |
|                                                       |
|o4 = infinity                                          |
|                                                       |
|o4 : InfiniteNumber                                    |
+-------------------------------------------------------+

See also
========

  * diameter(Graph) -- Computes the diameter of a
    graph
  * distanceMatrix -- Computes the distance matrix of a
    digraph

Ways to use distance :
======================

  * "distance(Digraph,Thing,Thing)"
  * distance(Digraph,Thing) (missing documentation)

For the programmer
==================

The object distance, is a method function (Macaulay2Doc).

distanceMatrix -- Computes the distance matrix of a digraph
***********************************************************

Synopsis
========

  * Usage:
        M = distanceMatrix(G)
  * Inputs:
      * G, a digraph,
  * Outputs:
      * M, a matrix (Macaulay2Doc), the distance matrix of G

Description
===========

The distance matrix is the matrix where entry M_(i,j) corresponds to the
distance between vertex indexed i and vertex indexed j in the specified graph.
If the distance between two vertexSet is infinite (i.e. the vertexSet are not
connected) the matrix lists the distance as -1.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4}},EntryMode=>"edges");      |
+-------------------------------------------------------------+
|i2 : d = distanceMatrix G                                    |
|                                                             |
|o2 = | 0 1 2 3 |                                             |
|     | 1 0 1 2 |                                             |
|     | 2 1 0 1 |                                             |
|     | 3 2 1 0 |                                             |
|                                                             |
|              4        4                                     |
|o2 : Matrix ZZ  <--- ZZ                                      |
+-------------------------------------------------------------+
|i3 : G = digraph({1,2,3,4},{{2,3},{3,4}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i4 : d = distanceMatrix G                                    |
|                                                             |
|o4 = | 0  -1 -1 -1 |                                         |
|     | -1 0  1  2  |                                         |
|     | -1 -1 0  1  |                                         |
|     | -1 -1 -1 0  |                                         |
|                                                             |
|              4        4                                     |
|o4 : Matrix ZZ  <--- ZZ                                      |
+-------------------------------------------------------------+

See also
========

  * diameter(Graph) -- Computes the diameter of a
    graph
  * distance -- Computes the distance between two vertexSet in
    a graph

Ways to use distanceMatrix :
============================

  * "distanceMatrix(Digraph)"

For the programmer
==================

The object distanceMatrix, is a method function (Macaulay2Doc).

doubleStar -- returns a double star graph
*****************************************

Synopsis
========

  * Usage:
        G = doubleStar (m,n)
  * Inputs:
      * n, an integer (Macaulay2Doc),
      * m, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph,

Description
===========

A double star graph is a graph formed by starting with 2 vertices and joining
them together. Then each vertex is connected to a fixed amount of leaves
(vertices of degree 1) specified by the user in the inputs.

+-----------------------------------+
|i1 : G = doubleStar(4,5)           |
|                                   |
|o1 = Graph{0 => {1, 2, 3, 4, 5, 6}}|
|           1 => {0}                |
|           2 => {0}                |
|           3 => {0}                |
|           4 => {0}                |
|           5 => {0}                |
|           6 => {0, 7, 8, 9, 10}   |
|           7 => {6}                |
|           8 => {6}                |
|           9 => {6}                |
|           10 => {6}               |
|                                   |
|o1 : Graph                         |
+-----------------------------------+

See also
========

  * starGraph -- Returns a star graph
  * isLeaf -- determines whether a vertex is a leaf

Ways to use doubleStar :
========================

  * "doubleStar(ZZ,ZZ)"

For the programmer
==================

The object doubleStar, is a method function (Macaulay2Doc).

eccentricity -- Returns the eccentricity of a vertex of a graph
***************************************************************

Synopsis
========

  * Usage:
        k = eccentricity (G, v)
  * Inputs:
      * G, a graph, G must be a connected graph
      * v, a thing (Macaulay2Doc), v needs to be a vertex of the
        graph
  * Outputs:
      * k, an integer (Macaulay2Doc),

Description
===========

The eccentricity of a vertex is the maximal distance between the given vertex
and any other vertex in the graph. It gives a measure of how far away a vertex
is from the rest of the graph.

+---------------------------------+
|i1 : eccentricity(pathGraph 5, 2)|
|                                 |
|o1 = 2                           |
+---------------------------------+
|i2 : eccentricity(pathGraph 5, 1)|
|                                 |
|o2 = 3                           |
+---------------------------------+
|i3 : eccentricity(pathGraph 5, 0)|
|                                 |
|o3 = 4                           |
+---------------------------------+

See also
========

  * distance -- Computes the distance between two vertexSet in
    a graph
  * radius -- Returns the radius of a graph
  * isConnected -- determines whether a graph is connected

Ways to use eccentricity :
==========================

  * "eccentricity(Graph,Thing)"

For the programmer
==================

The object eccentricity, is a method function (Macaulay2Doc).

edgeConnectivity -- computes the edge connectivity of a graph
*************************************************************

Synopsis
========

  * Usage:
        C = edgeConnectivity G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, an integer (Macaulay2Doc), the edge connectivity of a
        graph

Description
===========

The edge connectivity of a graph is the smallest amount of edges that need be
removed from a graph to make it not connected.  This corresponds to the size of
the edge cuts.  A not connected graph has edge connectivity equal to 0.

+-------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1},{3,4},{4,5},{5,3}},EntryMode=>"edges");|
+-------------------------------------------------------------------------+
|i2 : edgeConnectivity G                                                  |
|                                                                         |
|o2 = 2                                                                   |
+-------------------------------------------------------------------------+

See also
========

  * edgeCuts -- returns the edge cuts of a graph
  * vertexConnectivity -- computes the vertex
    connectivity of a graph

Ways to use edgeConnectivity :
==============================

  * "edgeConnectivity(Graph)"

For the programmer
==================

The object edgeConnectivity, is a method function (Macaulay2Doc).

edgeCuts -- returns the edge cuts of a graph
********************************************

Synopsis
========

  * Usage:
        C = edgeCuts G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a list (Macaulay2Doc), the edge cuts of a graph

Description
===========

An edge cut is a minimal set of edges that, when removed from a graph, make the
graph not connected.  If the graph is already not connected, the method returns
the empty set.

+-----------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1},{3,4},{4,5},{5,3}},EntryMode=>"edges");    |
+-----------------------------------------------------------------------------+
|i2 : edgeCuts G                                                              |
|                                                                             |
|o2 = {{{1, 2}, {1, 3}}, {{1, 2}, {2, 3}}, {{1, 3}, {2, 3}}, {{4, 3}, {5, 3}},|
|     ------------------------------------------------------------------------|
|     {{4, 3}, {4, 5}}, {{5, 3}, {4, 5}}}                                     |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * vertexCuts -- lists all the vertex cuts of a graph
  * minimalVertexCuts -- finds the minimal vertex
    cuts of a graph
  * edgeConnectivity -- computes the edge connectivity
    of a graph

Ways to use edgeCuts :
======================

  * "edgeCuts(Graph)"

For the programmer
==================

The object edgeCuts, is a method function (Macaulay2Doc).

edgeIdeal -- returns the edge ideal of a graph
**********************************************

Synopsis
========

  * Usage:
        I = edgeIdeal G
  * Inputs:
      * G, a graph,
  * Outputs:
      * I, an ideal (Macaulay2Doc), the edge ideal of a graph G

Description
===========

The edge ideal of a graph G is the ideal generated by the minimal nonfaces of
the independence complex of G.

+--------------------------------------------------------------------+
|i1 : G = graph({{1, 2}, {1, 3}, {2, 3}, {3, 4}},EntryMode=>"edges");|
+--------------------------------------------------------------------+
|i2 : edgeIdeal G                                                    |
|                                                                    |
|o2 = monomialIdeal (x x , x x , x x , x x )                         |
|                     1 2   1 3   2 3   3 4                          |
|                                                                    |
|o2 : MonomialIdeal of QQ[x ..x ]                                    |
|                          1   4                                     |
+--------------------------------------------------------------------+

See also
========

  * coverIdeal -- Returns the vertex cover ideal of a graph
  * independenceComplex -- constructs the
    independence complex of a graph

Ways to use edgeIdeal :
=======================

  * "edgeIdeal(Graph)"

For the programmer
==================

The object edgeIdeal, is a method function (Macaulay2Doc).

edges -- Returns the edges of a digraph or graph
************************************************

Synopsis
========

  * Usage:
        E = edges D
        E = edges G
  * Inputs:
      * D, a digraph,
      * G, a graph,
  * Outputs:
      * E, a list (Macaulay2Doc), The edges of digraph D or graph G

Description
===========

The edges of a graph are pairs (or ordered pairs if we are dealing with
digraphs) of vertices that are connected in a graph. Any edge must be a member
of the collection of subsets of the vertex set of a graph.

+---------------------------------------------------------+
|i1 : D = digraph({{1,2},{2,1},{3,1}},EntryMode=>"edges");|
+---------------------------------------------------------+
|i2 : edges D                                             |
|                                                         |
|o2 = {{1, 2}, {2, 1}, {3, 1}}                            |
|                                                         |
|o2 : List                                                |
+---------------------------------------------------------+
|i3 : G = cycleGraph 4;                                   |
+---------------------------------------------------------+
|i4 : edges G                                             |
|                                                         |
|o4 = {set {0, 1}, set {0, 3}, set {1, 2}, set {2, 3}}    |
|                                                         |
|o4 : List                                                |
+---------------------------------------------------------+

See also
========

  * vertexSet -- Returns the vertices of a graph or digraph

Ways to use edges :
===================

  * "edges(Digraph)"
  * "edges(Graph)"

For the programmer
==================

The object edges, is a method function (Macaulay2Doc).

expansion -- returns the expansion of a graph
*********************************************

Synopsis
========

  * Usage:
        h=expansion G
  * Inputs:
      * G, a graph,
  * Outputs:
      * h, a rational number (Macaulay2Doc), the expansion of a graph
        G

Description
===========

The expansion of a subset S of vertices is the ratio of the number of edges
leaving S and the size of S. The (edge) expansion of a graph G is the minimal
expansion of all not too large subsets of the vertex set. The expansion of a
disconnected graph is 0 whereas the expansion of the complete graph on n
vertices is ceiling(n/2)

+--------------------------------------------------------------------+
|i1 : G = graph({{1, 2}, {1, 3}, {2, 3}, {3, 4}},EntryMode=>"edges");|
+--------------------------------------------------------------------+
|i2 : expansion G                                                    |
|                                                                    |
|o2 = 1                                                              |
|                                                                    |
|o2 : QQ                                                             |
+--------------------------------------------------------------------+
|i3 : expansion pathGraph 7                                          |
|                                                                    |
|     1                                                              |
|o3 = -                                                              |
|     3                                                              |
|                                                                    |
|o3 : QQ                                                             |
+--------------------------------------------------------------------+

Ways to use expansion :
=======================

  * "expansion(Graph)"

For the programmer
==================

The object expansion, is a method function (Macaulay2Doc).

findPaths -- finds all the paths in a digraph of a given length starting at a given vertex
******************************************************************************************

Synopsis
========

  * Usage:
        F = findPaths(D,v,l)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), vertex at which paths start
      * l, an integer (Macaulay2Doc), length of desired paths
  * Outputs:
      * F, a list (Macaulay2Doc), list of paths starting at v of
        length l

Description
===========

The method will return a list of all the paths of length l starting at a vertex
v in the digraph D.  The method is compatible for graphs with loops or cycles,
as variables can be repeatedly visited in paths.

+-----------------------------------------------------------------------------+
|i1 : D = digraph(toList(1..5), {{1,2},{1,3},{2,5},{2,4}})                    |
|                                                                             |
|o1 = Digraph{1 => {2, 3}}                                                    |
|             2 => {4, 5}                                                     |
|             3 => {}                                                         |
|             4 => {}                                                         |
|             5 => {}                                                         |
|                                                                             |
|o1 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i2 : F = findPaths(D,1,2)                                                    |
|                                                                             |
|o2 = {{1, 2, 4}, {1, 2, 5}}                                                  |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : D = digraph(toList(a..d), {{a,c},{a,b},{b,b},{b,d}})                    |
|                                                                             |
|o3 = Digraph{a => {b, c}}                                                    |
|             b => {b, d}                                                     |
|             c => {}                                                         |
|             d => {}                                                         |
|                                                                             |
|o3 : Digraph                                                                 |
+-----------------------------------------------------------------------------+
|i4 : F = findPaths(D,a,100)                                                  |
|                                                                             |
|o4 = {{a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,  |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, d}, {a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,  |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, |
|     ------------------------------------------------------------------------|
|     b, b, b, b, b, b, b, b, b, b, b, b}}                                    |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * distance -- Computes the distance between two vertexSet in
    a graph
  * distanceMatrix -- Computes the distance matrix of a
    digraph

Ways to use findPaths :
=======================

  * "findPaths(Digraph,Thing,ZZ)"

For the programmer
==================

The object findPaths, is a method function (Macaulay2Doc).

finishingTime
*************

For the programmer
==================

The object finishingTime (missing documentation) is a symbol (Macaulay2Doc).

floydWarshall -- runs the Floyd-Warshall algorithm on a digraph to determine the minimum distance from one vertex to another in the digraph
*******************************************************************************************************************************************

Synopsis
========

  * Usage:
        F = floydWarshall D
  * Inputs:
      * D, a digraph,
  * Outputs:
      * F, a hash table (Macaulay2Doc), A hash table with the
        keys representing pairs of vertexSet (u,v) and the value being the
        distance from u to v.

Description
===========

The distance from one vertex u to another v in digraph D is the minimum number
of edges forming a path from u to v.  If v is not reachable from u, the
distance is infinity; if u = v, the distance is 0.

+--------------------------------------------------------------------+
|i1 : D = digraph({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges")|
|                                                                    |
|o1 = Digraph{0 => {1, 2}}                                           |
|             1 => {}                                                |
|             2 => {3}                                               |
|             3 => {4}                                               |
|             4 => {2}                                               |
|                                                                    |
|o1 : Digraph                                                        |
+--------------------------------------------------------------------+
|i2 : F = floydWarshall D                                            |
|                                                                    |
|o2 = HashTable{(0, 0) => 0       }                                  |
|               (0, 1) => 1                                          |
|               (0, 2) => 1                                          |
|               (0, 3) => 2                                          |
|               (0, 4) => 3                                          |
|               (1, 0) => infinity                                   |
|               (1, 1) => 0                                          |
|               (1, 2) => infinity                                   |
|               (1, 3) => infinity                                   |
|               (1, 4) => infinity                                   |
|               (2, 0) => infinity                                   |
|               (2, 1) => infinity                                   |
|               (2, 2) => 0                                          |
|               (2, 3) => 1                                          |
|               (2, 4) => 2                                          |
|               (3, 0) => infinity                                   |
|               (3, 1) => infinity                                   |
|               (3, 2) => 2                                          |
|               (3, 3) => 0                                          |
|               (3, 4) => 1                                          |
|               (4, 0) => infinity                                   |
|               (4, 1) => infinity                                   |
|               (4, 2) => 1                                          |
|               (4, 3) => 2                                          |
|               (4, 4) => 0                                          |
|                                                                    |
|o2 : HashTable                                                      |
+--------------------------------------------------------------------+

See also
========

  * distance -- Computes the distance between two vertexSet in
    a graph
  * distanceMatrix -- Computes the distance matrix of a
    digraph

Ways to use floydWarshall :
===========================

  * "floydWarshall(Digraph)"

For the programmer
==================

The object floydWarshall, is a method function (Macaulay2Doc).

forefathers -- returns the forefathers of a digraph
***************************************************

Synopsis
========

  * Usage:
        L = forefathers (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), v must be a vertex of D
  * Outputs:
      * L, a set (Macaulay2Doc), a set of all the forefathers of v
        in D

Description
===========

The forefathers of a vertex v in a digraph D are all the vertexSet u in D such
that v is reachable from u. Another way to more intuitively see what the
forefathers are is to see the forefathers of a vertex v can be found by first
taking the parents of v. Then if you find the parents of each of the parents of
v, and continue the process until the list stops growing, this will form all
the descandants of v.

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : forefathers (D, d)                                 |
|                                                        |
|o2 = set {a, b, d, e}                                   |
|                                                        |
|o2 : Set                                                |
+--------------------------------------------------------+

Caveat
======

The forefathers of a vertex in a digraph are more commonly known as the
ancestors. But ancestors is an entirely different function in Macaulay 2, so
forefathers is the convention we will use

See also
========

  * isReachable -- checks if a vertex u is reachable from a
    vertex v
  * parents -- returns the parents of a vertex on a digraph

Ways to use forefathers :
=========================

  * "forefathers(Digraph,Thing)"

For the programmer
==================

The object forefathers, is a method function (Macaulay2Doc).

friendshipGraph -- Returns a friendship Graph
*********************************************

Synopsis
========

  * Usage:
        G = friendshipGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph,

Description
===========

Friendship graphs of size n are a special case of windmill graphs. A friendship
graph of size n is n 3-cycles that all share one common vertex.

+-----------------------------------------+
|i1 : G = friendshipGraph 4               |
|                                         |
|o1 = Graph{0 => {1, 3, 5, 7, 2, 4, 6, 8}}|
|           1 => {0, 2}                   |
|           2 => {0, 1}                   |
|           3 => {0, 4}                   |
|           4 => {0, 3}                   |
|           5 => {0, 6}                   |
|           6 => {0, 5}                   |
|           7 => {0, 8}                   |
|           8 => {0, 7}                   |
|                                         |
|o1 : Graph                               |
+-----------------------------------------+
|i2 : H = windmillGraph (3,4)             |
|                                         |
|o2 = Graph{0 => {1, 3, 5, 7, 2, 4, 6, 8}}|
|           1 => {0, 2}                   |
|           2 => {0, 1}                   |
|           3 => {0, 4}                   |
|           4 => {0, 3}                   |
|           5 => {0, 6}                   |
|           6 => {0, 5}                   |
|           7 => {0, 8}                   |
|           8 => {0, 7}                   |
|                                         |
|o2 : Graph                               |
+-----------------------------------------+

See also
========

  * windmillGraph -- Constructs a windmill graph

Ways to use friendshipGraph :
=============================

  * "friendshipGraph(ZZ)"

For the programmer
==================

The object friendshipGraph, is a method function (Macaulay2Doc).

generalizedPetersenGraph -- Returns a generalized petersen graph
****************************************************************

Synopsis
========

  * Usage:
        G = generalizedPetersenGraph (n, k)
  * Inputs:
      * n, an integer (Macaulay2Doc), The number of vertices will be
        2*n, n in the outer ring and n in the inside ring
      * k, an integer (Macaulay2Doc), The middle ring is a complete
        graph but looks like a star, k is the number of vertices that get
        jumped for each connection k must be less than n/2.
  * Outputs:
      * G, a graph, The generalized petersen graph

Description
===========

The generalized Petersen Graph is a class of graphs with a particular edge set.
There are two equal sets of vertices and each set is a cycle graph. This forms
two disjoint cyclegraphs. Then each inside edge connects to an adjacent outside
edge, similar to the circular ladder graph. The outer loop keeps a more
"canonical" order for the cycle, in the sense that it does not "skip" vertices,
while the inner cycle takes on a "star-like pattern" that jumps vertices but is
still connected.

+-----------------------------------+
|i1 : generalizedPetersenGraph (5,2)|
|                                   |
|o1 = Graph{0 => {1, 4, 5}}         |
|           1 => {0, 2, 6}          |
|           2 => {1, 3, 7}          |
|           3 => {2, 4, 8}          |
|           4 => {0, 3, 9}          |
|           5 => {0, 7, 8}          |
|           6 => {1, 8, 9}          |
|           7 => {2, 5, 9}          |
|           8 => {3, 5, 6}          |
|           9 => {4, 6, 7}          |
|                                   |
|o1 : Graph                         |
+-----------------------------------+

See also
========

  * circularLadder -- Returns a circular ladder graph

Ways to use generalizedPetersenGraph :
======================================

  * "generalizedPetersenGraph(ZZ,ZZ)"

For the programmer
==================

The object generalizedPetersenGraph, is a
method function (Macaulay2Doc).

girth -- A method for computing the girth of a graph
****************************************************

Synopsis
========

  * Usage:
        g = girth G
  * Inputs:
      * G, a graph,
  * Outputs:
      * g, an integer (Macaulay2Doc), the girth of G

Description
===========

This method computes the girth (the smallest n such that G contains an n-cycle)
of any graph. If the graph has no n-cycle as a subgraph, the output will be
infinity.

+--------------------------+
|i1 : girth completeGraph 6|
|                          |
|o1 = 3                    |
+--------------------------+
|i2 : girth pathGraph 6    |
|                          |
|o2 = infinity             |
|                          |
|o2 : InfiniteNumber       |
+--------------------------+

Ways to use girth :
===================

  * "girth(Graph)"

For the programmer
==================

The object girth, is a method function (Macaulay2Doc).

Graph
*****

Functions and methods returning a graph :
=========================================

  * "addEdge(Digraph,Set)" -- see addEdge, -- A method for
    adding edges to a graph
  * addEdges'(Graph,List) (missing documentation)
  * "addVertices(Digraph,List)" -- see addVertex, -- A method
    for adding a set of vertices to a graph
  * addVertices(Graph,List) (missing documentation)
  * "barbellGraph(ZZ)" -- see barbellGraph, -- Returns the
    barbell graph
  * "barycenter(Graph)" -- see barycenter, -- Returns the
    barycenter of a grah
  * "cartesianProduct(Graph,Graph)" -- see cartesianProduct,
    -- Computes the cartesian product of two graphs
  * "circularLadder(ZZ)" -- see circularLadder, --
    Returns a circular ladder graph
  * "cocktailParty(ZZ)" -- see cocktailParty, -- Returns a
    cocktail party graph
  * "complementGraph(Graph)" -- see complementGraph, --
    Returns the complement of a graph
  * "completeGraph(ZZ)" -- see completeGraph, --
    Constructs a complete graph
  * "completeMultipartiteGraph(List)" -- see completeMultipartiteGraph,
    -- constructs a complete multipartite graph
  * "crownGraph(ZZ)" -- see crownGraph, -- Returns a crown
    graph
  * "cycleGraph(ZZ)" -- see cycleGraph, -- Constructs a cycle
    graph
  * "deleteEdges(Graph,List)" -- see deleteEdges, -- Deletes
    a list of edges from a graph
  * deleteEdges(Digraph,List) (missing documentation)
  * "deleteVertex(Graph,Thing)" -- see deleteVertex, -- a
    method for deleting the vertex of a graph
  * "directProduct(Graph,Graph)" -- see directProduct, --
    Computes the direct product of two graphs
  * "disjointUnion(List)" -- see disjointUnion, -- Returns
    the disjoint union of a list of graphs.
  * "doubleStar(ZZ,ZZ)" -- see doubleStar, -- returns a
    double star graph
  * "friendshipGraph(ZZ)" -- see friendshipGraph, --
    Returns a friendship Graph
  * "generalizedPetersenGraph(ZZ,ZZ)" -- see generalizedPetersenGraph,
    -- Returns a generalized petersen graph
  * "graph(HashTable)" -- see graph, -- Constructs a simple graph
  * "graph(List)" -- see graph, -- Constructs a simple graph
  * "graph(List,List)" -- see graph, -- Constructs a simple graph
  * "graph(List,Matrix)" -- see graph, -- Constructs a simple
    graph
  * "graph(Matrix)" -- see graph, -- Constructs a simple graph
  * "graphComposition(Graph,Graph)" -- see graphComposition,
    -- A method for composing two graphs
  * "graphLibrary(String)" -- see graphLibrary, --
    constructs a graph of a type specified in the string input
  * "graphPower(Graph,ZZ)" -- see graphPower, -- constructs a
    graph raised to a power
  * "indexLabelGraph(Graph)" -- see indexLabelGraph, --
    Relabels the vertices of a graph or digraph according to their indices,
    indexed from 0.
  * "inducedSubgraph(Graph,List)" -- see inducedSubgraph,
    -- A method for finding the induced subgraph of any Graph
    or Digraph
  * "kneserGraph(ZZ,ZZ)" -- see kneserGraph, -- constructs a
    kneser graph of specified size
  * "ladderGraph(ZZ)" -- see ladderGraph, -- Returns a
    ladder graph
  * "lineGraph(Graph)" -- see lineGraph, -- Returns the line
    graph of an undirected graph
  * "lollipopGraph(ZZ,ZZ)" -- see lollipopGraph, --
    constructs a lollipop graph
  * "monomialGraph(MonomialIdeal,ZZ)" -- see monomialGraph,
    -- Returns a monomial graph
  * "pathGraph(ZZ)" -- see pathGraph, -- A method that makes a
    path graph
  * "rattleGraph(ZZ,ZZ)" -- see rattleGraph, -- Returns a
    rattle graph
  * "reindexBy(Graph,String)" -- see reindexBy, -- reindexes
    the vertices according to the input ordering.
  * "spanningForest(Graph)" -- see spanningForest, --
    constructs a spanning forest of a graph
  * "starGraph(ZZ)" -- see starGraph, -- Returns a star graph
  * "strongProduct(Graph,Graph)" -- see strongProduct, --
    a method for taking the strong product of two graphs
  * "thresholdGraph(List)" -- see thresholdGraph, -- A
    method that generates a threshold graph from a binary list
  * "underlyingGraph(Digraph)" -- see underlyingGraph,
    -- Returns the underlying graph of a digraph
  * "vertexMultiplication(Graph,Thing,Thing)" -- see
    vertexMultiplication,
  * "wheelGraph(ZZ)" -- see wheelGraph, -- Constructs a wheel
    graph
  * "windmillGraph(ZZ,ZZ)" -- see windmillGraph, --
    Constructs a windmill graph

Methods that use a graph :
==========================

  * "bipartiteColoring(Graph)" -- see bipartiteColoring,
    -- Returns a coloring of a bipartite graph
  * "center(Graph)" -- see center, -- Returns the center of a
    graph
  * "chromaticNumber(Graph)" -- see chromaticNumber, --
    Computes the chromatic number of a graph
  * "cliqueComplex(Graph)" -- see cliqueComplex, --
    Returns the clique complex of a graph
  * "cliqueNumber(Graph)" -- see cliqueNumber, -- Returns
    the clique number of a graph
  * "closedNeighborhood(Graph,Thing)" -- see closedNeighborhood,
    -- Returns the closed neighborhood of a vertex of a
    graph
  * "clusteringCoefficient(Graph)" -- see clusteringCoefficient,
    -- a method for computing the clustering coefficient
    of a Graph
  * "clusteringCoefficient(Graph,Thing)" -- see clusteringCoefficient,
    -- a method for computing the clustering coefficient
    of a Graph
  * connectedComponents(Graph), --
    Computes the connected components of a graph
  * "coverIdeal(Graph)" -- see coverIdeal, -- Returns the
    vertex cover ideal of a graph
  * "criticalEdges(Graph)" -- see criticalEdges, -- Finds
    the critical edges of a graph
  * "degeneracy(Graph)" -- see degeneracy, -- Computes the
    degeneracy of a graph
  * degree(Graph,Thing) (missing documentation)
  * "degreeCentrality(Graph,Thing)" -- see degreeCentrality,
    -- Returns the degreeCentrality of a vertex of a graph
  * "degreeSequence(Graph)" -- see degreeSequence, -- the
    degree sequence of a graph
  * "density(Graph)" -- see density, -- computes the density of
    a graph
  * diameter(Graph) -- Computes the diameter of a
    graph
  * "eccentricity(Graph,Thing)" -- see eccentricity, --
    Returns the eccentricity of a vertex of a graph
  * "edgeConnectivity(Graph)" -- see edgeConnectivity,
    -- computes the edge connectivity of a graph
  * "edgeCuts(Graph)" -- see edgeCuts, -- returns the edge cuts
    of a graph
  * "edgeIdeal(Graph)" -- see edgeIdeal, -- returns the edge
    ideal of a graph
  * "edges(Graph)" -- see edges, -- Returns the edges of a digraph
    or graph
  * "expansion(Graph)" -- see expansion, -- returns the
    expansion of a graph
  * "girth(Graph)" -- see girth, -- A method for computing the
    girth of a graph
  * "hasEulerianTrail(Graph)" -- see hasEulerianTrail,
    -- determines whether a graph or a digraph has an Eulerian trail
  * "hasOddHole(Graph)" -- see hasOddHole, -- checks whether
    a graph has a odd hole
  * "incidenceMatrix(Graph)" -- see incidenceMatrix, --
    computes the incidence matrix of a graph
  * "independenceComplex(Graph)" -- see independenceComplex,
    -- constructs the independence complex of a graph
  * "independenceNumber(Graph)" -- see independenceNumber,
    -- computes the independence number of a graph
  * "isBipartite(Graph)" -- see isBipartite, -- determines
    whether a graph is bipartite
  * "isChordal(Graph)" -- see isChordal, -- checks whether a
    graph is chordal
  * "isCM(Graph)" -- see isCM, -- determines if a graph is
    Cohen-Macaulay
  * "isConnected(Graph)" -- see isConnected, -- determines
    whether a graph is connected
  * "isCyclic(Graph)" -- see isCyclic, -- determines whether a
    graph is cyclic
  * "isEulerian(Graph)" -- see isEulerian, -- determines if a
    graph or digraph is Eulerian
  * "isForest(Graph)" -- see isForest, -- determines whether a
    graph is a forest
  * "isLeaf(Graph,Thing)" -- see isLeaf, -- determines whether a
    vertex is a leaf
  * "isPerfect(Graph)" -- see isPerfect, -- checks whether a
    graph is perfect
  * "isRegular(Graph)" -- see isRegular, -- determines whether
    a graph is regular
  * "isRigid(Graph)" -- see isRigid, -- checks if a graph is
    rigid
  * "isSimple(Graph)" -- see isSimple, -- checks if a graph is
    simple
  * "isTree(Graph)" -- see isTree, -- determines whether a graph
    is a tree
  * "laplacianMatrix(Graph)" -- see laplacianMatrix, --
    Returns the laplacian matrix of a graph
  * "leaves(Graph)" -- see leaves, -- lists the leaves of a tree
    graph
  * "minimalDegree(Graph)" -- see minimalDegree, --
    computes the minimal degree of a graph
  * "minimalVertexCuts(Graph)" -- see minimalVertexCuts,
    -- finds the minimal vertex cuts of a graph
  * "neighbors(Graph,Thing)" -- see neighbors, -- returns the
    neighbors of a vertex in a graph
  * "nonneighbors(Graph,Thing)" -- see nonneighbors, --
    returns the non-neighbors of a vertex in a graph
  * "numberOfComponents(Graph)" -- see numberOfComponents,
    -- computes the number of connected components of a
    graph
  * "numberOfTriangles(Graph)" -- see numberOfTriangles,
    -- counts how many subtriangles are present in a graph
  * "radius(Graph)" -- see radius, -- Returns the radius of a
    graph
  * "spectrum(Graph)" -- see spectrum, -- Returns the spectrum
    of a graph
  * "vertexConnectivity(Graph)" -- see vertexConnectivity,
    -- computes the vertex connectivity of a graph
  * "vertexCoverNumber(Graph)" -- see vertexCoverNumber,
    -- returns the vertex cover number of a graph
  * "vertexCovers(Graph)" -- see vertexCovers, -- returns a
    list of the minimal vertex covers of a graph
  * "vertexCuts(Graph)" -- see vertexCuts, -- lists all the
    vertex cuts of a graph
  * "writeDotFile(String,Graph)" -- see writeDotFile, --
    Writes a graph to a dot file with a specified filename

For the programmer
==================

The object Graph, is a type (Macaulay2Doc), with
ancestor classes Digraph, < HashTable (Macaulay2Doc)
< Thing (Macaulay2Doc).

graph -- Constructs a simple graph
**********************************

Synopsis
========

  * Usage:
        G = graph E
        G = graph (V,E)
        G = graph H
        G = graph (V, A)
        G = graph A
  * Inputs:
      * E, a list (Macaulay2Doc),
      * V, a list (Macaulay2Doc),
      * H, a hash table (Macaulay2Doc),
      * A, a matrix (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * EntryMode => ..., default value "auto"
      * Singletons => ..., default value null
  * Outputs:
      * G, a graph, The graph with edges E and vertices V, or
        constructed from HashTable H, or from an adjacency matrix A, or from a
        new naming of vertices V and an adjacency matrix A.

Description
===========

A graph consists of two sets, a vertex set and an edge set which is a subset of
the collection of subsets of the vertex set. Edges in graphs are symmetric or
two-way; if u and v are vertices then if {u,v} is an edge connecting them,
{v,u} is also an edge (which is implicit in the definition, we will almost
always just use one of the pairs). Graphs are defined uniquely from their
Adjacency Matrices. These matrices use the entries as 0 or 1 to signal the
existence of an edge connecting vertices. The options for EntryMode are
"neighbors" and "edges" (the default).  This means that in including EntryMode
=> "edges" in the constructor allows the user to simply type in a list of edges
to construct a graph.  See example 1 below.  Using the default takes an input
of a list of pairs, where the first entry of each pair is a vertex and the
second entry of each pair is that vertex's neighborhood. The options for
Singletons allows the user to enter Singletons => {list of single points} in a
graph if they desire to have isolated points in a graph.  See second example
below.

+--------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4}})                           |
|                                                              |
|o1 = Graph{1 => {2}   }                                       |
|           2 => {1, 3}                                        |
|           3 => {2, 4}                                        |
|           4 => {3}                                           |
|                                                              |
|o1 : Graph                                                    |
+--------------------------------------------------------------+
|i2 : G = graph({{1,2},{2,3},{3,4}}, Singletons => {5,6,7})    |
|                                                              |
|o2 = Graph{1 => {2}   }                                       |
|           2 => {1, 3}                                        |
|           3 => {2, 4}                                        |
|           4 => {3}                                           |
|           5 => {}                                            |
|           6 => {}                                            |
|           7 => {}                                            |
|                                                              |
|o2 : Graph                                                    |
+--------------------------------------------------------------+
|i3 : G = graph ({{a,{b,c,d,e}}, {b,{d,e}}, {e,{a}}})          |
|                                                              |
|o3 = Graph{a => {e, b, c, d}}                                 |
|           b => {e, a, d}                                     |
|           c => {a}                                           |
|           d => {a, b}                                        |
|           e => {a, b}                                        |
|                                                              |
|o3 : Graph                                                    |
+--------------------------------------------------------------+
|i4 : G = graph hashTable {{1,{2}},{2,{1,3}},{3,{2,4}},{4,{3}}}|
|                                                              |
|o4 = Graph{1 => {2}   }                                       |
|           2 => {1, 3}                                        |
|           3 => {2, 4}                                        |
|           4 => {3}                                           |
|                                                              |
|o4 : Graph                                                    |
+--------------------------------------------------------------+
|i5 : G = graph(matrix {{0,1,1},{1,0,0},{1,0,0}})              |
|                                                              |
|o5 = Graph{0 => {1, 2}}                                       |
|           1 => {0}                                           |
|           2 => {0}                                           |
|                                                              |
|o5 : Graph                                                    |
+--------------------------------------------------------------+
|i6 : G = graph({a,b,c}, matrix {{0,1,1},{1,0,0},{1,0,0}})     |
|                                                              |
|o6 = Graph{a => {b, c}}                                       |
|           b => {a}                                           |
|           c => {a}                                           |
|                                                              |
|o6 : Graph                                                    |
+--------------------------------------------------------------+

See also
========

  * digraph -- Constructs a digraph

Ways to use graph :
===================

  * "graph(HashTable)"
  * "graph(List)"
  * "graph(List,List)"
  * "graph(List,Matrix)"
  * "graph(Matrix)"
  * graph(Digraph) -- Returns the legacy G#graph
    hash table

For the programmer
==================

The object graph, is a method function with options (Macaulay2Doc).

graph(Digraph) -- Returns the legacy G#graph hash table
*******************************************************

Synopsis
========

  * Function: graph,
  * Usage:
        G = graph D
  * Inputs:
      * D, a digraph,
  * Optional inputs (Macaulay2Doc),:
      * EntryMode, => ..., default value "auto", Constructs a
        simple graph
      * Singletons, => ..., default value null, Constructs a
        simple graph
  * Outputs:
      * H, a hash table (Macaulay2Doc), The hash table with a
        graph's vertices as keys and list of neighbors as values.

Description
===========

A graph consists of two sets, a vertex set and an edge set which is a subset of
the collection of subsets of the vertex set. Edges in graphs are symmetric or
two-way; if u and v are vertices then if {u,v} is an edge connecting them,
{v,u} is also an edge (which is implicit in the definition, we will almost
always just use one of the pairs). The options for EntryMode are "neighbors"
(the default) and "edges".  This method returns a hash table where the keys are
vertices of a given graph or digraph and the values are their children (or
neighbors, in the case of undirected graphs).

+-----------------------------------------------------------------+
|i1 : G = graph digraph({{1,2},{2,1},{3,1}}, EntryMode => "edges")|
|                                                                 |
|o1 = HashTable{1 => {2}}                                         |
|               2 => {1}                                          |
|               3 => {1}                                          |
|                                                                 |
|o1 : HashTable                                                   |
+-----------------------------------------------------------------+
|i2 : G = graph digraph(matrix {{0,1,1},{1,0,0},{1,0,0}})         |
|                                                                 |
|o2 = HashTable{0 => {1, 2}}                                      |
|               1 => {0}                                          |
|               2 => {0}                                          |
|                                                                 |
|o2 : HashTable                                                   |
+-----------------------------------------------------------------+

See also
========

  * digraph -- Constructs a digraph

Ways to use this method:
========================

  * graph(Digraph) -- Returns the legacy G#graph
    hash table

graphComposition -- A method for composing two graphs
*****************************************************

Synopsis
========

  * Usage:
        F = graphComposition(G,H)
  * Inputs:
      * G, a graph,
      * H, a graph,
  * Outputs:
      * F, a graph, The Graph Composition of G and H

Description
===========

This method will take in any two graphs and output the composition of the two
graphs. The vertex set of the graph composition of G and H is the cartesian
product of the vertex sets of G and H. The keys for each vertex will be output
as a sequence to represent this. The edge set is formed by the rule that any
two vertices (u,v) and (x,y) are adjacent the composition of G and H if and
only if either u is adjacent with x in G or u = x and v is adjacent with y in
H. Be careful, since this operation is not commutative, and the user needs to
be mindful what order the graphs are entered into the method.

+--------------------------------------------------------------+
|i1 : G = graph({1,2},{{1,2}});                                |
+--------------------------------------------------------------+
|i2 : H = graph({3,4,5},{{3,4},{4,5}})                         |
|                                                              |
|o2 = Graph{3 => {4}   }                                       |
|           4 => {3, 5}                                        |
|           5 => {4}                                           |
|                                                              |
|o2 : Graph                                                    |
+--------------------------------------------------------------+
|i3 : GH = graphComposition(G,H)                               |
|                                                              |
|o3 = Graph{(1, 3) => {(2, 5), (2, 3), (1, 4), (2, 4)}        }|
|           (1, 4) => {(2, 5), (1, 3), (2, 3), (2, 4), (1, 5)} |
|           (1, 5) => {(2, 5), (2, 3), (1, 4), (2, 4)}         |
|           (2, 3) => {(1, 3), (1, 4), (2, 4), (1, 5)}         |
|           (2, 4) => {(2, 5), (1, 3), (2, 3), (1, 4), (1, 5)} |
|           (2, 5) => {(1, 3), (1, 4), (2, 4), (1, 5)}         |
|                                                              |
|o3 : Graph                                                    |
+--------------------------------------------------------------+
|i4 : HG = graphComposition(H,G)                               |
|                                                              |
|o4 = Graph{(3, 1) => {(3, 2), (4, 1), (4, 2)}                }|
|           (3, 2) => {(3, 1), (4, 1), (4, 2)}                 |
|           (4, 1) => {(5, 2), (3, 1), (3, 2), (4, 2), (5, 1)} |
|           (4, 2) => {(5, 2), (3, 1), (3, 2), (4, 1), (5, 1)} |
|           (5, 1) => {(5, 2), (4, 1), (4, 2)}                 |
|           (5, 2) => {(4, 1), (4, 2), (5, 1)}                 |
|                                                              |
|o4 : Graph                                                    |
+--------------------------------------------------------------+

See also
========

  * strongProduct -- a method for taking the strong
    product of two graphs
  * directProduct (Polyhedra) -- computes the direct
    product of two convex objects
  * cartesianProduct -- Computes the cartesian product
    of two graphs

Ways to use graphComposition :
==============================

  * "graphComposition(Graph,Graph)"

For the programmer
==================

The object graphComposition, is a method function (Macaulay2Doc).

graphLibrary -- constructs a graph of a type specified in the string input
**************************************************************************

Synopsis
========

  * Usage:
        G = graphLibrary(name)
  * Inputs:
      * name, a string (Macaulay2Doc),
  * Outputs:
      * G, a graph, The graph of the type specified by the String
        name

Description
===========

The graph library takes in a name of a special graph and constructs a graph of
that type.  Possible inputs include:  "petersen", "bidiakis cube", "desargues",
"dodecahedron", "durer", "claw", "cubical", "f26a", "franklin", "chvatal",
"heawood", "paw", "mobius", "nauru", "kite", "house", "bull", "bowtie", "dart".
Each of these create the special graph described clearly by their name.

+---------------------------------+
|i1 : G = graphLibrary("petersen")|
|                                 |
|o1 = Graph{0 => {1, 4, 5}}       |
|           1 => {0, 2, 6}        |
|           2 => {1, 3, 7}        |
|           3 => {2, 4, 8}        |
|           4 => {0, 3, 9}        |
|           5 => {0, 7, 8}        |
|           6 => {1, 8, 9}        |
|           7 => {2, 5, 9}        |
|           8 => {3, 5, 6}        |
|           9 => {4, 6, 7}        |
|                                 |
|o1 : Graph                       |
+---------------------------------+
|i2 : G = graphLibrary("f26a")    |
|                                 |
|o2 = Graph{0 => {1, 7, 25}   }   |
|           1 => {0, 2, 20}       |
|           2 => {1, 3, 9}        |
|           3 => {2, 4, 22}       |
|           4 => {3, 5, 11}       |
|           5 => {4, 6, 24}       |
|           6 => {5, 7, 13}       |
|           7 => {0, 6, 8}        |
|           8 => {7, 9, 15}       |
|           9 => {2, 8, 10}       |
|           10 => {9, 11, 17}     |
|           11 => {4, 10, 12}     |
|           12 => {11, 13, 19}    |
|           13 => {6, 12, 14}     |
|           14 => {13, 15, 21}    |
|           15 => {8, 14, 16}     |
|           16 => {15, 17, 23}    |
|           17 => {10, 16, 18}    |
|           18 => {17, 19, 25}    |
|           19 => {12, 18, 20}    |
|           20 => {1, 19, 21}     |
|           21 => {14, 20, 22}    |
|           22 => {3, 21, 23}     |
|           23 => {16, 22, 24}    |
|           24 => {5, 23, 25}     |
|           25 => {0, 18, 24}     |
|                                 |
|o2 : Graph                       |
+---------------------------------+
|i3 : G = graphLibrary("chvatal") |
|                                 |
|o3 = Graph{0 => {1, 3, 6, 11} }  |
|           1 => {0, 2, 4, 7}     |
|           2 => {1, 3, 5, 8}     |
|           3 => {0, 2, 4, 10}    |
|           4 => {1, 3, 5, 9}     |
|           5 => {2, 4, 6, 11}    |
|           6 => {0, 5, 7, 9}     |
|           7 => {1, 6, 8, 10}    |
|           8 => {2, 7, 9, 11}    |
|           9 => {4, 6, 8, 10}    |
|           10 => {3, 7, 9, 11}   |
|           11 => {0, 5, 8, 10}   |
|                                 |
|o3 : Graph                       |
+---------------------------------+

Ways to use graphLibrary :
==========================

  * "graphLibrary(String)"

For the programmer
==================

The object graphLibrary, is a method function (Macaulay2Doc).

graphPower -- constructs a graph raised to a power
**************************************************

Synopsis
========

  * Usage:
        G' = graphPower(G,k)
  * Inputs:
      * G, a graph,
      * k, an integer (Macaulay2Doc),
  * Outputs:
      * G', a graph, graph G to the kth power

Description
===========

G^k is the graph with the same vertices as G, where the vertices of G^k are
adjacent if they are separated by distance less than or equal to k in graph G.
If the diameter of G is d, G^d is the complete graph with the same number of
vertices as G.

+-----------------------------+
|i1 : G = cycleGraph 6;       |
+-----------------------------+
|i2 : graphPower(G,2)         |
|                             |
|o2 = Graph{0 => {1, 2, 4, 5}}|
|           1 => {0, 2, 3, 5} |
|           2 => {0, 1, 3, 4} |
|           3 => {1, 2, 4, 5} |
|           4 => {0, 2, 3, 5} |
|           5 => {0, 1, 3, 4} |
|                             |
|o2 : Graph                   |
+-----------------------------+

See also
========

  * distance -- Computes the distance between two vertexSet in
    a graph
  * diameter(Graph) -- Computes the diameter of a
    graph

Ways to use graphPower :
========================

  * "graphPower(Graph,ZZ)"

For the programmer
==================

The object graphPower, is a method function (Macaulay2Doc).

hasEulerianTrail -- determines whether a graph or a digraph has an Eulerian trail
*********************************************************************************

Synopsis
========

  * Usage:
        E = hasEulerianTrail G
        E = hasEulerianTrail D
  * Inputs:
      * G, a graph,
      * D, a digraph,
  * Outputs:
      * E, a Boolean value (Macaulay2Doc), whether G or D has an
        Eulerian trail

Description
===========

A graph has an Eulerian trail if there is a path in the graph that visits each
edge exactly once.  A digraph has a Eulerian trail if there is a directed path
in the graph that visits each edge exactly once.  An Eulerian trail is also
called an Eulerian path.  Unconnected graphs can have a Eulerian trail, but all
vertices of degree greater than 0 of a graph (or all vertices of degree greater
than 0 in the underlying graph of a digraph) must belong to a single connected
component.

+----------------------------------------------------+
|i1 : G = cycleGraph 5;                              |
+----------------------------------------------------+
|i2 : hasEulerianTrail G                             |
|                                                    |
|o2 = true                                           |
+----------------------------------------------------+
|i3 : D = digraph(toList(1..4), {{1,2},{2,3},{3,4}});|
+----------------------------------------------------+
|i4 : hasEulerianTrail D                             |
|                                                    |
|o4 = true                                           |
+----------------------------------------------------+

See also
========

  * isEulerian -- determines if a graph or digraph is
    Eulerian

Ways to use hasEulerianTrail :
==============================

  * "hasEulerianTrail(Digraph)"
  * "hasEulerianTrail(Graph)"

For the programmer
==================

The object hasEulerianTrail, is a method function (Macaulay2Doc).

hasOddHole -- checks whether a graph has a odd hole
***************************************************

Synopsis
========

  * Usage:
        oddHole = hasOddHole G
  * Inputs:
      * G, a graph,
  * Outputs:
      * oddHole, a Boolean value (Macaulay2Doc), whether the
        graph has an odd hole

Description
===========

A graph has an odd hole if it has an induced cycle that is odd and has length
of at least 5.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{4,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : hasOddHole G                                            |
|                                                             |
|o2 = false                                                   |
+-------------------------------------------------------------+

See also
========

  * cycleGraph -- Constructs a cycle graph
  * isPerfect -- checks whether a graph is perfect
  * isChordal -- checks whether a graph is chordal

Ways to use hasOddHole :
========================

  * "hasOddHole(Graph)"

For the programmer
==================

The object hasOddHole, is a method function (Macaulay2Doc).

html(Digraph) -- Create an .svg representation of a graph or digraph
********************************************************************

Synopsis
========

  * Function: html (Macaulay2Doc),
  * Usage:
        html G
  * Inputs:
      * G, a digraph,
  * Outputs:
      * a string (Macaulay2Doc),

Description
===========

Uses graphviz to create an .svg representation of G, which is returned as a
string.

+-----------------------------------------------------------------------------+
|i2 : html completeGraph 2                                                    |
|                                                                             |
|o2 = <?xml version="1.0" encoding="UTF-8" standalone="no"?>                  |
|     <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"                          |
|      "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">                    |
|     <!-- Generated by graphviz version 2.43.0 (0)                           |
|     <!-- Title: G Pages: 1 -->                                              |
|     <svg width="62pt" height="116pt"                                        |
|      viewBox="0.00 0.00 62.00 116.00" xmlns="http://www.w3.org/2000/svg" xml|
|     <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4|
|     <title>G</title>                                                        |
|     <polygon fill="white" stroke="transparent" points="-4,4 -4,-112 58,-112 |
|     <!-- 0 -->                                                              |
|     <g id="node1" class="node">                                             |
|     <title>0</title>                                                        |
|     <ellipse fill="none" stroke="black" cx="27" cy="-90" rx="27" ry="18"/>  |
|     <text text-anchor="middle" x="27" y="-86.3" font-family="Times,serif" fo|
|     </g>                                                                    |
|     <!-- 1 -->                                                              |
|     <g id="node2" class="node">                                             |
|     <title>1</title>                                                        |
|     <ellipse fill="none" stroke="black" cx="27" cy="-18" rx="27" ry="18"/>  |
|     <text text-anchor="middle" x="27" y="-14.3" font-family="Times,serif" fo|
|     </g>                                                                    |
|     <!-- 0&#45;&#45;1 -->                                                   |
|     <g id="edge1" class="edge">                                             |
|     <title>0&#45;&#45;1</title>                                             |
|     <path fill="none" stroke="black" d="M27,-71.7C27,-60.85 27,-46.92 27,-36|
|     </g>                                                                    |
|     </g>                                                                    |
|     </svg>                                                                  |
|-----------------------------------------------------------------------------|
|ns:xlink="http://www.w3.org/1999/xlink">                                     |
| 112)">                                                                      |
|                                                                             |
|58,4 -4,4"/>                                                                 |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|nt-size="14.00">0</text>                                                     |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|nt-size="14.00">1</text>                                                     |
|                                                                             |
|                                                                             |
|                                                                             |
|                                                                             |
|.1"/>                                                                        |
+-----------------------------------------------------------------------------+

Ways to use this method:
========================

  * html(Digraph) -- Create an .svg representation of
    a graph or digraph

incidenceMatrix -- computes the incidence matrix of a graph
***********************************************************

Synopsis
========

  * Usage:
        M = incidenceMatrix G
  * Inputs:
      * G, a graph,
  * Outputs:
      * M, a matrix (Macaulay2Doc), the incidence matrix of graph
        G

Description
===========

An incidence matrix M is the #vertexSet of G by #edges of G matrix where entry
(i,j) equals 1 if vertex i is incident to edge j, and equals 0 otherwise.

+-------------------------------------+
|i1 : M = incidenceMatrix cycleGraph 3|
|                                     |
|o1 = | 1 1 0 |                       |
|     | 1 0 1 |                       |
|     | 0 1 1 |                       |
|                                     |
|              3        3             |
|o1 : Matrix ZZ  <--- ZZ              |
+-------------------------------------+

See also
========

  * adjacencyMatrix -- Returns the adjacency matrix of
    a Graph or Digraph

Ways to use incidenceMatrix :
=============================

  * "incidenceMatrix(Graph)"

For the programmer
==================

The object incidenceMatrix, is a method function (Macaulay2Doc).

independenceComplex -- constructs the independence complex of a graph
*********************************************************************

Synopsis
========

  * Usage:
        indG = independenceComplex G
  * Inputs:
      * G, a graph,
  * Outputs:
      * indG, an abstract simplicial complex (SimplicialComplexes),
        the independence complex of G

Description
===========

The independence complex of a graph G is the set of all the independent sets of
G.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{4,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : independenceComplex G                                   |
|                                                             |
|o2 = simplicialComplex | x_2x_5 x_2x_4 x_1x_4 x_1x_3x_5 |    |
|                                                             |
|o2 : SimplicialComplex                                       |
+-------------------------------------------------------------+

See also
========

  * independenceNumber -- computes the independence
    number of a graph
  * cliqueComplex -- Returns the clique complex of a
    graph

Ways to use independenceComplex :
=================================

  * "independenceComplex(Graph)"

For the programmer
==================

The object independenceComplex, is a method function (Macaulay2Doc).

independenceNumber -- computes the independence number of a graph
*****************************************************************

Synopsis
========

  * Usage:
        alpha = independenceNumber G
  * Inputs:
      * G, a graph,
  * Outputs:
      * alpha, an integer (Macaulay2Doc), the independence number of
        G

Description
===========

The independence number of a graph G is the maximum number of vertexSet in any
independent set of G.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{4,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : independenceNumber G                                    |
|                                                             |
|o2 = 3                                                       |
+-------------------------------------------------------------+

See also
========

  * independenceComplex -- constructs the
    independence complex of a graph
  * cliqueNumber -- Returns the clique number of a graph

Ways to use independenceNumber :
================================

  * "independenceNumber(Graph)"

For the programmer
==================

The object independenceNumber, is a method function (Macaulay2Doc).

indexLabelGraph -- Relabels the vertices of a graph or digraph according to their indices, indexed from 0.
**********************************************************************************************************

Synopsis
========

  * Usage:
        G' = indexLabelGraph G
        D' = indexLabelGraph D
  * Inputs:
      * G, a graph,
      * D, a digraph,
  * Outputs:
      * G', a graph,
      * D', a digraph, the graph or digraph with vertices
        relabeled according to their indices starting from 0.

Description
===========

This method relabels the vertices of a graph or digraph according to their
indices.  The method indexes from 0 to the number of vertices minus one.

+-------------------------------------------------------------+
|i1 : G = graph({1,2,3,4,5},{{1,3},{3,4},{4,5}});             |
+-------------------------------------------------------------+
|i2 : indexLabelGraph G                                       |
|                                                             |
|o2 = Graph{0 => {2}   }                                      |
|           1 => {}                                           |
|           2 => {0, 3}                                       |
|           3 => {2, 4}                                       |
|           4 => {3}                                          |
|                                                             |
|o2 : Graph                                                   |
+-------------------------------------------------------------+
|i3 : D = digraph({1,2,3,4,5},{{1,2},{2,3},{3,1},{4,5},{5,4}})|
|                                                             |
|o3 = Digraph{1 => {2}}                                       |
|             2 => {3}                                        |
|             3 => {1}                                        |
|             4 => {5}                                        |
|             5 => {4}                                        |
|                                                             |
|o3 : Digraph                                                 |
+-------------------------------------------------------------+
|i4 : indexLabelGraph D                                       |
|                                                             |
|o4 = Digraph{0 => {1}}                                       |
|             1 => {2}                                        |
|             2 => {0}                                        |
|             3 => {4}                                        |
|             4 => {3}                                        |
|                                                             |
|o4 : Digraph                                                 |
+-------------------------------------------------------------+

See also
========

  * reindexBy -- reindexes the vertices according to the
    input ordering.

Ways to use indexLabelGraph :
=============================

  * "indexLabelGraph(Digraph)"
  * "indexLabelGraph(Graph)"

For the programmer
==================

The object indexLabelGraph, is a method function (Macaulay2Doc).

inducedSubgraph -- A method for finding the induced subgraph of any Graph or Digraph
************************************************************************************

Synopsis
========

  * Usage:
        H = inducedSubgraph(G, L)
        D' = inducedSubgraph(D, L)
  * Inputs:
      * G, a graph,
      * D, a digraph,
      * L, a list (Macaulay2Doc), This list should contain vertices
        of G
  * Outputs:
      * H, a graph,
      * D', a digraph, The subgraph induced by removing the
        vertices in L

Description
===========

This method takes a graph or digraph and a list as the inputs. The List should
be the vertices of the subgraph the user wants to consider, and the output will
contain just those vertices and any edges from G that connect them.  This
method also is a way of iterating deleteVertex several times in a quick way.

+----------------------------------------------------------------------+
|i1 : G = completeGraph 5                                              |
|                                                                      |
|o1 = Graph{0 => {1, 2, 3, 4}}                                         |
|           1 => {0, 2, 3, 4}                                          |
|           2 => {0, 1, 3, 4}                                          |
|           3 => {0, 1, 2, 4}                                          |
|           4 => {0, 1, 2, 3}                                          |
|                                                                      |
|o1 : Graph                                                            |
+----------------------------------------------------------------------+
|i2 : S = {3,4}                                                        |
|                                                                      |
|o2 = {3, 4}                                                           |
|                                                                      |
|o2 : List                                                             |
+----------------------------------------------------------------------+
|i3 : inducedSubgraph(G,S)                                             |
|                                                                      |
|o3 = Graph{3 => {4}}                                                  |
|           4 => {3}                                                   |
|                                                                      |
|o3 : Graph                                                            |
+----------------------------------------------------------------------+
|i4 : D = digraph ({{1,2},{2,3},{3,4},{4,1},{2,4}},EntryMode=>"edges");|
+----------------------------------------------------------------------+
|i5 : D' = inducedSubgraph(D,{1,2,4})                                  |
|                                                                      |
|o5 = Digraph{1 => {2}}                                                |
|             2 => {4}                                                 |
|             4 => {1}                                                 |
|                                                                      |
|o5 : Digraph                                                          |
+----------------------------------------------------------------------+

See also
========

  * deleteVertex -- a method for deleting the vertex of a
    graph

Ways to use inducedSubgraph :
=============================

  * "inducedSubgraph(Digraph,List)"
  * "inducedSubgraph(Graph,List)"

For the programmer
==================

The object inducedSubgraph, is a method function (Macaulay2Doc).

isBipartite -- determines whether a graph is bipartite
******************************************************

Synopsis
========

  * Usage:
        b = isBipartite G
  * Inputs:
      * G, a graph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), whether graph G is
        bipartite

Description
===========

A graph is bipartite if it has a chromatic number less than or equal to 2.

+-------------------------------------------------------------------+
|i1 : G = graph({{0,1},{1,2},{2,4},{3,4},{4,5}},EntryMode=>"edges");|
+-------------------------------------------------------------------+
|i2 : isBipartite G                                                 |
|                                                                   |
|o2 = true                                                          |
+-------------------------------------------------------------------+

See also
========

  * bipartiteColoring -- Returns a coloring of a
    bipartite graph

Ways to use isBipartite :
=========================

  * "isBipartite(Graph)"

For the programmer
==================

The object isBipartite, is a method function (Macaulay2Doc).

isChordal -- checks whether a graph is chordal
**********************************************

Synopsis
========

  * Usage:
        c = isChordal G
  * Inputs:
      * G, a graph,
  * Outputs:
      * c, a Boolean value (Macaulay2Doc), whether the graph is
        chordal

Description
===========

A graph is chordal if its cycles with at least four vertices contain at least
one edge between two vertices which are not adjacent in the cycle.

+----------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{4,1},{2,4}}, EntryMode => "edges");|
+----------------------------------------------------------------------+
|i2 : isChordal G                                                      |
|                                                                      |
|o2 = true                                                             |
+----------------------------------------------------------------------+

See also
========

  * cycleGraph -- Constructs a cycle graph
  * isPerfect -- checks whether a graph is perfect
  * hasOddHole -- checks whether a graph has a odd hole

Ways to use isChordal :
=======================

  * "isChordal(Graph)"

For the programmer
==================

The object isChordal, is a method function (Macaulay2Doc).

isCM -- determines if a graph is Cohen-Macaulay
***********************************************

Synopsis
========

  * Usage:
        c = isCM G
  * Inputs:
      * G, a graph,
  * Outputs:
      * c, a Boolean value (Macaulay2Doc), whether the graph is
        Cohen-Macaulay

Description
===========

This uses the edge ideal notion of Cohen-Macaulayness; a graph is called C-M if
and only if its edge ideal is C-M.

+-------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{1,4},{2,5},{5,3},{3,2}},EntryMode=>"edges");|
+-------------------------------------------------------------------------+
|i2 : isCM G                                                              |
|                                                                         |
|o2 = true                                                                |
+-------------------------------------------------------------------------+

See also
========

  * edgeIdeal -- returns the edge ideal of a graph

Ways to use isCM :
==================

  * "isCM(Graph)"

For the programmer
==================

The object isCM, is a method function (Macaulay2Doc).

isConnected -- determines whether a graph is connected
******************************************************

Synopsis
========

  * Usage:
        C = isConnected G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a Boolean value (Macaulay2Doc), whether a graph is
        connected

Description
===========

A graph is connected when there exists a path of edges between any two vertices
in the graph.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{5,6}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : isConnected G;                                          |
+-------------------------------------------------------------+

See also
========

  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex
  * numberOfComponents -- computes the number of
    connected components of a graph

Ways to use isConnected :
=========================

  * "isConnected(Graph)"

For the programmer
==================

The object isConnected, is a method function (Macaulay2Doc).

isCyclic -- determines whether a graph is cyclic
************************************************

Synopsis
========

  * Usage:
        c = isCyclic G
  * Inputs:
      * G, a graph,
  * Outputs:
      * c, a Boolean value (Macaulay2Doc), whether a graph is
        cyclic

Description
===========

A graph is cyclic if it is composed of vertices connected by a single chain of
edges.

+-------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1}},EntryMode=>"edges");|
+-------------------------------------------------------+
|i2 : isCyclic G                                        |
|                                                       |
|o2 = true                                              |
+-------------------------------------------------------+
|i3 : G = graph({{1,2},{2,3},{3,4}},EntryMode=>"edges");|
+-------------------------------------------------------+
|i4 : isCyclic G                                        |
|                                                       |
|o4 = false                                             |
+-------------------------------------------------------+

See also
========

  * cycleGraph -- Constructs a cycle graph

Ways to use isCyclic :
======================

  * "isCyclic(Graph)"
  * isCyclic(Digraph) -- determines whether a
    digraph is cyclic

For the programmer
==================

The object isCyclic, is a method function (Macaulay2Doc).

isCyclic(Digraph) -- determines whether a digraph is cyclic
***********************************************************

Synopsis
========

  * Function: isCyclic,
  * Usage:
        C = isCyclic D
  * Inputs:
      * D, a digraph,
  * Outputs:
      * C, a Boolean value (Macaulay2Doc), Whether the digraph D
        is cyclic

Description
===========

A digraph is cyclic if it contains a cycle, i.e. for some vertex v of D, by
following the edges of D, one can return to v.

+---------------------------------------------------------------------+
|i1 : D = digraph ({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges")|
|                                                                     |
|o1 = Digraph{0 => {1, 2}}                                            |
|             1 => {}                                                 |
|             2 => {3}                                                |
|             3 => {4}                                                |
|             4 => {2}                                                |
|                                                                     |
|o1 : Digraph                                                         |
+---------------------------------------------------------------------+
|i2 : isCyclic D                                                      |
|                                                                     |
|o2 = true                                                            |
+---------------------------------------------------------------------+

See also
========

  * isCyclic -- determines whether a graph is cyclic

Ways to use this method:
========================

  * isCyclic(Digraph) -- determines whether a
    digraph is cyclic

isEulerian -- determines if a graph or digraph is Eulerian
**********************************************************

Synopsis
========

  * Usage:
        E = isEulerian G
        E = isEulerian D
  * Inputs:
      * G, a graph,
      * D, a digraph,
  * Outputs:
      * E, a Boolean value (Macaulay2Doc), whether G or D is
        Eulerian

Description
===========

A graph is Eulerian if it has a path in the graph that visits each vertex
exactly once.  A digraph is Eulerian if it has a directed path in the graph
that visits each vertex exactly once.  Such a path is called an Eulerian
circuit.  Unconnected graphs can be Eulerian, but all vertices of degree
greater than 0 of a graph (or all vertices of degree greater than 0 in the
underlying graph of a digraph) must belong to a single connected component.

+-----------------------------------------------------------------------------+
|i1 : bridges = graph ({{0,1},{0,2},{0,3},{1,3},{2,3}}, EntryMode => "edges");|
+-----------------------------------------------------------------------------+
|i2 : E = isEulerian bridges                                                  |
|                                                                             |
|o2 = false                                                                   |
+-----------------------------------------------------------------------------+
|i3 : D = digraph(toList(1..4), {{2,3},{3,4},{4,2}});                         |
+-----------------------------------------------------------------------------+
|i4 : E = isEulerian D                                                        |
|                                                                             |
|o4 = true                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * hasEulerianTrail -- determines whether a graph or
    a digraph has an Eulerian trail

Ways to use isEulerian :
========================

  * "isEulerian(Digraph)"
  * "isEulerian(Graph)"

For the programmer
==================

The object isEulerian, is a method function (Macaulay2Doc).

isForest -- determines whether a graph is a forest
**************************************************

Synopsis
========

  * Usage:
        f = isForest G
  * Inputs:
      * G, a graph,
  * Outputs:
      * f, a Boolean value (Macaulay2Doc), whether a graph is a
        forest

Description
===========

A graph is a forest if it is a disjoint collection of trees.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{6,4},{4,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : isForest G                                              |
|                                                             |
|o2 = true                                                    |
+-------------------------------------------------------------+

See also
========

  * isTree -- determines whether a graph is a tree
  * isLeaf -- determines whether a vertex is a leaf
  * leaves -- lists the leaves of a tree graph

Ways to use isForest :
======================

  * "isForest(Graph)"

For the programmer
==================

The object isForest, is a method function (Macaulay2Doc).

isLeaf -- determines whether a vertex is a leaf
***********************************************

Synopsis
========

  * Usage:
        l = isLeaf(G,v)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc),
  * Outputs:
      * l, a Boolean value (Macaulay2Doc), whether vertex v of
        graph G is a leaf

Description
===========

A vertex of a tree graph is a leaf if its degree is 1

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{3,4},{3,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : isLeaf(G,2)                                             |
|                                                             |
|o2 = true                                                    |
+-------------------------------------------------------------+

See also
========

  * isForest -- determines whether a graph is a forest
  * isTree -- determines whether a graph is a tree
  * leaves -- lists the leaves of a tree graph

Ways to use isLeaf :
====================

  * "isLeaf(Graph,Thing)"

For the programmer
==================

The object isLeaf, is a method function (Macaulay2Doc).

isPerfect -- checks whether a graph is perfect
**********************************************

Synopsis
========

  * Usage:
        p = isPerfect G
  * Inputs:
      * G, a graph,
  * Outputs:
      * p, a Boolean value (Macaulay2Doc), whether the graph is
        perfect

Description
===========

A perfect graph is a graph where the chromatic number of every induced subgraph
of G is equal to the clique number in that subgraph.

+-----------------------------------------------------+
|i1 : G = graph {{1,2},{1,3},{1,4},{2,5},{5,3},{3,2}};|
+-----------------------------------------------------+
|i2 : isPerfect G                                     |
|                                                     |
|o2 = true                                            |
+-----------------------------------------------------+

See also
========

  * chromaticNumber -- Computes the chromatic number of
    a graph
  * cliqueNumber -- Returns the clique number of a graph
  * hasOddHole -- checks whether a graph has a odd hole

Ways to use isPerfect :
=======================

  * "isPerfect(Graph)"

For the programmer
==================

The object isPerfect, is a method function (Macaulay2Doc).

isReachable -- checks if a vertex u is reachable from a vertex v
****************************************************************

Synopsis
========

  * Usage:
        r = isReachable(D, u, v)
  * Inputs:
      * D, a digraph,
      * u, a thing (Macaulay2Doc), this is the vertex that we are
        attempting to reach
      * v, a thing (Macaulay2Doc), this is the vertex that we are
        starting from
  * Outputs:
      * r, a Boolean value (Macaulay2Doc), whether or not us is
        reachable from v

Description
===========

In a Digraph D, a vertex u of D is reachable from another vertex v of D if u is
a descendant of v. Alternatively, u is reachable from v if there is some set of
vertices u_0, ... , u_n such that u_n = u and u_0 = v and (u_i, u_i+1) is and
edge of D for all i from 0 to n-1.

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : isReachable(D, e, a)                               |
|                                                        |
|o2 = false                                              |
+--------------------------------------------------------+
|i3 : isReachable(D, d, e)                               |
|                                                        |
|o3 = true                                               |
+--------------------------------------------------------+

See also
========

  * descendants -- returns the descendants of a digraph
  * forefathers -- returns the forefathers of a digraph

Ways to use isReachable :
=========================

  * "isReachable(Digraph,Thing,Thing)"

For the programmer
==================

The object isReachable, is a method function (Macaulay2Doc).

isRegular -- determines whether a graph is regular
**************************************************

Synopsis
========

  * Usage:
        r = isRegular G
  * Inputs:
      * G, a graph,
  * Outputs:
      * r, a Boolean value (Macaulay2Doc), whether the graph G
        is regular or not.

Description
===========

A graph is regular if all of its vertices have the same degree.

+----------------------+
|i1 : G = cycleGraph 5;|
+----------------------+
|i2 : isRegular G      |
|                      |
|o2 = true             |
+----------------------+

See also
========

  * completeGraph -- Constructs a complete graph
  * cycleGraph -- Constructs a cycle graph

Ways to use isRegular :
=======================

  * "isRegular(Graph)"

For the programmer
==================

The object isRegular, is a method function (Macaulay2Doc).

isRigid -- checks if a graph is rigid
*************************************

Synopsis
========

  * Usage:
        r = isRigid G
  * Inputs:
      * G, a graph,
  * Outputs:
      * r, a Boolean value (Macaulay2Doc),

Description
===========

A drawing of a graph is rigid in the plane if any continuous motion of the
vertices that preserve edge lengths must preserve the distance between every
pair of vertices.  A graph is generically rigid if any drawing of the graph
with vertices in general position is rigid. This method uses Laman's Theorem to
determine if a graph is rigid or not.

+--------------------------------------+
|i1 : G = cycleGraph 4;                |
+--------------------------------------+
|i2 : isRigid G                        |
|                                      |
|o2 = false                            |
+--------------------------------------+
|i3 : G' = addEdges' (G, {{1,1},{3,1}})|
|                                      |
|o3 = Graph{0 => {1, 3}      }         |
|           1 => {0, 1, 2, 3}          |
|           2 => {1, 3}                |
|           3 => {0, 1, 2}             |
|                                      |
|o3 : Graph                            |
+--------------------------------------+
|i4 : isRigid G'                       |
|                                      |
|o4 = true                             |
+--------------------------------------+

Ways to use isRigid :
=====================

  * "isRigid(Graph)"

For the programmer
==================

The object isRigid, is a method function (Macaulay2Doc).

isSimple -- checks if a graph is simple
***************************************

Synopsis
========

  * Usage:
        r = isSimple G
  * Inputs:
      * G, a graph,
  * Outputs:
      * r, a Boolean value (Macaulay2Doc),

Description
===========

A graph is said to be simple if it has a maximum of one edge between each
vertex, contains no loops (vertices connected to themselves by edges), and is
undirected. Since the Graph Type does not allow for multiple edges and directed
edges, it is sufficient to check that the graph has no loops.

+---------------------------------+
|i1 : G = cycleGraph 5;           |
+---------------------------------+
|i2 : isSimple G                  |
|                                 |
|o2 = true                        |
+---------------------------------+
|i3 : G' = addEdge (G, set {1,1});|
+---------------------------------+
|i4 : isSimple G'                 |
|                                 |
|o4 = false                       |
+---------------------------------+

Ways to use isSimple :
======================

  * "isSimple(Graph)"

For the programmer
==================

The object isSimple, is a method function (Macaulay2Doc).

isSink -- determines if a vertex of a digraph is a sink or not
**************************************************************

Synopsis
========

  * Usage:
        r = isSink (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), the vertex being texted
  * Outputs:
      * r, a Boolean value (Macaulay2Doc), whether the vertex v
        is a sink or not

Description
===========

A vertex v of a Digraph D is a sink if v has no children

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : isSink (D,b)                                       |
|                                                        |
|o2 = false                                              |
+--------------------------------------------------------+
|i3 : isSink (D,d)                                       |
|                                                        |
|o3 = true                                               |
+--------------------------------------------------------+

See also
========

  * sinks -- returns the sinks of a digraph

Ways to use isSink :
====================

  * "isSink(Digraph,Thing)"

For the programmer
==================

The object isSink, is a method function (Macaulay2Doc).

isSource -- determines if a vertex of a digraph is a source or not
******************************************************************

Synopsis
========

  * Usage:
        r = isSource (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), the vertex being texted
  * Outputs:
      * r, a Boolean value (Macaulay2Doc), whether the vertex v
        is a source or not

Description
===========

A vertex v of a Digraph D is a source if v has no parents

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : isSource (D,c)                                     |
|                                                        |
|o2 = false                                              |
+--------------------------------------------------------+
|i3 : isSource (D,e)                                     |
|                                                        |
|o3 = true                                               |
+--------------------------------------------------------+

See also
========

  * sources -- returns the sources of a digraph

Ways to use isSource :
======================

  * "isSource(Digraph,Thing)"

For the programmer
==================

The object isSource, is a method function (Macaulay2Doc).

isStronglyConnected -- checks if a digraph is strongly connected
****************************************************************

Synopsis
========

  * Usage:
        r = isStronglyConnected D
  * Inputs:
      * D, a digraph,
  * Outputs:
      * r, a Boolean value (Macaulay2Doc),

Description
===========

A digraph is said to be strongly connected if for each vertex u of D, any other
vertex of D is reachable from u. An equivalent definition is that D is strongly
connected if the distance matrix of D has only positive terms in the
non-diagonal entries.

+-------------------------------------------------------------+
|i1 : D = digraph({1,2,3,4},{{1,2},{2,3},{3,4},{4,2}});       |
+-------------------------------------------------------------+
|i2 : isStronglyConnected D                                   |
|                                                             |
|o2 = false                                                   |
+-------------------------------------------------------------+
|i3 : D' = digraph({1,2,3,4},{{1,2},{2,1},{2,3},{3,4},{4,2}});|
+-------------------------------------------------------------+
|i4 : isStronglyConnected D'                                  |
|                                                             |
|o4 = true                                                    |
+-------------------------------------------------------------+

See also
========

  * isWeaklyConnected -- checks if a digraph is
    weakly connected
  * distanceMatrix -- Computes the distance matrix of a
    digraph
  * isReachable -- checks if a vertex u is reachable from a
    vertex v

Ways to use isStronglyConnected :
=================================

  * "isStronglyConnected(Digraph)"

For the programmer
==================

The object isStronglyConnected, is a method function (Macaulay2Doc).

isTree -- determines whether a graph is a tree
**********************************************

Synopsis
========

  * Usage:
        t = isTree G
  * Inputs:
      * G, a graph,
  * Outputs:
      * t, a Boolean value (Macaulay2Doc), whether a graph is a
        tree

Description
===========

A graph is a tree if any two vertices are connected by a unique path of edges.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{3,4},{3,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : isTree G                                                |
|                                                             |
|o2 = true                                                    |
+-------------------------------------------------------------+

See also
========

  * isForest -- determines whether a graph is a forest
  * isLeaf -- determines whether a vertex is a leaf
  * leaves -- lists the leaves of a tree graph

Ways to use isTree :
====================

  * "isTree(Graph)"

For the programmer
==================

The object isTree, is a method function (Macaulay2Doc).

isWeaklyConnected -- checks if a digraph is weakly connected
************************************************************

Synopsis
========

  * Usage:
        r = isWeaklyConnected D
  * Inputs:
      * D, a digraph,
  * Outputs:
      * r, a Boolean value (Macaulay2Doc),

Description
===========

A digraph is said to be weakly connected if the underlying graph of D, that is,
the graph formed by taking away direction from the edges so each edge becomes
"2-way" again, is connected.

+------------------------------------------------------+
|i1 : D = digraph({1,2,3,4},{{1,2},{2,3},{3,4},{4,2}});|
+------------------------------------------------------+
|i2 : isWeaklyConnected D                              |
|                                                      |
|o2 = true                                             |
+------------------------------------------------------+

See also
========

  * weaklyConnectedComponents (missing documentation)
  * isStronglyConnected -- checks if a digraph is
    strongly connected

Ways to use isWeaklyConnected :
===============================

  * "isWeaklyConnected(Digraph)"

For the programmer
==================

The object isWeaklyConnected, is a method function (Macaulay2Doc).

kneserGraph -- constructs a kneser graph of specified size
**********************************************************

Synopsis
========

  * Usage:
        G = kneserGraph(n,k)
  * Inputs:
      * n, an integer (Macaulay2Doc),
      * k, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph, The kneser graph constructed with vertices
        corresponding to the k-element subsets of a set of n elements.

Description
===========

A kneser graph (n,k) has vertices corresponding to the k-element subsets of a
set of n elements, where two vertices are adjacent if and only if their
corresponding k-element subsets are disjoint.

+--------------------------+
|i1 : G = kneserGraph(5,2) |
|                          |
|o1 = Graph{0 => {5, 8, 9}}|
|           1 => {4, 7, 9} |
|           2 => {3, 6, 9} |
|           3 => {2, 7, 8} |
|           4 => {1, 6, 8} |
|           5 => {0, 6, 7} |
|           6 => {2, 4, 5} |
|           7 => {1, 3, 5} |
|           8 => {0, 3, 4} |
|           9 => {0, 1, 2} |
|                          |
|o1 : Graph                |
+--------------------------+

Ways to use kneserGraph :
=========================

  * "kneserGraph(ZZ,ZZ)"

For the programmer
==================

The object kneserGraph, is a method function (Macaulay2Doc).

ladderGraph -- Returns a ladder graph
*************************************

Synopsis
========

  * Usage:
        G = ladderGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc), The length length of the ladder
  * Outputs:
      * G, a graph, The ladder Graph

Description
===========

A ladder graph of length n is two path graphs of size n each joined by a set of
n edges. The first edge connects the top elements, the second the second
elements and the last edge connects the bottom elements, making a 2 by n grid
that looks like a ladder.

+--------------------------+
|i1 : ladderGraph 5        |
|                          |
|o1 = Graph{0 => {1, 5}   }|
|           1 => {0, 2, 6} |
|           2 => {1, 3, 7} |
|           3 => {2, 4, 8} |
|           4 => {3, 9}    |
|           5 => {0, 6}    |
|           6 => {1, 5, 7} |
|           7 => {2, 6, 8} |
|           8 => {3, 7, 9} |
|           9 => {4, 8}    |
|                          |
|o1 : Graph                |
+--------------------------+

See also
========

  * circularLadder -- Returns a circular ladder graph

Ways to use ladderGraph :
=========================

  * "ladderGraph(ZZ)"

For the programmer
==================

The object ladderGraph, is a method function (Macaulay2Doc).

laplacianMatrix -- Returns the laplacian matrix of a graph
**********************************************************

Synopsis
========

  * Usage:
        L = laplacianMatrix G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a matrix (Macaulay2Doc), the laplacian matrix of graph
        G

Description
===========

The laplacian matrix of a graph is the adjacency matrix of the graph subtracted
from the degree matrix of the graph.

+------------------------------------------------------------+
|i1 : G = graph({1,2,3,4,5},{{1,2},{2,3},{3,4},{3,5},{4,5}});|
+------------------------------------------------------------+
|i2 : laplacianMatrix G                                      |
|                                                            |
|o2 = | 1  -1 0  0  0  |                                     |
|     | -1 2  -1 0  0  |                                     |
|     | 0  -1 3  -1 -1 |                                     |
|     | 0  0  -1 2  -1 |                                     |
|     | 0  0  -1 -1 2  |                                     |
|                                                            |
|              5        5                                    |
|o2 : Matrix ZZ  <--- ZZ                                     |
+------------------------------------------------------------+

See also
========

  * adjacencyMatrix -- Returns the adjacency matrix of
    a Graph or Digraph
  * degreeMatrix -- Returns the degree matrix of a graph

Ways to use laplacianMatrix :
=============================

  * "laplacianMatrix(Graph)"

For the programmer
==================

The object laplacianMatrix, is a method function (Macaulay2Doc).

leaves -- lists the leaves of a tree graph
******************************************

Synopsis
========

  * Usage:
        L = leaves G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a list (Macaulay2Doc), list of leaves of a tree graph

Description
===========

A vertex of a tree graph is a leaf if the degree of the vertex is 1

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{3,4},{3,5}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : leaves G;                                               |
+-------------------------------------------------------------+

See also
========

  * isForest -- determines whether a graph is a forest
  * isLeaf -- determines whether a vertex is a leaf
  * isTree -- determines whether a graph is a tree

Ways to use leaves :
====================

  * "leaves(Graph)"

For the programmer
==================

The object leaves, is a method function (Macaulay2Doc).

lexicographicProduct
********************

Ways to use graphComposition :
==============================

  * "graphComposition(Graph,Graph)" -- see graphComposition,
    -- A method for composing two graphs

For the programmer
==================

The object lexicographicProduct (missing documentation) is a method function (Macaulay2Doc).

lineGraph -- Returns the line graph of an undirected graph
**********************************************************

Synopsis
========

  * Usage:
        L = lineGraph G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a graph, The line graph of G

Description
===========

The line graph L of an undirected graph G is the graph whose vertex set is the
edge set of the original graph G and in which two vertices are adjacent if
their corresponding edges share a common endpoint in G.

+--------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,4},{4,1},{1,3},{4,2}},EntryMode=>"edges")  |
|                                                                          |
|o1 = Graph{1 => {2, 3, 4}}                                                |
|           2 => {1, 3, 4}                                                 |
|           3 => {1, 2, 4}                                                 |
|           4 => {1, 2, 3}                                                 |
|                                                                          |
|o1 : Graph                                                                |
+--------------------------------------------------------------------------+
|i2 : lineGraph G                                                          |
|                                                                          |
|o2 = Graph{set {1, 2} => {set {1, 3}, set {1, 4}, set {2, 3}, set {2, 4}}}|
|           set {1, 3} => {set {1, 2}, set {1, 4}, set {2, 3}, set {3, 4}} |
|           set {1, 4} => {set {1, 2}, set {1, 3}, set {2, 4}, set {3, 4}} |
|           set {2, 3} => {set {1, 2}, set {1, 3}, set {2, 4}, set {3, 4}} |
|           set {2, 4} => {set {1, 2}, set {1, 4}, set {2, 3}, set {3, 4}} |
|           set {3, 4} => {set {1, 3}, set {1, 4}, set {2, 3}, set {2, 4}} |
|                                                                          |
|o2 : Graph                                                                |
+--------------------------------------------------------------------------+

Ways to use lineGraph :
=======================

  * "lineGraph(Graph)"

For the programmer
==================

The object lineGraph, is a method function (Macaulay2Doc).

lollipopGraph -- constructs a lollipop graph
********************************************

Synopsis
========

  * Usage:
        G = lollipopGraph (m, n)
  * Inputs:
      * m, an integer (Macaulay2Doc), The number of vertices in the
        complete graph element
      * n, an integer (Macaulay2Doc), The length of stem coming out
        of the complete graph element
  * Outputs:
      * G, a graph, The lollipop graph

Description
===========

A lollipop graph is a graph that is the union of two major elements. The
"candy" portion is a complete graph of size m. Coming out of this is the stick
or stem, just a path graph of size n. The combination of these yields a
lollipop graph.

+-----------------------------------+
|i1 : lollipopGraph (6,2)           |
|                                   |
|o1 = Graph{0 => {1, 2, 3, 4, 5}   }|
|           1 => {0, 2, 3, 4, 5}    |
|           2 => {0, 1, 3, 4, 5}    |
|           3 => {0, 1, 2, 4, 5}    |
|           4 => {0, 1, 2, 3, 5}    |
|           5 => {0, 1, 2, 3, 4, 6} |
|           6 => {5, 7}             |
|           7 => {6}                |
|                                   |
|o1 : Graph                         |
+-----------------------------------+

See also
========

  * rattleGraph -- Returns a rattle graph

Ways to use lollipopGraph :
===========================

  * "lollipopGraph(ZZ,ZZ)"

For the programmer
==================

The object lollipopGraph, is a method function (Macaulay2Doc).

lowestCommonAncestors -- determines the lowest common ancestors between two vertexSet
*************************************************************************************

Synopsis
========

  * Usage:
        A = lowestCommonAncestors(D,u,v)
  * Inputs:
      * D, a digraph,
      * u, a thing (Macaulay2Doc),
      * v, a thing (Macaulay2Doc),
  * Outputs:
      * A, a list (Macaulay2Doc), A list of the lowest common
        ancestors of u and v

Description
===========

The lowest common ancestors between two vertexSet are the vertexSet that are
ancestors of both u and v and are the shortest distance from the vertexSet in
the digraph.

+---------------------------------------------------------------------+
|i1 : D = digraph({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges");|
+---------------------------------------------------------------------+
|i2 : A = lowestCommonAncestors(D,1,3)                                |
|                                                                     |
|o2 = {0}                                                             |
|                                                                     |
|o2 : List                                                            |
+---------------------------------------------------------------------+

See also
========

  * reverseBreadthFirstSearch -- runs a
    reverse breadth first search on the digraph and returns a list of the
    vertexSet in the order they were discovered
  * forefathers -- returns the forefathers of a digraph

Ways to use lowestCommonAncestors :
===================================

  * "lowestCommonAncestors(Digraph,Thing,Thing)"

For the programmer
==================

The object lowestCommonAncestors, is a
method function (Macaulay2Doc).

minimalDegree -- computes the minimal degree of a graph
*******************************************************

Synopsis
========

  * Usage:
        d = minimalDegree G
  * Inputs:
      * G, a graph,
  * Outputs:
      * d, an integer (Macaulay2Doc), the minimal degree of a graph

Description
===========

This computes the minimal vertex degree of an undirected graph.

+------------------------+
|i1 : G = graph({{1,2}});|
+------------------------+
|i2 : minimalDegree G    |
|                        |
|o2 = 1                  |
+------------------------+

See also
========

  * degree (Macaulay2Doc)

Ways to use minimalDegree :
===========================

  * "minimalDegree(Graph)"

For the programmer
==================

The object minimalDegree, is a method function (Macaulay2Doc).

minimalVertexCuts -- finds the minimal vertex cuts of a graph
*************************************************************

Synopsis
========

  * Usage:
        C = minimalVertexCuts G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a list (Macaulay2Doc), the minimal vertex cuts of a
        graph

Description
===========

A vertex cut is a set of vertices that, when removed from a graph, make the
graph have more than one component.  The minimal vertex cuts are the only the
vertex cuts removing only the smallest amount of vertices.  If the graph is
complete, it has no vertex cuts, so the method returns an empty list.

+-------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1},{3,4},{4,5},{5,3}},EntryMode=>"edges");|
+-------------------------------------------------------------------------+
|i2 : minimalVertexCuts G                                                 |
|                                                                         |
|o2 = {{3}}                                                               |
|                                                                         |
|o2 : List                                                                |
+-------------------------------------------------------------------------+

See also
========

  * vertexCuts -- lists all the vertex cuts of a graph
  * vertexConnectivity -- computes the vertex
    connectivity of a graph

Ways to use minimalVertexCuts :
===============================

  * "minimalVertexCuts(Graph)"

For the programmer
==================

The object minimalVertexCuts, is a method function (Macaulay2Doc).

monomialGraph -- Returns a monomial graph
*****************************************

Synopsis
========

  * Usage:
        G = monomialGraph(I,n)
  * Inputs:
      * I, a monomial ideal (Macaulay2Doc), This monomial
        ideal be part of forming a quotient ring with respect to the ambient
        ring the ideal is in
      * n, an integer (Macaulay2Doc), This integer determines the
        degree of monomials that will be considered
  * Outputs:
      * G, a graph, The monomial graph

Description
===========

The monomial graph with respect to a monomial ideal and an integer n is a graph
with a vertex set of the monomials of the expression of the sum of the
generators of the ambient ring for I to the power n.  The edge set is formed by
the rule that there is an edge between two of the vertices (which we are
reminded are monomials) if and only if the degree of the least common multiple
of the two vertices is n+1.

+------------------------------------+
|i1 : R = QQ[x,y];                   |
+------------------------------------+
|i2 : I = monomialIdeal (x^3, y^2*x);|
|                                    |
|o2 : MonomialIdeal of R             |
+------------------------------------+
|i3 : monomialGraph (I, 3)           |
|                                    |
|            2                       |
|o3 = Graph{x y => {}}               |
|            3                       |
|           y  => {}                 |
|                                    |
|o3 : Graph                          |
+------------------------------------+

See also
========

  * lcm (Macaulay2Doc) -- least common multiple

Ways to use monomialGraph :
===========================

  * "monomialGraph(MonomialIdeal,ZZ)"

For the programmer
==================

The object monomialGraph, is a method function (Macaulay2Doc).

neighbors -- returns the neighbors of a vertex in a graph
*********************************************************

Synopsis
========

  * Usage:
        N = neighbors(G,v)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc),
  * Outputs:
      * N, a set (Macaulay2Doc), the neighbors of vertex v in graph
        G

Description
===========

The neighbors of a vertex v are all the vertexSet of G adjacent to v. That is,
if u is a neighbor to v, {v,u} is an edge of G.

+----------------------------------------+
|i1 : G = graph({1,2,3,4},{{2,3},{3,4}});|
+----------------------------------------+
|i2 : neighbors(G,3)                     |
|                                        |
|o2 = set {2, 4}                         |
|                                        |
|o2 : Set                                |
+----------------------------------------+

See also
========

  * nonneighbors -- returns the non-neighbors of a vertex
    in a graph

Ways to use neighbors :
=======================

  * "neighbors(Graph,Thing)"

For the programmer
==================

The object neighbors, is a method function (Macaulay2Doc).

newDigraph -- key used in the output of topSort
***********************************************

Description
===========

This is a key of the hashtable output SortedDigraph,  of
topSort.

+------------------------------------------------------+
|i1 : G = digraph{{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}} |
|                                                      |
|o1 = Digraph{0 => {}    }                             |
|             1 => {}                                  |
|             2 => {3}                                 |
|             3 => {1}                                 |
|             4 => {0, 1}                              |
|             5 => {2, 0}                              |
|                                                      |
|o1 : Digraph                                          |
+------------------------------------------------------+
|i2 : H = topSort G                                    |
|                                                      |
|o2 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 4}           |
|                                    1 => 6            |
|                                    2 => 3            |
|                                    3 => 5            |
|                                    4 => 2            |
|                                    5 => 1            |
|                   newDigraph => Digraph{1 => {3, 4}} |
|                                         2 => {4, 6}  |
|                                         3 => {5}     |
|                                         4 => {}      |
|                                         5 => {6}     |
|                                         6 => {}      |
|                                                      |
|o2 : SortedDigraph                                    |
+------------------------------------------------------+
|i3 : keys H                                           |
|                                                      |
|o3 = {map, digraph, newDigraph}                       |
|                                                      |
|o3 : List                                             |
+------------------------------------------------------+

See also
========

  * topSort -- outputs a hashtable containing original digraph,
    new digraph with vertices topologically sorted and a map from vertices of
    original digraph to new digraph.
  * SortedDigraph -- hashtable used in topSort
  * topologicalSort -- outputs a list of vertices in a
    topologically sorted order of a DAG.

For the programmer
==================

The object newDigraph, is a symbol (Macaulay2Doc).

nondescendants -- returns the nondescendants of a vertex of a digraph
*********************************************************************

Synopsis
========

  * Usage:
        L = nondescendants (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), a vertex of the digraph
  * Outputs:
      * L, a set (Macaulay2Doc), a set of all the nondescendants of
        v

Description
===========

The nondescendants of a directed graph are all the vertexSet u of D such that u
is not reachable from v.

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : nondescendants (D, d)                              |
|                                                        |
|o2 = set {a, b, c, e}                                   |
|                                                        |
|o2 : Set                                                |
+--------------------------------------------------------+

See also
========

  * children -- returns the children of a vertex of a digraph
  * descendants -- returns the descendants of a digraph
  * isReachable -- checks if a vertex u is reachable from a
    vertex v

Ways to use nondescendants :
============================

  * "nondescendants(Digraph,Thing)"

For the programmer
==================

The object nondescendants, is a method function (Macaulay2Doc).

nondescendents
**************

Ways to use nondescendants :
============================

  * "nondescendants(Digraph,Thing)" -- see nondescendants,
    -- returns the nondescendants of a vertex of a digraph

For the programmer
==================

The object nondescendents (missing documentation) is a method function (Macaulay2Doc).

nonneighbors -- returns the non-neighbors of a vertex in a graph
****************************************************************

Synopsis
========

  * Usage:
        N = nonneighbors(G,v)
  * Inputs:
      * G, a graph,
      * v, a thing (Macaulay2Doc),
  * Outputs:
      * N, a set (Macaulay2Doc), the non-neighbors of vertex v in
        graph G

Description
===========

The non-neighbors of a vertex v are all the vertexSet of G that are not
adjacent to v. That is, if u is a non-neighbor to v, {u,v} is not an edge in G.

+----------------------------------------+
|i1 : G = graph({1,2,3,4},{{2,3},{3,4}});|
+----------------------------------------+
|i2 : nonneighbors(G,2)                  |
|                                        |
|o2 = set {1, 4}                         |
|                                        |
|o2 : Set                                |
+----------------------------------------+

See also
========

  * neighbors -- returns the neighbors of a vertex in a graph

Ways to use nonneighbors :
==========================

  * "nonneighbors(Graph,Thing)"

For the programmer
==================

The object nonneighbors, is a method function (Macaulay2Doc).

numberOfComponents -- computes the number of connected components of a graph
****************************************************************************

Synopsis
========

  * Usage:
        n = numberOfComponents G
  * Inputs:
      * G, a graph,
  * Outputs:
      * n, an integer (Macaulay2Doc), the number of connected
        components of G

Description
===========

A connected component is a list of vertexSet of a graph that are connected,
i.e. there exists a path of edges between any two vertexSet in the component.

+-------------------------------------------------------+
|i1 : G = graph(toList(1..8),{{1,2},{2,3},{3,4},{5,6}});|
+-------------------------------------------------------+
|i2 : numberOfComponents G;                             |
+-------------------------------------------------------+

See also
========

  * isConnected -- determines whether a graph is connected
  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex

Ways to use numberOfComponents :
================================

  * "numberOfComponents(Graph)"

For the programmer
==================

The object numberOfComponents, is a method function (Macaulay2Doc).

numberOfTriangles -- counts how many subtriangles are present in a graph
************************************************************************

Synopsis
========

  * Usage:
        t = numberOfTriangles G
  * Inputs:
      * G, a graph,
  * Outputs:
      * t, an integer (Macaulay2Doc), number of subtriangles in a
        graph

Description
===========

A triangle is formed by three vertexSet which are mutually adjacent.

+-------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1},{3,4},{2,4}},EntryMode=>"edges");|
+-------------------------------------------------------------------+
|i2 : numberOfTriangles G                                           |
|                                                                   |
|o2 = 2                                                             |
+-------------------------------------------------------------------+

See also
========

  * hasOddHole -- checks whether a graph has a odd hole
  * isCyclic -- determines whether a graph is cyclic
  * inducedSubgraph -- A method for finding the induced
    subgraph of any Graph or Digraph

Ways to use numberOfTriangles :
===============================

  * "numberOfTriangles(Graph)"

For the programmer
==================

The object numberOfTriangles, is a method function (Macaulay2Doc).

parents -- returns the parents of a vertex on a digraph
*******************************************************

Synopsis
========

  * Usage:
        P = parents (D, v)
  * Inputs:
      * D, a digraph,
      * v, a thing (Macaulay2Doc), the vertex whose parents we
        want to find
  * Outputs:
      * P, a set (Macaulay2Doc), the parents of v

Description
===========

The parents of a vertex v in a digraph D are all the vertexSet u in D such that
{u,v} is an edge of D. In other words, the parents of v are all the vertexSet
that have edges coming out of them that point at v.

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : parents (D, b)                                     |
|                                                        |
|o2 = set {a, e}                                         |
|                                                        |
|o2 : Set                                                |
+--------------------------------------------------------+

See also
========

  * forefathers -- returns the forefathers of a digraph

Ways to use parents :
=====================

  * "parents(Digraph,Thing)"

For the programmer
==================

The object parents, is a method function (Macaulay2Doc).

pathGraph -- A method that makes a path graph
*********************************************

Synopsis
========

  * Usage:
        P = pathGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * P, a graph, the path grah of n vertices

Description
===========

A path graph on n vertices is a cycle graph of n vertices minus one edge.

+-----------------------+
|i1 : pathGraph 5       |
|                       |
|o1 = Graph{0 => {1}   }|
|           1 => {0, 2} |
|           2 => {1, 3} |
|           3 => {2, 4} |
|           4 => {3}    |
|                       |
|o1 : Graph             |
+-----------------------+

See also
========

  * cycleGraph -- Constructs a cycle graph

Ways to use pathGraph :
=======================

  * "pathGraph(ZZ)"

For the programmer
==================

The object pathGraph, is a method function (Macaulay2Doc).

prismGraph
**********

Ways to use circularLadder :
============================

  * "circularLadder(ZZ)" -- see circularLadder, --
    Returns a circular ladder graph

For the programmer
==================

The object prismGraph (missing documentation) is a method function (Macaulay2Doc).

radius -- Returns the radius of a graph
***************************************

Synopsis
========

  * Usage:
        r = radius G
  * Inputs:
      * G, a graph,
  * Outputs:
      * r, an integer (Macaulay2Doc),

Description
===========

The radius of a graph is defined to be the minimum of the eccentricities of the
vertexSet, i.e, the smallest number k such that for some vertex v, the distance
between v and another vertex is less than or equal to k.

+-------------------------------+
|i1 : radius completeGraph 5    |
|                               |
|o1 = 1                         |
+-------------------------------+
|i2 : radius pathGraph 5        |
|                               |
|o2 = 2                         |
+-------------------------------+
|i3 : radius graphLibrary "dart"|
|                               |
|o3 = 1                         |
+-------------------------------+

See also
========

  * eccentricity -- Returns the eccentricity of a vertex
    of a graph
  * barycenter -- Returns the barycenter of a grah
  * distance -- Computes the distance between two vertexSet in
    a graph

Ways to use radius :
====================

  * "radius(Graph)"

For the programmer
==================

The object radius, is a method function (Macaulay2Doc).

rattleGraph -- Returns a rattle graph
*************************************

Synopsis
========

  * Usage:
        G = rattleGraph (n, k)
  * Inputs:
      * n, an integer (Macaulay2Doc), n determines the amount of
        vertices for the bulb or rattle part of the graph
      * k, an integer (Macaulay2Doc), k determines the length of the
        stem coming out of the rattle part of the graph
  * Outputs:
      * G, a graph,

Description
===========

The rattle graph is the union of two graphs. The rattle or bulb part of the
graph is simply an n-cycle. This n cycle is joined to a stem or handle of a
rattle of length k, so the second piece is just a path graph on k vertices.

+--------------------------+
|i1 : rattleGraph (6, 3)   |
|                          |
|o1 = Graph{0 => {1, 5}   }|
|           1 => {0, 2}    |
|           2 => {1, 3}    |
|           3 => {2, 4}    |
|           4 => {3, 5}    |
|           5 => {0, 4, 6} |
|           6 => {5, 7}    |
|           7 => {6, 8}    |
|           8 => {7}       |
|                          |
|o1 : Graph                |
+--------------------------+

See also
========

  * lollipopGraph -- constructs a lollipop graph

Ways to use rattleGraph :
=========================

  * "rattleGraph(ZZ,ZZ)"

For the programmer
==================

The object rattleGraph, is a method function (Macaulay2Doc).

reachable -- Returns the vertices reachable in a digraph from a given collection of vertices
********************************************************************************************

Synopsis
========

  * Usage:
        Rl = reachable(D, L)
        Rs = reachable(D, S)
  * Inputs:
      * D, a digraph,
      * L, a list (Macaulay2Doc), a list of vertices
      * S, a set (Macaulay2Doc), a set of vertices
  * Outputs:
      * Rl, a list (Macaulay2Doc), the list of reachable vertices
      * Rs, a set (Macaulay2Doc), the set of reachable vertices

Description
===========

Given a collection of vertices of a digraph, the reachable vertices are those
that are on a path away from a vertices in the collection.

See also
========

  * descendants -- returns the descendants of a digraph
  * isReachable -- checks if a vertex u is reachable from a
    vertex v

Ways to use reachable :
=======================

  * "reachable(Digraph,List)"
  * "reachable(Digraph,Set)"

For the programmer
==================

The object reachable, is a method function (Macaulay2Doc).

reindexBy -- reindexes the vertices according to the input ordering.
********************************************************************

Synopsis
========

  * Usage:
        G' = reindexBy(G, ordering)
        D' = reindexBy(D, ordering)
  * Inputs:
      * G, a graph,
      * D, a digraph,
      * ordering, a string (Macaulay2Doc),
  * Outputs:
      * G', a graph,
      * D', a digraph, the graph or digraph with vertices
        reindexed according to the String ordering

Description
===========

This method reindexes the vertices of a specified graph or digraph according to
the ordering method entered by the user.  The orderings available for graphs
are:  "maxdegree" (orders the vertices in order of highest to lowest degree),
"mindegree" (orders the vertices in order of lowest to highest degree),
"random" (orders the vertices randomly), "components" (orders the vertices in
the same connected components close together in indices), and "sort" (orders
the vertices by sorting their names).  For digraphs, the orderings available
are:  "maxdegreein" (orders the vertices in order of highest in-degree to
lowest in-degree), "mindegreein" (orders the vertices in order of lowest
in-degree to highest in-degree), "maxdegreeout" (orders the vertices in order
of highest out-degree to lowest out-degree), "mindegreeout" (orders the
vertices in order of lowest out-degree to highest out-degree), "maxdegree"
(orders the vertices in order of highest to lowest degree in the underlying
undirected graph), "mindegree" (orders the vertices in order of lowest to
highest degree in the underlying undirected graph), "random" (orders the
vertices randomly), "sort" (orders the vertices by sorting their names).

+-------------------------------------------------------------+
|i1 : G = graph({1,2,3,4,5},{{1,3},{3,4},{4,5}});             |
+-------------------------------------------------------------+
|i2 : reindexBy(G,"maxdegree")                                |
|                                                             |
|o2 = Graph{1 => {3}   }                                      |
|           2 => {}                                           |
|           3 => {4, 1}                                       |
|           4 => {3, 5}                                       |
|           5 => {4}                                          |
|                                                             |
|o2 : Graph                                                   |
+-------------------------------------------------------------+
|i3 : D = digraph({1,2,3,4,5},{{1,2},{2,3},{3,1},{4,5},{5,4}})|
|                                                             |
|o3 = Digraph{1 => {2}}                                       |
|             2 => {3}                                        |
|             3 => {1}                                        |
|             4 => {5}                                        |
|             5 => {4}                                        |
|                                                             |
|o3 : Digraph                                                 |
+-------------------------------------------------------------+
|i4 : reindexBy(D, "mindegreeout")                            |
|                                                             |
|o4 = Digraph{1 => {2}}                                       |
|             2 => {3}                                        |
|             3 => {1}                                        |
|             4 => {5}                                        |
|             5 => {4}                                        |
|                                                             |
|o4 : Digraph                                                 |
+-------------------------------------------------------------+

See also
========

  * reindexBy -- reindexes the vertices according to the
    input ordering.

Ways to use reindexBy :
=======================

  * "reindexBy(Digraph,String)"
  * "reindexBy(Graph,String)"

For the programmer
==================

The object reindexBy, is a method function (Macaulay2Doc).

removeNodes
***********

Ways to use deleteVertices :
============================

  * "deleteVertices(Digraph,List)" -- see deleteVertices,
    -- Deletes specified vertices from a digraph or graph

For the programmer
==================

The object removeNodes (missing documentation) is a method function (Macaulay2Doc).

reverseBreadthFirstSearch -- runs a reverse breadth first search on the digraph and returns a list of the vertexSet in the order they were discovered
*****************************************************************************************************************************************************

Synopsis
========

  * Usage:
        bfs = reverseBreadthFirstSearch(D,v)
  * Inputs:
      * D, a digraph,
  * Outputs:
      * bfs, a list (Macaulay2Doc), A list of the vertexSet of D in
        order discovered by the breadth first search

Description
===========

A reverse breadth first search first searches the specified of a digraph,
followed by that vertex's parents, followed by their parents, etc, until all
the ancestors are exhausted, and returns a list, with the index of the item of
the list signifying the     depth level of the result, of the vertexSet in
order searched.

+---------------------------------------------------------------------+
|i1 : D = digraph ({{0,1},{0,2},{2,3},{3,4},{4,2}},EntryMode=>"edges")|
|                                                                     |
|o1 = Digraph{0 => {1, 2}}                                            |
|             1 => {}                                                 |
|             2 => {3}                                                |
|             3 => {4}                                                |
|             4 => {2}                                                |
|                                                                     |
|o1 : Digraph                                                         |
+---------------------------------------------------------------------+
|i2 : bfs = reverseBreadthFirstSearch(D,2)                            |
|                                                                     |
|o2 = {{2}, {4, 0}, {3}}                                              |
|                                                                     |
|o2 : List                                                            |
+---------------------------------------------------------------------+

See also
========

  * breadthFirstSearch -- runs a breadth first
    search on the digraph starting at a specified node and returns a list of
    the vertices in the order they were discovered
  * depthFirstSearch -- runs a depth first search on
    the digraph or digraph and returns the discovery time and finishing time
    for each vertex in the digraph
  * topologicalSort -- outputs a list of vertices in a
    topologically sorted order of a DAG.

Ways to use reverseBreadthFirstSearch :
=======================================

  * "reverseBreadthFirstSearch(Digraph,Thing)"

For the programmer
==================

The object reverseBreadthFirstSearch, is a
method function (Macaulay2Doc).

showTikZ -- Writes a string of TikZ syntax that can be pasted into a .tex file to display G
*******************************************************************************************

Synopsis
========

  * Usage:
        S = showTikZ(G)
  * Inputs:
      * G, a digraph,
      * S, a string (Macaulay2Doc), TikZ syntax used to display G
  * Optional inputs (Macaulay2Doc),:
      * Options (missing documentation) => ..., default value "-t math
        --prog=dot -f tikz --figonly", null

Description
===========

Writes a string of TikZ syntax that can be pasted into a .tex file to display G

See also
========

  * displayGraph -- displays a digraph or graph using
    Graphviz

Ways to use showTikZ :
======================

  * "showTikZ(Digraph)"

For the programmer
==================

The object showTikZ, is a method function with options (Macaulay2Doc).

simpleGraph
***********

For the programmer
==================

The object simpleGraph (missing documentation) is a symbol (Macaulay2Doc).

Singletons
**********

Functions with optional argument named Singletons :
===================================================

  * digraph(...,Singletons=>...) (missing documentation)
  * "graph(...,Singletons=>...)" -- see graph, -- Constructs a
    simple graph

For the programmer
==================

The object Singletons (missing documentation) is a symbol (Macaulay2Doc).

sinks -- returns the sinks of a digraph
***************************************

Synopsis
========

  * Usage:
        L = sinks D
  * Inputs:
      * D, a digraph, digraph whose sinks we are searching for
  * Outputs:
      * L, a list (Macaulay2Doc), list of all the sinks (if there
        are any)

Description
===========

A sink of a Digraph D is a vertex of D that has no children. That is, v is a
sink of D if and only if there are only edges pointing into v; none can be
pointing out (there is no edge of the form (v,u)).

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : sinks D                                            |
|                                                        |
|o2 = {c, d}                                             |
|                                                        |
|o2 : List                                               |
+--------------------------------------------------------+

See also
========

  * sources -- returns the sources of a digraph
  * isSink -- determines if a vertex of a digraph is a sink or
    not

Ways to use sinks :
===================

  * "sinks(Digraph)"

For the programmer
==================

The object sinks, is a method function (Macaulay2Doc).

SortedDigraph -- hashtable used in topSort
******************************************

Description
===========

This is a type of hashtable.The output of topSort, has class
SortedDigraph. In the current version of Graphs (version 0.3.3) the only use of
SortedDigraph is in topSort.

+------------------------------------------------------+
|i1 : G = digraph{{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}} |
|                                                      |
|o1 = Digraph{0 => {}    }                             |
|             1 => {}                                  |
|             2 => {3}                                 |
|             3 => {1}                                 |
|             4 => {0, 1}                              |
|             5 => {2, 0}                              |
|                                                      |
|o1 : Digraph                                          |
+------------------------------------------------------+
|i2 : H = topSort G                                    |
|                                                      |
|o2 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 4}           |
|                                    1 => 6            |
|                                    2 => 3            |
|                                    3 => 5            |
|                                    4 => 2            |
|                                    5 => 1            |
|                   newDigraph => Digraph{1 => {3, 4}} |
|                                         2 => {4, 6}  |
|                                         3 => {5}     |
|                                         4 => {}      |
|                                         5 => {6}     |
|                                         6 => {}      |
|                                                      |
|o2 : SortedDigraph                                    |
+------------------------------------------------------+
|i3 : class H                                          |
|                                                      |
|o3 = SortedDigraph                                    |
|                                                      |
|o3 : Type                                             |
+------------------------------------------------------+

See also
========

  * topSort -- outputs a hashtable containing original digraph,
    new digraph with vertices topologically sorted and a map from vertices of
    original digraph to new digraph.
  * newDigraph -- key used in the output of topSort
  * topologicalSort -- outputs a list of vertices in a
    topologically sorted order of a DAG.

Functions and methods returning an object of class SortedDigraph :
==================================================================

  * "topSort(Digraph)" -- see topSort, -- outputs a hashtable
    containing original digraph, new digraph with vertices topologically sorted
    and a map from vertices of original digraph to new digraph.
  * "topSort(Digraph,String)" -- see topSort, -- outputs a
    hashtable containing original digraph, new digraph with vertices
    topologically sorted and a map from vertices of original digraph to new
    digraph.

For the programmer
==================

The object SortedDigraph, is a type (Macaulay2Doc),
with ancestor classes HashTable (Macaulay2Doc),
< Thing (Macaulay2Doc).

sources -- returns the sources of a digraph
*******************************************

Synopsis
========

  * Usage:
        L = sources D
  * Inputs:
      * D, a digraph, digraph whose sources we are searching
        for
  * Outputs:
      * L, a list (Macaulay2Doc), list of all the sources (if there
        are any)

Description
===========

A source of a Digraph D is a vertex of D that has no parents. That is, v is a
source of D if and only if there are only edges pointing from v; none can be
pointing into v (there is no edge of the form (v,u)).

+--------------------------------------------------------+
|i1 : D = digraph({a,b,c,d,e},{{a,b},{b,c},{b,d},{e,b}});|
+--------------------------------------------------------+
|i2 : sources D                                          |
|                                                        |
|o2 = {a, e}                                             |
|                                                        |
|o2 : List                                               |
+--------------------------------------------------------+

See also
========

  * sinks -- returns the sinks of a digraph
  * isSource -- determines if a vertex of a digraph is a
    source or not

Ways to use sources :
=====================

  * "sources(Digraph)"

For the programmer
==================

The object sources, is a method function (Macaulay2Doc).

spanningForest -- constructs a spanning forest of a graph
*********************************************************

Synopsis
========

  * Usage:
        F = spanningForest G
  * Inputs:
      * G, a graph,
  * Outputs:
      * F, a graph, a forest spanning G

Description
===========

A graph is a forest if it is a disjoint collection of trees.  A graph is a tree
if any two vertices are connected by a unique path of edges.  A spanning forest
is a forest that spans all the vectors of G using edges of G.

+-----------------------+
|i1 : G = cycleGraph 5; |
+-----------------------+
|i2 : spanningForest G  |
|                       |
|o2 = Graph{0 => {1, 4}}|
|           1 => {0, 2} |
|           2 => {1, 3} |
|           3 => {2}    |
|           4 => {0}    |
|                       |
|o2 : Graph             |
+-----------------------+

See also
========

  * isForest -- determines whether a graph is a forest
  * isTree -- determines whether a graph is a tree

Ways to use spanningForest :
============================

  * "spanningForest(Graph)"

For the programmer
==================

The object spanningForest, is a method function (Macaulay2Doc).

spectrum -- Returns the spectrum of a graph
*******************************************

Synopsis
========

  * Usage:
        L = spectrum G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a list (Macaulay2Doc),

Description
===========

The spectrum of a graph G is the set of the eigenvalues of the adjacency matrix
A corresponding to G. For simple graphs, these eigenvalues are all real since A
must be symmetric. The user should be aware that Macaulay 2 does not give exact
values for these eigenvalues, they are numerical approximations, but it is
still a good tool to use to check if two graphs are isomorphic; isomorphic
graphs share the same spectrum although the converse is not necessarily true.

+---------------------------------------+
|i1 : spectrum completeGraph 6          |
|                                       |
|o1 = {-1, -1, -1, -1, -1, 5}           |
|                                       |
|o1 : List                              |
+---------------------------------------+
|i2 : spectrum graphLibrary "petersen"  |
|                                       |
|o2 = {-2, -2, -2, -2, 1, 1, 1, 1, 1, 3}|
|                                       |
|o2 : List                              |
+---------------------------------------+

Ways to use spectrum :
======================

  * "spectrum(Graph)"

For the programmer
==================

The object spectrum, is a method function (Macaulay2Doc).

starGraph -- Returns a star graph
*********************************

Synopsis
========

  * Usage:
        G = starGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph,

Description
===========

The star graph is a special class of the general windmill graph class, in
particular, it is windmill(2,n). A star graph is best visualized having one
vertex in the center of a circle of other vertices.  The edge set is formed by
connecting this center vertex to each of the outside vertices. The outside
vertices are only connected to the center vertex.

+--------------------------------+
|i1 : starGraph 5                |
|                                |
|o1 = Graph{0 => {1, 2, 3, 4, 5}}|
|           1 => {0}             |
|           2 => {0}             |
|           3 => {0}             |
|           4 => {0}             |
|           5 => {0}             |
|                                |
|o1 : Graph                      |
+--------------------------------+

See also
========

  * windmillGraph -- Constructs a windmill graph

Ways to use starGraph :
=======================

  * "starGraph(ZZ)"

For the programmer
==================

The object starGraph, is a method function (Macaulay2Doc).

strongProduct -- a method for taking the strong product of two graphs
*********************************************************************

Synopsis
========

  * Usage:
        F = strongProduct(G,H)
  * Inputs:
      * G, a graph,
      * H, a graph,
  * Outputs:
      * F, a graph, The Strong Product of G and H

Description
===========

This method will take in any two graphs and output the strong proudct of the
two graphs. The vertex set of the strong product of G and H is the cartesian
product of the vertex sets of G and H. The keys for each vertex will be output
as a sequence to represent this clearly. The edge set of the strong product of
G and H is formed by the rule any two distinct vertices (u,u') and (v,v') are
adjacent in G and H if and only if u' is adjacent with v' or u'=v' , and u is
adjacent with v or u = v.

+--------------------------------------------------------------+
|i1 : G = graph({1,2},{{1,2}});                                |
+--------------------------------------------------------------+
|i2 : H = graph({3,4,5},{{3,4},{4,5}});                        |
+--------------------------------------------------------------+
|i3 : strongProduct(G,H)                                       |
|                                                              |
|o3 = Graph{{1, 3} => {{2, 3}, {1, 4}, {2, 4}}                }|
|           {1, 4} => {{2, 5}, {1, 3}, {2, 3}, {2, 4}, {1, 5}} |
|           {1, 5} => {{2, 5}, {1, 4}, {2, 4}}                 |
|           {2, 3} => {{1, 3}, {1, 4}, {2, 4}}                 |
|           {2, 4} => {{2, 5}, {1, 3}, {2, 3}, {1, 4}, {1, 5}} |
|           {2, 5} => {{1, 4}, {2, 4}, {1, 5}}                 |
|                                                              |
|o3 : Graph                                                    |
+--------------------------------------------------------------+

See also
========

  * graphComposition -- A method for composing two
    graphs
  * directProduct (Polyhedra) -- computes the direct
    product of two convex objects
  * cartesianProduct -- Computes the cartesian product
    of two graphs

Ways to use strongProduct :
===========================

  * "strongProduct(Graph,Graph)"

For the programmer
==================

The object strongProduct, is a method function (Macaulay2Doc).

thresholdGraph -- A method that generates a threshold graph from a binary list
******************************************************************************

Synopsis
========

  * Usage:
        G = thresholdGraph L
  * Inputs:
      * L, a list (Macaulay2Doc), This list is of 0's and 1's only
  * Outputs:
      * G, a graph,

Description
===========

A threshold graph is a graph that is constructed by starting with an isolated
vertex and iteratively adding another isolated vertex or a vertex that shares
an edge with each vertex generated before it (the dominating vertices). The
isolated vertices are represented by 0's and the dominating vertices are
rerpresented by 1's. In this method, the initial vertex is implicit and by
default is constructed, so the first entry need not always be 0 in the list.

+-----------------------------------+
|i1 : L = {1,0,0,1,0,1}             |
|                                   |
|o1 = {1, 0, 0, 1, 0, 1}            |
|                                   |
|o1 : List                          |
+-----------------------------------+
|i2 : thresholdGraph L              |
|                                   |
|o2 = Graph{0 => {1, 4, 6}         }|
|           1 => {0, 4, 6}          |
|           2 => {4, 6}             |
|           3 => {4, 6}             |
|           4 => {0, 1, 2, 3, 6}    |
|           5 => {6}                |
|           6 => {0, 1, 2, 3, 4, 5} |
|                                   |
|o2 : Graph                         |
+-----------------------------------+

Ways to use thresholdGraph :
============================

  * "thresholdGraph(List)"

For the programmer
==================

The object thresholdGraph, is a method function (Macaulay2Doc).

topologicalSort -- outputs a list of vertices in a topologically sorted order of a DAG.
***************************************************************************************

Synopsis
========

  * Usage:
        topologicalSort(D,S)
        topologicalSort(D)
  * Inputs:
      * D, a digraph,
      * S, a string (Macaulay2Doc),
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

This function outputs a list of vertices in a topologically sorted order of a
directed acyclic graph (DAG). S provides the preference given to the vertices
in order to break ties and provide unique topological sorting to the DAG.

Permissible values of S are: "random", "max", "min", "degree".

S = "random" randomly sort the vertices of graph which have same precedence at
any instance of the algorithm to break the ties.

S = "min" sort the vertices according to their indices (from low to high) to
break the ties.

S = "max" sort the vertices according to their indices (from high to low) to
break the ties.

S = "degree" sort the vertices according to their degree (from low to high) to
break the ties.

+-----------------------------------------------------+
|i1 : G = digraph{{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}}|
|                                                     |
|o1 = Digraph{0 => {}    }                            |
|             1 => {}                                 |
|             2 => {3}                                |
|             3 => {1}                                |
|             4 => {0, 1}                             |
|             5 => {2, 0}                             |
|                                                     |
|o1 : Digraph                                         |
+-----------------------------------------------------+
|i2 : topologicalSort G                               |
|                                                     |
|o2 = {5, 4, 2, 0, 3, 1}                              |
|                                                     |
|o2 : List                                            |
+-----------------------------------------------------+
|i3 : topologicalSort(G,"min")                        |
|                                                     |
|o3 = {4, 5, 0, 2, 3, 1}                              |
|                                                     |
|o3 : List                                            |
+-----------------------------------------------------+
|i4 : topologicalSort(G,"max")                        |
|                                                     |
|o4 = {5, 4, 2, 3, 1, 0}                              |
|                                                     |
|o4 : List                                            |
+-----------------------------------------------------+
|i5 : topologicalSort(G,"random")                     |
|                                                     |
|o5 = {5, 2, 4, 3, 0, 1}                              |
|                                                     |
|o5 : List                                            |
+-----------------------------------------------------+
|i6 : topologicalSort(G,"degree")                     |
|                                                     |
|o6 = {4, 5, 0, 2, 3, 1}                              |
|                                                     |
|o6 : List                                            |
+-----------------------------------------------------+

See also
========

  * topSort -- outputs a hashtable containing original digraph,
    new digraph with vertices topologically sorted and a map from vertices of
    original digraph to new digraph.

Ways to use topologicalSort :
=============================

  * "topologicalSort(Digraph)"
  * "topologicalSort(Digraph,String)"

For the programmer
==================

The object topologicalSort, is a method function (Macaulay2Doc).

topSort -- outputs a hashtable containing original digraph, new digraph with vertices topologically sorted and a map from vertices of original digraph to new digraph.
**********************************************************************************************************************************************************************

Synopsis
========

  * Usage:
        topSort(D)
        topSort(D,S)
  * Inputs:
      * D, a digraph,
      * S, a string (Macaulay2Doc),
  * Outputs:
      * a hash table (Macaulay2Doc),

Description
===========

This method outputs a HashTable with keys digraph, map and newDigraph, where
digraph is the original digraph, map is the relation between old ordering and
the new ordering of vertices and newDigraph is the Digraph with topologically
sorted vertices. This method needs the input to be directed adyclic graph
(DAG). S provides the preference given to the vertices in order to break ties
and provide unique topological sorting to the DAG.

Permissible values of S are: "random", "max", "min", "degree".

S = "random" randomly sort the vertices of graph which have same precedence at
any instance of the algorithm to break the ties.

S = "min" sort the vertices according to their indices (from low to high) to
break the ties.

S = "max" sort the vertices according to their indices (from high to low) to
break the ties.

S = "degree" sort the vertices according to their degree (from low to high) to
break the ties.

+------------------------------------------------------+
|i1 : G = digraph{{5,2},{5,0},{4,0},{4,1},{2,3},{3,1}} |
|                                                      |
|o1 = Digraph{0 => {}    }                             |
|             1 => {}                                  |
|             2 => {3}                                 |
|             3 => {1}                                 |
|             4 => {0, 1}                              |
|             5 => {2, 0}                              |
|                                                      |
|o1 : Digraph                                          |
+------------------------------------------------------+
|i2 : H = topSort G                                    |
|                                                      |
|o2 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 4}           |
|                                    1 => 6            |
|                                    2 => 3            |
|                                    3 => 5            |
|                                    4 => 2            |
|                                    5 => 1            |
|                   newDigraph => Digraph{1 => {3, 4}} |
|                                         2 => {4, 6}  |
|                                         3 => {5}     |
|                                         4 => {}      |
|                                         5 => {6}     |
|                                         6 => {}      |
|                                                      |
|o2 : SortedDigraph                                    |
+------------------------------------------------------+
|i3 : H#digraph                                        |
|                                                      |
|o3 = Digraph{0 => {}    }                             |
|             1 => {}                                  |
|             2 => {3}                                 |
|             3 => {1}                                 |
|             4 => {0, 1}                              |
|             5 => {2, 0}                              |
|                                                      |
|o3 : Digraph                                          |
+------------------------------------------------------+
|i4 : H#map                                            |
|                                                      |
|o4 = HashTable{0 => 4}                                |
|               1 => 6                                 |
|               2 => 3                                 |
|               3 => 5                                 |
|               4 => 2                                 |
|               5 => 1                                 |
|                                                      |
|o4 : HashTable                                        |
+------------------------------------------------------+
|i5 : topSort(G,"min")                                 |
|                                                      |
|o5 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 3}           |
|                                    1 => 6            |
|                                    2 => 4            |
|                                    3 => 5            |
|                                    4 => 1            |
|                                    5 => 2            |
|                   newDigraph => Digraph{1 => {3, 6}} |
|                                         2 => {3, 4}  |
|                                         3 => {}      |
|                                         4 => {5}     |
|                                         5 => {6}     |
|                                         6 => {}      |
|                                                      |
|o5 : SortedDigraph                                    |
+------------------------------------------------------+
|i6 : topSort(G,"max")                                 |
|                                                      |
|o6 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 6}           |
|                                    1 => 5            |
|                                    2 => 3            |
|                                    3 => 4            |
|                                    4 => 2            |
|                                    5 => 1            |
|                   newDigraph => Digraph{1 => {3, 6}} |
|                                         2 => {5, 6}  |
|                                         3 => {4}     |
|                                         4 => {5}     |
|                                         5 => {}      |
|                                         6 => {}      |
|                                                      |
|o6 : SortedDigraph                                    |
+------------------------------------------------------+
|i7 : topSort(G,"random")                              |
|                                                      |
|o7 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 5}           |
|                                    1 => 6            |
|                                    2 => 2            |
|                                    3 => 4            |
|                                    4 => 3            |
|                                    5 => 1            |
|                   newDigraph => Digraph{1 => {2, 5}} |
|                                         2 => {4}     |
|                                         3 => {5, 6}  |
|                                         4 => {6}     |
|                                         5 => {}      |
|                                         6 => {}      |
|                                                      |
|o7 : SortedDigraph                                    |
+------------------------------------------------------+
|i8 : topSort(G,"degree")                              |
|                                                      |
|o8 = SortedDigraph{digraph => Digraph{0 => {}    }   }|
|                                      1 => {}         |
|                                      2 => {3}        |
|                                      3 => {1}        |
|                                      4 => {0, 1}     |
|                                      5 => {2, 0}     |
|                   map => HashTable{0 => 3}           |
|                                    1 => 6            |
|                                    2 => 4            |
|                                    3 => 5            |
|                                    4 => 1            |
|                                    5 => 2            |
|                   newDigraph => Digraph{1 => {3, 6}} |
|                                         2 => {3, 4}  |
|                                         3 => {}      |
|                                         4 => {5}     |
|                                         5 => {6}     |
|                                         6 => {}      |
|                                                      |
|o8 : SortedDigraph                                    |
+------------------------------------------------------+

See also
========

  * topologicalSort -- outputs a list of vertices in a
    topologically sorted order of a DAG.
  * SortedDigraph -- hashtable used in topSort
  * newDigraph -- key used in the output of topSort

Ways to use topSort :
=====================

  * "topSort(Digraph)"
  * "topSort(Digraph,String)"

For the programmer
==================

The object topSort, is a method function (Macaulay2Doc).

underlyingGraph -- Returns the underlying graph of a digraph
************************************************************

Synopsis
========

  * Usage:
        G = underlyingGraph D
  * Inputs:
      * D, a digraph,
  * Outputs:
      * G, a graph, The underlying graph of digraph D

Description
===========

The underlying graph of a digraph is the simple graph constructed by all edges
{u,v} such that (u,v) or (v,u) is a directed edge in the digraph.

+------------------------------------------------------------+
|i1 : D = digraph hashTable{1 => {2,3}, 2 => {1,3}, 3 => {}};|
+------------------------------------------------------------+
|i2 : underlyingGraph D                                      |
|                                                            |
|o2 = Graph{1 => {2, 3}}                                     |
|           2 => {1, 3}                                      |
|           3 => {1, 2}                                      |
|                                                            |
|o2 : Graph                                                  |
+------------------------------------------------------------+

Ways to use underlyingGraph :
=============================

  * "underlyingGraph(Digraph)"

For the programmer
==================

The object underlyingGraph, is a method function (Macaulay2Doc).

vertexConnectivity -- computes the vertex connectivity of a graph
*****************************************************************

Synopsis
========

  * Usage:
        C = vertexConnectivity G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, an integer (Macaulay2Doc), the vertex connectivity of a
        graph

Description
===========

The vertex connectivity of a graph is the smallest amount of vertices that need
be removed from a graph to make it not connected or have one vertex.  This
corresponds to the size of the smallest vertex cut.  A not connected graph has
connectivity equal to 0.

+-------------------------------------------------------------------------+
|i1 : G = graph({{1,2},{2,3},{3,1},{3,4},{4,5},{5,3}},EntryMode=>"edges");|
+-------------------------------------------------------------------------+
|i2 : vertexConnectivity G                                                |
|                                                                         |
|o2 = 1                                                                   |
+-------------------------------------------------------------------------+

See also
========

  * minimalVertexCuts -- finds the minimal vertex
    cuts of a graph
  * vertexCuts -- lists all the vertex cuts of a graph
  * edgeConnectivity -- computes the edge connectivity
    of a graph

Ways to use vertexConnectivity :
================================

  * "vertexConnectivity(Graph)"

For the programmer
==================

The object vertexConnectivity, is a method function (Macaulay2Doc).

vertexCoverNumber -- returns the vertex cover number of a graph
***************************************************************

Synopsis
========

  * Usage:
        v = vertexCoverNumber G
  * Inputs:
      * G, a graph,
  * Outputs:
      * v, an integer (Macaulay2Doc), the vertex cover number of
        graph G

Description
===========

The vertex cover number is the minimum length of the set of vertex covers of a
graph.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{1,4},{2,3}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : vertexCoverNumber G                                     |
|                                                             |
|o2 = 2                                                       |
+-------------------------------------------------------------+

See also
========

  * vertexCovers -- returns a list of the minimal vertex
    covers of a graph
  * coverIdeal -- Returns the vertex cover ideal of a graph

Ways to use vertexCoverNumber :
===============================

  * "vertexCoverNumber(Graph)"

For the programmer
==================

The object vertexCoverNumber, is a method function (Macaulay2Doc).

vertexCovers -- returns a list of the minimal vertex covers of a graph
**********************************************************************

Synopsis
========

  * Usage:
        V = vertexCovers G
  * Inputs:
      * G, a graph,
  * Outputs:
      * V, a list (Macaulay2Doc), the list of minimal vertex covers
        of graph G

Description
===========

A vertex cover of G is a set of vertexSet which intersects with every edge of
G. In other words, L is a vertex cover of a graph if and only if their does not
exist an edge {u,v} such that both u and v are not in L.

+-------------------------------------------------------------+
|i1 : G = graph({{1,2},{1,3},{1,4},{2,3}},EntryMode=>"edges");|
+-------------------------------------------------------------+
|i2 : vertexCovers G                                          |
|                                                             |
|o2 = {{1, 2}, {1, 3}, {2, 3, 4}}                             |
|                                                             |
|o2 : List                                                    |
+-------------------------------------------------------------+

See also
========

  * vertexCoverNumber -- returns the vertex cover
    number of a graph
  * coverIdeal -- Returns the vertex cover ideal of a graph

Ways to use vertexCovers :
==========================

  * "vertexCovers(Graph)"

For the programmer
==================

The object vertexCovers, is a method function (Macaulay2Doc).

vertexCuts -- lists all the vertex cuts of a graph
**************************************************

Synopsis
========

  * Usage:
        C = vertexCuts G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a list (Macaulay2Doc), the list of vertex cuts of a
        graph

Description
===========

A vertex cut is a set of vertices that, when removed from a graph, make the
graph have more than one component.  The complete graph has no vertex cuts, so
the method returns an empty list.

+-----------------------------------------------------------------------------+
|i1 : G = cycleGraph 5;                                                       |
+-----------------------------------------------------------------------------+
|i2 : vertexCuts G                                                            |
|                                                                             |
|o2 = {{0, 2}, {0, 3}, {1, 3}, {0, 1, 3}, {0, 2, 3}, {1, 4}, {2, 4}, {0, 2,   |
|     ------------------------------------------------------------------------|
|     4}, {1, 2, 4}, {1, 3, 4}}                                               |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * minimalVertexCuts -- finds the minimal vertex
    cuts of a graph
  * vertexConnectivity -- computes the vertex
    connectivity of a graph
  * edgeCuts -- returns the edge cuts of a graph

Ways to use vertexCuts :
========================

  * "vertexCuts(Graph)"

For the programmer
==================

The object vertexCuts, is a method function (Macaulay2Doc).

vertexMultiplication
********************

Synopsis
========

  * Usage:
        H = vertexMultiplication (G, v, u)
  * Inputs:
      * G, a graph,
      * u, a thing (Macaulay2Doc), u is the new vertex to be added
      * v, a thing (Macaulay2Doc), v is the vertex whose neighbors
        become the vertices that u connects to.
  * Outputs:
      * H, a graph,

Description
===========

Multiplying the vertex of a graph adds one vertex to the original graph. It
also adds several edges, namely, if we are multiplying a vertex v and calling
the new vertex u, {u,W} is an edge if and only if {v,w} is an edge.

+--------------------------------------+
|i1 : G = completeGraph 5              |
|                                      |
|o1 = Graph{0 => {1, 2, 3, 4}}         |
|           1 => {0, 2, 3, 4}          |
|           2 => {0, 1, 3, 4}          |
|           3 => {0, 1, 2, 4}          |
|           4 => {0, 1, 2, 3}          |
|                                      |
|o1 : Graph                            |
+--------------------------------------+
|i2 : H = vertexMultiplication(G, 0, 6)|
|                                      |
|o2 = Graph{0 => {1, 2, 3, 4}   }      |
|           1 => {0, 2, 3, 4, 6}       |
|           2 => {0, 1, 3, 4, 6}       |
|           3 => {0, 1, 2, 4, 6}       |
|           4 => {0, 1, 2, 3, 6}       |
|           6 => {1, 2, 3, 4}          |
|                                      |
|o2 : Graph                            |
+--------------------------------------+

Ways to use vertexMultiplication :
==================================

  * "vertexMultiplication(Graph,Thing,Thing)"

For the programmer
==================

The object vertexMultiplication, is a method function (Macaulay2Doc).

vertexSet -- Returns the vertices of a graph or digraph
*******************************************************

Synopsis
========

  * Usage:
        V = vertexSet D
        V = vertexSet G
  * Inputs:
      * D, a digraph,
      * G, a digraph,
  * Outputs:
      * V, a list (Macaulay2Doc), The vertices of digraph D

Description
===========

The vertices of a graph are just singletons that can be indexed by numbers,
letters, or even in some cases something as exotic as a monomial. These form
the base of a graph; the edges are 2 member subsets of the vertex set of a
graph.

+---------------------------------------------------------+
|i1 : D = digraph({{1,2},{2,1},{3,1}},EntryMode=>"edges");|
+---------------------------------------------------------+
|i2 : vertexSet D;                                        |
+---------------------------------------------------------+
|i3 : G = completeGraph 4;                                |
+---------------------------------------------------------+
|i4 : vertexSet G                                         |
|                                                         |
|o4 = {0, 1, 2, 3}                                        |
|                                                         |
|o4 : List                                                |
+---------------------------------------------------------+
|i5 : A = adjacencyMatrix G;                              |
|                                                         |
|              4        4                                 |
|o5 : Matrix ZZ  <--- ZZ                                  |
+---------------------------------------------------------+
|i6 : graph({a,b,c,d}, A)                                 |
|                                                         |
|o6 = Graph{a => {b, c, d}}                               |
|           b => {a, c, d}                                |
|           c => {a, b, d}                                |
|           d => {a, b, c}                                |
|                                                         |
|o6 : Graph                                               |
+---------------------------------------------------------+

See also
========

  * edges -- Returns the edges of a digraph or graph

Ways to use vertexSet :
=======================

  * "vertexSet(Digraph)"

For the programmer
==================

The object vertexSet, is a method function (Macaulay2Doc).

wheelGraph -- Constructs a wheel graph
**************************************

Synopsis
========

  * Usage:
        G = wheelGraph n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph, The wheel graph with n vertices

Description
===========

A wheel graph is a cycle graph on n-1 vertices with an extra single vertex
adjacent to every vertex in the cycle.

+--------------------------------+
|i1 : G = wheelGraph 6           |
|                                |
|o1 = Graph{0 => {1, 2, 3, 4, 5}}|
|           1 => {0, 2, 5}       |
|           2 => {0, 1, 3}       |
|           3 => {0, 2, 4}       |
|           4 => {0, 3, 5}       |
|           5 => {0, 1, 4}       |
|                                |
|o1 : Graph                      |
+--------------------------------+

See also
========

  * cycleGraph -- Constructs a cycle graph
  * windmillGraph -- Constructs a windmill graph

Ways to use wheelGraph :
========================

  * "wheelGraph(ZZ)"

For the programmer
==================

The object wheelGraph, is a method function (Macaulay2Doc).

windmillGraph -- Constructs a windmill graph
********************************************

Synopsis
========

  * Usage:
        G = windmillGraph(k,d)
  * Inputs:
      * k, an integer (Macaulay2Doc),
      * d, an integer (Macaulay2Doc),
  * Outputs:
      * G, a graph, The windmill graph constructed by joining d
        copies of the complete graph K_k at a shared vertex.

Description
===========

A whidmill joins d amount of copies of a complete graph on k vertices at
exactly one shared vertex.

+--------------------------------------------------------------------+
|i1 : G = windmillGraph(4,5)                                         |
|                                                                    |
|o1 = Graph{0 => {1, 4, 7, 10, 13, 2, 5, 8, 11, 14, 3, 6, 9, 12, 15}}|
|           1 => {0, 2, 3}                                           |
|           2 => {0, 1, 3}                                           |
|           3 => {0, 1, 2}                                           |
|           4 => {0, 5, 6}                                           |
|           5 => {0, 4, 6}                                           |
|           6 => {0, 4, 5}                                           |
|           7 => {0, 8, 9}                                           |
|           8 => {0, 7, 9}                                           |
|           9 => {0, 7, 8}                                           |
|           10 => {0, 11, 12}                                        |
|           11 => {0, 10, 12}                                        |
|           12 => {0, 10, 11}                                        |
|           13 => {0, 14, 15}                                        |
|           14 => {0, 13, 15}                                        |
|           15 => {0, 13, 14}                                        |
|                                                                    |
|o1 : Graph                                                          |
+--------------------------------------------------------------------+

See also
========

  * completeGraph -- Constructs a complete graph
  * wheelGraph -- Constructs a wheel graph
  * starGraph -- Returns a star graph
  * friendshipGraph -- Returns a friendship Graph

Ways to use windmillGraph :
===========================

  * "windmillGraph(ZZ,ZZ)"

For the programmer
==================

The object windmillGraph, is a method function (Macaulay2Doc).

writeDotFile -- Writes a graph to a dot file with a specified filename
**********************************************************************

Synopsis
========

  * Usage:
        writeDotFile(fileName,G)
  * Inputs:
      * G, a graph,
      * fileName, a string (Macaulay2Doc),

Description
===========

Writes the code for an inputted graph to be constructed in Graphviz with
specified file name.

Ways to use writeDotFile :
==========================

  * "writeDotFile(String,Digraph)"
  * "writeDotFile(String,Graph)"

For the programmer
==================

The object writeDotFile, is a method function (Macaulay2Doc).