Last active
October 22, 2018 20:49
-
-
Save kriskowal/576fa923822e17a74d2453af77e264a7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/bin/bash | |
jq -Rr 'split(",")' | jq -scr ' | |
def table_to_edges: . as [$src, $dst, $weight] | | |
{$src, $dst, weight: $weight | tonumber}; | |
def edges_to_table: . as {$src, $dst, $weight} | | |
[$src, $dst, $weight]; | |
def graph_to_edges: | |
. as $graph | | |
to_entries[] as {key: $src, value: $edges} | | |
$edges | to_entries[] as {key: $dst, value: $weight} | | |
{$src, $dst, $weight}; | |
def edges_to_graph: reduce .[] as {$src, $dst, $weight} ({}; | |
. + {($src): ((.[$src] // {}) + { | |
($dst): [ | |
(.[$src][$dst] // infinite), | |
$weight | |
] | min, | |
})} | |
); | |
def coedges: . as {$src, $dst, $weight} | {src: $dst, dst: $src, $weight}; | |
def cograph: [graph_to_edges | coedges] | edges_to_graph; | |
def shortest_paths: reduce to_entries[] as {key: $mid, value: $edges} ( | |
cograph; | |
. as $cograph | | |
[ | |
($cograph | graph_to_edges), | |
( | |
($cograph[$mid] // {}) | | |
to_entries[] as {key: $dst, value: $hemi} | | |
$edges | | |
to_entries[] as {key: $src, value: $demi} | | |
{$src, $dst, weight: ($hemi + $demi)} | |
) | |
] | | |
edges_to_graph | |
); | |
[.[] | table_to_edges] | | |
edges_to_graph | | |
shortest_paths | | |
cograph | | |
graph_to_edges | | |
edges_to_table | | |
@tsv | |
' | sort -n |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment