Lines Matching defs:graph
3 # Implementation of a graph data structure for Tcl.
17 namespace eval ::struct::graph {
18 # Data storage in the graph module
21 # There's a lot of bits to keep track of for each graph:
28 # within the graph namespace itself. Instead, each graph structure will
36 # counter is used to give a unique name for unnamed graph
39 # Only export one command, the one used to instantiate a new graph
43 # ::struct::graph::graph_tcl --
45 # Create a new graph with a given name; if no name is given, use
49 # name name of the graph; if null, generate one.
52 # name name of the graph created
54 proc ::struct::graph::graph_tcl {args} {
64 set name "graph${counter}"
67 # Standard call. New empty graph.
75 set srctype graph
82 "wrong # args: should be \"struct::graph ?name ?=|:=|as|deserialize source??\""
89 "wrong # args: should be \"struct::graph ?name ?=|:=|as|deserialize source??\""
104 return -code error "command \"$name\" already exists, unable to create graph"
110 # Set up the map for values associated with the graph itself
153 # Create the command to manipulate the graph
154 interp alias {} $name {} ::struct::graph::GraphProc $name
160 graph {_= $name $src}
175 # ::struct::graph::GraphProc --
177 # Command that processes all graph object commands.
180 # name name of the graph object to manipulate.
186 proc ::struct::graph::GraphProc {name {cmd ""} args} {
194 if { [llength [info commands ::struct::graph::$sub]] == 0 } {
195 set optlist [lsort [info commands ::struct::graph::_*]]
206 uplevel 1 [linsert $args 0 ::struct::graph::$sub $name]
209 # ::struct::graph::_= --
211 # Assignment operator. Copies the source graph into the
215 # name Name of the graph object we are copying into.
216 # source Name of the graph object providing us with the
222 proc ::struct::graph::_= {name source} {
227 # ::struct::graph::_--> --
229 # Reverse assignment operator. Copies this graph into the
233 # name Name of the graph object to copy
234 # dest Name of the graph object we are copying to.
239 proc ::struct::graph::_--> {name dest} {
244 # ::struct::graph::_append --
246 # Append a value for an attribute in a graph.
249 # name name of the graph.
255 proc ::struct::graph::_append {name key value} {
260 # ::struct::graph::_lappend --
262 # lappend a value for an attribute in a graph.
265 # name name of the graph.
271 proc ::struct::graph::_lappend {name key value} {
276 # ::struct::graph::_arc --
282 # name name of the graph.
289 proc ::struct::graph::_arc {name cmd args} {
293 if { [llength [info commands ::struct::graph::$sub]] == 0 } {
294 set optlist [lsort [info commands ::struct::graph::__arc_*]]
304 uplevel 1 [linsert $args 0 ::struct::graph::$sub $name]
307 # ::struct::graph::__arc_delete --
309 # Remove an arc from a graph, including all of its values.
312 # name name of the graph.
318 proc ::struct::graph::__arc_delete {name args} {
320 return {wrong # args: should be "::struct::graph::__arc_delete name arc arc..."}
356 # ::struct::graph::__arc_exists --
358 # Test for existence of a given arc in a graph.
361 # name name of the graph.
367 proc ::struct::graph::__arc_exists {name arc} {
371 # ::struct::graph::__arc_flip --
376 # name name of the graph object.
382 proc ::struct::graph::__arc_flip {name arc} {
407 # ::struct::graph::__arc_get --
409 # Get a keyed value from an arc in a graph.
412 # name name of the graph.
419 proc ::struct::graph::__arc_get {name arc key} {
435 # ::struct::graph::__arc_getall --
437 # Get a serialized array of key/value pairs from an arc in a graph.
440 # name name of the graph.
447 proc ::struct::graph::__arc_getall {name arc {pattern *}} {
460 # ::struct::graph::__arc_keys --
462 # Get a list of keys for an arc in a graph.
465 # name name of the graph.
472 proc ::struct::graph::__arc_keys {name arc {pattern *}} {
485 # ::struct::graph::__arc_keyexists --
487 # Test for existence of a given key for a given arc in a graph.
490 # name name of the graph.
497 proc ::struct::graph::__arc_keyexists {name arc key} {
510 # ::struct::graph::__arc_insert --
512 # Add an arc to a graph.
515 # name name of the graph.
524 proc ::struct::graph::__arc_insert {name source target args} {
530 return {wrong # args: should be "::struct::graph::__arc_insert name source target ?arc?"}
553 # ::struct::graph::__arc_rename --
558 # name name of the graph.
565 proc ::struct::graph::__arc_rename {name arc newname} {
611 # ::struct::graph::__arc_set --
613 # Set or get a value for an arc in a graph.
616 # name name of the graph.
624 proc ::struct::graph::__arc_set {name arc key args} {
650 # ::struct::graph::__arc_append --
652 # Append a value for an arc in a graph.
655 # name name of the graph.
662 proc ::struct::graph::__arc_append {name arc key value} {
676 # ::struct::graph::__arc_attr --
681 # name Name of the graph object.
687 proc ::struct::graph::__arc_attr {name key args} {
758 # ::struct::graph::__arc_lappend --
760 # lappend a value for an arc in a graph.
763 # name name of the graph.
770 proc ::struct::graph::__arc_lappend {name arc key value} {
784 # ::struct::graph::__arc_source --
789 # name name of the graph object.
795 proc ::struct::graph::__arc_source {name arc} {
802 # ::struct::graph::__arc_target --
807 # name name of the graph object.
813 proc ::struct::graph::__arc_target {name arc} {
820 # ::struct::graph::__arc_nodes --
825 # name name of the graph object.
832 proc ::struct::graph::__arc_nodes {name arc} {
839 # ::struct::graph::__arc_move-target --
846 # name name of the graph object.
853 proc ::struct::graph::__arc_move-target {name arc newtarget} {
870 # ::struct::graph::__arc_move-source --
877 # name name of the graph object.
884 proc ::struct::graph::__arc_move-source {name arc newsource} {
901 # ::struct::graph::__arc_move --
906 # name name of the graph object.
914 proc ::struct::graph::__arc_move {name arc newsource newtarget} {
939 # ::struct::graph::__arc_unset --
944 # name name of the graph.
951 proc ::struct::graph::__arc_unset {name arc key} {
972 # ::struct::graph::__arc_getunweighted --
977 # name name of the graph.
982 proc ::struct::graph::__arc_getunweighted {name} {
990 # ::struct::graph::__arc_getweight --
992 # Get the weight given to an arc in a graph.
996 # name name of the graph.
1002 proc ::struct::graph::__arc_getweight {name arc} {
1012 # ::struct::graph::__arc_setunweighted --
1018 # name name of the graph.
1024 proc ::struct::graph::__arc_setunweighted {name {weight 0}} {
1032 # ::struct::graph::__arc_setweight --
1037 # name name of the graph.
1044 proc ::struct::graph::__arc_setweight {name arc weight} {
1052 # ::struct::graph::__arc_unsetweight --
1057 # name name of the graph.
1063 proc ::struct::graph::__arc_unsetweight {name arc} {
1073 # ::struct::graph::__arc_hasweight --
1078 # name name of the graph.
1084 proc ::struct::graph::__arc_hasweight {name arc} {
1091 # ::struct::graph::__arc_weights --
1096 # name name of the graph.
1101 proc ::struct::graph::__arc_weights {name} {
1106 # ::struct::graph::_arcs --
1108 # Return a list of all arcs in a graph satisfying some
1112 # name name of the graph.
1117 proc ::struct::graph::_arcs {name args} {
1154 proc ::struct::graph::ArcsIN {name cn} {
1179 proc ::struct::graph::ArcsOUT {name cn} {
1199 proc ::struct::graph::ArcsADJ {name cn} {
1231 proc ::struct::graph::ArcsINN {name cn} {
1273 proc ::struct::graph::ArcsEMB {name cn} {
1323 proc ::struct::graph::ArcsNONE {name} {
1328 proc ::struct::graph::ArcsKV {name key value arcs} {
1341 proc ::struct::graph::ArcsK {name key arcs} {
1352 # ::struct::graph::_deserialize --
1358 # name Name of the graph object we are copying into.
1359 # serial Serialized graph to copy from.
1364 proc ::struct::graph::_deserialize {name serial} {
1365 # As we destroy the original graph as part of
1367 # with issues like node names from the new graph
1370 # I. Get the serialization of the source graph
1438 # ::struct::graph::_destroy --
1440 # Destroy a graph, including its associated command and data storage.
1443 # name name of the graph.
1448 proc ::struct::graph::_destroy {name} {
1453 # ::struct::graph::__generateUniqueArcName --
1455 # Generate a unique arc name for the given graph.
1458 # name name of the graph.
1461 # arc name of a arc guaranteed to not exist in the graph.
1463 proc ::struct::graph::__generateUniqueArcName {name} {
1471 # ::struct::graph::__generateUniqueNodeName --
1473 # Generate a unique node name for the given graph.
1476 # name name of the graph.
1479 # node name of a node guaranteed to not exist in the graph.
1481 proc ::struct::graph::__generateUniqueNodeName {name} {
1489 # ::struct::graph::_get --
1491 # Get a keyed value from the graph itself
1494 # name name of the graph.
1500 proc ::struct::graph::_get {name key} {
1503 return -code error "invalid key \"$key\" for graph \"$name\""
1508 # ::struct::graph::_getall --
1510 # Get an attribute dictionary from a graph.
1513 # name name of the graph.
1519 proc ::struct::graph::_getall {name {pattern *}} {
1524 # ::struct::graph::_keys --
1526 # Get a list of keys from a graph.
1529 # name name of the graph.
1535 proc ::struct::graph::_keys {name {pattern *}} {
1540 # ::struct::graph::_keyexists --
1542 # Test for existence of a given key in a graph.
1545 # name name of the graph.
1551 proc ::struct::graph::_keyexists {name key} {
1556 # ::struct::graph::_node --
1562 # name name of the graph.
1569 proc ::struct::graph::_node {name cmd args} {
1572 if { [llength [info commands ::struct::graph::$sub]] == 0 } {
1573 set optlist [lsort [info commands ::struct::graph::__node_*]]
1583 uplevel 1 [linsert $args 0 ::struct::graph::$sub $name]
1586 # ::struct::graph::__node_degree --
1593 # name name of the graph.
1599 proc ::struct::graph::__node_degree {name args} {
1667 # ::struct::graph::__node_delete --
1669 # Remove a node from a graph, including all of its values.
1673 # name name of the graph.
1679 proc ::struct::graph::__node_delete {name args} {
1681 return {wrong # args: should be "::struct::graph::__node_delete name node node..."}
1715 # ::struct::graph::__node_exists --
1717 # Test for existence of a given node in a graph.
1720 # name name of the graph.
1726 proc ::struct::graph::__node_exists {name node} {
1730 # ::struct::graph::__node_get --
1732 # Get a keyed value from a node in a graph.
1735 # name name of the graph.
1742 proc ::struct::graph::__node_get {name node key} {
1758 # ::struct::graph::__node_getall --
1760 # Get a serialized list of key/value pairs from a node in a graph.
1763 # name name of the graph.
1770 proc ::struct::graph::__node_getall {name node {pattern *}} {
1783 # ::struct::graph::__node_keys --
1785 # Get a list of keys from a node in a graph.
1788 # name name of the graph.
1795 proc ::struct::graph::__node_keys {name node {pattern *}} {
1808 # ::struct::graph::__node_keyexists --
1810 # Test for existence of a given key for a node in a graph.
1813 # name name of the graph.
1820 proc ::struct::graph::__node_keyexists {name node key} {
1833 # ::struct::graph::__node_insert --
1835 # Add a node to a graph.
1838 # name name of the graph.
1845 proc ::struct::graph::__node_insert {name args} {
1865 # ::struct::graph::__node_opposite --
1870 # name name of the graph.
1877 proc ::struct::graph::__node_opposite {name node arc} {
1891 in graph \"$name\""
1897 # ::struct::graph::__node_set --
1899 # Set or get a value for a node in a graph.
1902 # name name of the graph.
1910 proc ::struct::graph::__node_set {name node key args} {
1936 # ::struct::graph::__node_append --
1938 # Append a value for a node in a graph.
1941 # name name of the graph.
1948 proc ::struct::graph::__node_append {name node key value} {
1962 # ::struct::graph::__node_attr --
1967 # name Name of the graph object.
1973 proc ::struct::graph::__node_attr {name key args} {
2044 # ::struct::graph::__node_lappend --
2046 # lappend a value for a node in a graph.
2049 # name name of the graph.
2056 proc ::struct::graph::__node_lappend {name node key value} {
2070 # ::struct::graph::__node_unset --
2075 # name name of the graph.
2082 proc ::struct::graph::__node_unset {name node key} {
2103 # ::struct::graph::_nodes --
2105 # Return a list of all nodes in a graph satisfying some restriction.
2108 # name name of the graph.
2114 proc ::struct::graph::_nodes {name args} {
2151 proc ::struct::graph::NodesIN {name cn} {
2177 proc ::struct::graph::NodesOUT {name cn} {
2203 proc ::struct::graph::NodesADJ {name cn} {
2237 proc ::struct::graph::NodesINN {name cn} {
2280 proc ::struct::graph::NodesEMB {name cn} {
2327 proc ::struct::graph::NodesNONE {name} {
2332 proc ::struct::graph::NodesKV {name key value nodes} {
2345 proc ::struct::graph::NodesK {name key nodes} {
2356 # ::struct::graph::__node_rename --
2361 # name name of the graph.
2368 proc ::struct::graph::__node_rename {name node newname} {
2411 # ::struct::graph::_serialize --
2413 # Serialize a graph object (partially) into a transportable value.
2415 # graph in the mathematical sense of the word: These nodes and all
2420 # name Name of the graph.
2421 # args list of nodes to place into the serialized graph
2424 # A list structure describing the part of the graph which was serialized.
2426 proc ::struct::graph::_serialize {name args} {
2429 # graph are chosen for serialization. Because if that is true we
2517 # ::struct::graph::_set --
2519 # Set or get a keyed value from the graph itself
2522 # name name of the graph.
2529 proc ::struct::graph::_set {name key args} {
2542 # ::struct::graph::_swap --
2544 # Swap two nodes in a graph.
2547 # name name of the graph.
2554 proc ::struct::graph::_swap {name node1 node2} {
2619 # ::struct::graph::_unset --
2621 # Remove a keyed value from the graph itself
2624 # name name of the graph.
2630 proc ::struct::graph::_unset {name key} {
2638 # ::struct::graph::_walk --
2640 # Walk a graph using a pre-order depth or breadth first
2642 # a command will be called with the name of the graph and the node.
2645 # name name of the graph.
2653 proc ::struct::graph::_walk {name node args} {
2910 # ::struct::graph::Union --
2921 proc ::struct::graph::Union {args} {
2940 # ::struct::graph::GenAttributeStorage --
2945 # name Name of the graph containing the node
2952 proc ::struct::graph::GenAttributeStorage {name type obj} {
2961 proc ::struct::graph::CheckMissingArc {name arc} {
2963 return -code error "arc \"$arc\" does not exist in graph \"$name\""
2967 proc ::struct::graph::CheckMissingNode {name node {prefix {}}} {
2969 return -code error "${prefix}node \"$node\" does not exist in graph \"$name\""
2973 proc ::struct::graph::CheckDuplicateArc {name arc} {
2975 return -code error "arc \"$arc\" already exists in graph \"$name\""
2979 proc ::struct::graph::CheckDuplicateNode {name node} {
2981 return -code error "node \"$node\" already exists in graph \"$name\""
2985 proc ::struct::graph::CheckE {name what arguments} {
3090 proc ::struct::graph::CheckSerialization {ser gavar navar aavar inavar outavar arcnvar arcwvar} {
3117 "error in serialization: malformed graph attribute dictionary."
3208 proc ::struct::graph::K { x y } { set x }
3211 proc ::struct::graph::lset { var index arg } {
3217 proc ::struct::graph::ldelete {var index {end {}}} {
3224 proc ::struct::graph::luniq {list} {
3239 # Put 'graph::graph' into the general structure namespace
3242 namespace import -force graph::graph_tcl