graph2.nim

import tables, sets, queues
import strutils, sequtils

type
  GraphObj = object
    matrix: Table[string, seq[string]]
    root: string
  Graph* = ref GraphObj

discard """
Loads a graph from a file using adjacency lists
Example:
A B C
B D
D
C E
E Q
Q R
R

And a valid dfs would look like: A, B, D, C, E, Q, R
"""
proc loadGraphFromFile*(filename: string): Graph =
  new(result)
  result.matrix = initTable[string, seq[string]]()
  result.root = ""

  var file: File
  if open(file, filename):
    #Parse the adjecency list
    var firstRun: bool = true
    for line in file.lines:
      var neighbours = line.split(" ")

      #The first node is the node we are finding the neighbours of
      var node = neighbours[0]

      #Useful if we want to define a root for a tree
      if firstRun:
        result.root = node
        firstRun = false

      #Remove the node we are finding the neighbours of
      delete(neighbours, 0, 0)

      #Initialize the sequence of neighbours, use a temp seq to work around an
      #odd nim bug
      var tmpSeq = newSeq[string]()

      for n in neighbours:
        tmpSeq.add(n)

      #Finish working around the odd nim bug.
      result.matrix[node] = tmpSeq

proc traverse(g: Graph, root: string, visited: var HashSet[string]) =
  #Really just a derpy dfs
  visited.incl(root)
  for neighbour in g.matrix[root]:
    if neighbour notin visited:
      g.traverse(neighbour, visited)


proc nodeCount*(g: Graph, root: string): int =
  #Traverse wrapper
  var visited: HashSet[string] = initSet[string]()
  traverse(g, root, visited)
  return len(visited)

proc connected*(g: Graph): bool =
  #Determines if all nodes on a graph are connected
  var numNodes: int = len(g.matrix)

  #Loop over the keys..
  for v in g.matrix.keys():
    #If traversing any vertex hits all nodes, connected.
    if nodeCount(g, v) == numNodes:
      return true
  return false

proc connectedNonZeroDegree*(g: Graph): bool =
  #Determines if all nodes with non-zero degree on a graph are connected
  var numNonZero: int = 0

  #Loop through the keys
  for u in g.matrix.keys():
    #If it has outgoing, it isn't zero degree
    if len(g.matrix[u]) != 0:
      numNonZero += 1
      continue

    #Loop through the keys again...
    for v in g.matrix.keys():

      #If the vertex is present, it has an incoming edge. Not zero degree
      if u in g.matrix[v]:
        numNonZero += 1
        break

  #See if any vertex hits all vertices when traversing...
  for v in g.matrix.keys():
    if nodeCount(g, v) == numNonZero:
      return true

  return false

proc dijkstra*(g: Graph, start: string) =
  discard

proc undirectedEulerianCycle*(g: Graph): bool =
  #An undirected graph has an eulerian cycle if all of its vertices have an even
  #degree and all of its non zero degree vertices are connected
  if not connectedNonZeroDegree(g):
    return false

  for vertex in g.matrix.values():
    if len(vertex) mod 2 != 0:
      return false
  return true

proc undirectedEulerianTrail*(g: Graph): bool =
  #An undirecred graph has an eulerian trail if at most two of its vertices have
  #an odd degree and all of its non zero degree vertices are connected
  if not connectedNonZeroDegree(g):
    return false

  var oddCount: int = 0
  for vertex in g.matrix.values():
    if len(vertex) mod 2 != 0:
      oddCount += 1
    if oddCount > 2:
      return false

  return true

proc directedEulerianCycle*(g: Graph): bool =
  #A directed graph has an eulerian cycle if all of its non-zero degree vertices
  #have an equal degree and all of its non-zero degree vertices are connected
  if not connectedNonZeroDegree(g):
    return false

  for u in g.matrix.keys():
    var outDegree: int = len(g.matrix[u])
    var inDegree: int = 0

    #Get in degree by looping over keys
    for v in g.matrix.keys():
      if u in g.matrix[v]:
        inDegree += 1

    if outDegree != inDegree:
      return false
  return true

proc directedEulerianTrail*(g: Graph): bool =
  #A directed graph has an eulerian trail if at most, 1 of its vertices has
  #(out degree) - (in degree) = 1 and at most 1 of its vertices has
  #(in degree) - (out degree) = 1 and all else are even
  if not connectedNonZeroDegree(g):
    return false

  var outMinusInCount: int = 0
  var inMinusOutCount: int = 0

  #Determine difference between in and out degrees for each vertex
  for u in g.matrix.keys():
    if outMinusInCount > 1 or inMinusOutCount > 1:
      return false

    #Outgoing edges of u
    var outDegree = len(g.matrix[u])

    #Find incoming edges of u
    var inDegree = 0
    for v in g.matrix.keys():
      if u in g.matrix[v]:
        inDegree += 1

    var outMinusIn = outDegree - inDegree
    if outMinusIn == 1:
      outMinusInCount += 1

    var inMinusOut = inDegree - outDegree
    if inMinusOut == 1:
      inMinusOutCount += 1

    if abs(outMinusIn) > 1 or abs(inMinusOut) > 1:
      return false

  return true

proc dfs(g: Graph, root: string, nodeInQuestion: string, visited: var HashSet[string]): string =
  #Actual dfs implementation
  visited.incl(root)

  #We found it!
  if root == nodeInQuestion:
    return root

  #Iterate over non-visited neighbours to recurse
  for neighbour in g.matrix[root]:
    if neighbour notin visited:

      #Did we find it? If so, return it
      if g.dfs(neighbour, nodeInQuestion, visited) != "":
        return nodeInQuestion

  #Didn't find it down this path
  return ""

proc dfs*(g: Graph, start: string, nodeInQuestion: string): string =
  #Graph wrapper
  var visited: HashSet[string] = initSet[string]()
  return g.dfs(start, nodeInQuestion, visited)

proc dfs*(g: Graph, nodeInQuestion: string): string =
  #Tree wrapper
  return g.dfs(g.root, nodeInQuestion)

proc bfs*(g: Graph, nodeInQuestion: string): string =
  var visited: HashSet[string] = initSet[string]()
  var q: Queue[string] = initQueue[string]()

  var start: string = g.root
  visited.incl(start)
  q.enqueue(start)
  while len(q) != 0:
    var workingNode = q.dequeue()

    #Found it
    if workingNode == nodeInQuestion:
      return workingNode

    var adjacencyList = g.matrix[workingNode]

    #Populate queue in a breadth first manner
    for node in adjacencyList:

      #Only add nodes to queue not previously there
      if node notin visited:
        visited.incl(visited)
        q.enqueue(node)

  #If wee don't fnid our node, return empty string
  return ""

var g: Graph = loadGraphFromFile("g1.txt")
echo(dfs(g, "Q"))
echo(bfs(g, "Q"))
echo(bfs(g, "Z"))
echo("CONNECTED: ", connected(g))
echo("CONNECTED NON-ZERO: ", connectedNonZeroDegree(g))
echo("HAS DIRECTED EULERIAN CYCLE: ", directedEulerianCycle(g))
echo("HAS DIRECTED EULERIAN TRAIL: ", directedEulerianTrail(g))
discard """
echo("----------------------")
g = loadGraphFromFile("g4.txt")
echo(dfs(g, "F"))
echo("CONNECTED: ", connected(g))
echo("CONNECTED NON-ZERO: ", connectedNonZeroDegree(g))
echo("HAS DIRECTED EULERIAN CYCLE: ", directedEulerianCycle(g))
echo("HAS DIRECTED EULERIAN TRAIL: ", directedEulerianTrail(g))
"""