Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind
 [Top of Book]  [Contents]   [Next Chapter] 

Digraphs

Version 1.5.3

Jan De Beule
Email: jdebeule@cage.ugent.be
Homepage: http://homepages.vub.ac.be/~jdbeule

Julius Jonušas
Email: julius.jonusas@tuwien.ac.at
Homepage: http://julius.jonusas.work

James D. Mitchell
Email: jdm3@st-and.ac.uk
Homepage: https://jdbm.me

Maria Tsalakou
Email: mt200@st-andrews.ac.uk
Homepage: https://mariatsalakou.github.io

Wilf A. Wilson
Email: gap@wilf-wilson.net
Homepage: https://wilf.me

Michael C. Young
Email: mct25@st-andrews.ac.uk
Homepage: https://mct25.host.cs.st-andrews.ac.uk

Marina Anagnostopoulou-Merkouri

Finn Buck

Stuart Burrell

Reinis Cirpons

Tom Conti-Leslie

Luke Elliott

Ewan Gilligan

Max Horn

Christopher Jefferson

Markus Pfeiffer

Lea Racine

Christopher Russell

Finn Smith

Ben Spiers

Murray White

Abstract

The Digraphs package is a GAP package containing methods for graphs, digraphs, and multidigraphs.

Copyright

© 2014-22 by Jan De Beule, Julius Jonušas, James D. Mitchell, Wilf A. Wilson, Michael Young et al.

Digraphs is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

Acknowledgements

We would like to thank Christopher Jefferson for his help in including bliss in Digraphs. This package's methods for computing digraph homomorphisms are based on work by Max Neunhöffer, and independently Artur Schäfer.

Contents

1 The Digraphs package
 1.1 Introduction

  1.1-1 Definitions
2 Installing Digraphs
 2.1 For those in a hurry

  2.1-1 Configuration options
 2.2 Optional package dependencies

  2.2-1 The Grape package
 2.3 Compiling the kernel module
 2.4 Rebuilding the documentation

  2.4-1 DigraphsMakeDoc
 2.5 Testing your installation

  2.5-1 DigraphsTestInstall
  2.5-2 DigraphsTestStandard
  2.5-3 DigraphsTestExtreme
3 Creating digraphs
 3.1 Creating digraphs

  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 PartialOrderDigraphMeetOfVertices
  5.2-16 DegreeMatrix
  5.2-17 LaplacianMatrix
 5.3 Reachability and connectivity

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

  5.4-1 GroupOfCayleyDigraph
  5.4-2 GeneratorsOfCayleyDigraph
 5.5 Associated semigroups

  5.5-1 AsSemigroup
  5.5-2 AsSemigroup
 5.6 Planarity

  5.6-1 KuratowskiPlanarSubdigraph
  5.6-2 KuratowskiOuterPlanarSubdigraph
  5.6-3 PlanarEmbedding
  5.6-4 OuterPlanarEmbedding
  5.6-5 SubdigraphHomeomorphicToK23
6 Properties of digraphs
 6.1 Edge properties

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

  6.2-1 IsInRegularDigraph
  6.2-2 IsOutRegularDigraph
  6.2-3 IsRegularDigraph
  6.2-4 IsDistanceRegularDigraph
 6.3 Connectivity and cycles

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

  6.4-1 IsPlanarDigraph
  6.4-2 IsOuterPlanarDigraph
 6.5 Homomorphisms and transformations

  6.5-1 IsDigraphCore
  6.5-2 IsEdgeTransitive
  6.5-3 IsVertexTransitive
7 Homomorphisms
 7.1 Acting on digraphs

  7.1-1 OnDigraphs
  7.1-2 OnMultiDigraphs
 7.2 Isomorphisms and canonical labellings

  7.2-1 DigraphsUseNauty
  7.2-2 AutomorphismGroup
  7.2-3 BlissAutomorphismGroup
  7.2-4 NautyAutomorphismGroup
  7.2-5 AutomorphismGroup
  7.2-6 AutomorphismGroup
  7.2-7 BlissCanonicalLabelling
  7.2-8 BlissCanonicalLabelling
  7.2-9 BlissCanonicalDigraph
  7.2-10 DigraphGroup
  7.2-11 DigraphOrbits
  7.2-12 DigraphOrbitReps
  7.2-13 DigraphSchreierVector
  7.2-14 DigraphStabilizer
  7.2-15 IsIsomorphicDigraph
  7.2-16 IsIsomorphicDigraph
  7.2-17 IsomorphismDigraphs
  7.2-18 IsomorphismDigraphs
  7.2-19 RepresentativeOutNeighbours
  7.2-20 IsDigraphIsomorphism
  7.2-21 IsDigraphColouring
  7.2-22 MaximalCommonSubdigraph
  7.2-23 MinimalCommonSuperdigraph
 7.3 Homomorphisms of digraphs

  7.3-1 HomomorphismDigraphsFinder
  7.3-2 DigraphHomomorphism
  7.3-3 HomomorphismsDigraphs
  7.3-4 DigraphMonomorphism
  7.3-5 MonomorphismsDigraphs
  7.3-6 DigraphEpimorphism
  7.3-7 EpimorphismsDigraphs
  7.3-8 DigraphEmbedding
  7.3-9 EmbeddingsDigraphs
  7.3-10 IsDigraphHomomorphism
  7.3-11 IsDigraphEmbedding
  7.3-12 DigraphsRespectsColouring
  7.3-13 GeneratorsOfEndomorphismMonoid
  7.3-14 DigraphColouring
  7.3-15 DigraphGreedyColouring
  7.3-16 DigraphWelshPowellOrder
  7.3-17 ChromaticNumber
  7.3-18 DigraphCore
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

 [Top of Book]  [Contents]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 A Bib Ind

generated by GAPDoc2HTML