#!/bin/bash
#---------------------------------------------------------------------
##
##
## @Synopsis A library for non-cyclic directed graph structures.
##
## @Copyright (C) 2002 Paul Mahon <dufflebunk@dufflebunk.homeip.net>
##
#---------------------------------------------------------------------


#---------------------------------------------------------------------
## @param data
## @param variable
## Creates a graph node and binds it to the specified variable.
#---------------------------------------------------------------------
function graph_new_node()  
{ #$1=data, $2=var to assign NODE to

	local NODE
	
	# Get a unique ID for this node. 
#	NODE_COUNT=${NODE_COUNT:-0} This must be set outside the function
	NODE=${NODE_COUNT}
	let NODE_COUNT++

	debug libgraph "graph_new_node() --- DB2 ($NODE / ${NODE_COUNT})"

	# Make sure this node doesn't exist
	[[ `hash_get "GRAPHS" "${NODE}_data"` ]] && return -1

	# Create node
	hash_put "GRAPHS" "${NODE}_data" "$1"

	# Bind the node to the variable and return the node's ID
	[[ $2 ]] && eval $2=$NODE
	return $NODE

}


#---------------------------------------------------------------------
## @param from-node
## @param to-node
## @param distance (optional)
## Connects two nodes with an optional distance
##
#---------------------------------------------------------------------
function graph_connect_node()
{ #$1=node start, $2=node end, $3(opt)distance

	hash_put "GRAPHS" "${1}_to_${2}" " $3 "

}


#---------------------------------------------------------------------
## @param node
## @Stdout all direct connections
## Prints all direct connections to and from this node.
##
#---------------------------------------------------------------------
function graph_node_connections()
{ #$1=node start

  graph_node_connections_to    $1
  graph_node_connections_from  $1
	
}


#---------------------------------------------------------------------
## @param node
## @Stdout all direct connections
## Prints all direct connections to this node.
##
#---------------------------------------------------------------------
function graph_node_connections_to()
{ #$1=node start
	
	hash_get_table_fields "GRAPHS" | sed -n 's/\([[:digit:]]*\)_to_'$1'.*$/\1/p'
}


#---------------------------------------------------------------------
## @param node
## @Stdout all direct connections
## Prints all direct connections from this node.
##
#---------------------------------------------------------------------
function graph_node_connections_from()
{ #$1=node start
	
	hash_get_table_fields "GRAPHS" | sed -n 's/'$1'_to_\([[:digit:]]*\).*$/\1/p'	
}


#---------------------------------------------------------------------
## @param node-from
## @param node-to
## Remove a connection from one node to another
##
#---------------------------------------------------------------------
function graph_disconnect_node()
{ #$1=node_start, $2=node end

	hash_unset "GRAPHS" "${1}_to_${2}"

}


#---------------------------------------------------------------------
## @param node-from
## @param node-to
## Remove a connection from one node to another
##
#---------------------------------------------------------------------
function graph_unset_node()
{ #$1=node

	local i

	hash_unset "GRAPHS" "${1}_data"
	for i in `graph_node_connections_from  $1` ; do
	  graph_disconnect_node $1 $i
	done
	for i in `graph_node_connections_to  $1` ; do
	  graph_disconnect_node $i $1
	done
	
}

#---------------------------------------------------------------------
## @param node
## @Stdout nodedata
## Prints the node's data
##
#---------------------------------------------------------------------
function graph_node_data()
{ #1=node

	hash_get "GRAPHS" "${1}_data"

}


#---------------------------------------------------------------------
## @param node
## @param data 
## @Stdout nodedata
## Prints the node's data
##
#---------------------------------------------------------------------
function graph_node_modify_data()
{ #1=node, 2=new data

  hash_put "GRAPHS" "${1}_data" "${2}"

}


#---------------------------------------------------------------------
## @Stdout connections
## Prints all nodes connected directly or indirectly from a node.
## Used to get all nodes in a connected graph
##
#---------------------------------------------------------------------
function graph_all_connected()
{ #$1=start node

	local numNodes=1 nodeList
	local i j newNodes
	
	nodeList[0]=$1

	for (( i=0 ; i<$numNodes ; i++ )) ; do
		newNodes=`graph_node_connections ${nodeList[$i]}`
		debug "libgraph" "graph_all_connected() --- newnodes=${newNodes}"
		for j in $newNodes ; do
			#If we already have the node in our main list, skip it
			echo " ${nodeList[*]} " | grep -q " $j " && continue
			nodeList[$numNodes]="$j"
			let numNodes++
		done
	done
	
	echo ${nodeList[*]}
	
}

function graph_all_downstream()
{ #1=start node

	local numNodes=1 nodeList
	local i j newNodes
	
	nodeList[0]=$1

	for (( i=0 ; i<$numNodes ; i++ )) ; do
		newNodes=`graph_node_connections_from ${nodeList[$i]}`
		debug "libgraph" "graph_all_downstream() --- newnodes=${newNodes}"
		for j in $newNodes ; do
			#If we already have the node in our main list, skip it
			echo " ${nodeList[*]} " | grep -q " $j " && continue
			nodeList[$numNodes]="$j"
			let numNodes++
		done
	done
	
	echo ${nodeList[*]}

}


function graph_all_upstream()
{ #1=start node

	local numNodes=1 nodeList
	local i j newNodes
	
	nodeList[0]=$1

	for (( i=0 ; i<$numNodes ; i++ )) ; do
		newNodes=`graph_node_connections_to ${nodeList[$i]}`
		debug "libgraph" "graph_all_upstream() --- newnodes=${newNodes}"
		for j in $newNodes ; do
			#If we already have the node in our main list, skip it
			echo " ${nodeList[*]} " | grep -q " $j " && continue
			nodeList[$numNodes]="$j"
			let numNodes++
		done
	done
	
	echo ${nodeList[*]}

}

#set -x
# Necessary for unique IDs of nodes:
NODE_COUNT=${NODE_COUNT:-0}


#---------------------------------------------------------------------
##
## This software is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 2 of the License, or
## (at your option) any later version.
##
## This software is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with this software; if not, write to the Free Software
## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
##
#---------------------------------------------------------------------
