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.
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
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
strongProduct -- a method for taking the strong product of two graphs
tensorProduct (missing documentation)
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
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
"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)" -- see connectedComponents -- 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
"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
"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
"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 digrah
"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
"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