Multigraphs
- Introduction
- Construction of Multigraphs
- The Vertex–Set and Edge–Set of Multigraphs
EdgeIndices(u, v): GrphVert, GrphVert → SeqEnumIndices(u, v): GrphVert, GrphVert → SeqEnumEdgeMultiplicity(u, v): GrphVert, GrphVert → RngIntEltMultiplicity(u, v): GrphVert, GrphVert → RngIntEltEdges(u, v): GrphVert, GrphVert → SeqEnumIncidentEdges(u): GrphVert → SetEnumE ! < { u, v }, i >: GrphEdgeSet, < . > → GrphEdgeE ! < [ u, v ], i >: GrphEdgeSet, < . > → GrphEdgeE.i {E . i}: GrphEdgeSet, RngIntElt → GrphEdgeEndVertices(e): GrphEdge → { GrphVert, GrphVert }EndVertices(e): GrphEdge → [ GrphVert, GrphVert ]InitialVertex(e): GrphEdge → GrphVertTerminalVertex(e): GrphEdge → GrphVertIndex(e): GrphEdge → RngIntElts eq t: GrphEdge, GrphEdge → BoolEltExample: GrphMult Edges
- Vertex and Edge Decorations
- Vertex Decorations: Labels
AssignLabel(~G, u, l): GrphMult, GrphVert, .AssignLabels(~G, S, L): GrphMult, [GrphVert], SeqEnumAssignLabels(~G, S, L): GrphMult, { @ GrphVert @}, SeqEnumAssignVertexLabels(~G, L): GrphMult, SeqEnumIsLabelled(u): GrphVert → BoolEltIsLabelled(V): GrphVertSet → BoolEltIsVertexLabelled(G): GrphMult → BoolEltLabel(u): GrphVert → .Labels(S): [GrphVert] → SeqEnumLabels(V): GrphVertSet → SeqEnumVertexLabels(G): GrphMult → SeqEnumDeleteLabel(~G, u): GrphMult, GrphVertDeleteLabels(~G, S): GrphMult, [GrphVert]DeleteVertexLabels(~G): GrphMult
- Edge Decorations
- Assigning Edge Decorations
AssignLabel(~G, e, l): GrphMult, GrphEdge, .AssignCapacity(~G, e, c): GrphMult, GrphEdge, RngIntEltAssignWeight(~G, e, w): GrphMult, GrphEdge, RngEltAssignLabels(~G, S, D): GrphMult, [GrphEdge], SeqEnumAssignLabels(~G, S, D): GrphMult, { @ GrphEdge @}, SeqEnumAssignCapacities(~G, S, D): GrphMult, [GrphEdge], [RngIntElt]AssignCapacities(~G, S, D): GrphMult, { @ GrphEdge @}, [RngIntElt]AssignWeights(~G, S, D): GrphMult, [GrphEdge], [RngElt]AssignWeights(~G, S, D): GrphMult, { @ GrphEdge @}, [RngElt]AssignEdgeLabels(~G, D): GrphMult, SeqEnumAssignCapacities(~G, D): GrphMult, [RngIntElt]AssignWeights(~G, D): GrphMult, [RngElt]
- Testing for Edge Decorations
- Reading Edge Decorations
- Deleting Edge Decorations
DeleteLabel(~G, e): GrphMult, GrphEdgeDeleteCapacity(~G, e): GrphMult, GrphEdgeDeleteWeight(~G, e): GrphMult, GrphEdgeDeleteLabels(~G, S): GrphMult, [GrphEdge]DeleteCapacities(~G, S): GrphMult, [GrphEdge]DeleteWeights(~G, S): GrphMult, [GrphEdge]DeleteEdgeLabels(~G): GrphMultDeleteCapacities(~G): GrphMultDeleteWeights(~G): GrphMult
- Unlabelled, or Uncapacitated, or Unweighted Graphs
- Standard Construction for Multigraphs
- Subgraphs
- Incremental Construction of Multigraphs
- Adding Vertices
G + n: GrphMult, RngIntElt → GrphMultG +:= n: GrphMult, RngIntEltAddVertex(~G): GrphMultAddVertices(~G, n): GrphMult, RngIntEltAddVertex(~G, l): GrphMult, .AddVertices(~G, n, L): GrphMult, RngIntElt, SeqEnum
- Removing Vertices
- Adding Edges
G + { u, v }: GrphMultUnd, {{ GrphVert, GrphVert } } → GrphMultUnd, GrphEdgeG + [ u, v ]: GrphMultDir, { [ GrphVert, GrphVert ] } → GrphMultDir, GrphEdgeG + [ u, v ]: GrphNet, { [ GrphVert, GrphVert ] } → GrphNet, GrphEdgeG + { { u, v } }: GrphMultUnd, { { GrphVert, GrphVert } } → GrphMultUndG + [ { u, v } ]: GrphMultUnd, [ { GrphVert, GrphVert } ] → GrphMultUndG + { [ u, v ] }: GrphMultDir, { [ GrphVert, GrphVert ] } → GrphDirG + [ [ u, v ] ]: GrphMultDir, [ [ GrphVert, GrphVert ] ] → GrphDirG + { [ u, v ] }: GrphNet, { [ GrphVert, GrphVert ] } → GrphNetG + [ [ u, v ] ]: GrphNet, [ [ GrphVert, GrphVert ] ] → GrphNetG +:= { u, v }: GrphMultUnd, { GrphVert, GrphVert }G +:= [ u, v ]: GrphDir, [ GrphVert, GrphVert ]G +:= [ u, v ]: GrphNet, [ GrphVert, GrphVert ]G +:= { { u, v } }: GrphMultUnd, { { GrphVert, GrphVert } }G +:= [ { u, v } ]: GrphMultUnd, [ { GrphVert, GrphVert } ]G +:= { [ u, v ] }: GrphMultDir, { [ GrphVert, GrphVert ] }G +:= [ [ u, v ] ]: GrphMultDir, [ [ GrphVert, GrphVert ] ]G +:= { [ u, v ] }: GrphNet, { [ GrphVert, GrphVert ] }G +:= [ [ u, v ] ]: GrphNet, [ [ GrphVert, GrphVert ] ]AddEdge(G, u, v): GrphMult, GrphVert, GrphVert → GrphMult, GrphEdgeAddEdge(G, u, v, l): GrphMultUnd, GrphVert, GrphVert, . → GrphMult, GrphEdgeAddEdge(G, u, v, l): GrphMultDir, GrphVert, GrphVert, . → GrphMultDir, GrphEdgeAddEdge(G, u, v, c): GrphNet, GrphVert, RngIntElt, . → GrphNet, GrphEdgeAddEdge(G, u, v, c, l): GrphNet, GrphVert, GrphVert, RngIntElt, . → GrphNet, GrphEdgeAddEdge(~G, u, v): GrphMult, GrphVert, GrphVertAddEdge(~G, u, v, l): GrphMultUnd, GrphVert, GrphVert, .AddEdge(~G, u, v, l): GrphMultDir, GrphVert, GrphVert, .AddEdge(~G, u, v, c): GrphNet, GrphVert, GrphVert, RngIntEltAddEdge(~G, u, v, c, l): GrphNet, GrphVert, GrphVert, RngIntElt, .AddEdges(G, S): GrphMultUnd, { { GrphVert, GrphVert } } → GrphMultUndAddEdges(G, S): GrphMultUnd, [ { GrphVert, GrphVert } ] → GrphMultUndAddEdges(G, S): GrphMultDir, { [ GrphVert, GrphVert ] } → GrphMultDirAddEdges(G, S): GrphMultDir, [ [ GrphVert, GrphVert ] ] → GrphMultDirAddEdges(G, S): GrphNet, { [ GrphVert, GrphVert ] } → GrphNetAddEdges(G, S): GrphNet, [ [ GrphVert, GrphVert ] ] → GrphNetAddEdges(G, S, L): GrphMult, SeqEnum, SeqEnum → GrphMultAddEdges(~G, S): GrphMultUnd, { { GrphVert, GrphVert } }AddEdges(~G, S): GrphMultUnd, [ { GrphVert, GrphVert } ]AddEdges(~G, S): GrphMultDir, { [ GrphVert, GrphVert ] }AddEdges(~G, S): GrphMultDir, [ [ GrphVert, GrphVert ] ]AddEdges(~G, S): GrphNet, { [ GrphVert, GrphVert ] }AddEdges(~G, S): GrphNet, [ [ GrphVert, GrphVert ] ]AddEdges(~G, S, L): GrphMult, SeqEnum, SeqEnum
- Removing Edges
G - e: GrphMult, GrphEdge → GrphMultG - { e }: GrphMult, { GrphEdge } → GrphMultG - { { u, v } }: GrphMultUnd, { { GrphVert, GrphVert rbrace } → GrphMultUndG - { [u, v] }: GrphMultDir, { [ GrphVert, GrphVert ] } → GrphMultDirG -:= e: GrphMult, GrphEdgeG -:= { e }: GrphMult, { GrphEdge }G -:= { { u, v } }: GrphMultUnd, { { GrphVert, GrphVert rbrace }G -:= { [u, v] }: GrphMultDir, { [ GrphVert, GrphVert ] }RemoveEdge(~G, e): GrphMult, GrphEdgeRemoveEdges(~G, S): GrphMult, { GrphEdge }RemoveEdge(~G, u, v): GrphMult, GrphVert, GrphVertRemoveEdges(~G, S): GrphMultDir, { { GrphVert, GrphVert } }RemoveEdges(~G, S): GrphMultDir, { [ GrphVert, GrphVert ] }
- Vertex Insertion, Contraction
- Unions of Multigraphs
Union(G, H): GrphMultUnd, GrphMultUnd → GrphMultUndUnion(G, H): GrphMultDir, GrphMultDir → GrphMultDirG join H: GrphMultUnd, GrphMultUnd → GrphMultUndG join H: GrphMultDir, GrphMultDir → GrphMultDirUnion(N, H): GrphNet, GrphNet → GrphNetN join H: GrphNet, GrphNet → GrphNet& join S: [ MultiUnd ] → GrphMultUnd& join S: [ GrphMultDir ] → GrphMultDir& join S: [ GrphNet ] → GrphNet& join S: { MultiUnd } → GrphMultUnd& join S: { GrphMultDir } → GrphMultDir& join S: { GrphNet } → GrphNetEdgeUnion(G, H): GrphMultUnd, GrphMultUnd → GrphMultUndEdgeUnion(G, H): GrphMultDir, GrphMultDir → GrphMultDirEdgeUnion(N, H): GrphNet, GrphNet → GrphNet
- Conversion Functions
- Orientated Graphs
- Converse
- Converting between Simple Graphs and Multigraphs
UnderlyingGraph(G): GrphMult → GrphUnd, GrphVertSet, GrphEdgeSetUnderlyingGraph(G): Grph → GrphUnd, GrphVertSet, GrphEdgeSetUnderlyingDigraph(G): GrphMult → GrphDir, GrphVertSet, GrphEdgeSetUnderlyingDigraph(G): Grph → GrphDir, GrphVertSet, GrphEdgeSetUnderlyingMultiGraph(G): Grph → GrphMultUnd, GrphVertSet, GrphEdgeSetUnderlyingMultiGraph(G): GrphMult → GrphMultUnd, GrphVertSet, GrphEdgeSetUnderlyingMultiDigraph(G): Grph → GrphMultDir, GrphVertSet, GrphEdgeSetUnderlyingMultiDigraph(G): GrphMult → GrphMultDir, GrphVertSet, GrphEdgeSetUnderlyingNetwork(G): Grph → GrphNet, GrphVertSet, GrphEdgeSetUnderlyingNetwork(G): GrphMult → GrphNet, GrphVertSet, GrphEdgeSet
- Elementary Invariants and Predicates for Multigraphs
Order(G): GrphMult → RngIntEltNumberOfVertices(G): GrphMult → RngIntEltSize(G): GrphMult → RngIntEltNumberOfEdges(G): GrphMult → RngIntEltu adj v: GrphVert, GrphVert → BoolElte adj f: GrphEdge, GrphEdge → BoolEltu notadj v: GrphVert, GrphVert → BoolElte notadj f: GrphEdge, GrphEdge → BoolEltu in e: GrphVert, GrphEdge → BoolEltu notin e: GrphVert, GrphEdge → BoolEltG eq H: GrphMultUnd, GrphMultUnd → BoolEltG eq H: GrphMultDir, GrphMultDir → BoolEltG eq H: GrphNet, GrphNet → BoolEltIsSubgraph(G, H): GrphMultUnd, GrphMultUnd → BoolEltIsSubgraph(G, H): GrphMultDir, GrphMultDir → BoolEltIsSubgraph(G, H): GrphNet, GrphNet → BoolEltIsBipartite(G): GrphMultUnd → BoolEltBipartition(G): GrphMultUnd → [ { GrphVert} ]IsRegular(G): GrphMult → BoolEltIsComplete(G): GrphMult → BoolEltIsEmpty(G): GrphMult → BoolEltIsNull(G): GrphMult → BoolEltIsSimple(G): GrphMult → BoolEltIsSimple(G): Grph → BoolEltIsUndirected(G): GrphMult → BoolEltIsUndirected(G): Grph → BoolEltIsDirected(G): GrphMult → BoolEltIsDirected(G): Grph → BoolElt
- Adjacency and Degree
- Adjacency and Degree Functions for Multigraphs
- Adjacency and Degree Functions for Multidigraphs
InDegree(u): GrphVert → RngIntEltOutDegree(u): GrphVert → RngIntEltMaximumInDegree(G): GrphMultDir → RngIntElt, GrphVertMaxindeg(G): GrphMultDir → RngIntElt, GrphVertMinimumInDegree(G): GrphMultDir → RngIntElt, GrphVertMinindeg(G)): GrphMultDir → RngIntElt, GrphVertMaximumOutDegree(G): GrphMultDir → RngIntElt, GrphVertMaxoutdeg(G): GrphMultDir → RngIntElt, GrphVertMinimumOutDegree(G): GrphMultDir → RngIntElt, GrphVertMinoutdeg(G): GrphMultDir → RngIntElt, GrphVertDegree(u): GrphVert → RngIntEltMaximumDegree(G): GrphMultDir → RngIntElt, GrphVertMaxdeg(G): GrphMultDir → RngIntElt, GrphVertMinimumDegree(G): GrphMultDir → RngIntElt, GrphVertMindeg(G): GrphMultDir → RngIntElt, GrphVertAlldeg(G, n): GrphMultDir, RngIntElt → { GrphVert}DegreeSequence(G): GrphMultDir → [ { GrphVert } ]InNeighbours(u): GrphVert → { GrphVert}InNeighbors(u): GrphVert → { GrphVert}OutNeighbours(u): GrphVert → { GrphVert}OutNeighbors(u): GrphVert → { GrphVert}IncidentEdges(u): GrphVert → { GrphEdge}
- Connectedness
- Spanning Trees
SpanningTree(G): GrphMultUnd → GrphMultUnd, GrphVertSet, GrphEdgeSetSpanningForest(G): GrphMult → GrphMult, GrphVertSet, GrphEdgeSetBreadthFirstSearchTree(u): GrphVert → GrphMult, GrphVertSet, GrphEdgeSetBFSTree(u): GrphVert → GrphMultDepthFirstSearchTree(u): GrphVert → GrphMult, GrphVertSet, GrphEdgeSet, SeqEnumDFSTree(u): GrphVert → GrphMult, GrphVertSet, GrphEdgeSet, SeqEnum
- Planar Graphs
- Distances, Shortest Paths and Minimum Weight Trees
Reachable(u, v : parameters): GrphVert, GrphVert → BoolElt, RngEltDistance(u, v : parameters): GrphVert, GrphVert → RngEltDistances(u : parameters): GrphVert → EseqPathExists(u, v : parameters): GrphVert, GrphVert → BoolElt, EseqPath(u, v : parameters): GrphVert, GrphVert → EseqShortestPath(u, v : parameters): GrphVert, GrphVert → EseqPaths(u : parameters): GrphVert → EseqShortestPaths(u : parameters): GrphVert → EseqGeodesicExists(u, v : parameters): GrphVert, GrphVert → BoolElt, EseqGeodesic(u, v : parameters): GrphVert, GrphVert → EseqGeodesics(u : parameters): GrphVert → EseqHasNegativeWeightCycle(u : parameters): GrphVert → BoolEltHasNegativeWeightCycle(G): Grph → BoolEltHasNegativeWeightCycle(G): GrphMult → BoolEltAllPairsShortestPaths(G : parameters): Grph → SeqEnum, SeqEnumAllPairsShortestPaths(G : parameters): GrphMult → SeqEnum, SeqEnumMinimumWeightTree(u : parameters): GrphVert → SeqEnumExample: GrphMult ShortPExample: GrphMult MinW
