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
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
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
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
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
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