Tcl Library Source Code

Documentation
Login
EuroTcl/OpenACS 11 - 12 JULY 2024, VIENNA


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

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

Table Of Contents

SYNOPSIS

package require Tcl 8.6 9
package require struct::graph::op ?0.11.4?

struct::graph::op::toAdjacencyMatrix g
struct::graph::op::toAdjacencyList G ?options...?
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...?
struct::graph::op::BellmanFord G startnode
struct::graph::op::Johnsons G ?options...?
struct::graph::op::FloydWarshall G
struct::graph::op::MetricTravellingSalesman G
struct::graph::op::Christofides G
struct::graph::op::GreedyMaxMatching G
struct::graph::op::MaxCut G U V
struct::graph::op::UnweightedKCenter G k
struct::graph::op::WeightedKCenter G nodeWeights W
struct::graph::op::GreedyMaxIndependentSet G
struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
struct::graph::op::VerticesCover G
struct::graph::op::EdmondsKarp G s t
struct::graph::op::BusackerGowen G desiredFlow s t
struct::graph::op::ShortestsPathsByBFS G s outputFormat
struct::graph::op::BFS G s ?outputFormat...?
struct::graph::op::MinimumDiameterSpanningTree G
struct::graph::op::MinimumDegreeSpanningTree G
struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
struct::graph::op::BlockingFlowByDinic G s t
struct::graph::op::BlockingFlowByMKM G s t
struct::graph::op::createResidualGraph G f
struct::graph::op::createAugmentingNetwork G f path
struct::graph::op::createLevelGraph Gf s
struct::graph::op::TSPLocalSearching G C
struct::graph::op::TSPLocalSearching3Approx G C
struct::graph::op::createSquaredGraph G
struct::graph::op::createCompleteGraph G originalEdges

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

Background theory and terms

Shortest Path Problem

Travelling Salesman Problem

Matching Problem

Cut Problems

K-Center Problem

Flow Problems

Approximation algorithm

References

  1. Adjacency matrix

  2. Adjacency list

  3. Kruskal's algorithm

  4. Prim's algorithm

  5. Bipartite graph

  6. Strongly connected components

  7. Tarjan's strongly connected components algorithm

  8. Cut vertex

  9. Bridge

  10. Bellman-Ford's algorithm

  11. Johnson's algorithm

  12. Floyd-Warshall's algorithm

  13. Travelling Salesman Problem

  14. Christofides Algorithm

  15. Max Cut

  16. Matching

  17. Max Independent Set

  18. Vertex Cover

  19. Ford-Fulkerson's algorithm

  20. Maximum Flow problem

  21. Busacker-Gowen's algorithm

  22. Dinic's algorithm

  23. K-Center problem

  24. BFS

  25. Minimum Degree Spanning Tree

  26. Approximation algorithm

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 Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

adjacency list, adjacency matrix, adjacent, approximation algorithm, arc, articulation point, augmenting network, augmenting path, bfs, bipartite, blocking flow, bridge, complete graph, connected component, cut edge, cut vertex, degree, degree constrained spanning tree, diameter, dijkstra, distance, eccentricity, edge, flow network, graph, heuristic, independent set, isthmus, level graph, local searching, loop, matching, max cut, maximum flow, minimal spanning tree, minimum cost flow, minimum degree spanning tree, minimum diameter spanning tree, neighbour, node, radius, residual graph, shortest path, squared graph, strongly connected component, subgraph, travelling salesman, vertex, vertex cover

CATEGORY

Data structures

COPYRIGHT

Copyright © 2008 Alejandro Paz
Copyright © 2008 (docs) Andreas Kupries
Copyright © 2009 Michal Antoniewski