Action:
|
Returns a graph representing the lightest path between two vertices of a graph.
|
|
Filename:
|
kern/kern_scm/graph_scm.cxx
|
|
Syntax:
|
(graph:lightest-path in-graph in-vertex1 in-vertex2)
|
|
Arg Types:
|
in-graph
|
graph
|
|
in-vertex1
|
string | entity
|
|
in-vertex2
|
string | entity
|
|
Returns:
|
graph
|
|
Description:
|
After all edges have a weight assigned, this Scheme extension returns a graph representing the path with the lightest total weight from one given vertex to another.
|
|
|
in-graph specifies a graph.
|
|
|
in-vertex1 could be either a vertex or a string representing the vertex in the graph.
|
|
|
in-vertex2 could be either a vertex or a string representing the vertex in the graph.
|
|
Limitations:
|
All edges of the graph require a weight.
|
|
Example:
|
; graph:lightest-path
|
|
; Create a simple graph.
|
|
(define g1 (graph "a-b1 a-b2 b1-c b2-c c-d"))
|
|
;; g1
|
|
(graph:edge-weight g1 "a" "b1" 3)
|
|
;; #[graph "a-b1 a-b2 b1-c b2-c c-d"]
|
|
(graph:edge-weight g1 "a-b2" 5)
|
|
;; #[graph "a-b1 a-b2 b1-c b2-c c-d"]
|
|
(graph:edge-weight g1 "b1-c" 1)
|
|
;; #[graph "a-b1 a-b2 b1-c b2-c c-d"]
|
|
(graph:edge-weight g1 "b2-c" 1)
|
|
;; #[graph "a-b1 a-b2 b1-c b2-c c-d"]
|
|
(graph:edge-weight g1 "c-d" 1)
|
|
;; #[graph "a-b1 a-b2 b1-c b2-c c-d"]
|
|
(graph:lightest-path g1 "a" "d")
|
|
;; #[graph "a-b1 b1-c c-d"]
|