GAP (digraphs) - Contents

  3.1-1 IsDigraph
  3.1-2 IsMutableDigraph
  3.1-3 IsImmutableDigraph
  3.1-4 IsCayleyDigraph
  3.1-5 IsDigraphWithAdjacencyFunction
  3.1-6 DigraphByOutNeighboursType
  3.1-7 Digraph
  3.1-8 DigraphByAdjacencyMatrix
  3.1-9 DigraphByEdges
  3.1-10 EdgeOrbitsDigraph
  3.1-11 DigraphByInNeighbours
  3.1-12 CayleyDigraph
  3.1-13 ListNamedDigraphs

3.2 Changing representations

  3.2-1 AsBinaryRelation
  3.2-2 AsDigraph
  3.2-3 Graph
  3.2-4 AsGraph
  3.2-5 AsTransformation

3.3 New digraphs from old

  3.3-1 DigraphImmutableCopy
  3.3-2 DigraphImmutableCopyIfImmutable
  3.3-3 InducedSubdigraph
  3.3-4 ReducedDigraph
  3.3-5 MaximalSymmetricSubdigraph
  3.3-6 MaximalAntiSymmetricSubdigraph
  3.3-7 UndirectedSpanningForest
  3.3-8 DigraphShortestPathSpanningTree
  3.3-9 QuotientDigraph
  3.3-10 DigraphReverse
  3.3-11 DigraphDual
  3.3-12 DigraphSymmetricClosure
  3.3-13 DigraphTransitiveClosure
  3.3-14 DigraphTransitiveReduction
  3.3-15 DigraphAddVertex
  3.3-16 DigraphAddVertices
  3.3-17 DigraphAddEdge
  3.3-18 DigraphAddEdgeOrbit
  3.3-19 DigraphAddEdges
  3.3-20 DigraphRemoveVertex
  3.3-21 DigraphRemoveVertices
  3.3-22 DigraphRemoveEdge
  3.3-23 DigraphRemoveEdgeOrbit
  3.3-24 DigraphRemoveEdges
  3.3-25 DigraphRemoveLoops
  3.3-26 DigraphRemoveAllMultipleEdges
  3.3-27 DigraphReverseEdges
  3.3-28 DigraphDisjointUnion
  3.3-29 DigraphEdgeUnion
  3.3-30 DigraphJoin
  3.3-31 DigraphCartesianProduct
  3.3-32 DigraphDirectProduct
  3.3-33 ConormalProduct
  3.3-34 HomomorphicProduct
  3.3-35 LexicographicProduct
  3.3-36 ModularProduct
  3.3-37 StrongProduct
  3.3-38 DigraphCartesianProductProjections
  3.3-39 DigraphDirectProductProjections
  3.3-40 LineDigraph
  3.3-41 LineUndirectedDigraph
  3.3-42 DoubleDigraph
  3.3-43 BipartiteDoubleDigraph
  3.3-44 DigraphAddAllLoops
  3.3-45 DistanceDigraph
  3.3-46 DigraphClosure
  3.3-47 DigraphMycielskian

3.4 Random digraphs

  3.4-1 RandomDigraph
  3.4-2 RandomMultiDigraph
  3.4-3 RandomTournament
  3.4-4 RandomLattice

3.5 Standard examples

  3.5-1 AndrasfaiGraph
  3.5-2 BananaTree
  3.5-3 BinaryTree
  3.5-4 BinomialTreeGraph
  3.5-5 BishopsGraph
  3.5-6 BondyGraph
  3.5-7 BookGraph
  3.5-8 StackedBookGraph
  3.5-9 ChainDigraph
  3.5-10 CirculantGraph
  3.5-11 CompleteDigraph
  3.5-12 CompleteBipartiteDigraph
  3.5-13 CompleteMultipartiteDigraph
  3.5-14 CycleDigraph
  3.5-15 CycleGraph
  3.5-16 EmptyDigraph
  3.5-17 GearGraph
  3.5-18 HaarGraph
  3.5-19 HalvedCubeGraph
  3.5-20 HanoiGraph
  3.5-21 HelmGraph
  3.5-22 HypercubeGraph
  3.5-23 JohnsonDigraph
  3.5-24 KellerGraph
  3.5-25 KingsGraph
  3.5-26 KneserGraph
  3.5-27 KnightsGraph
  3.5-28 LindgrenSousselierGraph
  3.5-29 LollipopGraph
  3.5-30 MobiusLadderGraph
  3.5-31 MycielskiGraph
  3.5-32 OddGraph
  3.5-33 PathGraph
  3.5-34 PermutationStarGraph
  3.5-35 PetersenGraph
  3.5-36 GeneralisedPetersenGraph
  3.5-37 PrismGraph
  3.5-38 StackedPrismGraph
  3.5-39 QueensGraph
  3.5-40 RooksGraph
  3.5-41 SquareGridGraph
  3.5-42 TriangularGridGraph
  3.5-43 StarGraph
  3.5-44 TadpoleGraph
  3.5-45 WalshHadamardGraph
  3.5-46 WebGraph
  3.5-47 WheelGraph
  3.5-48 WindmillGraph

4 Operators

4.1 Operators for digraphs

4.1-1 IsSubdigraph
4.1-2 IsUndirectedSpanningTree

5 Attributes and operations

5.1 Vertices and edges

  5.1-1 DigraphVertices
  5.1-2 DigraphNrVertices
  5.1-3 DigraphEdges
  5.1-4 DigraphNrEdges
  5.1-5 DigraphNrLoops
  5.1-6 DigraphSinks
  5.1-7 DigraphSources
  5.1-8 DigraphTopologicalSort
  5.1-9 DigraphVertexLabel
  5.1-10 DigraphVertexLabels
  5.1-11 DigraphEdgeLabel
  5.1-12 DigraphEdgeLabels
  5.1-13 DigraphInEdges
  5.1-14 DigraphOutEdges
  5.1-15 IsDigraphEdge
  5.1-16 IsMatching
  5.1-17 DigraphMaximalMatching
  5.1-18 DigraphMaximumMatching

5.2 Neighbours and degree

  5.2-1 AdjacencyMatrix
  5.2-2 CharacteristicPolynomial
  5.2-3 BooleanAdjacencyMatrix
  5.2-4 DigraphAdjacencyFunction
  5.2-5 DigraphRange
  5.2-6 OutNeighbours
  5.2-7 InNeighbours
  5.2-8 OutDegrees
  5.2-9 InDegrees
  5.2-10 OutDegreeOfVertex
  5.2-11 OutNeighboursOfVertex
  5.2-12 InDegreeOfVertex
  5.2-13 InNeighboursOfVertex
  5.2-14 DigraphLoops
  5.2-15 DegreeMatrix
  5.2-16 LaplacianMatrix

5.3 Orders

5.3-1 PartialOrderDigraphMeetOfVertices
5.3-2 NonUpperSemimodularPair

5.4 Reachability and connectivity

  5.4-1 DigraphDiameter
  5.4-2 DigraphShortestDistance
  5.4-3 DigraphShortestDistances
  5.4-4 DigraphLongestDistanceFromVertex
  5.4-5 DigraphDistanceSet
  5.4-6 DigraphGirth
  5.4-7 DigraphOddGirth
  5.4-8 DigraphUndirectedGirth
  5.4-9 DigraphConnectedComponents
  5.4-10 DigraphConnectedComponent
  5.4-11 DigraphStronglyConnectedComponents
  5.4-12 DigraphStronglyConnectedComponent
  5.4-13 DigraphBicomponents
  5.4-14 ArticulationPoints
  5.4-15 Bridges
  5.4-16 StrongOrientation
  5.4-17 DigraphPeriod
  5.4-18 DigraphFloydWarshall
  5.4-19 IsReachable
  5.4-20 IsDigraphPath
  5.4-21 VerticesReachableFrom
  5.4-22 DigraphPath
  5.4-23 DigraphShortestPath
  5.4-24 DigraphRandomWalk
  5.4-25 Dominators
  5.4-26 DominatorTree
  5.4-27 IteratorOfPaths
  5.4-28 DigraphAllSimpleCircuits
  5.4-29 DigraphLongestSimpleCircuit
  5.4-30 DigraphLayers
  5.4-31 DigraphDegeneracy
  5.4-32 DigraphDegeneracyOrdering
  5.4-33 HamiltonianPath
  5.4-34 NrSpanningTrees
  5.4-35 DigraphDijkstra

5.5 Cayley graphs of groups

5.5-1 GroupOfCayleyDigraph
5.5-2 GeneratorsOfCayleyDigraph

5.6 Associated semigroups

5.6-1 AsSemigroup
5.6-2 AsSemigroup

5.7 Planarity

  5.7-1 KuratowskiPlanarSubdigraph
  5.7-2 KuratowskiOuterPlanarSubdigraph
  5.7-3 PlanarEmbedding
  5.7-4 OuterPlanarEmbedding
  5.7-5 SubdigraphHomeomorphicToK23

6 Properties of digraphs

6.1 Vertex properties

6.1-1 DigraphHasAVertex
6.1-2 DigraphHasNoVertices

6.2 Edge properties

  6.2-1 DigraphHasLoops
  6.2-2 IsAntiSymmetricDigraph
  6.2-3 IsBipartiteDigraph
  6.2-4 IsCompleteBipartiteDigraph
  6.2-5 IsCompleteDigraph
  6.2-6 IsCompleteMultipartiteDigraph
  6.2-7 IsEmptyDigraph
  6.2-8 IsEquivalenceDigraph
  6.2-9 IsFunctionalDigraph
  6.2-10 IsPermutationDigraph
  6.2-11 IsMultiDigraph
  6.2-12 IsNonemptyDigraph
  6.2-13 IsReflexiveDigraph
  6.2-14 IsSymmetricDigraph
  6.2-15 IsTournament
  6.2-16 IsTransitiveDigraph

6.3 Orders

  6.3-1 IsPreorderDigraph
  6.3-2 IsPartialOrderDigraph
  6.3-3 IsMeetSemilatticeDigraph
  6.3-4 DigraphMeetTable
  6.3-5 IsUpperSemimodularDigraph
  6.3-6 IsDistributiveLatticeDigraph

6.4 Regularity

  6.4-1 IsInRegularDigraph
  6.4-2 IsOutRegularDigraph
  6.4-3 IsRegularDigraph
  6.4-4 IsDistanceRegularDigraph

6.5 Connectivity and cycles

  6.5-1 IsAcyclicDigraph
  6.5-2 IsChainDigraph
  6.5-3 IsConnectedDigraph
  6.5-4 IsBiconnectedDigraph
  6.5-5 IsBridgelessDigraph
  6.5-6 IsStronglyConnectedDigraph
  6.5-7 IsAperiodicDigraph
  6.5-8 IsDirectedTree
  6.5-9 IsUndirectedTree
  6.5-10 IsEulerianDigraph
  6.5-11 IsHamiltonianDigraph
  6.5-12 IsCycleDigraph

6.6 Planarity

6.6-1 IsPlanarDigraph
6.6-2 IsOuterPlanarDigraph

6.7 Homomorphisms and transformations

  6.7-1 IsDigraphCore
  6.7-2 IsEdgeTransitive
  6.7-3 IsVertexTransitive

7 Homomorphisms

7.1 Acting on digraphs

  7.1-1 OnDigraphs
  7.1-2 OnMultiDigraphs
  7.1-3 OnTuplesDigraphs

8 Finding cliques and independent sets

8.1 Finding cliques

  8.1-1 IsClique
  8.1-2 CliquesFinder
  8.1-3 DigraphClique
  8.1-4 DigraphMaximalCliques
  8.1-5 CliqueNumber

8.2 Finding independent sets

  8.2-1 IsIndependentSet
  8.2-2 DigraphIndependentSet
  8.2-3 DigraphMaximalIndependentSets

9 Visualising and IO

9.1 Visualising a digraph

  9.1-1 Splash
  9.1-2 DotDigraph
  9.1-3 DotSymmetricDigraph
  9.1-4 DotPartialOrderDigraph
  9.1-5 DotPreorderDigraph
  9.1-6 DotHighlightedDigraph

9.2 Reading and writing digraphs to a file

  9.2-1 String
  9.2-2 DigraphFromGraph6String
  9.2-3 Graph6String
  9.2-4 DigraphFile
  9.2-5 ReadDigraphs
  9.2-6 WriteDigraphs
  9.2-7 IteratorFromDigraphFile
  9.2-8 DigraphPlainTextLineEncoder
  9.2-9 TournamentLineDecoder
  9.2-10 AdjacencyMatrixUpperTriangleLineDecoder
  9.2-11 TCodeDecoder
  9.2-12 PlainTextString
  9.2-13 WritePlainTextDigraph
  9.2-14 WriteDIMACSDigraph

A Grape to Digraphs Command Map

A.1 Functions to construct and modify graphs

A.2 Functions to inspect graphs, vertices and edges

A.3 Functions to determine regularity properties of graphs

A.4 Some special vertex subsets of a graph

A.5 Functions to construct new graphs from old

A.6 Vertex-Colouring and Complete Subgraphs

A.7 Automorphism groups and isomorphism testing for graphs

References

Index

Digraphs

Abstract

Copyright

Acknowledgements

Contents