[ Main table Of Contents | Tcllib Table Of Contents | Tcllib Index ]

struct::graph::op(n) 0.9 "Tcl Data Structures"

Name

struct::graph::op - Operation for (un)directed graph objects

Table Of Contents

Synopsis

  • package require Tcl 8.4
  • package require struct::graph::op ?0.9?

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 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

  2. Kruskal's algorithm

  3. Prim's algorithm

  4. Bipartite graph

  5. Strongly connected components

  6. Tarjan's strongly connected components algorithm

  7. Cut vertex

  8. Bridge

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. 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

Category

Data structures

Copyright © 2009 for compilation: ActiveState