next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Graphs :: Graphs

Graphs

Authors

Version

This documentation describes version 0.3.1 of Graphs.

Source code

The source code from which this documentation is derived is in the file Graphs.m2.

Exports

  • 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)
    • bigraph (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 (missing documentation)
    • cocktailParty -- Returns a cocktail party graph
    • collateVertices (missing documentation)
    • complementGraph -- Returns the complement of a graph
    • completeGraph -- Constructs a complete graph
    • completeMultipartiteGraph -- constructs a complete multipartite graph
    • connectedComponents -- Computes the connected components of a 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
    • 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)
    • diameter -- Computes the diameter of a graph
    • digraph -- Constructs a digraph
    • digraphTranspose -- returns the transpose of a Digraph
    • 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 (missing documentation)
    • forefathers -- returns the forefathers of a digrah
    • 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
    • labeledGraph (missing documentation)
    • 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
    • mixedGraph (missing documentation)
    • 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
    • tensorProduct (missing documentation)
    • thresholdGraph -- A method that generates a threshold graph from a binary list
    • topologicalSort (missing documentation)
    • topSort (missing documentation)
    • 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
    • barycenter(Graph), see barycenter -- Returns the barycenter of a grah
    • bigraph(MixedGraph) (missing documentation)
    • 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
    • children(MixedGraph,Thing) (missing documentation)
    • 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) (missing documentation)
    • clusteringCoefficient(Graph,Thing) (missing documentation)
    • collateVertices(MixedGraph) (missing documentation)
    • complementGraph(Graph), see complementGraph -- Returns the complement of a 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
    • 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
    • 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 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
    • descendants(MixedGraph,Thing) (missing documentation)
    • diameter(Graph), see diameter -- Computes the diameter of a graph
    • Digraph _ List (missing documentation)
    • Digraph _ ZZ (missing documentation)
    • Digraph _* (missing documentation)
    • digraph(MixedGraph) (missing documentation)
    • digraphTranspose(Digraph), see digraphTranspose -- returns the transpose of a Digraph
    • directProduct(Graph,Graph), see directProduct -- Computes the direct product of two 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
    • 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
    • forefathers(MixedGraph,Thing) (missing documentation)
    • girth(Graph), see girth -- A method for computing the girth of a graph
    • graph(Digraph) -- Returns the legacy G#graph hash table
    • graph(LabeledGraph) (missing documentation)
    • graph(MixedGraph) (missing documentation)
    • graphComposition(Graph,Graph), see graphComposition -- A method for composing two graphs
    • 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
    • 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
    • labeledGraph(Digraph,List) (missing documentation)
    • 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
    • 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
    • mixedGraph(Digraph) (missing documentation)
    • mixedGraph(Digraph,Bigraph) (missing documentation)
    • mixedGraph(Graph,Digraph) (missing documentation)
    • mixedGraph(Graph,Digraph,Bigraph) (missing documentation)
    • neighbors(Graph,Thing), see neighbors -- returns the neighbors of a vertex in a graph
    • neighbors(MixedGraph,Thing) (missing documentation)
    • net(Digraph) (missing documentation)
    • net(LabeledGraph) (missing documentation)
    • net(MixedGraph) (missing documentation)
    • nondescendants(Digraph,Thing), see nondescendants -- returns the nondescendants of a vertex of a digraph
    • nondescendants(MixedGraph,Thing) (missing documentation)
    • nonneighbors(Graph,Thing), see nonneighbors -- returns the non-neighbors of a vertex in a graph
    • nonneighbors(MixedGraph,Thing) (missing documentation)
    • 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
    • parents(MixedGraph,Thing) (missing documentation)
    • radius(Graph), see radius -- Returns the radius of a 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
    • strongProduct(Graph,Graph), see strongProduct -- a method for taking the strong product of two graphs
    • topologicalSort(Digraph) (missing documentation)
    • topologicalSort(Digraph,String) (missing documentation)
    • topSort(Digraph) (missing documentation)
    • toString(Digraph) (missing documentation)
    • toString(LabeledGraph) (missing documentation)
    • toString(MixedGraph) (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
    • vertices(MixedGraph) (missing documentation)
    • writeDotFile(String,Graph), see writeDotFile -- Writes a graph to a dot file with a specified filename
  • Symbols
    • discoveryTime (missing documentation)
    • EntryMode (missing documentation)
    • finishingTime (missing documentation)
    • newDigraph (missing documentation)
    • simpleGraph (missing documentation)
    • Singletons (missing documentation)