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  opera-
       tions 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  con-
	      tains 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 isthmus). 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 dictionary 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 -arcmode 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/Tarjan%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://sourceforge.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, dijk-
       stra, 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)