experimental/graph

    Dark Mode
Search:
  Source   Edit

Generic implementation of graph data structure

Types

Graph[Id] = object
  isDirected*: bool
  edges: OrderedTable[Id, seq[Id]]
  Source   Edit 
GraphCyclesError = ref object of GraphError
  Source   Edit 
GraphEdge[Id] = tuple[src, dst: Id]
  Source   Edit 
GraphError = ref object of CatchableError
  Source   Edit 
Path[Id] = seq[Id]
  Source   Edit

Procs

proc `$`[Id](graph: Graph[Id]): string
  Source   Edit 
proc allNodes[Id](graph: Graph[Id]): seq[Id]
  Source   Edit 
func computeInDegrees[Id](graph: Graph[Id]): CountTable[Id]
  Source   Edit 
proc connectedComponents[Id](graph: Graph[Id]; overrideDirected: bool = false): seq[
    HashSet[Id]]
Return nodes forming strongly connected components   Source   Edit 
func contains[Id](graph: Graph[Id]; edge: GraphEdge[Id]): bool
  Source   Edit 
func contains[Id](graph: Graph[Id]; node: Id): bool
  Source   Edit 
func default[Id](graph: typedesc[Graph[Id]]): Graph[Id]
  Source   Edit 
func edgeCount[Id](graph: Graph[Id]): int
  Source   Edit 
proc findCycles[Id](graph: Graph[Id]; ignoreSelf: bool = false;
                    overrideDirected: bool = false; yieldMultiedge: bool = false): seq[
    Path[Id]]
  Source   Edit 
func getEdge[Id](graph: Graph[Id]; source, target: Id): GraphEdge[Id]
  Source   Edit 
proc getNoIncoming[Id](graph: Graph[Id]): seq[Id]
Get all nodes with zero in degree of zero   Source   Edit 
proc graphEasyRepr[Id](graph: Graph[Id]; name: proc (id: Id): string): string
  Source   Edit 
func inDeg[Id](graph: Graph[Id]; node: Id): int {.inline.}
Return in degree for @arg{node}   Source   Edit 
proc mergeCycleSets[Id](cycles: seq[seq[Id]]): seq[HashSet[Id]]
  Source   Edit 
func newGraph[Id](isDirected: bool = true): Graph[Id]
  Source   Edit 
func newGraph[Id](values: openArray[(Id, Id)]; isDirected: bool = true): Graph[
    Id]
  Source   Edit 
func nodeCount[Id](graph: Graph[Id]): int
  Source   Edit 
func outDeg[Id](graph: Graph[Id]; node: Id): int
  Source   Edit 
proc removeEdge[Id](graph: var Graph[Id]; edge: GraphEdge[Id])
Remove edge from graph. Note that starting/ending nodes will not be removed.   Source   Edit 
proc removeNode[Id](graph: var Graph[Id]; node: Id)

Remove node from graph.

Note that all edges that node is part of are removed too.

  Source   Edit 
proc topologicalOrdering[Id](graph: Graph[Id]; start: openArray[Id] = []): seq[
    Id]
Return graph nodes in topological ordering if possible. Otherwise (if graph contains cycles raise GraphCyclesError)   Source   Edit

Iterators

iterator breadthFirst[Id](graph: Graph[Id]; root: Id): Id
Perform breadth-first iteration of parent graph, starting from node   Source   Edit 
iterator depthFirst[Id](graph: Graph[Id]; root: Id): tuple[id: Id, depth: int]
Perform depth-first iteration of mutable nodes in graph, starting from node   Source   Edit 
iterator edgePairs[Id](graph: Graph[Id]): GraphEdge[Id]
  Source   Edit 
iterator inEdges[Id](graph: Graph[Id]; target: Id): GraphEdge[Id]
Iterate over ingoing edges for target   Source   Edit 
iterator nodes[Id](graph: Graph[Id]): Id
  Source   Edit 
iterator outEdges[Id](graph: Graph[Id]; source: Id): GraphEdge[Id]
Iterate over outgoing edges for source   Source   Edit 
iterator ritems[T](s: openArray[T]): T
Iterate over sequence starting from the right   Source   Edit

Templates

template findIt(s: typed; op: untyped): int
Find first element of the sequence for which op evaluates as true and return it's index. If no such element is found return -1   Source   Edit 
template findMaxIt(s: untyped; op: untyped): untyped
  Source   Edit

Made with Nim. Generated: 2024-10-24 00:00:00 UTC