next | previous | forward | backward | up | top | index | toc | packages | Macaulay2 website
Graphs :: Graphs

Graphs

Authors

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.

Exports

  • Types
  • 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.