|
|
This manual page is for Mac OS X version 10.6.3If you are running a different version of Mac OS X, view the documentation locally:
Reading manual pagesManual pages are intended as a quick reference for people who already understand a technology.
|
struct::graph::op(n) Tcl Data Structures struct::graph::op(n)
____________________________________________________________________________________________________________
NAME
struct::graph::op - Operation for (un)directed graph objects
SYNOPSIS
package require Tcl 8.4
package require struct::graph::op ?0.9?
struct::graph:op::toAdjacencyMatrix g
struct::graph:op::kruskal g
struct::graph:op::prim g
struct::graph:op::isBipartite? g ?bipartvar?
struct::graph:op::tarjan g
struct::graph:op::connectedComponents g
struct::graph:op::connectedComponentOf g n
struct::graph:op::isConnected? g
struct::graph:op::isCutVertex? g n
struct::graph:op::isBridge? g a
struct::graph:op::isEulerian? g ?tourvar?
struct::graph:op::isSemiEulerian? g ?pathvar?
struct::graph:op::dijkstra g start ?options...?
struct::graph:op::distance g origin destination ?options...?
struct::graph:op::eccentricity g n ?options...?
struct::graph:op::radius g ?options...?
struct::graph:op::diameter g ?options...?
____________________________________________________________________________________________________________
DESCRIPTION
The package described by this document, struct::graph::op, is a companion to the package
struct::graph. It provides a series of common operations and algorithms applicable to (un)directed
graphs.
Despite being a companion the package is not directly dependent on struct::graph, only on the API
defined by that package. I.e. the operations of this package can be applied to any and all graph
objects which provide the same API as the objects created through struct::graph.
OPERATIONS
struct::graph:op::toAdjacencyMatrix g
This command takes the graph g and returns a nested list containing the adjacency matrix of g.
The elements of the outer list are the rows of the matrix, the inner elements are the column
values in each row. The matrix has "n+1" rows and columns, with the first row and column
(index 0) containing the name of the node the row/column is for. All other elements are
boolean values, True if there is an arc between the 2 nodes of the respective row and column,
and False otherwise.
Note that the matrix is symmetric. It does not represent the directionality of arcs, only
their presence between nodes. It is also unable to represent parallel arcs in g.
struct::graph:op::kruskal g
This command takes the graph g and returns a list containing the names of the arcs in g which
span up a minimum spanning tree (MST), or, in the case of an un-connected graph, a minimum
spanning forest. Kruskal's algorithm is used to compute the tree or forest.
The command will throw an error if one or more arcs in g have no weight associated with them.
A note regarding the result, the command refrains from explicitly listing the nodes of the MST
as this information is implicitly provided in the arcs already.
struct::graph:op::prim g
This command takes the graph g and returns a list containing the names of the arcs in g which
span up a minimum spanning tree (MST), or, in the case of an un-connected graph, a minimum
spanning forest. Prim's algorithm is used to compute the tree or forest.
The command will throw an error if one or more arcs in g have no weight associated with them.
A note regarding the result, the command refrains from explicitly listing the nodes of the MST
as this information is implicitly provided in the arcs already.
struct::graph:op::isBipartite? g ?bipartvar?
This command takes the graph g and returns a boolean value indicating whether it is bipartite
(true) or not (false). If the variable bipartvar is specified the two partitions of the graph
are there as a list, if, and only if the graph is bipartit. If it is not the variable, if
specified, is not touched.
struct::graph:op::tarjan g
This command computes the set of strongly connected components (SCCs) of the graph g. The
result of the command is a list of sets, each of which contains the nodes for one of the SCCs
of g. The union of all SCCs covers the whole graph, and no two SCCs intersect with each other.
The graph g is acyclic if all SCCs in the result contain only a single node. The graph g is
strongly connected if the result contains only a single SCC containing all nodes of g.
struct::graph:op::connectedComponents g
This command computes the set of connected components (CCs) of the graph g. The result of the
command is a list of sets, each of which contains the nodes for one of the CCs of g. The union
of all CCs covers the whole graph, and no two CCs intersect with each other.
The graph g is connected if the result contains only a single SCC containing all nodes of g.
struct::graph:op::connectedComponentOf g n
This command computes the connected component (CC) of the graph g containing the node n. The
result of the command is a sets which contains the nodes for the CC of n in g.
The command will throw an error if n is not a node of the graph g.
struct::graph:op::isConnected? g
This is a convenience command determining whether the graph g is connected or not. The result
is a boolean value, true if the graph is connected, and false otherwise.
struct::graph:op::isCutVertex? g n
This command determines whether the node n in the graph g is a cut vertex (aka articulation
point). The result is a boolean value, true if the node is a cut vertex, and false otherwise.
The command will throw an error if n is not a node of the graph g.
struct::graph:op::isBridge? g a
This command determines whether the arc a in the graph g is a bridge (aka cut edge, or isth-mus). isthmus).
mus). The result is a boolean value, true if the arc is a bridge, and false otherwise.
The command will throw an error if a is not an arc of the graph g.
struct::graph:op::isEulerian? g ?tourvar?
This command determines whether the graph g is eulerian or not. The result is a boolean
value, true if the graph is eulerian, and false otherwise.
If the graph is eulerian and tourvar is specified then an euler tour is computed as well and
stored in the named variable. The tour is represented by the list of arcs traversed, in the
order of traversal.
struct::graph:op::isSemiEulerian? g ?pathvar?
This command determines whether the graph g is semi-eulerian or not. The result is a boolean
value, true if the graph is semi-eulerian, and false otherwise.
If the graph is semi-eulerian and pathvar is specified then an euler path is computed as well
and stored in the named variable. The path is represented by the list of arcs traversed, in
the order of traversal.
struct::graph:op::dijkstra g start ?options...?
This command determines distances in the weighted g from the node start to all other nodes in
the graph. The options specify how to traverse graphs, and the format of the result.
Two options are recognized
-arcmode mode
The accepted mode values are directed and undirected. For directed traversal all arcs
are traversed from source to target. For undirected traversal all arcs are traversed in
the opposite direction as well. Undirected traversal is the default.
-outputformat format
The accepted format values are distances and tree. In both cases the result is a dic-tionary dictionary
tionary keyed by the names of all nodes in the graph. For distances the value is the
distance of the node to start, whereas for tree the value is the path from the node to
start, excluding the node itself, but including start. Tree format is the default.
struct::graph:op::distance g origin destination ?options...?
This command determines the (un)directed distance between the two nodes origin and destination
in the graph g. It accepts the option -arcmode of struct::graph:op::dijkstra.
struct::graph:op::eccentricity g n ?options...?
This command determines the (un)directed eccentricity of the node n in the graph g. It accepts
the option -arcmode of struct::graph:op::dijkstra.
The (un)directed eccentricity of a node is the maximal (un)directed distance between the node
and any other node in the graph.
struct::graph:op::radius g ?options...?
This command determines the (un)directed radius of the graph g. It accepts the option -arcmode
of struct::graph:op::dijkstra.
The (un)directed radius of a graph is the minimal (un)directed eccentricity of all nodes in
the graph.
struct::graph:op::diameter g ?options...?
This command determines the (un)directed diameter of the graph g. It accepts the option -arc-mode -arcmode
mode of struct::graph:op::dijkstra.
The (un)directed diameter of a graph is the maximal (un)directed eccentricity of all nodes in
the graph.
REFERENCES
[1] Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]
[2] Kruskal's algorithm [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
[3] Prim's algorithm [http://en.wikipedia.org/wiki/Prim%27s_algorithm]
[4] Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]
[5] Strongly connected components [http://en.wikipedia.org/wiki/Strongly_connected_components]
[6] Tarjan's strongly connected components algorithm [http://en.wikipedia.org/wiki/Tar-
jan%27s_strongly_connected_components_algorithm]
[7] Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]
[8] Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)!-->]
BUGS, IDEAS, FEEDBACK
This document, and the package it describes, will undoubtedly contain bugs and other problems.
Please report such in the category struct :: graph of the Tcllib SF Trackers [http://source-
forge.net/tracker/?group_id=12883]. Please also report any ideas for enhancements you may have for
either package and/or documentation.
KEYWORDS
adjacency matrix, adjacent, arc, articulation point, bipartite, bridge, connected component, cut
edge, cut vertex, degree, diameter, dijkstra, distance, eccentricity, edge, graph, isthmus, loop,
minimal spanning tree, neighbour, node, radius, strongly connected component, subgraph, vertex
COPYRIGHT
Copyright (c) 2008 Alejandro Paz <vidriloco@gmail.com>
Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>
struct 0.9 struct::graph::op(n)
|
The way to report a problem with this manual page depends on the type of problem: