#! /usr/bin/env python3
#
def digraph_dict_test ( ):

#*****************************************************************************80
#
## digraph_dict_test() tests digraph_dict().
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    04 April 2023
#
#  Author:
#
#    Original code by Bernd Klein,
#    Modifications by John Burkardt
#
#  Reference:
#
#    Bernd Klein,
#    Graph Theory and Graphs in Python,
#    https://python-course.eu/applications-python/graphs-python.php
#
  print ( '' )
  print ( 'digraph_dict_test():' )
  print ( '  Some simple functions for a directed graph ("digraph")' )
  print ( '  defined using a Python dictionary: 
  print ( '  digraph = { from0: [ to0, to1, ... tok], from1:[], ...}' )

  digraph = digraph_dict_example1 ( )
  print ( '' )
  print ( '  The digraph:' )
  print ( digraph )

  print ( '' )
  print ( '  Seek path from "a" to "b"' )
  path = digraph_dict_path_find ( digraph, "a", "b" )
  print ( path )

  nodes = digraph_dict_nodes_all ( digraph )
  print ( '' )
  print ( '  The nodes:' )
  print ( nodes )

  edges = digraph_dict_edges_all ( digraph )
  print ( '' )
  print ( '  The edges:' )
  print ( edges )

  digraph_dict_plot ( digraph )

  isolated = digraph_dict_find_isolated_nodes ( digraph )
  print ( '' )
  print ( '  The isolated nodes:' )
  print ( isolated )

  print ( '' )
  print ( '  Add node "c":' )
  digraph = digraph_dict_add_node ( digraph, 'c' )
  print ( '  Add node "h":' )
  digraph = digraph_dict_add_node ( digraph, 'h' )
  print ( '  Updated node list:' )
  nodes = digraph_dict_nodes_all ( digraph )
  print ( nodes )

  print ( '' )
  print ( '  Add edge "a->f":' )
  digraph = digraph_dict_add_edge ( digraph, [ 'a', 'f' ] )
  edges = digraph_dict_edges_all ( digraph )
  print ( '  Updated edge list.' )
  print ( edges )

  print ( '' )
  print ( '  List all edges from node "c":' )
  edges = digraph_dict_edges_node_from ( digraph, 'c' )
  print ( edges )

  print ( '' )
  print ( '  List all edges to node "c":' )
  edges = digraph_dict_edges_node_to ( digraph, 'c' )
  print ( edges )
#
#  Terminate.
#
  print ( '' )
  print ( 'digraph_dict_test():' )
  print ( '  Normal end of execution.' )

  return

def digraph_dict_add_edge ( digraph, e ):
  n0 = e[0]
  n1 = e[1]
  if ( n0 in digraph ):
    digraph[n0].append ( n1 )
  else:
    digraph[n0] = [ n1 ]
  return digraph

def digraph_dict_add_node ( digraph, n ):
  if ( n not in digraph ):
    digraph[n] = []
  else:
    print ( 'Node', n, 'is already in the digraph.' )
  return digraph

def digraph_dict_edges_all ( digraph ):
  edges = []
  for node in digraph.keys ( ):
    for neighbor in digraph[node]:
      edges.append ( [ node, neighbor ] )
  return edges

def digraph_dict_edges_node_from ( digraph, node ):
  edges = []
  if ( node in digraph.keys ( ) ):
    for dest in digraph[node]:
      edges.append ( [ node, dest ] )
  else:
    print ( node, 'is not a node of this digraph!' )
  return edges

def digraph_dict_edges_node_to ( digraph, node ):
  edges = []
  for src in digraph.keys ( ):
    if ( node in digraph[src] ):
      edges.append ( [ src, node ] )
  return edges

def digraph_dict_example1 ( ):
  digraph = { 
    "a" : [ "c" ],
    "b" : [ "c", ],
    "c" : [ "b", "d", "e" ], 
    "d" : [ "c" ], 
    "e" : [ "b" ], 
    "f" : [ ]
   }
  return digraph

def digraph_dict_find_isolated_nodes ( digraph ):
  isolated = list()
  for node in digraph:
    if ( not digraph[node] ):
      isolated.append ( node )
  return isolated

def digraph_dict_nodes_all ( digraph ):
  nodes = list ( digraph.keys ( ) )
  return nodes

def digraph_dict_path_find ( digraph, start_vertex, end_vertex, path = None ):
  if ( path == None ):
    path = []
  path = path + [ start_vertex ]
  if ( start_vertex == end_vertex ):
    return path
  if ( start_vertex not in digraph ):
    return None
  for vertex in digraph[start_vertex]:
    if ( vertex not in path ):
      extended_path = digraph_dict_path_find ( digraph, vertex, end_vertex, path )
      if ( extended_path ):
        return extended_path
  return None

def digraph_dict_plot ( digraph ):
  from graphviz import Digraph
  edges = digraph_dict_edges_all ( digraph )
  nodes = digraph_dict_nodes_all ( digraph )
  dot = Digraph ( format = 'png' )
  for n in nodes:
    dot.node ( n )
  for e in edges:
    dot.edge ( e[0], e[1] )
  dot.render ( 'digraph.dot', view = False )
  filename = 'digraph.dot.png'
  print ( '  Graphics saved as "%s"' % ( filename ) )
  return

def timestamp ( ):

#*****************************************************************************80
#
## timestamp() prints the date as a timestamp.
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    21 August 2019
#
#  Author:
#
#    John Burkardt
#
  import time

  t = time.time ( )
  print ( time.ctime ( t ) )

  return

if ( __name__ == "__main__" ):
  timestamp ( )
  digraph_dict_test ( )
  timestamp ( )