Graflib
A simple graph implementation library. To scrutiny the trail when walking the graph, define trail to see in stdout the nodes visited. Compile it:
$ nim c -d:trail yourcodefile
The current implementation walks into graph nodes to find the connection between origin node to destination node without specifically calculating weight cost. The weight cost actually user-calculated by defining proc cost[T, C](n1, n2: T): C with C is must be comparable (<) and addable (+). This function will be used when searching path using A*.
Example
from sequtils import mapIt import graflib # we build undirected empty graph var graph = buildGraph[string]() doAssert(graph.vertices.len == 0) doAssert(graph.edges.len == 0) # Add edgest to our graph graph.addEdges [ ("origin1", "destination1"), ("origin2", "destination2"), ("origin1", "destination2"), ("origin1", "origin2") ].mapIt( initEdge(it[0], it[1]) ) doAssert(graph.edges.len == 4) doAssert(graph.vertices.len == 4) # Find paths from origin to destination node var paths = graph.paths("origin1", "destination2") doAssert(paths.len == 2) doAssert(paths[0] == @["origin1", "destination2"] # degree = indegree + outdegree doAssert(graph.degree("origin1") == 3) doAssert(graph.degree("origin2") == 2) # Another version would be defining edge each time node visited var graph2 = buildGraph[string]() func next(s: string; edges: seq[Edge[string]]): seq[string] = if s == "origin1": return @["destination1", "destination2", "origin2"] if s == "origin2": return @["destination2", "origin1"] if s == "destination1": return @["origin1"] if s == "destination2": return @["origin1", "origin2"] paths = graph2.paths("origin1", "destination2") doAssert(paths.len == 2) doAssert(paths[0] == @["origin1", "destination2"]
With user-defined neighboring, user can keep their own structure to search for next nodes to visit. Above example is illustrated a constant and hard-coded connection from each nodes but user can use, for example, table to keep nodes' connections and can be added removed dynamically during the program running. When walking the connected graph, we use defined == for Vertex comparison. Hence if we use a specialized type for Vertex label, we need to define == operator for our type.
With additional A* search (proc a*), users must provide additional procs to make it works. Read the a* proc documentation for the detail.
Types
Graph[T] = object directed*: bool ## If true, every edge has only a direction ## for each time its defined. vertices*: seq[T] ## Vertices or nodes edges*: seq[Edge[T]] ## Edge which spanned between node1 and node2
- Graph type that implemented generically using T type as the node. Source Edit
Vertex[T] = T
- Alias left-over from previous dev version Source Edit
Edge[T] = object node1*: T node2*: T
- Representation of two connected nodes. Source Edit
GraphRef[T] = ref Graph[T]
- Reference-type graph. Source Edit
Procs
proc `==`(a, b: Edge): bool
- Source Edit
proc initEdge[T](n1, n2: T): Edge[T]
- Source Edit
proc isDirected(graph: Graph): bool
- Source Edit
proc contains(graph: Graph; vertice: Vertex): bool
- Source Edit
proc contains[T](graph: Graph[T]; edge: Edge[T]): bool
- Source Edit
proc contains[T](edge: Edge[T]; vertex: Vertex[T]): bool
- Source Edit
proc addVertices[T](graph: var Graph[T]; vertices: varargs[T])
- Source Edit
proc addEdges[T](graph: var Graph; edges: varargs[Edge[T]])
- Source Edit
proc addEdges[T](graph: var Graph; edges: varargs[(T, T)])
- Source Edit
proc buildGraph[T](vertices: openArray[Vertex[T]] = @[]; edges: openArray[Edge[T]] = @[]; directed: bool = false; weighted: bool = false): Graph[T]
- Source Edit
proc neighbors[T](graph: Graph[T]; vertex: T): seq[T]
- Source Edit
proc `$`[T](graph: Graph[T]): string
- Source Edit
proc `$`(edge: Edge): string
- Source Edit
proc indegree[T](graph: Graph[T]; vertex: T): int
- Source Edit
proc outdegree[T](graph: Graph[T]; vertex: T): int
- Source Edit
proc degree(graph: Graph; vertex: Vertex): int
- Source Edit
proc buildDigraph[T](): Graph
- Source Edit
proc newGraph[T](): GraphRef[T]
- Source Edit
proc isConnected[T](graph: Graph[T]): bool
- Source Edit
proc paths[T](graph: Graph[T]; v1, v2: sink Vertex[T]): unown seq[seq[Vertex[T]]]
-
Paths is searching for all availables path from v1 to v2. By default searching for paths is not cycled, e.g. we have edges, a->b, b->c, c->d, a->c, a->d, c->b when we searched a-b-c and c has path to b, since it's not cycled c cannot visit b once more because it's has been visited. By defining the func isCycle(node: N): bool we can make a rule that it can visit more than once for a node. By default it's not defined and defaulting to false, or in other word, not cycled.
Users can provide custom next nodes by defining proc next(node: N, edges: seq[Edge[N]]): seq[N] for their particular purpose. The arg edges is the current edges that graph has. It's supplied when users want to use it but in most cases they can ignore it.
Source Edit proc shortestPath[T](graph: Graph[T]; v1, v2: T): seq[Vertex[T]] {...}{. deprecated: "Use `a*` proc for better customized search".}
- Source Edit
proc adjacencyMatrix[T](graph: Graph[T]): seq[seq[int]]
- Source Edit
proc incidenceMatrix(graph: Graph): seq[seq[int]]
- Source Edit
proc deleteVertex[T](graph: var Graph[T]; vertex: Vertex[T]): bool
- Source Edit
proc deleteEdge[T](graph: var Graph[T]; edge: Edge[T]): bool
- Source Edit
proc `<`[T, C](p1, p2: PriorityNode[T, C]): bool
- Internal function. Won't be usable because the PriorityNode itself is private. Added to support priority queue that requires this operator visible in the priority queue module. Source Edit
proc a*[T, C](graph: var Graph[T]; start, goal: T): seq[Vertex[T]]
-
A* search based on its start (v1) label (v2) to end. Users need to provide accessible proc cost(v1, v2: T): C and proc distance(v1, v2: T): C with T is matched with Graph[T] and C is Addable and Comparable type. In rare case users could also need to provide operator "+" and "<" for C that returns the C type itself viz
proc `+`(cost1, cost2: C): C
andproc `<`(cost1, cost2: C): bool
. Additionally users could be needed to provide the hash proc for T, i.e proc hash(t: T): Hash. Check the std/hashes on how to do it. Source Edit