assignment algorithm graphs

Reset password New user? Sign up

Existing user? Log in

Hungarian Maximum Matching Algorithm

Already have an account? Log in here.

The Hungarian matching algorithm , also called the Kuhn-Munkres algorithm, is a \(O\big(|V|^3\big)\) algorithm that can be used to find maximum-weight matchings in bipartite graphs , which is sometimes called the assignment problem . A bipartite graph can easily be represented by an adjacency matrix , where the weights of edges are the entries. Thinking about the graph in terms of an adjacency matrix is useful for the Hungarian algorithm.

A matching corresponds to a choice of 1s in the adjacency matrix, with at most one 1 in each row and in each column.

The Hungarian algorithm solves the following problem:

In a complete bipartite graph \(G\), find the maximum-weight matching. (Recall that a maximum-weight matching is also a perfect matching.)

This can also be adapted to find the minimum-weight matching.

Say you are having a party and you want a musician to perform, a chef to prepare food, and a cleaning service to help clean up after the party. There are three companies that provide each of these three services, but one company can only provide one service at a time (i.e. Company B cannot provide both the cleaners and the chef). You are deciding which company you should purchase each service from in order to minimize the cost of the party. You realize that is an example of the assignment problem, and set out to make a graph out of the following information: \(\quad\) Company\(\quad\) \(\quad\) Cost for Musician\(\quad\) \(\quad\) Cost for Chef\(\quad\) \(\quad\) Cost for Cleaners\(\quad\) \(\quad\) Company A\(\quad\) \(\quad\) $108\(\quad\) \(\quad\) $125\(\quad\) \(\quad\) $150\(\quad\) \(\quad\) Company B\(\quad\) \(\quad\) $150\(\quad\) \(\quad\) $135\(\quad\) \(\quad\) $175\(\quad\) \(\quad\) Company C\(\quad\) \(\quad\) $122\(\quad\) \(\quad\) $148\(\quad\) \(\quad\) $250\(\quad\) Can you model this table as a graph? What are the nodes? What are the edges? Show Answer The nodes are the companies and the services. The edges are weighted by the price.

What are some ways to solve the problem above? Since the table above can be thought of as a \(3 \times 3\) matrix, one could certainly solve this problem using brute force, checking every combination and seeing what yields the lowest price. However, there are \(n!\) combinations to check, and for large \(n\), this method becomes very inefficient very quickly.

The Hungarian Algorithm Using an Adjacency Matrix

The hungarian algorithm using a graph.

With the cost matrix from the example above in mind, the Hungarian algorithm operates on this key idea: if a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.

The Hungarian Method [1] Subtract the smallest entry in each row from all the other entries in the row. This will make the smallest entry in the row now equal to 0. Subtract the smallest entry in each column from all the other entries in the column. This will make the smallest entry in the column now equal to 0. Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn. If there are \(n\) lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than \(n\), then the optimal number of zeroes is not yet reached. Go to the next step. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3.

Solve for the optimal solution for the example in the introduction using the Hungarian algorithm described above. Here is the initial adjacency matrix: Subtract the smallest value in each row from the other values in the row: Now, subtract the smallest value in each column from all other values in the column: Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn: There are 2 lines drawn, and 2 is less than 3, so there is not yet the optimal number of zeroes. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3. 2 is the smallest entry. First, subtract from the uncovered rows: Now add to the covered columns: Now go back to step 3, drawing lines through the rows and columns that have 0 entries: There are 3 lines (which is \(n\)), so we are done. The assignment will be where the 0's are in the matrix such that only one 0 per row and column is part of the assignment. Replace the original values: The Hungarian algorithm tells us that it is cheapest to go with the musician from company C, the chef from company B, and the cleaners from company A. We can verify this by brute force. 108 + 135 + 250 = 493 108 + 148 + 175 = 431 150 + 125 + 250 = 525 150 + 148 + 150 = 448 122 + 125 + 175 = 422 122 + 135 + 150 = 407. We can see that 407 is the lowest price and matches the assignment the Hungarian algorithm determined. \(_\square\)

The Hungarian algorithm can also be executed by manipulating the weights of the bipartite graph in order to find a stable, maximum (or minimum) weight matching. This can be done by finding a feasible labeling of a graph that is perfectly matched, where a perfect matching is denoted as every vertex having exactly one edge of the matching.

How do we know that this creates a maximum-weight matching?

A feasible labeling on a perfect match returns a maximum-weighted matching. Suppose each edge \(e\) in the graph \(G\) connects two vertices, and every vertex \(v\) is covered exactly once. With this, we have the following inequality: \[w(M’) = \sum_{e\ \epsilon\ E} w(e) \leq \sum_{e\ \epsilon\ E } \big(l(e_x) + l(e_y)\big) = \sum_{v\ \epsilon\ V} l(v),\] where \(M’\) is any perfect matching in \(G\) created by a random assignment of vertices, and \(l(x)\) is a numeric label to node \(x\). This means that \(\sum_{v\ \epsilon\ V}\ l(v)\) is an upper bound on the cost of any perfect matching. Now let \(M\) be a perfect match in \(G\), then \[w(M) = \sum_{e\ \epsilon\ E} w(e) = \sum_{v\ \epsilon\ V}\ l(v).\] So \(w(M’) \leq w(M)\) and \(M\) is optimal. \(_\square\)

Start the algorithm by assigning any weight to each individual node in order to form a feasible labeling of the graph \(G\). This labeling will be improved upon by finding augmenting paths for the assignment until the optimal one is found.

A feasible labeling is a labeling such that

\(l(x) + l(y) \geq w(x,y)\ \forall x \in X, y \in Y\), where \(X\) is the set of nodes on one side of the bipartite graph, \(Y\) is the other set of nodes, \(l(x)\) is the label of \(x\), etc., and \(w(x,y)\) is the weight of the edge between \(x\) and \(y\).

A simple feasible labeling is just to label a node with the number of the largest weight from an edge going into the node. This is certain to be a feasible labeling because if \(A\) is a node connected to \(B\), the label of \(A\) plus the label of \(B\) is greater than or equal to the weight \(w(x,y)\) for all \(y\) and \(x\).

A feasible labeling of nodes, where labels are in red [2] .

Imagine there are four soccer players and each can play a few positions in the field. The team manager has quantified their skill level playing each position to make assignments easier.

How can players be assigned to positions in order to maximize the amount of skill points they provide?

The algorithm starts by labeling all nodes on one side of the graph with the maximum weight. This can be done by finding the maximum-weighted edge and labeling the adjacent node with it. Additionally, match the graph with those edges. If a node has two maximum edges, don’t connect them.

Although Eva is the best suited to play defense, she can't play defense and mid at the same time!

If the matching is perfect, the algorithm is done as there is a perfect matching of maximum weights. Otherwise, there will be two nodes that are not connected to any other node, like Tom and Defense. If this is the case, begin iterating.

Improve the labeling by finding the non-zero label vertex without a match, and try to find the best assignment for it. Formally, the Hungarian matching algorithm can be executed as defined below:

The Hungarian Algorithm for Graphs [3] Given: the labeling \(l\), an equality graph \(G_l = (V, E_l)\), an initial matching \(M\) in \(G_l\), and an unmatched vertex \(u \in V\) and \(u \notin M\) Augmenting the matching A path is augmenting for \(M\) in \(G_l\) if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices , or unmatched, in \(M\). We will keep track of a candidate augmenting path starting at the vertex \(u\). If the algorithm finds an unmatched vertex \(v\), add on to the existing augmenting path \(p\) by adding the \(u\) to \(v\) segment. Flip the matching by replacing the edges in \(M\) with the edges in the augmenting path that are not in \(M\) \((\)in other words, the edges in \(E_l - M).\) Improving the labeling \(S \subseteq X\) and \(T \subseteq Y,\) where \(S\) and \(T\) represent the candidate augmenting alternating path between the matching and the edges not in the matching. Let \(N_l(S)\) be the neighbors to each node that is in \(S\) along edges in \(E_l\) such that \(N_l(S) = \{v|\forall u \in S: (u,v) \in E_l\}\). If \(N_l(S) = T\), then we cannot increase the size of the alternating path (and therefore can't further augment), so we need to improve the labeling. Let \(\delta_l\) be the minimum of \(l(u) + l(v) - w(u,v)\) over all of the \(u \in S\) and \(v \notin T\). Improve the labeling \(l\) to \(l'\): If \(r \in S,\) then \(l'(r) = l(r) - \delta_l,\) If \(r \in T,\) then \(l'(r) = l(r) + \delta_l.\) If \(r \notin S\) and \(r \notin T,\) then \(l'(r) = l(r).\) \(l'\) is a valid labeling and \(E_l \subset E_{l'}.\) Putting it all together: The Hungarian Algorithm Start with some matching \(M\), a valid labeling \(l\), where \(l\) is defined as the labelling \(\forall x \in X, y \in Y| l(y) = 0, l(x) = \text{ max}_{y \in Y}(w\big(x, y)\big)\). Do these steps until a perfect matching is found \((\)when \(M\) is perfect\():\) (a) Look for an augmenting path in \(M.\) (b) If an augmenting path does not exist, improve the labeling and then go back to step (a).

Each step will increase the size of the matching \(M\) or it will increase the size of the set of labeled edges, \(E_l\). This means that the process will eventually terminate since there are only so many edges in the graph \(G\). [4]

When the process terminates, \(M\) will be a perfect matching. By the Kuhn-Munkres theorem , this means that the matching is a maximum-weight matching.

The algorithm defined above can be implemented in the soccer scenario. First, the conflicting node is identified, implying that there is an alternating tree that must be reconfigured.

There is an alternating path between defense, Eva, mid, and Tom.

To find the best appropriate node, find the minimum \(\delta_l\), as defined in step 4 above, where \(l_u\) is the label for player \(u,\) \(l_v\) is the label for position \(v,\) and \(w_{u, v}\) is the weight on that edge.

The \(\delta_l\) of each unmatched node is computed, where the minimum is found to be a value of 2, between Tom playing mid \((8 + 0 – 6 = 2).\)

The labels are then augmented and the new edges are graphed in the example. Notice that defense and mid went down by 2 points, whereas Eva’s skillset got back two points. However, this is expected as Eva can't play in both positions at once.

Augmenting path leads to relabeling of nodes, which gives rise to the maximum-weighted path.

These new edges complete the perfect matching of the graph, which implies that a maximum-weighted graph has been found and the algorithm can terminate.

The complexity of the algorithm will be analyzed using the graph-based technique as a reference, yet the result is the same as for the matrix-based one.

Algorithm analysis [3] At each \(a\) or \(b\) step, the algorithm adds one edge to the matching and this happens \(O\big(|V|\big)\) times. It takes \(O\big(|V|\big)\) time to find the right vertex for the augmenting (if there is one at all), and it is \(O\big(|V|\big)\) time to flip the matching. Improving the labeling takes \(O\big(|V|\big)\) time to find \(\delta_l\) and to update the labelling accordingly. We might have to improve the labeling up to \(O\big(|V|\big)\) times if there is no augmenting path. This makes for a total of \(O\big(|V|^2\big)\) time. In all, there are \(O\big(|V|\big)\) iterations each taking \(O\big(|V|\big)\) work, leading to a total running time of \(O\big(|V|^3\big)\).

• Matching Algorithms
• Bruff, D. The Assignment Problem and the Hungarian Method . Retrieved June 26, 2016, from http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
• Golin, M. Bipartite Matching & the Hungarian Method . Retrieved Retrieved June 26th, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
• Grinman, A. The Hungarian Algorithm for Weighted Bipartite Graphs . Retrieved June 26, 2016, from http://math.mit.edu/~rpeng/18434/hungarianAlgorithm.pdf
• Golin, M. Bipartite Matching & the Hungarian Method . Retrieved June 26, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf

Problem Loading...

Note Loading...

Set Loading...

Solving assignment problem using min-cost-flow ¶

The assignment problem has two equivalent statements:

• Given a square matrix $A[1..N, 1..N]$ , you need to select $N$ elements in it so that exactly one element is selected in each row and column, and the sum of the values of these elements is the smallest.
• There are $N$ orders and $N$ machines. The cost of manufacturing on each machine is known for each order. Only one order can be performed on each machine. It is required to assign all orders to the machines so that the total cost is minimized.

Here we will consider the solution of the problem based on the algorithm for finding the minimum cost flow (min-cost-flow) , solving the assignment problem in $\mathcal{O}(N^3)$ .

Description ¶

Let's build a bipartite network: there is a source $S$ , a drain $T$ , in the first part there are $N$ vertices (corresponding to rows of the matrix, or orders), in the second there are also $N$ vertices (corresponding to the columns of the matrix, or machines). Between each vertex $i$ of the first set and each vertex $j$ of the second set, we draw an edge with bandwidth 1 and cost $A_{ij}$ . From the source $S$ we draw edges to all vertices $i$ of the first set with bandwidth 1 and cost 0. We draw an edge with bandwidth 1 and cost 0 from each vertex of the second set $j$ to the drain $T$ .

We find in the resulting network the maximum flow of the minimum cost. Obviously, the value of the flow will be $N$ . Further, for each vertex $i$ of the first segment there is exactly one vertex $j$ of the second segment, such that the flow $F_{ij}$ = 1. Finally, this is a one-to-one correspondence between the vertices of the first segment and the vertices of the second part, which is the solution to the problem (since the found flow has a minimal cost, then the sum of the costs of the selected edges will be the lowest possible, which is the optimality criterion).

The complexity of this solution of the assignment problem depends on the algorithm by which the search for the maximum flow of the minimum cost is performed. The complexity will be $\mathcal{O}(N^3)$ using Dijkstra or $\mathcal{O}(N^4)$ using Bellman-Ford . This is due to the fact that the flow is of size $O(N)$ and each iteration of Dijkstra algorithm can be performed in $O(N^2)$ , while it is $O(N^3)$ for Bellman-Ford.

Implementation ¶

The implementation given here is long, it can probably be significantly reduced. It uses the SPFA algorithm for finding shortest paths.

• Daili01 (75.89%)
• prpr (12.5%)
• Oleksandr Kulkov (7.14%)
• Shadab Zafar (2.68%)
• Jakob Kogler (0.89%)
• Hasan-Mesbaul-Ali-Taher (0.89%)

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Algorithms in Graph Theory written in Java, C++, and Python

akueisara/algo-on-graphs

Folders and files.

Name		Name
15 Commits

Repository files navigation

Algorithms on graphs.

Assignments in Java, C++, Python for Algorithms on Graphs on Coursera

Note: I don't have access to submitting my assignments. It's just for my personal learning purpose.

Study Notes

Programming Assignment 1: Decomposition of Graphs

Problem: Finding an Exit from a Maze Problem: Adding Exits to a Maze

Programming Assignment 2: Decomposition of Graphs

Problem: Checking Consistency of CS Curriculum Problem: Determining an Order of Courses Advanced Problem: Checking Whether Any Intersection in a City is Reachable from Any Other

Programming Assignment 3: Paths in Graphs

Problem: Computing the Minimum Number of Flight Segments Problem: Checking whether a Graph is Bipartite

Programming Assignment 4: Paths in Graphs

Problem: Computing the Minimum Cost of a Flight Problem: Detecting Anomalies in Currency Exchange Rates Advanced Problem: Exchanging Money Optimally

Programming Assignment 5: Minimum Spanning Trees

Problem: Building Roads to Connect Cities Problem: Clustering

Programming Assignment 6: Advanced Shortest Paths

Problem: Friend Suggestion Problem: Compute Distance Faster Using Coordinates

Contributors 3

• Python 25.6%

GRAPH	VERTICES	EDGES
Communication	telephones, computers	fiber optic cable
Circuits	gates, registers, processors	wires
Mechanical	joints	rods, beams, springs
Hydraulic	reservoirs, pumping stations	pipelines
Financial	stocks, currency	transactions
Transportation	street intersections, airports	highways, air routes
Scheduling	tasks	precedence constraints
Software systems	functions	function calls
Internet	web pages	hyperlinks
Games	board positions	legal moves
Social networks	people, actors, terrorists	friendships, movie casts, associations
Protein interaction networks	proteins	protein-protein interactions
Genetic regulatory networks	genes	regulatory interactions
Ecological food web	species	predator-prey relationships
Neural networks	neurons	synapses
Infectious disease	people	infections
Electrical power grid	transmission stations	cable
Chemical compounds	molecules	chemical bonds
Phone records	People	phone calls

Java programs in this chapter.

REF PROGRAM DESCRIPTION / JAVADOC - Graph.java undirected graph - GraphGenerator.java generate random graphs - DepthFirstSearch.java depth-first search in a graph - NonrecursiveDFS.java DFS in a graph (nonrecursive) 4.1 DepthFirstPaths.java paths in a graph (DFS) 4.2 BreadthFirstPaths.java paths in a graph (BFS) 4.3 CC.java connected components of a graph - Bipartite.java bipartite or odd cycle (DFS) - BipartiteX.java bipartite or odd cycle (BFS) - Cycle.java cycle in a graph - EulerianCycle.java Eulerian cycle in a graph - EulerianPath.java Eulerian path in a graph - SymbolGraph.java symbol graph - DegreesOfSeparation.java degrees of separation - Digraph.java directed graph - DigraphGenerator.java generate random digraphs 4.4 DirectedDFS.java depth-first search in a digraph - NonrecursiveDirectedDFS.java DFS in a digraph (nonrecursive) - DepthFirstDirectedPaths.java paths in a digraph (DFS) - BreadthFirstDirectedPaths.java paths in a digraph (BFS) - DirectedCycle.java cycle in a digraph - DirectedCycleX.java cycle in a digraph (nonrecursive) - DirectedEulerianCycle.java Eulerian cycle in a digraph - DirectedEulerianPath.java Eulerian path in a digraph - DepthFirstOrder.java depth-first order in a digraph 4.5 Topological.java topological order in a DAG - TopologicalX.java topological order (nonrecursive) - TransitiveClosure.java transitive closure - SymbolDigraph.java symbol digraph 4.6 KosarajuSharirSCC.java strong components (Kosaraju–Sharir) - TarjanSCC.java strong components (Tarjan) - GabowSCC.java strong components (Gabow) - EdgeWeightedGraph.java edge-weighted graph - Edge.java weighted edge - LazyPrimMST.java MST (lazy Prim) 4.7 PrimMST.java MST (Prim) 4.8 KruskalMST.java MST (Kruskal) - BoruvkaMST.java MST (Boruvka) - EdgeWeightedDigraph.java edge-weighted digraph - DirectedEdge.java weighted, directed edge 4.9 DijkstraSP.java shortest paths (Dijkstra) - DijkstraUndirectedSP.java undirected shortest paths (Dijkstra) - DijkstraAllPairsSP.java all-pairs shortest paths 4.10 AcyclicSP.java shortest paths in a DAG - AcyclicLP.java longest paths in a DAG - CPM.java critical path method 4.11 BellmanFordSP.java shortest paths (Bellman–Ford) - EdgeWeightedDirectedCycle.java cycle in an edge-weighted digraph - Arbitrage.java arbitrage detection - FloydWarshall.java all-pairs shortest paths (dense) - AdjMatrixEdgeWeightedDigraph.java edge-weighted graph (dense)

Graph algorithms

Graph coloring algorithms.

• Scheduling algorithms: imagine having a set of jobs to do, and a number of workers, you need to assign each worker a job during some time slot (for simplification, assume each job requires one time slot). Jobs can be scheduled in any order, but pairs of jobs may be in conflict in the sense that they may not be assigned to the same time slot, for example because they both rely on a shared resource. The corresponding graph contains a vertex for every job and an edge for every conflicting pair of jobs. If you have an unlimited number of workers, the chromatic number of the graph is exactly the optimal time to finish all jobs without conflicts.
• Register allocation: a compiler is a computer programs that transforms source code from a high-level language (such as C, Java or OCaml) to machine code. This is usually done is several steps, and one of the last steps consists in allocating registers to the most frequently used values of the program, while putting the other ones in memory. We can model this as a graph coloring problem: the compiler constructs an interference graph, where vertices are symbolic registers and an edge connects two nodes if they are needed at the same time. If the graph can be colored with k colors then the variables can be stored in k registers.
• Pattern matching also has applications in graph coloring.

In this section we will see how to color a graph with k colors. We say that a graph is k-colorable if and only if it can be colored using k or fewer colors.

2-colorability

There is a simple algorithm for determining whether a graph is 2-colorable and assigning colors to its vertices: do a breadth-first search, assigning "red" to the first layer, "blue" to the second layer, "red" to the third layer, etc. Then go over all the edges and check whether the two endpoints of this edge have different colors. This algorithm is O (| V |+| E |) and the last step ensures its correctness.

k-colorability for k>2

For k > 2 however, the problem is much more difficult. For those interested in complexity theory, it can be shown that deciding whether a given graph is k-colorable for k > 2 is an NP-complete problem. The first algorithm that can be thought of is brute-force search: consider every possible assignment of k colors to the vertices, and check whether any of them are correct. This of course is very expensive, on the order of O (( n +1)!) , and impractical. Therefore we have to think of a better algorithm.

A greedy algorithm for finding a non-optimal coloring

Here we will present an algorithm called greedy coloring for coloring a graph. In general, the algorithm does not give the lowest k for which there exists a k-coloring, but tries to find a reasonable coloring while still being reasonably expensive. This is known as an approximation algorithm : we don't find the best solution, but we still find some reasonable solution.

The algorithm is as follows: Consider the vertices in a specific order v 1 ,..., v n and assign to v i the smallest available color not used by v i 's neighbors among v 1 ,..., v i − 1 , adding a fresh color if needed. This algorithm finds a reasonable coloring and is O (| V |+| E |) .

The five color theorem and the four color theorem

A planar graph is a graph which can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. For a long time, it has been known that any planar graph is 5-colorable, this is known as the five color theorem; the proof is usually done by contradiction and can be found on wikipedia .

For a long time, a conjecture was that any planar graph was 4-colorable, since all the known planar graphs (and maps) had been four-colorable. The conjecture was proposed in 1852, and finally proven in 1976 by Kenneth Appel and Wolfgang Haken using a proof by computer (K. Appel and W. Haken, "Every map is four colorable", Bulletin of the American Mathematical Society 82 (1976), 711–12). The proof was also formalized in the Coq theorem prover by Georges Gonthier .

PageRank is an algorithm first used by the Google search engine which tries to rank how important a web page is by giving it a score (or page rank). Described by Google, "PageRank relies on the uniquely democratic nature of the web by using its vast link structure as an indicator of an individual page's value. In essence, Google interprets a link from page A to page B as a vote, by page A, for page B. But, Google looks at more than the sheer volume of votes, or links a page receives; it also analyzes the page that casts the vote. Votes cast by pages that are themselves "important" weigh more heavily and help to make other pages "important".

First of all, the web can be seen as very big graph, with the vertices being the web pages, and the edges being the links between web pages. The first idea is that the more a web page is linked to, the more valuable it is. Therefore the idea is to have in-degree in the web graph as a measure of a page's "value". The second idea is that one might want to weight the incoming links proportional to the value of the referring pages. This is now a recursive problem, which is not easily solveable.

A simplified algorithm

PageRank can be seen as a probability distribution used to represent the likelihood that a person (usually called the surfer) randomly clicking on links will arrive at any particular page. Here, we will take this assumptions, and so the different scores will be number between 0 and 1, adding up to 1. The algorithm presented here is an iterative algorithm and it is simplified.

Let us work out an example on four pages A, B, C and D. Since there are four pages, we initialize the values of the PR (PageRanks) to 0.25 each. Let us say pages B, C and D point to A, and that B has 2 outgoing edges, C one and D three. A simplistic view would compute the new PR(A) as PR(A)=PR(B)+PR(C)+PR(D). However the pageranks have to be normalized by the number of outgoing edges of each page, and we get PR(A)=PR(B)/2+PR(C)/2+PR(D)/3. More generally, if L(P) is the number of outgoing links for page P, then PR(A)=PR(B)/L(B)+PR(C)/L(C)+PR(D)/L(D). In the most general case, the new PR(P) is the sum of all the PR(Q)/L(Q), for all Q pointing to P.

Actually, the imaginary surfer has to stop clicking at some point. In the PageRank theory, the probability that the surfer stops clicking is called the dumping factor and is denoted 1-d (d being the probability that he continues to click. That is, the new PageRank of A is: PR(A)=1-d+d(PR(B)/L(B)+PR(C)/L(C)+PR(D)/L(D)+...).

It can be shown that this algorithm converges. In the limit it can be solved as an eigenvector problem on a matrix representation of the graph, but we won't go into details about that.

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Lowest Cost non-bipartite assignment problem

Any ideas of how to implement an efficient algorithm (better than O(n 2 )) to solve the assignment problem in a non-bipartite graph?

The main idea is the following:

I have two identical sets, lets say S1 = [A,B,C,D] , and S2 = [A,B,C,D] , and there are some edges between different elements of the sets, with a given cost, e.g. A->B (cost 4) , B->C (cost 3) , C->A (cost 10) , D->A (cost 6) .

I want to find the best assignation such that: the amount of assigned elements is maximum with the lowest total cost. (The amount of assigned elements is more important).

So for this example, the best assignation would be:

[A,B,C,D] where assigned and the cost is minimum: 9

Another one, but not the best would be:

The rest cannot be assigned caused A has already been assigned, thus the assignation is not the maximum as possible

I've designed a greedy solution in O(n 2 ) that is too slow.

The size of the sets is usually small (5-10) elements.

• variable-assignment
• graph-theory

• What's the significance of having two sets? –  Mark Elliot Commented Nov 10, 2010 at 0:21
• Your costs list does not match the assignations in your examples. Perhaps some explanation is missing –  Dr. belisarius Commented Nov 10, 2010 at 0:46
• You're right (erasing mistake :P). I've just edited the cost list –  Javierfdr Commented Nov 10, 2010 at 1:23
• How O(n^2) for 4 or 5 item is slow? –  Saeed Amiri Commented Nov 10, 2010 at 10:49
• Because there can be many edges connecting the nodes (elements). Also, the algorithm is executed many times (many different assignments are required), which in sum makes the O(n^2) to affect the general performance –  Javierfdr Commented Nov 12, 2010 at 6:00

2 Answers 2

I'll assume you have an undirected graph and you want to select a maximal number of edges such that no two edges are incident on the same node (node = set element in your description). You also want to break ties using minimal total cost of the selected edges. Let me know if this doesn't fit what you're asking for.

Create the dual graph of the one above (one node for each original edge, two nodes are connected if the corresponding original edges are incident to the same vertex). You are then looking for a maximum independent set of the dual nodes. That's an NP-hard problem, unfortunately. And that's just for the maximum count of edges, it's probably slightly harder to break ties using weights. Luckily for you, your N is 5-10 so you may be able to brute force it.

• Yep, the problem is more or like you describe it. It is definitely NP-hard, when thinking of it as the maximum independent set problem. I wanted to know if there were any other solution smarter than my sort of "constrained brute force", that avoids the adaptation to another NP-hard problem, given the small amount of nodes. Thx for your answer –  Javierfdr Commented Nov 10, 2010 at 3:56
• Your proof that this is NP-hard is wrong. You don't prove NP-hardness by reducing the problem to an NP-hard problem, you prove it by reducing an NP-hard problem to the problem you're trying to solve. Also, if I understand the question correctly this isn't NP-hard. –  IVlad Commented Nov 10, 2010 at 7:15
• You're right, that's not a proof-providing reduction direction. I never claimed it was. –  Keith Randall Commented Nov 10, 2010 at 17:06

Sounds like you want a maximum non-bipartite matching: 1 , 2 .

The algorithm is pretty difficult to implement and I haven't seen any implementations around, especially if you want the minimum cost. For such small input, you're better off brute forcing it in my opinion.

How did you solve it with a greedy algorithm? Are you sure it works?

• IVlad is right here. Greedy approaches normally do not work for this one. bipartite matching is very similar to the maximum flow problem. –  guruslan Commented Nov 10, 2010 at 13:08
• I've checked Edmond's algorithm. It is quite difficult to implement indeed. I didn't try it because the greedy solution was giving acceptable results... Although the graph size is small, I have to calculate the assignment plenty of times, so brute force is just to heavy. The greedy solution does not always calculate the best assignment, but it does give acceptable solutions. Thx –  Javierfdr Commented Nov 10, 2010 at 23:02

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithm search graph variable-assignment graph-theory or ask your own question .

• The Overflow Blog
• One of the best ways to get value for AI coding tools: generating tests
• The world’s largest open-source business has plans for enhancing LLMs
• Featured on Meta
• User activation: Learnings and opportunities
• Site maintenance - Mon, Sept 16 2024, 21:00 UTC to Tue, Sept 17 2024, 2:00...
• What does a new user need in a homepage experience on Stack Overflow?
• Announcing the new Staging Ground Reviewer Stats Widget

Hot Network Questions

• Can All Truths Be Scientifically Verified?
• What would a planet need for rain drops to trigger explosions upon making contact with the ground?
• Copyright Fair Use: Is using the phrase "Courtesy of" legally acceptable when no permission has been given?
• security concerns of executing mariadb-dump with password over ssh
• C++ std::function-like queue
• Should I be careful about setting levels too high at one point in a track?
• Is it possible to draw this picture without lifting the pen? (I actually want to hang string lights this way in a gazebo without doubling up)
• How should I email HR after an unpleasant / annoying interview?
• Multi-producer, multi-consumer blocking queue
• Doesn't nonlocality follow from nonrealism in the EPR thought experiment and Bell tests?
• How in the world do I fix this anciently old slop sink? I am okay even with a temporary fix
• Solaris 11 cbe: no more updates?
• How many engineers/scientists believed that human flight was imminent as of the late 19th/early 20th century?
• Browse a web page through SSH? (Need to access router web interface remotely, but only have SSH access to a different device on LAN)
• "There is a bra for every ket, but there is not a ket for every bra"
• How to avoid bringing paper silverfish home from a vacation place?
• History of the migration of ERA from AMS to AIMS in 2007
• When I use \llap to overlap words, the space between the overlapped words and the rest of the text is too much: how do I fix it?
• 1950s comic book about bowling ball looking creatures that inhabit the underground of Earth
• The meaning of an implication with the existential quantifier
• Offset+Length vs 2 Offsets
• Why does a capacitor act as an open circuit under a DC circuit?
• What is the action-cost of grabbing spell components?
• What was the newest chess piece

Introduction to Graph Algorithms

--> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> --> -->

Note: This exam date is subject to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout.

• Incremental greedy template
• Krushkals algorithms and partition ADT
• PRIMS algorithm and Fibonacci Heaps

Books and references

Instructor bio.

Prof. C. Pandu Rangan

Course certificate.

DOWNLOAD APP

SWAYAM SUPPORT

Please choose the SWAYAM National Coordinator for support. * :

• Interview Problems on Graph
• Practice Graph
• MCQs on Graph
• Graph Tutorial
• Graph Representation
• Graph Properties
• Types of Graphs
• Graph Applications
• BFS on Graph
• DFS on Graph
• Graph VS Tree
• Transpose Graph
• Dijkstra's Algorithm
• Minimum Spanning Tree
• Prim’s Algorithm
• Topological Sorting
• Floyd Warshall Algorithm
• Strongly Connected Components
• Advantages & Disadvantages

Introduction to Graph Data Structure

Graph Data Structure is a non-linear data structure consisting of vertices and edges. It is useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structure can be used to analyze and understand the dynamics of team performance and player interactions on the field.

Table of Content

What is Graph Data Structure?

Components of graph data structure.

• Types Of Graph Data Structure
• Representation of Graph Data Structure
• Adjacency Matrix Representation of Graph Data Structure
• Adjacency List Representation of Graph
• Basic Operations on Graph Data Structure
• Difference between Tree and Graph
• Real-Life Applications of Graph Data Structure
• Advantages of Graph Data Structure
• Disadvantages of Graph Data Structure
• Frequently Asked Questions(FAQs) on Graph Data Structure

Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E).

Imagine a game of football as a web of connections, where players are the nodes and their interactions on the field are the edges. This web of connections is exactly what a graph data structure represents, and it’s the key to unlocking insights into team performance and player dynamics in sports.

• Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
• Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labelled/unlabelled.

Types Of Graphs in Data Structure and Algorithms

1. null graph.

A graph is known as a null graph if there are no edges in the graph.

2. Trivial Graph

3. Undirected Graph

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge. 

4. Directed Graph

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

5. Connected Graph

The graph in which from one node we can visit any other node in the graph is known as a connected graph. 

6. Disconnected Graph

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

7. Regular Graph

The graph in which the degree of every vertex is equal to K is called K regular graph.

8. Complete Graph

9. Cycle Graph

The graph in which the graph is a cycle in itself, the minimum value of degree of each vertex is 2. 

10. Cyclic Graph

A graph containing at least one cycle is known as a Cyclic graph.

11. Directed Acyclic Graph

A Directed Graph that does not contain any cycle. 

12. Bipartite Graph

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

13. Weighted Graph

•   A graph in which the edges are already specified with suitable weight is known as a weighted graph. 
•  Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs. 

Representation of Graph Data Structure:

There are multiple ways to store a graph: The following are the most common representations.

• Adjacency Matrix
• Adjacency List

Adjacency Matrix Representation of Graph Data Structure:

In this method, the graph is stored in the form of the 2D matrix where rows and columns denote vertices. Each entry in the matrix represents the weight of the edge between those vertices. 

Below is the implementation of Graph Data Structure represented using Adjacency Matrix:

Adjacency List Representation of Graph:

This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges connected to that vertex. 

Below is the implementation of Graph Data Structure represented using Adjacency List:

Comparison between Adjacency Matrix and Adjacency List

When the graph contains a large number of edges then it is good to store it as a matrix because only some entries in the matrix will be empty. An algorithm such as Prim’s and Dijkstra adjacency matrix is used to have less complexity.

Course Status :	Ongoing
Course Type :	Core
Duration :	8 weeks
Category :
Credit Points :	2
Undergraduate/Postgraduate
Start Date :	22 Jul 2024
End Date :	13 Sep 2024
Enrollment Ends :	05 Aug 2024
Exam Registration Ends :	16 Aug 2024
Exam Date :	22 Sep 2024 IST

Action	Adjacency Matrix	Adjacency List
Adding Edge	O(1)	O(1)
Removing an edge	O(1)	O(N)
Initializing	O(N*N)	O(N)

Basic Operations on Graph Data Structure:

Below are the basic operations on the graph:

• Add and Remove vertex in Adjacency List representation of Graph
• Add and Remove vertex in Adjacency Matrix representation of Graph
• Add and Remove Edge in Adjacency List representation of a Graph
• Add and Remove Edge in Adjacency Matrix representation of a Graph
• Searching in Graph Data Structure- Search an entity in the graph.
• Traversal of Graph Data Structure- Traversing all the nodes in the graph.

Difference between Tree and Graph:

Tree is a restricted type of Graph Data Structure, just with some more rules. Every tree will always be a graph but not all graphs will be trees. Linked List , Trees , and Heaps all are special cases of graphs. 

Real-Life Applications of Graph Data Structure:

Graph Data Structure has numerous real-life applications across various fields. Some of them are listed below:

• If we recall all the previous data structures that we have studied like array, linked list, tree, etc. All these had some restrictions on structure (mostly linear and tree hierarchical which means no loops). Graph allows random connections between nodes which is useful in many real world problems where do have restrictions of previous data structures.
• Used heavily in social networks. Everyone on the network is a vertex (or node) of the graph and if connected, then there is an edge. Now imagine all the features that you see, mutual friends, people that follow you, etc can seen as graph problems.
• Used to represent the topology of computer networks, such as the connections between routers and switches.
• Used to represent the connections between different places in a transportation network, such as roads and airports.
• Neural Networks: Vertices represent neurons and edges represent the synapses between them. Neural networks are used to understand how our brain works and how connections change when we learn. The human brain has about 10^11 neurons and close to 10^15 synapses.
• Compilers: Graph Data Structure is used extensively in compilers. They can be used for type inference, for so-called data flow analysis, register allocation, and many other purposes. They are also used in specialized compilers, such as query optimization in database languages.
• Robot planning: Vertices represent states the robot can be in and the edges the possible transitions between the states. Such graph plans are used, for example, in planning paths for autonomous vehicles.
• Dependencies in a software project (or any other type of project) can be seen as graph and generating a sequence to solve all tasks before dependents is a standard graph topological sorting algorithm.
• For optimizing the cost of connecting all locations of a network. For example, minimizing wire length in a wired network to make sure all devices are connected is a standard Graph problem called Minimum Spanning Tree.

Advantages of Graph Data Structure:

• Graph Data Structure used to represent a wide range of relationships as we do not have any restrictions like previous data structures (Tree cannot have loops and have to be hierarchical. Arrays, Linked List, etc are linear)
• They can be used to model and solve a wide range of problems, including pathfinding, data clustering, network analysis, and machine learning.
• Any real world problem where we certain set of items and relations between them can be easily modeled as a graph and a lot of standard graph algorithms like BFS, DFS, Spanning Tree, Shortest Path, Topological Sorting and Strongly Connected
• Graph Data Structure can be used to represent complex data structures in a simple and intuitive way, making them easier to understand and analyze.

Disadvantages of Graph Data Structure:

• Graph Data Structure can be complex and difficult to understand, especially for people who are not familiar with graph theory or related algorithms.
• Creating and manipulating graphs can be computationally expensive, especially for very large or complex graphs.
• Graph algorithms can be difficult to design and implement correctly, and can be prone to bugs and errors.
• Graph Data Structure can be difficult to visualize and analyze, especially for very large or complex graphs, which can make it challenging to extract meaningful insights from the data.

Frequently Asked Questions(FAQs) on Graph Data Structure:

1. what is a graph.

A graph is a data structure consisting of a set of vertices (nodes) and a set of edges that connect pairs of vertices.

2. What are the different types of Graph Data Structure?

Graph Data Structure can be classified into various types based on properties such as directionality of edges (directed or undirected), presence of cycles (acyclic or cyclic), and whether multiple edges between the same pair of vertices are allowed (simple or multigraph).

3. What are the applications of Graph Data Structure?

Graph Data Structure has numerous applications in various fields, including social networks, transportation networks, computer networks, recommendation systems, biology, chemistry, and more.

4. What is the difference between a directed graph and an undirected graph?

In an undirected graph, edges have no direction, meaning they represent symmetric relationships between vertices. In a directed graph (or digraph), edges have a direction, indicating a one-way relationship between vertices.

5. What is a weighted graph?

A weighted graph is a graph in which each edge is assigned a numerical weight or cost. These weights can represent distances, costs, or any other quantitative measure associated with the edges.

6. What is the degree of a vertex in a graph?

The degree of a vertex in a graph is the number of edges incident to that vertex. In a directed graph, the indegree of a vertex is the number of incoming edges, and the outdegree is the number of outgoing edges.

7. What is a path in a graph?

A path in a graph is a sequence of vertices connected by edges. The length of a path is the number of edges it contains.

8. What is a cycle in a graph?

A cycle in a graph is a path that starts and ends at the same vertex, traversing a sequence of distinct vertices and edges in between.

9. What are spanning trees and minimum spanning trees?

A spanning tree of a graph is a subgraph that is a tree and includes all the vertices of the original graph. A minimum spanning tree (MST) is a spanning tree with the minimum possible sum of edge weights.

10. What algorithms are commonly used to traverse or search Graph Data Structure?

Common graph traversal algorithms include depth-first search (DFS) and breadth-first search (BFS). These algorithms are used to explore or visit all vertices in a graph, typically starting from a specified vertex. Other algorithms, such as Dijkstra’s algorithm and Bellman-Ford algorithm, are used for shortest path finding.

More Resources of Graph:

• Recent Articles on Graph
• Practice problems on Graph
• Algorithms on Graphs

Please Login to comment...

Similar reads.

• Data Structures
• PS5 Pro Launched: Controller, Price, Specs & Features, How to Pre-Order, and More
• How to Make Money on Twitch
• How to activate Twitch on smart TV
• 105 Funny Things to Do to Make Someone Laugh
• #geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

Improve your Coding Skills with Practice

What kind of Experience do you want to share?