File Coverage

blib/lib/Graph/Dijkstra.pm

Criterion	Covered	Total	%
statement	16	18	88.8
branch			n/a
condition			n/a
subroutine	6	6	100.0
pod			n/a
total	22	24	91.6

package Graph::Dijkstra;

use strict;
use warnings;

use Carp qw(croak carp);

use English qw(-no_match_vars);
$OUTPUT_AUTOFLUSH=1;


use vars qw($VERSION);
$VERSION = '0.55';

my $VERBOSE = 0;

use Readonly;

Readonly my $EMPTY_STRING => q{};
Readonly my %IS_GRAPHML_WEIGHT_ATTR => map { ($_ => 1) } qw(weight value cost distance height);
Readonly my %IS_GRAPHML_LABEL_ATTR => map { ($_ => 1) } qw(label name description nlabel);
Readonly my $PINF => 1e9999;         # positive infinity
Readonly my %GRAPH_ATTRIBUTES => (label=>$EMPTY_STRING, creator=>$EMPTY_STRING, edgedefault=>'undirected');
Readonly my %NODE_ATTRIBUTES => (label=>$EMPTY_STRING);
Readonly my %EDGE_ATTRIBUTES => (id=>$EMPTY_STRING, label=>$EMPTY_STRING, directed=>'undirected', weight=>0);

## no critic (PostfixControls)

#############################################################################
#used Modules                                                               #
#############################################################################


use Benchmark qw(:hireswallclock);
use Array::Heap::ModifiablePriorityQueue;
use Scalar::Util qw(looks_like_number);
use HTML::Entities qw(encode_entities);
use utf8;

#############################################################################
#Class Methods                                                              #
#############################################################################

sub VERBOSE {
	my $either = shift;
	$VERBOSE = shift;
	print "verbose output set\n" if ($VERBOSE);
	return $either;
}

sub stringifyAttribs {
	my ($either, $attribHref) = @_;

	return if ref($attribHref) ne 'HASH';

	my $val = '';
	foreach my $attrib (sort keys %$attribHref) {
		$val .= ', ' if $val;
		my $printval = (looks_like_number($attribHref->{$attrib})) ? "$attribHref->{$attrib}" : "'".encode_entities($attribHref->{$attrib})."'";
		$val .= "$attrib=>$printval";
	}
	return "( $val )";
}

sub hashifyAttribs {
	my ($either, $attribStr) = @_;

	my %keyvals = ();

	if ($attribStr =~ /^\(\s*(.+)\s*\)$/) {
		$attribStr = $1;
	}
	while ($attribStr =~ /([a-z]+) => ([+-]? [0-9]+ (?: \. [0-9]+ )?+|(?:(?:\')(?:[^\\\']*(?:\\.[^\\\']*)*)(?:\')))/igx) {
		my $id = $1;
		my $val = $2;
		$val = substr($val,1,-1) if substr($val,0,1) eq "'";
		$keyvals{$id} = $val;
	}
	return \%keyvals;
}


sub _initialize {
	my ($self, $options) = @_;
	$self->{graph} = ();

	foreach my $attrib (keys %GRAPH_ATTRIBUTES) {
		$self->{$attrib} = $GRAPH_ATTRIBUTES{$attrib};
	}

	if (ref($options) eq 'HASH') {
		foreach my $attrib (keys %$options) {
			if (exists($GRAPH_ATTRIBUTES{$attrib})) {
				$self->{$attrib} = $options->{$attrib};
			}
			else {
				carp "new: unrecognized graph attribute '$attrib'";
			}
		}
	}
	return $self;
}

sub new {
	my ($class, $options) = @_;

	my $self = {};
  bless $self, $class;

  return $self->_initialize($options);

  #return $self;
}


#############################################################################
#Graph Method(s)                                                            #
#############################################################################

sub graph {
	my ($self, $options) = @_;
	if (defined($options) and ref($options) eq 'HASH') {  #SET method call
		foreach my $attrib (keys %$options) {
			if (exists($GRAPH_ATTRIBUTES{$attrib})) {
				utf8::upgrade($options->{$attrib});
				$self->{$attrib} = $options->{$attrib};
			}
			else {
				carp "new: unrecognized graph attribute '$attrib'";
			}
		}
		return $self;
	}
	#GET method call

	return( {map { ($_ => $self->{$_} ) } (keys %GRAPH_ATTRIBUTES)} );
}

#############################################################################
#Node Methods                                                               #
#############################################################################

sub node {
	my ($self, $nodeParam) = @_;

	croak "node: missing nodeID / options parameter" if !defined($nodeParam);

	if (ref($nodeParam) eq $EMPTY_STRING) {  #GET method call
		#my $nodeID = $nodeParam;

		if (exists($self->{graph}{$nodeParam})) {
			my %node = map { ($_ => $self->{graph}{$nodeParam}{$_} ) } (keys %NODE_ATTRIBUTES);
			$node{id} = $nodeParam;
			return( \%node );
		}
		return;
	}

	if (ref($nodeParam) eq 'HASH') {  #SET method call

		croak "node: missing \"id\" attribute in attributes hash" if !exists($nodeParam->{id});
		my $nodeID = $nodeParam->{id};
		croak "node: nodeID is not a SCALAR value" if ref($nodeID) ne $EMPTY_STRING;

		if (!exists($self->{graph}{$nodeID})) {  #set default node attribute values for new node
			foreach my $attrib (keys %NODE_ATTRIBUTES) {
				$self->{graph}{$nodeID}{$attrib} = $NODE_ATTRIBUTES{$attrib};
			}
		}

		foreach my $attrib (keys %$nodeParam) { #update node attribute values from parameter values
			if ( exists($NODE_ATTRIBUTES{$attrib}) ) {
				utf8::upgrade($nodeParam->{$attrib});
				$self->{graph}{$nodeID}{$attrib} = $nodeParam->{$attrib};
			}
			elsif ($attrib ne 'id') {
				carp "node: unrecognized node attribute '$attrib'";
			}
		}

		return $self;
	}
	croak "node: invalid parameter: must be either a nodeID (simple scalar) or an attributes hash (reference)";
}

sub nodeExists {
	my ($self, $nodeID) = @_;

	croak "nodeExists: missing nodeID parameter" if !defined($nodeID);

	return (exists($self->{graph}{$nodeID})) ? 1 : 0;
}


sub nodeList {
	my $self = shift;

	my @nodeList = ();
	foreach my $node (keys %{$self->{graph}}) {
		push(@nodeList, { id=>$node, map {($_ => $self->{graph}{$node}{$_})} (keys %NODE_ATTRIBUTES) } );
	}
	return @nodeList;
}


sub removeNode {
	my ($self, $nodeID) = @_;

	croak "removeNode: missing nodeID parameter" if !defined($nodeID);

	if (exists($self->{graph}{$nodeID})) {
		if (exists($self->{graph}{$nodeID}{edges})) {
			foreach my $targetID (sort keys %{$self->{graph}{$nodeID}{edges}}) {
				delete($self->{graph}{$targetID}{edges}{$nodeID});
			}
		}
		delete($self->{graph}{$nodeID});
		return $self;
	}
	return;
}

#############################################################################
#Edge Methods                                                               #
#############################################################################


sub edge {
	my ($self, $edgeHref) = @_;

	croak "edge: missing parameter hash reference" if !defined($edgeHref) or ref($edgeHref) ne 'HASH';
	croak "edge: parameter hash missing sourceID" if !exists($edgeHref->{sourceID});
	croak "edge: parameter hash missing targetID" if !exists($edgeHref->{targetID});

	my $sourceID = $edgeHref->{sourceID};
	my $targetID = $edgeHref->{targetID};

	if (defined( $edgeHref->{weight} )) {  #SET method call

		my $weight = $edgeHref->{weight};

		if ($weight <= 0) {
			carp "edge: invalid edge cost $sourceID $targetID $weight";
			return;
		}

		if ($sourceID eq $targetID) {
			carp "edge: source and target node IDs must be different";
			return;
		}

		if (!exists($self->{graph}{$sourceID})) {
			carp "edge: sourceID $sourceID does not exist.  Edge not created.";
			return;
		}
		if (!exists($self->{graph}{$targetID})) {
			carp "edge: targetID $targetID does not exist.  Edge not created.";
			return;
		}
		if (exists($edgeHref->{directed}) and ($edgeHref->{directed} ne 'directed' and $edgeHref->{directed} ne 'undirected')) {
			carp "edge: unrecognized 'directed' attribute value '$edgeHref->{directed}'.  Edge not created.";
			return;
		}

		$edgeHref->{directed} = $self->{edgedefault} if !exists($edgeHref->{directed});

		if (exists($self->{graph}{$sourceID}{edges}{$targetID}) and $self->{graph}{$sourceID}{edges}{$targetID}{directed} ne $edgeHref->{directed} ) {
			carp "edge: edge (arc) $sourceID $targetID exists with different directed value. Edge not created.";
			return;
		}
		if ($edgeHref->{directed} eq 'undirected' and exists($self->{graph}{$targetID}{edges}{$sourceID}) and $self->{graph}{$targetID}{edges}{$sourceID}{directed} eq 'directed') {
			carp "edge: directed arc (edge) $targetID $sourceID exists. Undirected edges $sourceID $targetID not created.";
			return;
		}

		if (!exists($self->{graph}{$sourceID}{edges}{$targetID})) {  #set default edge attribute values for new edge
			foreach my $attrib (keys %EDGE_ATTRIBUTES) {
				$self->{graph}{$sourceID}{edges}{$targetID}{$attrib} = $EDGE_ATTRIBUTES{$attrib};
				$self->{graph}{$targetID}{edges}{$sourceID}{$attrib} = $EDGE_ATTRIBUTES{$attrib} if $edgeHref->{directed} eq 'undirected';
			}
		}

		foreach my $attrib (keys %$edgeHref) { #update node attribute values from parameter values
			if ( exists($EDGE_ATTRIBUTES{$attrib}) ) {
				utf8::upgrade($edgeHref->{$attrib});
				$self->{graph}{$sourceID}{edges}{$targetID}{$attrib} = $edgeHref->{$attrib};
				$self->{graph}{$targetID}{edges}{$sourceID}{$attrib} = $edgeHref->{$attrib} if $edgeHref->{directed} eq 'undirected';
			}
			elsif ($attrib ne 'sourceID' and $attrib ne 'targetID') {
				carp "edge: unrecognized attribute '$attrib' not set";
			}
		}

		#$self->{graph}{$sourceID}{edges}{$targetID}{weight} = $weight;
		#$self->{graph}{$targetID}{edges}{$sourceID}{weight} = $weight;

		return($self);
	}
	else {  #GET method call

		if (exists($self->{graph}{$sourceID}{edges}{$targetID})) {
			#return( {sourceID=>$sourceID, targetID=>$targetID, weight=>$self->{graph}{$sourceID}{edges}{$targetID}{weight} } );
			return( {sourceID=>$sourceID, targetID=>$targetID, map { ($_ => $self->{graph}{$sourceID}{edges}{$targetID}{$_} ) } (keys %EDGE_ATTRIBUTES) } );
		}

		if (exists($self->{graph}{$sourceID}) and exists($self->{graph}{$targetID})) {
			return( {sourceID=>$sourceID, targetID=>$targetID, weight=>0} );
		}

		if (!exists($self->{graph}{$sourceID})) {
			carp "edge: sourceID $sourceID does not exist";
			return;
		}

		carp "edge: targetID $targetID does not exist";
		return;
	}
}


sub removeEdge {
	my ($self, $edgeHref) = @_;

	croak "removeEdge: missing parameter hash reference" if !defined($edgeHref);
	croak "removeEdge: parameter hash missing sourceID" if !exists($edgeHref->{sourceID});
	croak "removeEdge: parameter hash missing targetID" if !exists($edgeHref->{targetID});

	my $sourceID = $edgeHref->{sourceID};
	my $targetID = $edgeHref->{targetID};

	if (exists($self->{graph}{$sourceID}{edges}{$targetID})) {

		my $directed = $self->{graph}{$sourceID}{edges}{$targetID}{directed};

		delete($self->{graph}{$sourceID}{edges}{$targetID});

		my $hasNeighbors = 0;
		foreach my $neighbor (keys %{$self->{graph}{$sourceID}{edges}}) {
			$hasNeighbors = 1;
			last;
		}
		if (!$hasNeighbors) {
			delete($self->{graph}{$sourceID}{edges});
		}

		if ($directed eq 'undirected') {  #remove $targetID $sourceID for undirected edges

			delete($self->{graph}{$targetID}{edges}{$sourceID});

			my $hasNeighbors = 0;
			foreach my $neighbor (keys %{$self->{graph}{$targetID}{edges}}) {
				$hasNeighbors = 1;
				last;
			}
			if (!$hasNeighbors) {
				delete($self->{graph}{$targetID}{edges});
			}
		}
	}
	else {
		carp "removeEdge: no edge found for sourceID $sourceID and targetID $targetID";
	}

	return $self;
}



sub edgeExists {
	my ($self, $edgeHref) = @_;

	croak "edgeExists: missing parameter hash reference" if !defined($edgeHref);
	croak "edgeExists: parameter hash missing sourceID" if !exists($edgeHref->{sourceID});
	croak "edgeExists: parameter hash missing targetID" if !exists($edgeHref->{targetID});

	my $sourceID = $edgeHref->{sourceID};
	my $targetID = $edgeHref->{targetID};

	return (exists($self->{graph}{$sourceID}{edges}{$targetID})) ? 1 : 0;
}


sub adjacent {
	my ($self, $edgeHref) = @_;

	croak "adjacent: missing parameter hash reference" if !defined($edgeHref);
	croak "adjacent: parameter hash missing sourceID" if !exists($edgeHref->{sourceID});
	croak "adjacent: parameter hash missing targetID" if !exists($edgeHref->{targetID});

	my $sourceID = $edgeHref->{sourceID};
	my $targetID = $edgeHref->{targetID};

	return ( exists($self->{graph}{$sourceID}{edges}{$targetID}) ) ? 1 : 0;
}


sub adjacentNodes {
	my ($self, $sourceID) = @_;

	if (!defined($sourceID)) {
		croak "adjacentNodes: missing node ID parameter";
	}

	my @neighbors = ();
	if (exists($self->{graph}{$sourceID}{edges})) {
		foreach my $targetID (sort keys %{$self->{graph}{$sourceID}{edges}}) {
			push(@neighbors, $targetID);
		}
	}
	return @neighbors;
}



#############################################################################
#Dijkstra Computation Methods                                               #
#############################################################################

#Computes Jordan center by creating all pairs shortest path matrix

sub vertexCenter {
	my ($self, $solutionMatrix) = @_;

	%$solutionMatrix = ();

	my @connectedNodeList = ();

	my $totalNodes = 0;
	foreach my $nodeID ( keys %{$self->{graph}} ) {
		$totalNodes++;
		next if !exists($self->{graph}{$nodeID}{edges});	#exclude disconnected nodes.
		push(@connectedNodeList, $nodeID);
	}
	my $nodeCount = scalar(@connectedNodeList);
	print "vertexCenter: graph contains $nodeCount connected nodes (nodes >= 1 edges)\n" if $VERBOSE;
	carp "vertexCenter: excluded one or more disconnected nodes (nodes with no edges)" if ($nodeCount < $totalNodes);

	foreach my $fromNodeID (@connectedNodeList) {

		$solutionMatrix->{rowMax}{$fromNodeID} = $PINF;

		foreach my $toNodeID (@connectedNodeList) {
			$solutionMatrix->{row}{$fromNodeID}{$toNodeID} = $PINF;
		}
		$solutionMatrix->{row}{$fromNodeID}{$fromNodeID} = 0;
	}
	my $hasDirectedEdges = 0;
	foreach my $nodeID (@connectedNodeList) {
		foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
			if ($self->{graph}{$nodeID}{edges}{$targetID}{directed} eq 'directed') {
				$hasDirectedEdges = 1;
				last;
			}
		}
		last if $hasDirectedEdges;
	}
	my $matrixComputations = ($nodeCount * $nodeCount) - $nodeCount;
	$matrixComputations = $matrixComputations / 2 if !$hasDirectedEdges;
	print "vertexCenter: graph has directed edges.  Computing shortest path for A -> C and C -> A separately.\n" if $hasDirectedEdges and $VERBOSE;
	print "vertexCenter: graph has no directed edges.  Shortest path for A -> C and C -> A are same.\n" if !$hasDirectedEdges and $VERBOSE;
	print "vertexCenter: performing $matrixComputations shortest path computations.\n" if $VERBOSE;

	#should add code to limit computations at reasonable number

	my $cycle = 0;
	my $t0 = Benchmark->new;

	foreach my $origin (@connectedNodeList) {
		foreach my $destination (@connectedNodeList) {

			next if $solutionMatrix->{row}{$origin}{$destination} < $PINF or $origin eq $destination;
			#print "shortest path $origin -> $destination...";

			my $pq = Array::Heap::ModifiablePriorityQueue->new();

			my %solution = ();
			my %unvisited = ();
			foreach my $node (@connectedNodeList) {
				$solution{$node}{weight} = $PINF;
				$pq->add($node, $PINF);
			}

			$solution{$origin}{weight} = 0;
			$pq->add($origin,0); #modify weight of origin node


			#my $foundSolution = 0;
			while ($pq->size()) {
				$cycle++;

				my $visitNode = $pq->get();

				$solutionMatrix->{row}{$origin}{$visitNode} = $solution{$visitNode}{weight};
				$solutionMatrix->{row}{$visitNode}{$origin} = $solution{$visitNode}{weight} if !$hasDirectedEdges;

				last if ($visitNode eq $destination);

				foreach my $adjacentNode (keys %{$self->{graph}{$visitNode}{edges}}) {
					next if !defined($pq->weight($adjacentNode));

					my $thisWeight = $solution{$visitNode}{weight} + $self->{graph}{$visitNode}{edges}{$adjacentNode}{weight};
					if ($thisWeight < $solution{$adjacentNode}{weight}) {
						$solution{$adjacentNode}{weight} = $thisWeight;
					#	$solution{$adjacentNode}{prevnode} = $visitNode;
						$pq->add($adjacentNode, $thisWeight);
					}
				}
			}

			undef($pq);
		}
	}
	if ($VERBOSE) {
		my $t1 = Benchmark->new;
		#if ($cycle >= 1000) {
		#	print "\n";
		#}
		my $td = timediff($t1, $t0);
	  print "computing shortest path matrix took: ",timestr($td),"\n";
	}
	my $graphMinMax = $PINF;
	my $centerNode = '';
	foreach my $origin (@connectedNodeList) {
		my $rowMax = 0;
		foreach my $destination (@connectedNodeList) {
			next if $origin eq $destination;
			if ($solutionMatrix->{row}{$origin}{$destination} > $rowMax) {
				$rowMax = $solutionMatrix->{row}{$origin}{$destination};
			}
		}
		$solutionMatrix->{rowMax}{$origin} = $rowMax;
		if ($rowMax < $graphMinMax) {
			$graphMinMax = $rowMax;
		}
	}
	$solutionMatrix->{centerNodeSet} = [];
	if ($graphMinMax < $PINF) {
		foreach my $origin (@connectedNodeList) {
			if ($solutionMatrix->{rowMax}{$origin} == $graphMinMax) {
				push(@{$solutionMatrix->{centerNodeSet}}, $origin);
			}
		}
	}
	else {
		carp "Graph contains disconnected sub-graph. Center node set undefined.";
		$graphMinMax = 0;
	}
	#print "centernodeset ", join(',', @{$solutionMatrix->{centerNodeSet}}), "\n";
	return($graphMinMax);
}

sub farthestNode {  ## no critic (ProhibitExcessComplexity)
	my ($self, $solutionHref) = @_;

	if (!exists($solutionHref->{originID})) {
		croak "farthestNode: originID attribute not set in solution hash reference parameter";
	}
	my $originID = $solutionHref->{originID};

	if (!exists($self->{graph}{$originID})) {
		carp "farthestNode: originID not found: $originID";
		return 0;
	}
	elsif (!exists($self->{graph}{$originID}{edges})) {
		carp "farthestNode: origin node $originID has no edges";
		return 0;
	}
	my $pq = Array::Heap::ModifiablePriorityQueue->new();

	my %solution = ();		#initialize the solution hash
	my %unvisited = ();
	foreach my $node (keys %{$self->{graph}}) {
		if (exists($self->{graph}{$node}{edges})) {  #nodes without edges cannot be part of the solution
			$solution{$node}{weight} = $PINF;
			$solution{$node}{prevnode} = $EMPTY_STRING;
			$pq->add($node, $PINF);
		}
	}

	$solution{$originID}{weight} = 0;
	$pq->add($originID,0); #modify weight of origin node

	my $cycle = 0;
	my $t0 = Benchmark->new;

	while ($pq->size()) {
		$cycle++;
		#print '.' if $VERBOSE and ($cycle % 1000 == 0);

		my $visitNode = $pq->get();

		foreach my $adjacentNode (keys %{$self->{graph}{$visitNode}{edges}}) {
			next if !defined($pq->weight($adjacentNode));

			my $thisWeight = $solution{$visitNode}{weight} + $self->{graph}{$visitNode}{edges}{$adjacentNode}{weight};
			if ($thisWeight < $solution{$adjacentNode}{weight}) {
				$solution{$adjacentNode}{weight} = $thisWeight;
				$solution{$adjacentNode}{prevnode} = $visitNode;
				$pq->add($adjacentNode, $thisWeight);
			}
		}
	}
	if ($VERBOSE) {
		my $t1 = Benchmark->new;
		#if ($cycle >= 1000) {
		#	print "\n";
		#}
		my $td = timediff($t1, $t0);
	  print "dijkstra's algorithm took: ",timestr($td),"\n";
	}

	my $farthestWeight = 0;
	foreach my $node (sort keys %solution) {
		if ($solution{$node}{weight} < $PINF and $solution{$node}{weight} > $farthestWeight) {
			$farthestWeight = $solution{$node}{weight};
			#$farthestnode = $node;
		}
	}

	my $solutioncnt = 0;
	%{$solutionHref} = (
		desc => 'farthest',
		originID => $originID,
		weight => $farthestWeight,
	);

	foreach my $farthestnode (sort keys %solution) {
		if ($solution{$farthestnode}{weight} == $farthestWeight) {

			$solutioncnt++;

			print "\nfarthestNode: (solution $solutioncnt) farthest node from origin $originID is $farthestnode at weight (cost) $farthestWeight\n" if $VERBOSE;

			my $fromNode = $solution{$farthestnode}{prevnode};
			my @path = ( $farthestnode, $fromNode );

			my %loopCheck = ();
			while ($solution{$fromNode}{prevnode} ne $EMPTY_STRING) {
				$fromNode = $solution{$fromNode}{prevnode};
				if (exists($loopCheck{$fromNode})) {
					print "farthestNode: path loop at $fromNode\n";
					print 'farthestNode: path = ', join(',',@path), "\n";
					die 'farthestNode internal error: destination to origin path logic error';
				}
				$loopCheck{$fromNode} = 1;
				push(@path,$fromNode);
			}

			@path = reverse(@path);

			my $nexttolast = $#path - 1;

			$solutionHref->{path}{$solutioncnt}{destinationID} = $farthestnode;
			$solutionHref->{path}{$solutioncnt}{edges} = [];

			foreach my $i (0 .. $nexttolast) {

				push(@{$solutionHref->{path}{$solutioncnt}{edges}}, {sourceID => $path[$i], targetID => $path[$i+1], weight => $self->edge( { sourceID=>$path[$i], targetID=>$path[$i+1] } )->{weight} } );

			}
		}
	}

	$solutionHref->{count} = $solutioncnt;

	return($farthestWeight);
}

sub shortestPath { ## no critic (ProhibitExcessComplexity)
	my ($self, $solutionHref) = @_;

	if (!exists($solutionHref->{originID})) {
		croak "farthestNode: originID attribute not set in solution hash reference parameter";
	}
	my $originID = $solutionHref->{originID};

	if (!exists($solutionHref->{destinationID})) {
		croak "farthestNode: destinationID attribute not set in solution hash reference parameter";
	}
	my $destinationID = $solutionHref->{destinationID};

	if (!exists($self->{graph}{$originID})) {
		carp "shortestPath: originID not found: $originID";
		return 0;
	}

	if (!exists($self->{graph}{$originID}{edges})) {
		carp "shortestPath: origin node $originID has no edges";
		return 0;
	}
	if (!exists($self->{graph}{$destinationID})) {
		carp "shortestPath: destinationID not found: $destinationID";
		return 0;
	}
	if (!exists($self->{graph}{$destinationID}{edges})) {
		carp "shortestPath: destination node $destinationID has no edges";
		return 0;
	}

	my $pq = Array::Heap::ModifiablePriorityQueue->new();

	my %solution = ();		#initialize the solution hash
	my %unvisited = ();
	foreach my $node (keys %{$self->{graph}}) {
		if (exists($self->{graph}{$node}{edges})) {  #nodes without edges cannot be part of the solution
			$solution{$node}{weight} = $PINF;
			$solution{$node}{prevnode} = $EMPTY_STRING;
			$pq->add($node, $PINF);
		}
	}

	$solution{$originID}{weight} = 0;
	$pq->add($originID,0); #modify weight of origin node

	my $cycle = 0;
	my $t0 = Benchmark->new;

	my $foundSolution = 0;
	while ($pq->size()) {
		$cycle++;
		#print '.' if $VERBOSE and ($cycle % 1000 == 0);

		my $visitNode = $pq->get();

		if ($visitNode eq $destinationID) {
			$foundSolution = 1 if $solution{$visitNode}{weight} < $PINF;
			last;
		}

		foreach my $adjacentNode (keys %{$self->{graph}{$visitNode}{edges}}) {
			next if !defined($pq->weight($adjacentNode));

			my $thisWeight = $solution{$visitNode}{weight} + $self->{graph}{$visitNode}{edges}{$adjacentNode}{weight};
			if ($thisWeight < $solution{$adjacentNode}{weight}) {
				$solution{$adjacentNode}{weight} = $thisWeight;
				$solution{$adjacentNode}{prevnode} = $visitNode;
				$pq->add($adjacentNode, $thisWeight);
			}
		}
	}
	if ($VERBOSE) {
		my $t1 = Benchmark->new;
		#if ($cycle >= 1000) {
		#	print "\n";
		#}
		my $td = timediff($t1, $t0);
	  print "dijkstra's algorithm took: ",timestr($td),"\n";
	}

  my $pathWeight = 0;
  if ($foundSolution) {
	  $pathWeight = $solution{$destinationID}{weight};
		print "shortestPath: pathWeight (cost) = $pathWeight\n" if $VERBOSE;

		my $solutioncnt = 0;
		%{$solutionHref} = (
			desc => 'path',
			originID => $originID,
			destinationID => $destinationID,
			weight => $pathWeight,
		);

		my $fromNode = $solution{$destinationID}{prevnode};
		my @path = ( $destinationID, $fromNode );

		my %loopCheck = ();
		while ($solution{$fromNode}{prevnode} ne $EMPTY_STRING) {
			$fromNode = $solution{$fromNode}{prevnode};
			if (exists($loopCheck{$fromNode})) {
				print "shortestPath: path loop at $fromNode\n";
				print "shortestPath: path = ", join(',',@path), "\n";
				die "shortestPath internal error: destination to origin path logic error";
			}
			$loopCheck{$fromNode} = 1;
			push(@path,$fromNode);
		}

		@path = reverse(@path);

		my $nexttolast = $#path - 1;
		foreach my $i (0 .. $nexttolast) {
			push(@{$solutionHref->{edges}}, {sourceID => $path[$i], targetID => $path[$i+1], weight => $self->edge( { sourceID=>$path[$i], targetID=>$path[$i+1] } )->{weight} } );
		}
	}
	return($pathWeight);
}



#############################################################################
#input / output file methods                                                #
#############################################################################

{ #CSV file format methods

	use Text::CSV_XS;

	sub getRowHref {
		my $row = shift;
		my $attribStr = $EMPTY_STRING;
		foreach my $i (1 .. $#$row) {
			$attribStr .= ', ' if $attribStr;
			$attribStr .= $row->[$i];
		}
		return Graph::Dijkstra->hashifyAttribs( "($attribStr)" );
	}

	sub inputGraphfromCSV {
		my ($self, $filename) = @_;

		if (!ref($self)) {
			$self = Graph::Dijkstra->new();
		}

		my $nodecount = 0;
		my $edgecount = 0;

		open(my $infile, '<:encoding(UTF-8)', $filename) or croak "could not open '$filename'";

		print "inputGraphfromCSV: opened '$filename' for input\n" if $VERBOSE;

		my $csv = Text::CSV_XS->new ({ binary => 1, auto_diag => 1 });
		while (my $row = $csv->getline ($infile)) {
			if (lc($row->[0]) eq 'graph') {
				$self->graph( getRowHref( $row ) ) if $#$row;
			}
			elsif (lc($row->[0]) eq 'node') {
				$self->node( getRowHref( $row ) );
				$nodecount++;
			}
			elsif (lc($row->[0]) eq 'edge') {
				$self->edge( getRowHref( $row ) );
				$edgecount++;
			}
		}
		close($infile);

		carp "inputGraphfromCSV: no nodes read from '$filename'" if !$nodecount;
		carp "inputGraphfromCSV: no edges read from '$filename'" if !$edgecount;

		print "inputGraphfromCSV: found $nodecount nodes and $edgecount edges\n" if $VERBOSE;
		return $self;
	}

	sub makeRow {
		my $href = shift;
		my @rowdata = ();
		foreach my $attrib (sort keys %$href) {
			next if $href->{$attrib} eq $EMPTY_STRING;
			my $printVal = (looks_like_number($href->{$attrib})) ? $href->{$attrib} : "'$href->{$attrib}'";
			push(@rowdata, "$attrib=>$printVal");
		}
		return @rowdata;
	}

	sub outputGraphtoCSV {
		my ($self, $filename) = @_;

		open(my $outfile, '>:encoding(UTF-8)', $filename) or croak "could not open '$filename'";

		print "outputGraphtoCSV: opened '$filename' for output\n" if $VERBOSE;

		my $csv = Text::CSV_XS->new ({ binary => 1, auto_diag => 1 });

		my $nodecount = 0;
		my $edgecount = 0;
		my $graphHref = $self->graph();

		$csv->say( $outfile, ['graph', makeRow( $self->graph() ) ] );

		my $graphDirected = $self->{edgedefault};

		my %edges = ();
		foreach my $nodeID (keys %{$self->{graph}}) {

			$csv->say($outfile, ['node', makeRow( $self->node($nodeID) ) ]);

			$nodecount++;
			if (exists($self->{graph}{$nodeID}{edges})) {
				foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
					my $edgeDirected = $self->{graph}{$nodeID}{edges}{$targetID}{directed};
					if ( ($edgeDirected eq 'undirected' and !exists($edges{$targetID}{$nodeID})) or $edgeDirected eq 'directed') {
						$edges{$nodeID}{$targetID}{weight} = $self->{graph}{$nodeID}{edges}{$targetID}{weight};
					}
				}
			}
		}
		foreach my $sourceID (keys %edges) {
			foreach my $targetID (keys %{$edges{$sourceID}}) {

				$csv->say($outfile, ['edge', makeRow( $self->edge( {sourceID=>$sourceID, targetID=>$targetID} ) ) ]);

				$edgecount++;
			}
		}
		close($outfile);
		print "outputGraphtoCSV: wrote $nodecount nodes and $edgecount edges to '$filename'\n" if $VERBOSE;

		return $self;
	}

	sub outputAPSPmatrixtoCSV {
		my ($either, $solutionMatrix, $filename, $labelSort) = @_;

		$labelSort = '' if !defined($labelSort);

		open(my $outfile, '>:encoding(UTF-8)', $filename) or croak "could not open '$filename'";

		print "outputAPSPmatrixtoCSV: opened '$filename' for output\n" if $VERBOSE;

		my $csv = Text::CSV_XS->new ({ binary => 1, auto_diag => 1 });

		my @nodeList = (lc($labelSort) eq 'numeric') ? (sort {$a <=> $b} keys %{$solutionMatrix->{row}}) : (sort keys %{$solutionMatrix->{row}});

		$csv->say($outfile, ['From/To', @nodeList ]);
		my $rowcount = 1;

		foreach my $nodeID (@nodeList) {
			my @row = ();
			foreach my $destinationID (@nodeList) {
				push(@row, $solutionMatrix->{row}{$nodeID}{$destinationID});
			}
			$csv->say($outfile, [$nodeID, @row]);
			$rowcount++;
		}
		close($outfile);
		print "outputAPSPmatrixtoCSV: wrote $rowcount rows to '$filename'\n" if $VERBOSE;
		return $either;

	}

} #CSV file format I/O methods

#############################################################################
#JSON Graph Specification file format methods                               #
#############################################################################
{

	use JSON;

	sub inputGraphfromJSON {
		my ($self, $filename, $options) = @_;

		if (!ref($self)) {
			$self = Graph::Dijkstra->new();
		}

		my $json_text = $EMPTY_STRING;
		open(my $infile, '<:encoding(UTF-8)', $filename) or croak "could not open '$filename'";

		print "inputGraphfromJSON: opened '$filename' for input\n" if $VERBOSE;

		while (my $line = <$infile>) {
			$json_text .= $line;
		}
		close($infile);

		my $graphHref = from_json( $json_text, {utf8 => 1} ) or croak "inputGraphfromJSON: invalid json text";

		if (ref($graphHref) ne 'HASH') {
			croak "inputGraphfromJSON: invalid JSON text";
		}

		if (exists($graphHref->{graphs})) {
			croak "inputGraphfromJSON: JSON \"multi graph\" type not supported";
		}
		if (!exists($graphHref->{graph}{edges})) {
			croak "inputGraphfromJSON: not a JSON graph specification or graph has no edges";
		}
		my $edgeWeightKey = (defined($options) and ref($options) eq 'HASH' and exists($options->{edgeWeightKey})) ? $options->{edgeWeightKey} : 'value';

		my $graphDirected = 'undirected';
		if (exists($graphHref->{graph}{directed}) and $graphHref->{graph}{directed} ) {
			$graphDirected = 'directed';
		}
		print "inputGraphfromJSON: graph edge default is '$graphDirected'.\n" if $VERBOSE;

		$self->graph( {label=>$graphHref->{graph}{label} } ) if exists($graphHref->{graph}{label});
		$self->graph( {creator=>$graphHref->{graph}{metadata}{creator} } ) if exists($graphHref->{graph}{metadata}{creator});

		my $nodecount = 0;
		my $edgecount = 0;
		my $dupedgecount = 0;

		foreach my $nodeHref (@{$graphHref->{graph}{nodes}}) {
			$nodecount++;
			$self->node( {id=>$nodeHref->{id}, label=>$nodeHref->{label} } );
		}
		foreach my $edgeHref (@{$graphHref->{graph}{edges}}) {

			my $edgeDirected = $graphDirected;
			if (exists($edgeHref->{directed})) {
				$edgeDirected = ($edgeHref->{directed}) ? 'directed' : 'undirected';
			}
			my $edgeLabel = $edgeHref->{label} || $EMPTY_STRING;
			my $edgeID = $edgeHref->{metadata}{id} || $EMPTY_STRING;
			my $weight = $edgeHref->{metadata}{$edgeWeightKey} || 1;

			$edgecount++;
			$dupedgecount++ if $self->edgeExists( { sourceID=>$edgeHref->{source}, targetID=>$edgeHref->{target} } );
			$self->edge( { sourceID=>$edgeHref->{source}, targetID=>$edgeHref->{target}, weight=>$weight, label=>$edgeLabel, directed=>$edgeDirected, id=>$edgeID } );
		}

		carp "inputGraphfromJSON: no nodes read from '$filename'" if !$nodecount;
		carp "inputGraphfromJSON: no edges read from '$filename'" if !$edgecount;

		print "inputGraphfromJSON: found $nodecount nodes and $edgecount edges\n" if $VERBOSE;
		print "inputGraphfromJSON: found $dupedgecount duplicate edges\n" if $dupedgecount and $VERBOSE;

		return $self;
	}


	sub outputGraphtoJSON {
		my ($self, $filename, $options) = @_;

		my $nodecount = 0;
		my $edgecount = 0;

		my %graph = ();
		my $graphDirected = $self->{edgedefault};

		$graph{graph}{directed} = ($graphDirected eq 'directed') ? JSON::true : JSON::false;
		@{$graph{graph}{nodes}} = ();
		@{$graph{graph}{edges}} = ();

		$graph{graph}{metadata}{comment} = 'generated by Graph::Dijkstra on ' . localtime;
		$graph{graph}{label} = $self->{label} if $self->{label};
		$graph{graph}{metadata}{creator} = $self->{creator} if $self->{creator};

		my $edgeWeightKey = (defined($options) and ref($options) eq 'HASH' and exists($options->{edgeWeightKey})) ? $options->{edgeWeightKey} : 'value';

		my %edges = ();
		foreach my $nodeID (keys %{$self->{graph}}) {

			push(@{$graph{graph}{nodes}}, { id => $nodeID, label => $self->{graph}{$nodeID}{label} } );

			$nodecount++;
			if (exists($self->{graph}{$nodeID}{edges})) {
				foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {

					my $edgeDirected = $self->{graph}{$nodeID}{edges}{$targetID}{directed};
					if ( ($edgeDirected eq 'undirected' and !exists($edges{$targetID}{$nodeID})) or $edgeDirected eq 'directed') {

						$edges{$nodeID}{$targetID} = 1;
						my %edgeData = ( source => $nodeID, target => $targetID, metadata => {$edgeWeightKey => $self->{graph}{$nodeID}{edges}{$targetID}{weight} } );

						$edgeData{label} = $self->{graph}{$nodeID}{edges}{$targetID}{label} if $self->{graph}{$nodeID}{edges}{$targetID}{label};

						if ($edgeDirected ne $graphDirected) {
							$edgeData{directed} = ($edgeDirected eq 'directed') ? JSON::true : JSON::false;
						}
						if ($self->{graph}{$nodeID}{edges}{$targetID}{id} ne $EMPTY_STRING) {
							$edgeData{metadata}{id} = $self->{graph}{$nodeID}{edges}{$targetID}{id};
						}

						push( @{$graph{graph}{edges}}, \%edgeData );
						$edgecount++;
					}
				}
			}
		}

		my $json_text = to_json(\%graph, {utf8 => 1, pretty => 1});

		open(my $outfile, '>:encoding(UTF-8)', $filename) or croak "could not open '$filename'";

		print "outputGraphtoJSON: opened '$filename' for output\n" if $VERBOSE;
		print {$outfile} $json_text;
		close($outfile);
		print "outputGraphtoJSON: wrote $nodecount nodes and $edgecount edges to '$filename'\n" if $VERBOSE;

		return $self;
	}

} #JSON Graph Specification file format methods

#############################################################################
#GML file format methods                                                    #
#############################################################################
{

	use Regexp::Common;

	sub inputGraphfromGML { ## no critic (ProhibitExcessComplexity)
		my ($self, $filename) = @_;

		if (!ref($self)) {
			$self = Graph::Dijkstra->new();
		}
		my $buffer = $EMPTY_STRING;
		my $linecount = 0;
		open(my $infile, '<:encoding(UTF-8)', $filename) or croak "could not open '$filename'";

		print "inputGraphfromGML: opened '$filename' for input\n" if $VERBOSE;

		while (my $line = <$infile>) {
			next if substr($line,0,1) eq '#';
			$buffer .= $line;
			$linecount++;
		}
		close($infile);
		print "inputGraphfromGML: read $linecount lines\n" if $VERBOSE;

		if ($buffer !~ /graph\s+\[.+?(?:node|edge)\s+\[/ixs) {
			croak "file does not appear to be GML format";
		}

		my $graphDirected = 'undirected';

		if ($buffer =~ /graph\s+\[\s+directed\s+(\d)/ixs) {
			$graphDirected = ($1) ? 'directed' : 'undirected';
		}

		print "inputGraphfromGML: graph edge default = '$graphDirected'\n" if $VERBOSE;
		$self->graph( { edgedefault=>$graphDirected } );

		if ($buffer =~ /^\s*creator\s+\"([^\"]+)\"/i) {
			my $creator = $1;
			$self->graph( {creator=>$creator} );
			print "inputGraphfromGML: graph attribute creator set: $creator\n" if $VERBOSE;

		}

		my $has_graphics_elements = ($buffer =~ /graphics\s+\[/) ? 1 : 0;
		print "GML file contain graphics elements\n" if ($VERBOSE and $has_graphics_elements);

		my $balancedRE = $RE{balanced}{-parens=>'[]'};


		my $nodecount = 0;
		my $edgecount = 0;
		my $dupedgecount = 0;

		while ($buffer =~ /(node|edge)\s+$balancedRE/gixso) {
			my $type = lc($1);
			my $attribs = $2;
			#my $bufferPos = $-[0];

			$attribs = substr($attribs, 1, -1);

			$attribs =~ s/graphics\s+$balancedRE//xio if $has_graphics_elements and $type eq 'node';

			my %keyvals = ();
			while ($attribs =~/(id|label|source|target|value)\s+(?|([0-9\.]+)|\"([^\"]+)\")/gixs) {
				my $attrib = lc($1);
				my $attribValue = $2;
				if ($type eq 'edge' and $attrib eq 'value' and !looks_like_number($attribValue)) {
					carp "non-numeric edge value '$attribValue'.  Skipped.";
					next;
				}
				$keyvals{$attrib} = $attribValue;
			}

			if ($type eq 'node') {
				$nodecount++;
				if (exists($keyvals{id})) {
					$self->{graph}{$keyvals{id}}{label} = $keyvals{label} || $EMPTY_STRING;
				}
				else {
					croak "inputGraphfromGML: node: missing id problem -- matched attribs: '$attribs'";
				}
			}
			else {
				$edgecount++;
				my $edgeLabel = $keyvals{label} || $EMPTY_STRING;
				if (exists($keyvals{source}) and exists($keyvals{target}) and exists($keyvals{value}) and $keyvals{value} > 0) {
					$dupedgecount++ if $self->edgeExists( { sourceID=>$keyvals{source}, targetID=>$keyvals{target} } );
					$self->edge( { sourceID=>$keyvals{source}, targetID=>$keyvals{target}, weight=>$keyvals{value}, label=>$edgeLabel, directed=>$graphDirected } );
				}
				else {
					croak "inputGraphfromGML: edge: missing source, target, value, or value <= 0 problem -- matched attribs '$attribs'";
				}
			}
		}

		carp "inputGraphfromGML: no nodes read from '$filename'" if !$nodecount;
		carp "inputGraphfromGML: no edges read from '$filename'" if !$edgecount;

		print "inputGraphfromGML: found $nodecount nodes and $edgecount edges\n" if $VERBOSE;
		print "inputGraphfromGML: found $dupedgecount duplicate edges\n" if $dupedgecount and $VERBOSE;

		return $self;
	}


	sub outputGraphtoGML {
		my ($self, $filename) = @_;

		open(my $outfile, '>:encoding(UTF-8)', $filename) or croak "could not open '$filename' for output";

		print "outputGraphtoGML: opened '$filename' for output\n" if $VERBOSE;

		{
			my $now_string = localtime;
			print {$outfile} "# Generated by Graph::Dijkstra on $now_string\n";
		}

		print {$outfile} "Creator \"$self->{creator}\"\n" if $self->{creator};
		my $graphDirected = ($self->{edgedefault} eq 'directed') ? 1 : 0;
		print {$outfile} "Graph [\n\tDirected ", (($self->{edgedefault} eq 'directed') ? 1 : 0), "\n";
		$graphDirected = $self->{edgedefault};

		my $nodecount = 0;
		my $edgecount = 0;

		my %edges = ();
		foreach my $nodeID (keys %{$self->{graph}}) {
			my $nodeIDprint = (looks_like_number($nodeID)) ? $nodeID : '"' . encode_entities($nodeID) . '"';
			my $nodeLabel = encode_entities($self->{graph}{$nodeID}{label});
			print {$outfile} "\tnode [\n\t\tid $nodeIDprint\n\t\tlabel \"$nodeLabel\"\n\t]\n";
			$nodecount++;
			if (exists($self->{graph}{$nodeID}{edges})) {
				foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
					croak "outputGraphtoGML: internal graph includes both directed and undirected edges. Not supported by GML format." if $self->{graph}{$nodeID}{edges}{$targetID}{directed} ne $graphDirected;
					if ( ($graphDirected eq 'undirected' and !exists($edges{$targetID}{$nodeID})) or $graphDirected eq 'directed') {
						$edges{$nodeID}{$targetID}{weight} = $self->{graph}{$nodeID}{edges}{$targetID}{weight};
						$edges{$nodeID}{$targetID}{label} = $self->{graph}{$nodeID}{edges}{$targetID}{label};
					}
				}
			}
		}
		foreach my $sourceID (keys %edges) {
			foreach my $targetID (keys %{$edges{$sourceID}}) {
				my $sourceIDprint = (looks_like_number($sourceID)) ? $sourceID : '"' . encode_entities($sourceID) . '"';
				my $targetIDprint = (looks_like_number($targetID)) ? $targetID : '"' . encode_entities($targetID) . '"';
				my $edgeLabelprint = ($edges{$sourceID}{$targetID}{label}) ? "\t\tlabel \"" . encode_entities($edges{$sourceID}{$targetID}{label}) . "\"\n" : $EMPTY_STRING;
				print {$outfile} "\tedge [\n\t\tsource $sourceIDprint\n\t\ttarget $targetIDprint\n$edgeLabelprint\t\tvalue $edges{$sourceID}{$targetID}{weight}\n\t]\n";
				$edgecount++;
			}
		}
		print {$outfile} "]\n";
		close($outfile);
		print "outputGraphtoGML: wrote $nodecount nodes and $edgecount edges to '$filename'\n" if $VERBOSE;

		return $self;
	}

} #GML file format methods

#############################################################################
#XML file format methods: GraphML and GEXF                                  #
#############################################################################
{

	use XML::LibXML;


	sub inputGraphfromGraphML { ## no critic (ProhibitExcessComplexity)
		my ($self, $filename, $options) = @_;

		if (!ref($self)) {
			$self = Graph::Dijkstra->new();
		}

		my $dom = XML::LibXML->load_xml(location => $filename);

		print "inputGraphfromGraphML: input '$filename'\n" if $VERBOSE;

		my $topNode = $dom->nonBlankChildNodes()->[0];

		croak "inputGraphfromGraphML: not a GraphML format XML file" if lc($topNode->nodeName()) ne 'graphml';

		my $nsURI = $topNode->getAttribute('xmlns') || '';

		croak "inputGraphfromGraphML: not a GraphML format XML file" if (lc($nsURI) ne 'http://graphml.graphdrawing.org/xmlns');

		my $xpc = XML::LibXML::XPathContext->new($dom);
		$xpc->registerNs('gml', $nsURI);

		my $labelKey = $options->{nodeKeyLabelID} || $EMPTY_STRING;
		my $weightKey = $options->{edgeKeyValueID} || $EMPTY_STRING;
		my $edgeLabelKey = 'label';

		my $defaultWeight = 1;

		my $nodecount = 0;
		my $edgecount = 0;
		my $dupedgecount = 0;
		my $graphDirected = $EMPTY_STRING;

		if (my $graphNode = $xpc->findnodes('/gml:graphml/gml:graph')->[0] ) {
			$graphDirected = lc($graphNode->getAttribute('edgedefault'));
			print "inputGraphfromGraphML: graph edge default is '$graphDirected'.\n" if $VERBOSE;
		}
		else {
			croak "inputGraphfromGraphML: GraphML file has no  element";
		}

		if (my $graphNode = $xpc->findnodes('/gml:graphml/gml:graph[2]')->[0] ) {
			croak "inputGraphfromGraphML: file contains more than one graph.  Not supported.";
		}

		if (my $graphNode = $xpc->findnodes('/gml:graphml/gml:graph/gml:node/gml:graph')->[0] ) {
			croak "inputGraphfromGraphML: file contains one or more embedded graphs.  Not supported.";
		}

		if ($weightKey) {
			if (my $keyWeightNode = $xpc->findnodes("/gml:graphml/gml:key[\@for=\"edge\" and \@id=\"$weightKey\"]")->[0]) {
				print "inputGraphfromGraphML: found edgeKeyWeightID '$weightKey' in GraphML key elements list\n" if $VERBOSE;
				if (my $defaultNode = $xpc->findnodes('.//gml:default[1]',$keyWeightNode)->[0]) {
					$defaultWeight = $defaultNode->textContent();
				}
			}
			else {
				carp "inputGraphfromGraphML: edgeKeyValueID '$weightKey' not found in GraphML key elements list";
				$weightKey = $EMPTY_STRING;
			}
		}

		if (!$weightKey) {
			foreach my $keyEdge ($xpc->findnodes('/gml:graphml/gml:key[@for="edge"]') ) {
				my $attrName = $keyEdge->getAttribute('attr.name');
				if ($IS_GRAPHML_WEIGHT_ATTR{ lc($attrName) } ) {
					$weightKey = $keyEdge->getAttribute('id');
					print "inputGraphfromGraphML: found key attribute for edge attr.name='$attrName' id='$weightKey'\n" if $VERBOSE;
					if (my $defaultNode = $xpc->findnodes('.//gml:default[1]',$keyEdge)->[0]) {
						$defaultWeight = $defaultNode->textContent();
					}
					last;
				}
			}

			if (!$weightKey) {
				croak "inputGraphfromGraphML: graph does not contain key attribute for edge weight/value/cost/distance ''.  Not supported.";
			}
		}

		if ($edgeLabelKey) {
			if (my $keyEdgeLabelNode = $xpc->findnodes("/gml:graphml/gml:key[\@for=\"edge\" and \@id=\"$edgeLabelKey\"]")->[0]) {
				print "inputGraphfromGraphML: found edgeKeyLabelID '$edgeLabelKey' in GraphML key elements list\n" if $VERBOSE;
			}
			else {
#				carp "inputGraphfromGraphML: edgeKeyLabelID '$edgeLabelKey' not found in GraphML key elements list";
				$edgeLabelKey = $EMPTY_STRING;
			}
		}
		my $edgeLabelXPATH = ($edgeLabelKey) ? ".//gml:data[\@key=\"$edgeLabelKey\"]" : $EMPTY_STRING;

		my $labelXPATH = $EMPTY_STRING;

		if ($labelKey) {
			if (my $keyNodeLabelNode = $xpc->findnodes("/gml:graphml/gml:key[\@for=\"node\" and \@id=\"$labelKey\"]")->[0]) {
				print "inputGraphfromGraphML: found nodeLabelValueID '$labelKey' in GraphML key elements list\n" if $VERBOSE;
			}
			else {
				carp "inputGraphfromGraphML: nodeLabelValueID '$labelKey' not found in GraphML key elements list";
				$labelKey = $EMPTY_STRING;
			}
		}

		if (!$labelKey) {
			foreach my $keyNode ($xpc->findnodes('/gml:graphml/gml:key[@for="node" and @attr.type="string"]')) {
				my $attrName = $keyNode->getAttribute('attr.name') || $EMPTY_STRING;
				if ($IS_GRAPHML_LABEL_ATTR{lc($attrName)}) {
					$labelKey = $keyNode->getAttribute('id');
					print "inputGraphfromGraphML: found key attribute for node 'label' attr.name='$attrName' id='$labelKey'\n" if $VERBOSE;
					last;
				}
			}
		}

		if (!$labelKey) {
			carp "inputGraphfromGraphML: key node name / label / description attribute not found in graphml";
		}
		else {
			$labelXPATH = ".//gml:data[\@key=\"$labelKey\"]";
		}

		if (my $keyGraphCreator = $xpc->findnodes("/gml:graphml/gml:key[\@for=\"graph\" and \@id=\"creator\"]")->[0]) {
			if (my $dataGraphCreator = $xpc->findnodes("/gml:graphml/gml:graph/gml:data[\@key=\"creator\"]")->[0]) {
				if (my $creator = $dataGraphCreator->textContent()) {
					$self->graph( {creator=>$creator} );
				}
			}
		}
		if (my $keyGraphLabel = $xpc->findnodes("/gml:graphml/gml:key[\@for=\"graph\" and \@id=\"graphlabel\"]")->[0]) {
			if (my $dataGraphLabel = $xpc->findnodes("/gml:graphml/gml:graph/gml:data[\@key=\"graphlabel\"]")->[0]) {
				if (my $label = $dataGraphLabel->textContent()) {
					$self->graph( {label=>$label} );
				}
			}
		}

		foreach my $nodeElement ($xpc->findnodes('/gml:graphml/gml:graph/gml:node')) {

			my $node = $nodeElement->nodeName();
			my $id = $nodeElement->getAttribute('id');
			my $label = $EMPTY_STRING;
			if ($labelXPATH and my $dataNameNode = $xpc->findnodes($labelXPATH,$nodeElement)->[0]) {
				$label = $dataNameNode->textContent();
			}
			$self->node( {id=>$id,label=>$label } );
			$nodecount++;
		}

		my $weightXPATH = ".//gml:data[\@key=\"$weightKey\"]";

		foreach my $edgeElement ($xpc->findnodes('/gml:graphml/gml:graph/gml:edge')) {

			my $edge = $edgeElement->nodeName();
			my $source = $edgeElement->getAttribute('source');
			my $target = $edgeElement->getAttribute('target');
			my $edgeID = ($edgeElement->hasAttribute('id')) ? $edgeElement->getAttribute('id') : $EMPTY_STRING;
			my $edgeDirected = ($edgeElement->hasAttribute('directed')) ? $edgeElement->getAttribute('directed') : $graphDirected;
			my $edgeLabel = '';
			if ($edgeLabelXPATH and my $dataEdgeLabelNode = $xpc->findnodes($edgeLabelXPATH,$edgeElement)->[0]) {
				$edgeLabel = $dataEdgeLabelNode->textContent();
			}
			my $weight = $defaultWeight;
			if (my $dataWeightNode = $xpc->findnodes($weightXPATH,$edgeElement)->[0]) {
				$weight = $dataWeightNode->textContent();
			}
			if ($weight) {
				$dupedgecount++ if $self->edgeExists( { sourceID=>$source, targetID=>$target } );
				$self->edge( { sourceID=>$source, targetID=>$target, weight=>$weight, id=>$edgeID, directed=>$edgeDirected, label=>$edgeLabel } );
				$edgecount++;
			}
			else {
				carp "inputGraphfromGraphML: edge $source $target has no weight. Not created."
			}

		}

		carp "inputGraphfromGraphML: no nodes read from '$filename'" if !$nodecount;
		carp "inputGraphfromGraphML: no edges read from '$filename'" if !$edgecount;

		print "inputGraphfromGraphML: found $nodecount nodes and $edgecount edges\n" if $VERBOSE;
		print "inputGraphfromGraphML: found $dupedgecount duplicate edges\n" if $dupedgecount and $VERBOSE;

		return $self;
	}


	sub outputGraphtoGraphML {
		my ($self, $filename, $options) = @_;

		my $nsURI = "http://graphml.graphdrawing.org/xmlns";

		my $doc = XML::LibXML::Document->new('1.0','UTF-8');
		my $graphML = $doc->createElementNS( $EMPTY_STRING, 'graphml' );
		$doc->setDocumentElement( $graphML );

		$graphML->setNamespace( $nsURI , $EMPTY_STRING, 1 );

		{
			my $now_string = localtime;
			$graphML->appendChild($doc->createComment("Generated by Graph::Dijkstra on $now_string"));
		}

		$graphML->setAttribute('xmlns:xsi','http://www.w3.org/2001/XMLSchema-instance');
		$graphML->setAttribute('xsi:schemaLocation','http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd');



		my $keyEdgeWeightID = $options->{keyEdgeWeightID} || 'weight';
		my $keyEdgeWeightAttrName = $options->{keyEdgeWeightAttrName} || 'weight';
		my $keyNodeLabelID = $options->{keyNodeLabelID} || 'name';
		my $keyNodeLabelAttrName = $options->{keyNodeLabelAttrName} || 'name';
		my $keyEdgeLabelID = $options->{keyEdgeLabelID} || 'label';
		my $keyEdgeLabelAttrName = $options->{keyEdgeLabelAttrName} || 'label';

		my $keyNode = $graphML->addNewChild( $nsURI, 'key' );

		$keyNode->setAttribute('for','node');
		$keyNode->setAttribute('id', $keyNodeLabelID );
		$keyNode->setAttribute('attr.name', $keyNodeLabelAttrName );
		$keyNode->setAttribute('attr.type', 'string' );

		my $keyEdge = $graphML->addNewChild( $nsURI, 'key' );
		$keyEdge->setAttribute('for','edge');
		$keyEdge->setAttribute('id', $keyEdgeWeightID );
		$keyEdge->setAttribute('attr.name', $keyEdgeWeightAttrName );
		$keyEdge->setAttribute('attr.type', 'double' );

		$keyEdge = $graphML->addNewChild( $nsURI, 'key' );
		$keyEdge->setAttribute('for','edge');
		$keyEdge->setAttribute('id', $keyEdgeLabelID );
		$keyEdge->setAttribute('attr.name', $keyEdgeLabelAttrName );
		$keyEdge->setAttribute('attr.type', 'string' );

		if ($self->{creator}) {
			my $keyGraph = $graphML->addNewChild( $nsURI, 'key' );
			$keyGraph->setAttribute('for','graph');
			$keyGraph->setAttribute('id','creator');
			$keyGraph->setAttribute('attr.name','creator');
			$keyGraph->setAttribute('attr.type','string');
		}
		if ($self->{label}) {
			my $keyGraph = $graphML->addNewChild( $nsURI, 'key' );
			$keyGraph->setAttribute('for','graph');
			$keyGraph->setAttribute('id','graphlabel');
			$keyGraph->setAttribute('attr.name','label');
			$keyGraph->setAttribute('attr.type','string');
		}

		my $graph = $graphML->addNewChild( $nsURI, 'graph' );
		$graph->setAttribute('id','G');
		$graph->setAttribute('edgedefault', $self->{edgedefault} );
		if ($self->{creator}) {
			my $dataNode = $graph->addNewChild( $nsURI, 'data');
			$dataNode->setAttribute('key', 'creator');
			$dataNode->appendTextNode( $self->{creator} );
		}
		if ($self->{label}) {
			my $dataNode = $graph->addNewChild( $nsURI, 'data');
			$dataNode->setAttribute('key', 'label');
			$dataNode->appendTextNode( $self->{label} );
		}

		my $nodecount = 0;
		my $edgecount = 0;

		my %edges = ();
		foreach my $nodeID (keys %{$self->{graph}}) {

			my $nodeNode = $graph->addNewChild( $nsURI, 'node' );
			$nodeNode->setAttribute('id', $nodeID);
			my $dataNode = $nodeNode->addNewChild( $nsURI, 'data');
			$dataNode->setAttribute('key', $keyNodeLabelID);
			$dataNode->appendTextNode( $self->{graph}{$nodeID}{label} );

			$nodecount++;
			if (exists($self->{graph}{$nodeID}{edges})) {
				foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
					my $directed = $self->{graph}{$nodeID}{edges}{$targetID}{directed};
					if ( ($directed eq 'undirected' and !exists($edges{$targetID}{$nodeID})) or $directed eq 'directed') {
						$edges{$nodeID}{$targetID}{weight} = $self->{graph}{$nodeID}{edges}{$targetID}{weight};
						$edges{$nodeID}{$targetID}{id} = $self->{graph}{$nodeID}{edges}{$targetID}{id};
						$edges{$nodeID}{$targetID}{directed} = $directed;
						$edges{$nodeID}{$targetID}{label} = $self->{graph}{$nodeID}{edges}{$targetID}{label};
					}
				}
			}
		}
		foreach my $sourceID (keys %edges) {
			foreach my $targetID (keys %{$edges{$sourceID}}) {

				$edgecount++;
				my $edgeNode = $graph->addNewChild( $nsURI, 'edge');
				$edgeNode->setAttribute('id', ($edges{$sourceID}{$targetID}{id} ne $EMPTY_STRING) ? $edges{$sourceID}{$targetID}{id} : $edgecount);
				$edgeNode->setAttribute('source', $sourceID );
				$edgeNode->setAttribute('target', $targetID );
				$edgeNode->setAttribute('directed', $edges{$sourceID}{$targetID}{directed} ) if $edges{$sourceID}{$targetID}{directed} ne $self->{edgedefault};
				my $dataNode = $edgeNode->addNewChild( $nsURI, 'data');
				$dataNode->setAttribute('key', $keyEdgeWeightID );
				$dataNode->appendTextNode( $edges{$sourceID}{$targetID}{weight} );

				if ( $edges{$sourceID}{$targetID}{label} ) {
					$dataNode = $edgeNode->addNewChild( $nsURI, 'data');
					$dataNode->setAttribute('key', $keyEdgeLabelID );
					$dataNode->appendTextNode( $edges{$sourceID}{$targetID}{label} );
				}
			}
		}

		my $state = $doc->toFile($filename,2);
		croak "could not output internal grap to '$filename'" if !$state;

		print "outputGraphtoGraphML: wrote $nodecount nodes and $edgecount edges to '$filename'\n" if $VERBOSE;
		return $self;
	}


	sub inputGraphfromGEXF { ## no critic (ProhibitExcessComplexity)
		my ($self, $filename) = @_;

		if (!ref($self)) {
			$self = Graph::Dijkstra->new();
		}

		my $dom = XML::LibXML->load_xml(location => $filename);

		print "inputGraphfromGEXF: input '$filename'\n" if $VERBOSE;

		my $topNode = $dom->nonBlankChildNodes()->[0];

		croak "inputGraphfromGEXF: not a GEXF format XML file" if lc($topNode->nodeName()) ne 'gexf';

		my $nsURI = $topNode->getAttribute('xmlns') || '';

		croak "inputGraphfromGEXF: not a GEXF draft specification 1.1 or 1.2 format XML file" if ( $nsURI !~ /^http:\/\/www.gexf.net\/1\.[1-2]draft$/i );

		my $gexfVersion = $topNode->getAttribute('version') || '';  #don't do anything with the GEXF version string

		my $xpc = XML::LibXML::XPathContext->new($dom);
		$xpc->registerNs('gexf', $nsURI);

		my $nodecount = 0;
		my $edgecount = 0;
		my $dupedgecount = 0;
		my $defaultWeight = 1;
		my $graphDirected = 'undirected';

		if (my $graphNode = $xpc->findnodes('/gexf:gexf/gexf:graph')->[0] ) {
			$graphDirected = ($graphNode->hasAttribute('defaultedgetype')) ? lc($graphNode->getAttribute('defaultedgetype')) : 'undirected';
			croak "inputGraphfromGEXF: graph defaultedgetype is 'mutual'. Not supported." if $graphDirected eq 'mutual';
			$self->graph( {edgedefault=>$graphDirected} );
			print "inputGraphfromGEXF: graph edgedefault is '$graphDirected'.\n" if $VERBOSE;
			my $mode = $graphNode->getAttribute('mode') || $EMPTY_STRING;
			carp "inputGraphfromGEXF: graph mode is 'dynamic'.  Not supported." if lc($mode) eq 'dynamic';
		}
		else {
			croak "inputGraphfromGEXF: GEXF file has no  element";
		}

		if (my $graphNode = $xpc->findnodes('/gexf:gexf/gexf:graph[2]')->[0] ) {
			croak "inputGraphfromGEXF: file contains more than one graph.  Not supported.";
		}

		if (my $heirarchyNode = $xpc->findnodes('/gexf:gexf/gexf:graph/gexf:nodes/gexf:node/gexf:nodes')->[0] ) {
			croak "inputGraphfromGEXF: file contains heirarchical nodes.  Not supported.";
		}
		if (my $parentsNode = $xpc->findnodes('/gexf:gexf/gexf:graph/gexf:nodes/gexf:node/gexf:parents')->[0] ) {
			croak "inputGraphfromGEXF: file contains parent nodes.  Not supported.";
		}

		if (my $metaNode = $xpc->findnodes('/gexf:gexf/gexf:meta/gexf:creator')->[0] ) {
			if (my $creator = $metaNode->textContent()) {
				$self->graph( { creator=>$creator } );
				print "inputGraphfromGEXF: set graph attribute creator: $creator\n" if $VERBOSE;
			}
		}

		if (my $metaNode = $xpc->findnodes('/gexf:gexf/gexf:meta/gexf:description')->[0] ) {
			if (my $label = $metaNode->textContent()) {
				$self->graph( { label=>$label } );
				print "inputGraphfromGEXF: set graph attribute label (from meta attribute description): $label\n" if $VERBOSE;
			}
		}


		foreach my $nodeElement ($xpc->findnodes('/gexf:gexf/gexf:graph/gexf:nodes/gexf:node')) {

			#my $node = $nodeElement->nodeName();
			my $id = $nodeElement->getAttribute('id');
			my $label = $nodeElement->getAttribute('label') || $EMPTY_STRING;
			$self->node( {id=>$id, label=>$label} );
			$nodecount++;
		}

		foreach my $edgeElement ($xpc->findnodes('/gexf:gexf/gexf:graph/gexf:edges/gexf:edge')) {

			#my $edge = $edgeElement->nodeName();
			my $source = $edgeElement->getAttribute('source');  #source, target, and id are required attributes
			my $target = $edgeElement->getAttribute('target');
			my $edgeID = $edgeElement->getAttribute('id');
			my $weight = ($edgeElement->hasAttribute('weight')) ? $edgeElement->getAttribute('weight') :  $defaultWeight;
			my $label = ($edgeElement->hasAttribute('label')) ? $edgeElement->getAttribute('label') :  $EMPTY_STRING;
			my $edgeDirected = ($edgeElement->hasAttribute('type')) ? $edgeElement->getAttribute('type') :  $graphDirected;
			if ($weight) {
				$dupedgecount++ if $self->edgeExists( { sourceID=>$source, targetID=>$target } );
				$self->edge( { sourceID=>$source, targetID=>$target, weight=>$weight, directed=>$edgeDirected, label=>$label, id=>$edgeID } );
				$edgecount++;
			}
			else {
				carp "inputGraphfromGEXF: edge $source $target has no weight. Not created."
			}

		}

		carp "inputGraphfromGEXF: no nodes read from '$filename'" if !$nodecount;
		carp "inputGraphfromGEXF: no edges read from '$filename'" if !$edgecount;

		print "inputGraphfromGEXF: found $nodecount nodes and $edgecount edges\n" if $VERBOSE;
		print "inputGraphfromGEXF: found $dupedgecount duplicate edges\n" if $dupedgecount and $VERBOSE;

		return $self;
	}


	sub outputGraphtoGEXF {
		my ($self, $filename) = @_;

		my $nsURI = 'http://www.gexf.net/1.2draft';

		my $doc = XML::LibXML::Document->new('1.0','UTF-8');
		my $GEXF = $doc->createElementNS( $EMPTY_STRING, 'gexf' );
		$doc->setDocumentElement( $GEXF );

		$GEXF->setNamespace( $nsURI , $EMPTY_STRING, 1 );

		$GEXF->setAttribute('xmlns:xsi','http://www.w3.org/2001/XMLSchema-instance');
		$GEXF->setAttribute('xsi:schemaLocation','http://www.gexf.net/1.2draft http://www.gexf.net/1.2draft/gexf.xsd');
		$GEXF->setAttribute('version','1.2');

		{
			my $now_string = localtime;
			$GEXF->appendChild($doc->createComment("Generated by Graph::Dijkstra on $now_string"));
		}
		{
			my (undef, undef, undef, $mday, $month, $year, undef, undef, undef) = localtime;
			my $ISODATE = sprintf "%4d-%02d-%02d", $year+1900, $month+1, $mday;
			my $meta = $GEXF->addNewChild( $nsURI, 'meta');
			$meta->setAttribute('lastmodifieddate', $ISODATE);
			if ($self->{creator}) {
				my $creatorNode = $meta->addNewChild( $nsURI, 'creator');
				$creatorNode->appendTextNode( $self->{creator} );
			}
			if ($self->{label}) {
				my $descriptionNode = $meta->addNewChild( $nsURI, 'description');
				$descriptionNode->appendTextNode( $self->{label} );
			}
		}

		my $graph = $GEXF->addNewChild( $nsURI, 'graph' );
		$graph->setAttribute('mode','static');
		$graph->setAttribute('defaultedgetype', $self->{edgedefault} );
		my $nodesElement = $graph->addNewChild( $nsURI, 'nodes' );

		my $nodecount = 0;
		my $edgecount = 0;

		my %edges = ();
		foreach my $nodeID (keys %{$self->{graph}}) {

			my $nodeNode = $nodesElement->addNewChild( $nsURI, 'node' );
			$nodeNode->setAttribute('id', $nodeID);
			$nodeNode->setAttribute('label', $self->{graph}{$nodeID}{label} );

			$nodecount++;
			if (exists($self->{graph}{$nodeID}{edges})) {
				foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
					my $directed = $self->{graph}{$nodeID}{edges}{$targetID}{directed};
					if ( ($directed eq 'undirected' and !exists($edges{$targetID}{$nodeID})) or $directed eq 'directed') {
						$edges{$nodeID}{$targetID}{weight} = $self->{graph}{$nodeID}{edges}{$targetID}{weight};
						$edges{$nodeID}{$targetID}{id} = $self->{graph}{$nodeID}{edges}{$targetID}{id};
						$edges{$nodeID}{$targetID}{directed} = $directed;
						$edges{$nodeID}{$targetID}{label} = $self->{graph}{$nodeID}{edges}{$targetID}{label};
					}
				}
			}
		}

		my $edgesElement = $graph->addNewChild( $nsURI, 'edges' );

		foreach my $sourceID (keys %edges) {
			foreach my $targetID (keys %{$edges{$sourceID}}) {

				$edgecount++;
				my $edgeNode = $edgesElement->addNewChild( $nsURI, 'edge');
				$edgeNode->setAttribute('id', ($edges{$sourceID}{$targetID}{id} ne '') ? $edges{$sourceID}{$targetID}{id} : $edgecount);
				$edgeNode->setAttribute('source', $sourceID );
				$edgeNode->setAttribute('target', $targetID );
				$edgeNode->setAttribute('weight', $edges{$sourceID}{$targetID}{weight} );
				$edgeNode->setAttribute('directed', $edges{$sourceID}{$targetID}{directed} ) if $edges{$sourceID}{$targetID}{directed} ne $self->{edgedefault};
				$edgeNode->setAttribute('label', $edges{$sourceID}{$targetID}{label} ) if $edges{$sourceID}{$targetID}{label};

			}
		}
		my $state = $doc->toFile($filename,2);
		croak "could not output internal grap to '$filename'" if !$state;

		print "outputGraphtoGEXF: wrote $nodecount nodes and $edgecount edges to '$filename'\n" if $VERBOSE;
		return $self;
	}

	sub validateGraphMLxml {
		my ($either, $filename) = @_;

		my $GraphML_URL = 'http://graphml.graphdrawing.org/xmlns/1.1/graphml.xsd';

		my $GraphMLschema = XML::LibXML::Schema->new( location => $GraphML_URL );
		print "validateGraphMLxml: loaded GraphML schema\n" if $VERBOSE;

		my $dom = XML::LibXML->load_xml(location => $filename);
		print "validateGraphMLxml: loaded '$filename'\n" if $VERBOSE;

		eval { $GraphMLschema->validate( $dom ); };

		if ($@) {
			print "validateGraphMLxml: validate failed\n$@\n" if $VERBOSE;
			return(0,$@);
		}
		else {
			print "validateGraphMLxml: validated\n" if $VERBOSE;
			return(1,$EMPTY_STRING);
		}

	}

	sub validateGEXFxml {
		my ($either, $filename) = @_;

		my $GEXF_URL = 'http://www.gexf.net/1.2draft/gexf.xsd';

		my $GEXFschema = XML::LibXML::Schema->new( location => $GEXF_URL );
		print "validateGEXFxml: loaded GEXF schema\n" if $VERBOSE;

		my $dom = XML::LibXML->load_xml(location => $filename);
		print "validateGEXFxml: loaded '$filename'\n" if $VERBOSE;

		eval { $GEXFschema->validate( $dom ); };

		if ($@) {
			print "validateGEXFxml: validate failed\n$@\n" if $VERBOSE;
			return(0,$@);
		}
		else {
			print "validateGEXFxml: validated\n" if $VERBOSE;
			return(1,$EMPTY_STRING);
		}

	}


} #XML file format methods

#############################################################################
#NET (Pajek) file format methods                                            #
#############################################################################
{
	sub inputGraphfromNET {
		my ($self, $filename) = @_;

		use Regexp::Common qw /delimited/;

		if (!ref($self)) {
			$self = Graph::Dijkstra->new();
		}

		open(my $infile, '<:encoding(UTF-8)', $filename) or croak "inputGraphfromNET: could not open '$filename' for input";

		print "inputGraphfromNET: opened '$filename' for input\n" if $VERBOSE;

		my $nodes = 0;
		while (my $line = <$infile>) {
			if ($line =~ /^\*vertices\s+(\d+)/ix) {
				$nodes = $1;
				last;
			}
		}
		croak "inputGraphfromNET: vertices element not found" if !$nodes;
		print "inputGraphfromNET: vertices = $nodes\n" if $VERBOSE;

		my $nodecount = 0;
		my $edgecount = 0;
		my $dupedgecount = 0;

		my $quotedRE = $RE{delimited}{-delim=>'"'};
		#print "quotedRE = '$quotedRE'\n";

		my $nextSection = '';
		foreach my $i (1 .. $nodes) {
			my $line = '';
			while(1) {
				$line = <$infile>;
				chomp $line;
				croak "inputGraphfromNET: unexpected EOF in vertices section" if !defined($line);
				last if substr($line,0,1) ne '%';
			}

			if (substr($line,0,1) eq '*') {
				chomp $line;
				$nextSection = lc($line);
				last;
			}

			if ($line =~ /^\s*(\d+)\s+($quotedRE)/ix) {
				my $id = $1;
				my $label = $2;
				$label = substr($label,1,-1);  #strip quotes
				$self->node( {id=>$id, label=>$label} );
				$nodecount++;
			}
		}
		if ($nextSection and $nodecount == 0) {
			print "inputGraphfromNET: empty vertices section (no node labels).  Generating node ID values 1 .. $nodes\n" if $VERBOSE;
			foreach my $i (1 .. $nodes) {
				$self->node( {id=>$i, label=>$EMPTY_STRING} );
				$nodecount++;
			}
		}
		elsif ($nodes != $nodecount) {
			die "inputGraphfromNET: internal logic error: # vertices ($nodes) != # read nodes ($nodecount)";
		}

		if ($nextSection =~ /^(\*\w+)/) {
			$nextSection = $1;
		}
		elsif ($nextSection) {
			die "inputGraphfromNET: internal logic error.  Did not recognize next section '$nextSection' in NET (pajek) file.";
		}

		croak "inputGraphfromNET: input file contains *arclist section.  Not supported." if $nextSection eq '*arclist';
		croak "inputGraphfromNET: input file contains *edgelist section.  Not supported." if $nextSection eq '*edgelist';

		print "inputGraphfromNET: next section is '$nextSection'\n" if $nextSection and $VERBOSE;

		while (1) {

			if ($nextSection ne '*arcs' and $nextSection ne '*edges') {
				$nextSection = '';
				while (my $line = <$infile>) {
					if ($line =~ /^(\*(?:edges|arcs))/i) {
						$nextSection = lc($1);
						last;
					}
				}
				last if !$nextSection;
			}

			my $edgeDirected = ($nextSection eq '*edges') ? 'undirected' : 'directed';
			$nextSection = '';

			while (my $line = <$infile>) {
				chomp $line;
				next if !$line;
				next if substr($line,0,1) eq '%';
				if ($line =~ /^(\*\w+)/) {
					$nextSection = lc($1);
					last;
				}
				if ($line =~ /^\s+(\d+)\s+(\d+)\s+([0-9\.]+)/s) {
					my $sourceID = $1;
					my $targetID = $2;
					my $weight = $3;
					$dupedgecount++ if $self->edgeExists( { sourceID=>$sourceID, targetID=>$targetID } );
					$self->edge( { sourceID=>$sourceID, targetID=>$targetID, weight=>$weight, directed=>$edgeDirected } );
					$edgecount++;
				}
				else {
					chomp $line;
					carp "inputGraphfromNET: unrecognized input line (maybe edge with no weight?) =>$line<=";
					last;
				}
			}
			last if !$nextSection;
		}
		close($infile);

		carp "inputGraphfromNET: no nodes read from '$filename'" if !$nodecount;
		carp "inputGraphfromNET: no edges read from '$filename'" if !$edgecount;

		print "inputGraphfromNET: found $nodecount nodes and $edgecount edges\n" if $VERBOSE;
		print "inputGraphfromNET: found $dupedgecount duplicate edges\n" if $dupedgecount and $VERBOSE;

		return $self;
	}

	sub outputGraphtoNET {
		my ($self, $filename) = @_;

		open(my $outfile, '>:encoding(UTF-8)', $filename) or croak "outputGraphtoNET: could not open '$filename' for output";

		print "outputGraphtoNET: opened '$filename' for output\n" if $VERBOSE;

		my %edges = ();
		my $nodecount = 0;
		my $edgecount = 0;
		my $useConsecutiveNumericIDs = 1;
		my $hasNonBlankLabels = 0;
		my $highestNumericID = 0;
		my $lowestNumericID = $PINF;

		my @nodeList = $self->nodeList();

		foreach my $nodeHref (@nodeList) {
			$nodecount++;
			my $nodeID = $nodeHref->{id};
			my $label = $nodeHref->{label};
			if ($useConsecutiveNumericIDs) {
				if ($nodeID =~ /^\d+$/) {
					$highestNumericID = $nodeID if $nodeID > $highestNumericID;
					$lowestNumericID = $nodeID if $nodeID < $lowestNumericID;
				}
				else {
					$useConsecutiveNumericIDs = 0;
				}
			}

			$hasNonBlankLabels = 1 if (!$hasNonBlankLabels and $label ne $EMPTY_STRING);
		}
		print "outputGraphtoNET: internal graph has non-blank labels.\n" if $VERBOSE and $hasNonBlankLabels;

		if ($useConsecutiveNumericIDs) {
			if ($highestNumericID != $nodecount or $lowestNumericID != 1) {
				$useConsecutiveNumericIDs = 0;
			}
		}


		{
			my $now_string = localtime;
			print {$outfile} "% Generated by Graph::Dijkstra on $now_string\n";
		}

		print {$outfile} "*Vertices $nodecount\n";

		my $hasArcs = 0;
		my $hasEdges = 0;

		if ($useConsecutiveNumericIDs) {

			print "outputGraphtoNET: internal graph has consecutive numeric IDs.\n" if $VERBOSE;
			$nodecount = 0;
			foreach my $nodeHref (sort { $a->{id} <=> $b->{id} } @nodeList) {

				$nodecount++;

				my $nodeID = $nodeHref->{id};
				my $label = $nodeHref->{label};
				croak "outputGraphtoNET: node IDs are not consecutive numeric integers starting at 1" if ($nodeID != $nodecount);

				if ($hasNonBlankLabels) {
					printf {$outfile} "%7d \"%s\"\n", $nodeID, $label;
				}

				if (exists($self->{graph}{$nodeID}{edges})) {
					foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
						my $edgeDirected = $self->{graph}{$nodeID}{edges}{$targetID}{directed};
						if ( ($edgeDirected eq 'undirected' and !exists($edges{$targetID}{$nodeID}) ) or $edgeDirected eq 'directed') {
							$edges{$nodeID}{$targetID}{weight} = $self->{graph}{$nodeID}{edges}{$targetID}{weight};
							$edges{$nodeID}{$targetID}{directed} = $edgeDirected;
							if ($edgeDirected eq 'directed') {
								$hasArcs++;
							}
							else {
								$hasEdges++;
							}
						}
					}
				}
			}
		}
		else {
			if ($VERBOSE) {
				print "outputGraphtoNET: internal graph node ID values are not consecutive integer values starting at 1.\n";
				print "outputGraphtoNET: internal graph node ID values not perserved in output\n";
				print "outputGraphtoNET: generating consecutive integer ID values in output\n";
			}

			my %nodeIDtoNumericID = ();
			foreach my $i (0 .. $#nodeList) {
				$nodeIDtoNumericID{ $nodeList[$i]->{id} } = $i+1;
			}

			foreach my $nodeID (sort {$nodeIDtoNumericID{$a} <=> $nodeIDtoNumericID{$b}} keys %nodeIDtoNumericID) {
				if ($hasNonBlankLabels) {
					printf {$outfile} "%7d \"%s\"\n", $nodeIDtoNumericID{$nodeID}, $self->{graph}{$nodeID}{label};
				}

				if (exists($self->{graph}{$nodeID}{edges})) {
					my $numericNodeID = $nodeIDtoNumericID{$nodeID};
					foreach my $targetID (keys %{$self->{graph}{$nodeID}{edges}}) {
						my $edgeDirected = $self->{graph}{$nodeID}{edges}{$targetID}{directed};
						my $numericTargetID = $nodeIDtoNumericID{$targetID};
						if ( ($edgeDirected eq 'undirected' and !exists($edges{$numericTargetID}{$numericNodeID})) or $edgeDirected eq 'directed') {
							$edges{$numericNodeID}{$numericTargetID}{weight} = $self->{graph}{$nodeID}{edges}{$targetID}{weight};
							$edges{$numericNodeID}{$numericTargetID}{directed} = $edgeDirected;
							if ($edgeDirected eq 'directed') {
								$hasArcs++;
							}
							else {
								$hasEdges++;
							}
						}
					}
				}
			}
		}

		if ($hasEdges) {
			print {$outfile} "*Edges\n";
			foreach my $sourceID (sort {$a <=> $b} keys %edges) {
				foreach my $targetID (sort {$a <=> $b} keys %{$edges{$sourceID}} ) {
					next if $edges{$sourceID}{$targetID}{directed} eq 'directed';
					printf {$outfile} "%7d %7d %10s\n", $sourceID, $targetID, "$edges{$sourceID}{$targetID}{weight}";
					$edgecount++;
				}
			}
		}
		if ($hasArcs) {
			print {$outfile} "*Arcs\n";
			foreach my $sourceID (sort {$a <=> $b} keys %edges) {
				foreach my $targetID (sort {$a <=> $b} keys %{$edges{$sourceID}} ) {
					next if $edges{$sourceID}{$targetID}{directed} eq 'undirected';
					printf {$outfile} "%7d %7d %10s\n", $sourceID, $targetID, "$edges{$sourceID}{$targetID}{weight}";
					$edgecount++;
				}
			}
		}
		close($outfile);

		print "outputGraphtoNET: wrote $nodecount nodes and $edgecount edges to '$filename'\n" if $VERBOSE;
		return $self;
	}


}  #NET (Pagek) file format methods

1;

__END__