Macaulay2 » Documentation
Packages » Graphs :: Graphs
next | previous | forward | backward | up | index | toc

Graphs -- graphs and digraphs

Description

This package defines classes for graphs and digraphs and related methods.

Contributors

Carlos Amendola, Alex Diaz, Luis David Garcia Puente, Roser Homs Pons, Olga Kuznetsova, Shaowei Lin, Sonja Mapes, Harshit J Motwani, Mike Stillman, and Doug Torrance contributed to this package.

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
    • 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
    • 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
    • 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 starting at a specified node
    • 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 -- topologically sort the vertices of a 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
    • addEdges'(Graph,List) (missing documentation)
    • 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
    • addVertices(Graph,List) (missing documentation)
    • 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
    • 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
    • degree(Graph,Thing) (missing documentation)
    • 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
    • deleteEdges(Digraph,List) (missing documentation)
    • deleteVertex(Graph,Thing) -- see deleteVertex -- a method for deleting the vertex of a graph
    • deleteVertex(Digraph,Thing) (missing documentation)
    • 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
    • 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
    • Digraph _ List (missing documentation)
    • Digraph _ ZZ (missing documentation)
    • Digraph _* (missing documentation)
    • 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
    • distance(Digraph,Thing) (missing documentation)
    • 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
    • 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
    • net(Digraph) (missing documentation)
    • 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 starting at a specified node
    • 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 -- topologically sort the vertices of a digraph
    • topSort(Digraph,String) -- see topSort -- topologically sort the vertices of a digraph
    • toString(Digraph) (missing documentation)
    • 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.