struct::graph::op(3tcl)

📦
version 2.0 · 2 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

💅 struct::graph::op — graph algorithms, but make it iconic 💅

the struct::graph::op(3tcl) manual page, rewritten with love by your favorite Unix bestie

✨ NAME ✨

struct::graph::op — operation for (un)directed graph objects 🦋

🌸 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

okay that's a LOT of entry points but bestie, every single one of them ate. 💖

🫶 DESCRIPTION 🫶

So the package this page is about, struct::graph::op, is a companion to the package struct::graph. It hands you a whole series of common operations and algorithms that you can throw at (un)directed graphs. no cap, it's the group chat of graph tooling.

And here's the plot twist — even though it's a companion, the package is not directly dependent on struct::graph. It only depends on the API that package defines. Which means: the operations in here can be applied to any and all graph objects that provide the same API as the objects created through struct::graph. it's giving "I don't need your whole personality, just your interface." 💀

👑 OPERATIONS 👑

💫 struct::graph::op::toAdjacencyMatrix g

Takes the graph g and hands you back a nested list containing the adjacency matrix of g. ✨

The elements of the outer list are the rows</> of the matrix, and the inner elements are the column values in each row. The matrix has "n+1" rows and columns, where the first row and column (index 0) hold the name of the node that row/column is for. Everything else? Boolean values — True if there's an arc between the 2 nodes of the respective row and column, and False otherwise.

Heads up bestie: the matrix is symmetric. It does not represent the directionality of arcs, only their presence between nodes. It's also unable to represent parallel arcs in g. so don't come for it about that, it simply cannot. 😭

💫 struct::graph::op::toAdjacencyList G ?options...?

This procedure creates, for input graph G, its representation as an Adjacency List. It handles both directed and undirected graphs (default is undirected). It returns a dictionary that for each node (the key) returns a list of nodes adjacent to it. When you're in weighted mode, each adjacent node also gets the weight of the edge included. 🎀

Arguments:

  • Graph object G (input) — a graph to convert into an Adjacency List.

Options:

  • -directed — by default G is operated as if it were an Undirected graph. Using this option tells the command to handle G as the directed graph it is.
  • -weights — by default any weight information the graph G may have is ignored. Using this option tells the command to put weight information into the result. In that case it is expected that all arcs have a proper weight, and an error is thrown if that is not the case. (so if you're missing a weight, that's on you, not on the command 💅)

💫 struct::graph::op::kruskal g

Takes the graph g and returns a list containing the names of the arcs in g which span up a minimum weight spanning tree (MST) — or, in the case of an un-connected graph, a minimum weight spanning forest (except for the 1-vertex components, those get left out). Kruskal's algorithm is the one doing the work here. ⭐

Time complexity: O(E*log E) or O(E* log V), where V is the number of vertices and E is the number of edges in graph g.

The command will throw an error if one or more arcs in g have no weight associated with them. no weight, no entry, periodt.

A note regarding the result: the command refrains from explicitly listing the nodes of the MST, because that info is implicitly provided in the arcs already. efficient queen behavior. 👑

💫 struct::graph::op::prim g

Takes the graph g and returns a list containing the names of the arcs in g which span up a minimum weight spanning tree (MST) — or, in the case of an un-connected graph, a minimum weight spanning forest (again, except for the 1-vertex components). This time it's Prim's algorithm computing the tree or forest. 🌸

Time complexity lands somewhere between O(E+V*log V) and O(V*V), depending on the implementation (Fibonacci heap + Adjacency list versus Adjacency Matrix). As usual, V is the number of vertices and E the number of edges in graph g.

Also throws an error if one or more arcs in g have no weight associated with them. same energy, same consequences.

And same note about the result: it refrains from explicitly listing the nodes of the MST, because the arcs already say everything. 🦋

💫 struct::graph::op::isBipartite? g ?bipartvar?

Takes the graph g and returns a boolean value telling you whether it's bipartite — true — or not — false. 🎀

If the variable bipartvar is specified, the two partitions of the graph are stored there as a list, if, and only if the graph is bipartit. If it is not, the variable — if specified — is not touched. so it stays exactly as it was, respectfully minding its own business. 🙈

💫 struct::graph::op::tarjan g

Computes the set of strongly connected components (SCCs) of the graph g. The result is a list of sets, each one containing 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. overlap? never heard of her. 💅

  • 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

Computes the set of connected components (CCs) of the graph g. The result is a list of sets, each containing 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

Computes the connected component (CC) of the graph g that contains the node n. The result is a set 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. don't be out here passing random names bestie, it will clock you. 💀

💫 struct::graph::op::isConnected? g

The convenience command of the group — it determines whether the graph g is connected or not. Result is a boolean: true if the graph is connected, false otherwise. short, sweet, slayed. ⭐

💫 struct::graph::op::isCutVertex? g n

Determines whether the node n in the graph g is a cut vertex (aka articulation point). Result is a boolean: true if the node is a cut vertex, false otherwise. 🔥

The command will throw an error if n is not a node of the graph g.

💫 struct::graph::op::isBridge? g a

Determines whether the arc a in the graph g is a bridge (aka cut edge, or isthmus — yes, isthmus, she contains multitudes 🌈). Result is a boolean: true if the arc is a bridge, false otherwise.

The command will throw an error if a is not an arc of the graph g.

💫 struct::graph::op::isEulerian? g ?tourvar?

Determines whether the graph g is eulerian or not. Result is a boolean: true if the graph is eulerian, 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. a whole itinerary, iconic.

💫 struct::graph::op::isSemiEulerian? g ?pathvar?

Determines whether the graph g is semi-eulerian or not. Result is a boolean: true if the graph is semi-eulerian, 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. chef's kiss. 👑

💫 struct::graph::op::dijkstra g start ?options...?

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, every arc goes from source to target, no detours 💫 For undirected traversal, all the arcs also get walked in the opposite direction too. And bestie, undirected is the default. That's just how we're rolling unless you say otherwise 🫶
  • -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. 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 that node and any other node in the graph. So basically how far is your most far-away bestie from you 🥺

🌸 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. Yes, the smallest of all the eccentricities — the most chill node's worst-case distance, lowkey iconic 👑

🌸 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. The biggest of the big ones, periodt 🔥

🌸 struct::graph::op::BellmanFord G startnode 🌸

Searching for shortests paths between chosen node and all other nodes in graph G. Based on relaxation method — not the self-care kind, the algorithm kind 😌 In comparison to struct::graph::op::dijkstra it doesn't need the assumption that all weights on edges in input graph G have to be positive. So if your edges are out here being negative, BellmanFord said "not my problem, I got you" 💜

That generality sets the complexity of the algorithm to — O(V*E), where V is the number of vertices and E is number of edges in graph G.

Arguments:

  • Graph object G (input) — Directed, connected and edge weighted graph G, without any negative cycles (presence of cycles with the negative sum of weight means that there is no shortest path, since the total weight becomes lower each time the cycle is traversed). Negative weights on edges are allowed ✨
  • Node startnode (input) — The node for which we find all shortest paths to each other node in graph G.

Result:

Dictionary containing for each node (key) distances to each other node in graph G.

🚨 Note: If the algorithm finds a negative cycle, it will return an error message. No cap.

🌸 struct::graph::op::Johnsons G ?options...? 🌸

Searching for shortest paths between all pairs of vertices in graph. For sparse graphs asymptotically quicker than struct::graph::op::FloydWarshall algorithm. Johnson's algorithm uses struct::graph::op::BellmanFord and struct::graph::op::dijkstra as subprocedures — it's literally assembling the squad 🫶

Time complexity: O(n**2*log(3tcl) +n*m), where n is the number of nodes and m is the number of edges in graph G.

Arguments:

  • Graph object G (input) — Directed graph G, weighted on edges and not containing any cycles with negative sum of weights (the presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed). Negative weights on edges are allowed ✨

Options:

  • -filter — Returns only existing distances, cuts all Inf values for non-existing connections between pairs of nodes.

Result:

Dictionary containing distances between all pairs of vertices.

🌸 struct::graph::op::FloydWarshall G 🌸

Searching for shortest paths between all pairs of edges in weighted graphs.

Time complexity: O(V^3) — where V is number of vertices.

Memory complexity: O(V^2).

Arguments:

  • Graph object G (input) — Directed and weighted graph G.

Result:

Dictionary containing shortest distances to each node from each node.

💀 Note: Algorithm finds solutions dynamically. It compares all possible paths through the graph between each pair of vertices. Graph shouldn't possess any cycle with negative sum of weights (the presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed).

On the other hand, the algorithm can be used to find those cycles — if any shortest distance found by the algorithm for any nodes v and u (when v is the same node as u) is negative, that node surely belongs to at least one negative cycle. Sneaky little detective behaviour, we love to see it 🔍

🌸 struct::graph::op::MetricTravellingSalesman G 🌸

Algorithm for solving a metric variation of Travelling salesman problem. TSP problem is NP-Complete, so there is no efficient algorithm to solve it. Greedy methods are getting extremely slow, with the increase in the set of nodes 😭

Arguments:

  • Graph object G (input) — Undirected, weighted graph G.

Result:

Approximated solution of minimum Hamilton Cycle — closed path visiting all nodes, each exactly one time. One loop, everyone gets visited once, no repeats, periodt 💅

Note: It's a 2-approximation algorithm.

🌸 struct::graph::op::Christofides G 🌸

Another algorithm for solving metric TSP problem. Christofides implementation uses Max Matching for reaching better approximation factor. Upgrading the fit, honestly 🎀

Arguments:

  • Graph Object G (input) — Undirected, weighted graph G.

Result:

Approximated solution of minimum Hamilton Cycle — closed path visiting all nodes, each exactly one time.

Note: It's a 3/2 approximation algorithm.

🌸 struct::graph::op::GreedyMaxMatching G 🌸

Greedy Max Matching procedure, which finds maximal matching (not maximum) for given graph G. It adds edges to solution, beginning from edges with the lowest cost. Cheapest first, that's the whole strategy 💸

Arguments:

  • Graph Object G (input) — Undirected graph G.

Result:

Set of edges — the max matching for graph G.

🌸 struct::graph::op::MaxCut G U V 🌸

Algorithm solving a Maximum Cut Problem.

Arguments:

  • Graph Object G (input) — The graph to cut.
  • List U (output) — Variable storing first set of nodes (cut) given by solution.
  • List V (output) — Variable storing second set of nodes (cut) given by solution.

Result:

Algorithm returns number of edges between found two sets of nodes.

Note: MaxCut is a 2-approximation algorithm.

🌸 struct::graph::op::UnweightedKCenter G k 🌸

Approximation algorithm that solves a k-center problem.

Arguments:

  • Graph Object G (input) — Undirected complete graph G, which satisfies triangle inequality.
  • Integer k (input) — Positive integer that sets the number of nodes that will be included in k-center.

Result:

Set of nodes — k center for graph G.

Note: UnweightedKCenter is a 2-approximation algorithm.

🌸 struct::graph::op::WeightedKCenter G nodeWeights W 🌸

Approximation algorithm that solves a weighted version of k-center problem.

Arguments:

  • Graph Object G (input) — Undirected complete graph G, which satisfies triangle inequality.
  • Integer W (input) — Positive integer that sets the maximum possible weight of k-center found by algorithm.
  • List nodeWeights (input) — List of nodes and its weights in graph G.

Result:

Set of nodes, which is solution found by algorithm.

Note: WeightedKCenter is a 3-approximation algorithm.

🌸 struct::graph::op::GreedyMaxIndependentSet G 🌸

A maximal independent set is an independent set such that adding any other node to the set forces the set to contain an edge. Like, it's maximally independent — one more node and the whole vibe collapses into an edge 😅

Algorithm for input graph G returns set of nodes (list), which are contained in Max Independent Set found by algorithm.

🌸 struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights 🌸

Weighted variation of Maximal Independent Set. It takes as an input argument not only graph G but also set of weights for all vertices in graph G.

Note: Read also Maximal Independent Set description for more info.

🌸 struct::graph::op::VerticesCover G 🌸

Vertices cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. This 2-approximation algorithm searches for minimum vertices cover, which is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. For input graph G the algorithm returns the set of edges (list), which is Vertex Cover found by algorithm.

🌸 struct::graph::op::EdmondsKarp G s t 🌸

Improved Ford-Fulkerson's algorithm, computing the maximum flow in given flow network G. Glow up of the classic, fr fr 🔥

Arguments:

  • Graph Object G (input) — the weighted, directed graph itself. Every edge needs an integer attribute set on it, and that attribute is treated as the maximum throughput that link can carry. Basically: how much juice can this pipe move? 🚰
  • Node s (input) — the source node for graph G. Where all the flow starts, the origin story ✨
  • Node t (input) — the sink node for graph G. Where all the flow wants to end up, the final destination 💖

Result:

The procedure hands you back a dictionary stuffed with throughputs for all the edges. For each key (and the key is the edge between nodes u and v, written as the list u v) there's a value, and that value is the throughput for that key. Lowkey important detail: edges where the throughput value is 0 are not returned at all. It's like there was never a link in the flow network between the nodes those edges connect. Not me ghosting edges with zero throughput 💀

The whole general idea of the algorithm is finding the shortest augumenting paths in graph G for as long as they exist, and for each path, updating the edge's weights along that path with the maximum possible throughput. The final (maximum) flow is found when there's no other augumenting path left from source to sink. Periodt.

Note: Algorithm complexity: O(V*E), where V is the number of nodes and E is the number of edges in graph G.

struct::graph::op::BusackerGowen G desiredFlow s t 🫶

Bestie this one solves the minimum cost flow problem. So the goal is finding a flow whose max value can be desiredFlow, going from source node s to sink node t in the given flow network G. And here's the twist — that network, on top of having throughputs at the edges, also has a non-negative cost defined on every edge. That cost is the price of using that edge when you're directing flow through it. Think of it as fuel usage, time, or honestly any other measure that depends on how much you use it. It's giving "cheap route vs expensive route" energy 💸

Arguments:

  • Graph Object G (input) — the flow network, a directed graph. Every edge in here should carry two integer attributes: cost and throughput.
  • Integer desiredFlow (input) — the max value of the flow for that network. That's the ceiling you're aiming for 🔥
  • Node s (input) — the source node for graph G.
  • Node t (input) — the sink node for graph G.

Result:

A dictionary containing the values of used throughputs for each edge (that's the key), found by the algorithm. Iconic.

Note: Algorithm complexity: O(V**2*desiredFlow), where V is the number of nodes in graph G.

struct::graph::op::ShortestsPathsByBFS G s outputFormat 🦋

Shortest pathfinding, but make it BFS. The big flex here: compared to struct::graph::op::dijkstra, this one can actually work with negative weights on edges. Of course negative cycles are not allowed — absolutely not, we do not do that here 🙈 The algorithm is better than dijkstra for sparse graphs, but lowkey there are some pathological cases (and ngl those cases generally don't show up in practise) where the time complexity increases exponentially as the number of nodes grows. So, y'know. Situational slay 💅

Arguments:

  • Graph Object G (input) — the input graph.
  • Node s (input) — the source node, the one you compute all distances from to every other node in graph G.

Options and result:

  • distances — when the selected outputFormat is distances, the procedure returns a dictionary containing the distances between source node s and each other node in graph G.
  • paths — when the selected outputFormat is paths, the procedure returns a dictionary containing, for each node v, a list of nodes which is a path between source node s and node v.

struct::graph::op::BFS G s ?outputFormat...? 🌸

Breadth-First Search, bestie — the algorithm builds the BFS Tree. Memory and time complexity: O(V + E), where V is the number of nodes and E is number of edges. Efficient queen 👑

Arguments:

  • Graph Object G (input) — the input graph.
  • Node s (input) — the source node for the BFS procedure.

Options and result:

  • graph — when the selected outputFormat is graph, the procedure returns a graph structure (struct::graph) that's equivalent to the BFS tree found by the algorithm.
  • tree — when the selected outputFormat is tree, the procedure returns a tree structure (struct::tree) that's equivalent to the BFS tree found by the algorithm.

struct::graph::op::MinimumDiameterSpanningTree G 🎀

The goal here is finding, for the input graph G, the spanning tree that has the minimum diameter value. Skinny legend behavior.

Okay so the general idea of the algorithm is to run BFS over all the vertices in graph G. If the diameter d of the tree is odd, then we're sure the tree given by BFS is minimum (when we're considering diameter value). When the diameter d is even, though, the optimal tree can have a minimum diameter equal to d or d-1. Sneaky.

In that case, what the algorithm does is rebuild the tree given by BFS by adding a vertice between the root node and root's child node (nodes), in such a way that the subtree created with the child node as root node is the greatest one (meaning it has the greatests height). Then, in the next step, for that rebuilded tree, we run BFS again with the new node as root node. If the height of the tree didn't change, we've found a better solution. Glow up achieved ✨

For input graph G, the algorithm returns the graph structure (struct::graph) that is a spanning tree with the minimum diameter found by the algorithm.

struct::graph::op::MinimumDegreeSpanningTree G 💜

The algorithm finds, for input graph G, a spanning tree T with the minimum possible degree. Okay heads up though — that problem is NP-hard, so this algorithm is an approximation algorithm. Not a perfect solution, but she's doing her best and honestly? Respect 🫡

Let V be the set of nodes for graph G, and let W be any subset of V. Let's also assume OPT is the optimal solution and ALG is the solution found by the algorithm for input graph G.

It can be proven that the solution found with the algorithm must fulfil this inequality:

((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(3tcl) + 1.

Math ate, no crumbs left 🔥

Arguments:

  • Graph Object G (input) — an undirected simple graph.

Result:

The algorithm returns a graph structure which is equivalent to the spanning tree T found by the algorithm.

struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg 🌈

This one finds the maximum flow for the flow network that graph G represents. It's based on the blocking-flow finding methods, which give us different complexities — and that's what makes it a better fit for different graphs. Choose your fighter 💅

Arguments:

  • Graph Object G (input) — a directed graph G representing the flow network. Each edge should have the attribute throughput set with an integer value.
  • Node s (input) — the source node for the flow network G.
  • Node t (input) — the sink node for the flow network G.

Options:

  • dinic — the procedure will find the maximum flow for flow network G using Dinic's algorithm (struct::graph::op::BlockingFlowByDinic) for blocking flow computation.
  • mkm — the procedure will find the maximum flow for flow network G using Malhotra, Kumar and Maheshwari's algorithm (struct::graph::op::BlockingFlowByMKM) for blocking flow computation.

Result:

The algorithm returns a dictionary containing its flow value for each edge (key) in network G.

Note: struct::graph::op::BlockingFlowByDinic gives O(m*n^2) complexity and struct::graph::op::BlockingFlowByMKM gives O(n^3) complexity, where n is the number of nodes and m is the number of edges in flow network G.

struct::graph::op::BlockingFlowByDinic G s t ⭐

For the given network G with source s and sink t, this algorithm finds a blocking flow, which can then be used to obtain a maximum flow for that network G. Serving as the building block, literally 👑

Arguments:

  • Graph Object G (input) — a directed graph G representing the flow network. Each edge should have the attribute throughput set with an integer value.
  • Node s (input) — the source node for the flow network G.
  • Node t (input) — the sink node for the flow network G.

Result:

The algorithm returns a dictionary containing its blocking flow value for each edge (key) in network G.

Note: Algorithm's complexity is O(n*m), where n is the number of nodes and m is the number of edges in flow network G.

struct::graph::op::BlockingFlowByMKM G s t 🧚

Same mission, different method, bestie. For the given network G with source s and sink t, this algorithm finds a blocking flow, which can be used to obtain a maximum flow for that network G. Malhotra, Kumar and Maheshwari said "we got this" 💪

Arguments:

  • Graph Object G (input) — a directed graph G representing the flow network. Each edge should have the attribute throughput set with an integer value.
  • Node s (input) — the source node for the flow network G.
  • Node t (input) — the sink node for the flow network G.

Result:

The algorithm returns a dictionary containing its blocking flow value for each edge (key) in network G.

Note: Algorithm's complexity is O(n^2), where n is the number of nodes in flow network G.

struct::graph::op::createResidualGraph G f 🍓

This procedure creates a residual graph (or residual network) for network G and the given flow f. Residual era ✨

Arguments:

  • Graph Object G (input) — a flow network, meaning a directed graph where each edge has the attribute throughput set on it.
  • dictionary f (input) — the current flows in flow network G.

Result:

The procedure returns a graph structure that is a residual graph created from input flow network G.

struct::graph::op::createAugmentingNetwork</p> 💫

struct::graph::op::createAugmentingNetwork G f path

Okay bestie, this one builds you an augmenting network ✨ — you feed it a residual network G, a flow f, and an augmenting path path, and it handles the glow-up.

Arguments:

  • Graph Object G (input) — the residual network (a directed graph), where every edge has two attributes set on it: throughput and cost. Both. No skipping. 💅
  • Dictionary f (input) — a dictionary holding, for every edge (as key 🔑), the current value of the flow running along that edge.
  • List path (input) — the augmenting path, a set of edges (as a list) that we're doing the network modification for.

Result:

The algorithm hands back a graph structure containing the modified augmenting network. 🎀

struct::graph::op::createLevelGraph</p> 🌈

struct::graph::op::createLevelGraph Gf s

For a given residual graph Gf, this procedure finds the level graph. It's giving BFS energy fr fr 🦋

Arguments:

  • Graph Object Gf (input) — the residual network, where each edge has its throughput attribute set to some certain value.
  • Node s (input) — the source node for the residual network Gf. 🌟

Result:

The procedure returns a level graph created from the input residual network. Slay. ✨

struct::graph::op::TSPLocalSearching</p> 🚗

struct::graph::op::TSPLocalSearching G C

This is a heuristic of local searching for the Travelling Salesman Problem. Given some solution to TSP, it checks whether it's possible to find a better one. TSP is famously NP-Complete 😭 so this is an approximation algorithm — with a 2 approximation factor.

Arguments:

  • Graph Object G (input) — an undirected and complete graph with the attribute "weight" set on each single edge.
  • List C (input) — a list of edges forming a Hamiltonian cycle, which is a solution of the TSP Problem for graph G.

Result:

The algorithm returns the best solution for the TSP problem that it was able to find. Bestie tried her best 💖

Note: The solution depends on the choosing of the beginning cycle C. It's not true that a better cycle assures that a better solution will be found — but practise shows that we should give a starting cycle with as small a sum of weights as possible. 👑

struct::graph::op::TSPLocalSearching3Approx</p> 🌟

struct::graph::op::TSPLocalSearching3Approx G C

Same local-searching heuristic vibe as above, but this time we're rocking a 3 approximation factor instead of 2. Again: TSP is NP-Complete, so approximation is just the move. 💅

Arguments:

  • Graph Object G (input) — an undirected and complete graph with the attribute "weight" set on each single edge.
  • List C (input) — a list of edges being a Hamiltonian cycle, which is a solution of the TSP Problem for graph G.

Result:

The algorithm returns the best solution for the TSP problem that it was able to find. 🎀

Note: In practise, the 3-approximation algorithm turns out to be far more effective than the 2-approximation one, but it gives a worser approximation factor. Further heuristics of local searching (e.g. 4-approximation) don't give enough boost to square the increase of approximation factor, so 2 and 3 approximations are mainly used. That's the tea. ☕

struct::graph::op::createSquaredGraph</p> 🦋

struct::graph::op::createSquaredGraph G

An X-Squared graph is a graph with the same set of nodes as the input graph G, but a different set of edges. It has an edge (u,v) if and only if the distance between the u and v nodes is not greater than X, and u != v. Periodt. ✨

For an input graph G, this procedure returns its two-squared graph.

Note: The distances used in choosing the new set of edges are considering the number of edges, not the sum of weights at edges. Don't get it twisted. 💀

struct::graph::op::createCompleteGraph</p> 👑

struct::graph::op::createCompleteGraph G originalEdges

For an input graph G, this procedure adds the missing arcs to make it a complete graph 🌈. It also holds, in the variable originalEdges, the set of arcs that graph G possessed before that operation. Iconic. 💖

✨ BACKGROUND THEORY AND TERMS ✨ 🎀

Okay so now we're doing the lore section, bestie. Grab a snack 🍓 — this is the theory behind all those algorithms above, and it's lowkey fascinating ngl.

SHORTEST PATH PROBLEM 🛣️

Definition (single-pair shortest path problem):

Formally, given a weighted graph (let V be the set of vertices, and E a set of edges), and one vertice v of V, find a path P from v to a v' of V so that the sum of weights on edges along the path is minimal among all paths connecting v to v'. 💫

Generalizations:

  • The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph.
  • The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by reversing the edges in the graph. Big brain move 🧠
  • The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices v, v' in the graph.
Note: The result of the Shortest Path problem can be a Shortest Path tree, which is a subgraph of a given (possibly weighted) graph constructed so that the distance between a selected root node and all other nodes is minimal. It is a tree because if there are two paths between the root node and some vertex v (i.e. a cycle), we can delete the last edge of the longer path without increasing the distance from the root node to any node in the subgraph. So elegant, honestly. 🌸

TRAVELLING SALESMAN PROBLEM 🚗💨

Definition:

For a given edge-weighted graph (weights on edges should be positive), the goal is to find the cycle that visits each node in the graph exactly once (a Hamiltonian cycle). The way that's so simple to say and so hard to do 😭

Generalizations:

  • Metric TSP — a very natural restriction of the TSP is to require that the distances between cities form a metric, i.e., they satisfy the triangle inequality. That is, for any 3 cities A, B and C, the distance between A and C must be at most the distance from A to B plus the distance from B to C. Most natural instances of TSP satisfy this constraint. ✨
  • Euclidean TSP — Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. Euclidean TSP is a particular case of TSP with triangle inequality, since distances in the plane obey the triangle inequality. However, it seems to be easier than general TSP with triangle inequality. For example, the minimum spanning tree of the graph associated with an instance of Euclidean TSP is a Euclidean minimum spanning tree, and so can be computed in expected O(n log n) time for n points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly. 🏃‍♀️
  • Asymmetric TSP — in most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance from A to B is not equal to the distance from B to A is called asymmetric TSP. A practical application of an asymmetric TSP is route optimisation using street-level routing (asymmetric due to one-way streets, slip-roads and motorways). Real world tea ☕

MATCHING PROBLEM 💞

Definition:

Given a graph G = (V,E), a matching or edge-independent set M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex. A vertex is matched if it is incident to an edge in the matching M. Otherwise the vertex is unmatched. We love a clean pairing 🫶

Generalizations:

  • Maximal matching — a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a proper subset of any other matching in graph G. In other words, a matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M.
  • Maximum matching — a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number of a graph G is the size of a maximum matching. Note that every maximum matching is maximal, but not every maximal matching is a maximum matching. Sneaky distinction, ik 😭
  • Perfect matching — a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching. Every perfect matching is maximum and hence maximal. In some literature, the term complete matching is used. A perfect matching is also a minimum-size edge cover. Moreover, the size of a maximum matching is no larger than the size of a minimum edge cover. So much terminology, but we move 💅
  • Near-perfect matching — a matching in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.

Related terms:

  • Alternating path — given a matching M, an alternating path is a path in which the edges belong alternatively to the matching and not to the matching. 🔄
  • Augmenting path — given a matching M, an augmenting path is an alternating path that starts from and ends on free (unmatched) vertices. ✨

✂️ CUT PROBLEMS ✂️

Definition:

okay so a cut is literally a partition of the vertices of a graph into two disjoint subsets, bestie 💅. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they're in its cut-set.

Formally:

  • a cut C = (S,T) is a partition of V of a graph G = (V, E).
  • an s-t cut C = (S,T) of a flow network N = (V, E) is a cut of N such that s is included in S and t is included in T, where s and t are the source and the sink of N respectively.
  • The cut-set of a cut C = (S,T) is such set of edges from graph G = (V, E) that each edge (u, v) satisfies condition that u is included in S and v is included in T.

In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted graph, the same term is defined by the sum of the weights of the edges crossing the cut.

In a flow network, an s-t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set.

The cut of a graph can sometimes refer to its cut-set instead of the partition. iykyk 💀

Generalizations:

  • Minimum cut — A cut is minimum if the size of the cut is not larger than the size of any other cut.
  • Maximum cut — A cut is maximum if the size of the cut is not smaller than the size of any other cut.
  • Sparsest cut — The Sparsest cut problem is to bipartition the vertices so as to minimize the ratio of the number of edges across the cut divided by the number of vertices in the smaller half of the partition.

🎯 K-CENTER PROBLEM 🎯

Definitions:

Unweighted K-Center

For any set S ( which is subset of V ) and node v, let the connect(v,S) be the cost of cheapest edge connecting v with any node in S. The goal is to find such S, that |S| = k and max_v{connect(v,S)} is possibly small.

In other words, we can use it i.e. for finding best locations in the city ( nodes of input graph ) for placing k buildings, such that those buildings will be as close as possible to all other locations in town. main character energy for city planning tbh 🏙️✨

Weighted K-Center

The variation of unweighted k-center problem. Besides the fact graph is edge-weighted, there are also weights on vertices of input graph G. We've got also restriction W. The goal is to choose such set of nodes S ( which is a subset of V ), that it's total weight is not greater than W and also function: max_v { min_u { cost(u,v) }} has the smallest possible worth ( v is a node in V and u is a node in S ).

🌊 FLOW PROBLEMS 🌊

Definitions:

  • the maximum flow problem — the goal is to find a feasible flow through a single-source, single-sink flow network that is maximum. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in the network, as stated in the max-flow min-cut theorem.

More formally for flow network G = (V,E), where for each edge (u, v) we have its throuhgput c(u,v) defined. As flow F we define set of non-negative integer attributes f(u,v) assigned to edges, satisfying such conditions:

  • [1] for each edge (u, v) in G such condition should be satisfied: 0 <= f(u,v) <= c(u,v)
  • [2] Network G has source node s such that the flow F is equal to the sum of outcoming flow decreased by the sum of incoming flow from that source node s.
  • [3] Network G has sink node t such that the the -F value is equal to the sum of the incoming flow decreased by the sum of outcoming flow from that sink node t.
  • [4] For each node that is not a source or sink the sum of incoming flow and sum of outcoming flow should be equal.
  • the minimum cost flow problem — the goal is finding the cheapest possible way of sending a certain amount of flow through a flow network.
  • blocking flow — a blocking flow for a residual network Gf we name such flow b in Gf that:
    • [1] Each path from sink to source is the shortest path in Gf.
    • [2] Each shortest path in Gf contains an edge with fully used throughput in Gf+b.
  • residual network — for a flow network G and flow f residual network is built with those edges, which can send larger flow. It contains only those edges, which can send flow larger than 0.
  • level network — it has the same set of nodes as residual graph, but has only those edges (u,v) from Gf for which such equality is satisfied: distance(s,u)+1 = distance(s,v).
  • augmenting network — it is a modification of residual network considering the new flow values. Structure stays unchanged but values of throughputs and costs at edges are different.

🧮 APPROXIMATION ALGORITHM 🧮

k-approximation algorithm:

Algorithm is a k-approximation, when for ALG (solution returned by algorithm) and OPT (optimal solution), such inequality is true:

  • for minimalization problems: ALG/OPT <= k
  • for maximalization problems: OPT/ALG <= k

📚 REFERENCES 📚

🐛 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 [http://core.tcl.tk/tcllib/reportlist]. 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 (c) 2008 Alejandro Paz <vidriloco@gmail.com>
  • Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>
  • Copyright (c) 2009 Michal Antoniewski <antoniewski.m@gmail.com>

okay bestie that's the whole vibe 💖 source/version: tcllib 0.11.4, struct::graph::op(3tcl). periodt. 💅✨

📦 where this page comes from