[FIXED] How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Issue

Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' acyclic.

More formal: The desired algorithm consumes G and creates a set of acyclic graphs S, where each graph G' in S satisfies following properties:

1. G' contains all vertices of G.
2. G' contains a subset of edges of G, such that G' is acyclic.
3. The number of edges of G' is maximised. Which means: There is no G'' satisfying properties 1 and 2, such that G'' contains more edges then G' and G'' is acyclic.

Background: The original graph G models a pairwise ordering between elements. This can't be exploited as an ordering over all elements due to cycles in the graph. The maximal acyclic graphs G' therefore should model a best-possible approximation to this ordering, trying to respect as much of the pairwise ordering relation as possible.

In a naive approach, one could remove all possible combinations of edges and check for acyclicity after each removal. In this case there is a strongly branching tree of variations meaning bad time and space complexity.

Note: The problem may be related to a spanning tree, and you could define the G' graphs as a kind of directed spanning tree. But keep in mind that in my scenario a pair of edges in G' may have the same starting or the same ending vertex. This conflicts with some definitions of directed spanning trees used in literature.

EDIT: Added intuitive description, background information and note related to spanning trees.

Solution

This problem is called Feedback Arc Set. Since it is NP-hard, it is unlikely that you will find a scalable fast algorithm. However, if your instances are small, then algorithms such as the one from the paper “On enumerating all minimal solutions of feedback problems” by B. Schwikowski and E. Speckenmeyer might work.

Answered By - Falk Hüffner

Answer Checked By - Pedro (PHPFixing Volunteer)

Read More

[FIXED] How can I remove the 'fishbowl' effect when creating a square grid on MATLAB?

Issue

I have been trying to create a graph representing a square grid with 8 nodes. I have been using code given by Mathworks here:

n = 8;
A = delsq(numgrid('S',n+2));
G = graph(A,'omitselfloops');
p = plot(G);` 

The plotted result is:

But I just wondered if I could make the image less curved. In order to make the graph look more 'uniform' and have all the edges the same length.

Solution

The graph G contains no coordinates for the nodes, so MATLAB basically has to "guess" where to put them (and does a remarkably good job). You can use the additional argument XData, YData (and ZData) to add coordinates to your nodes (see documentation), so in your case you might want to use e.g meshgrid:

n = 8; 
A = delsq(numgrid('S',n+2)); 
G = graph(A,'omitselfloops'); 
[x,y] = meshgrid(1:n, 1:n);
p = plot(G, 'XData',x(:), 'YData',y(:));

Answered By - flawr

Answer Checked By - Marilyn (PHPFixing Volunteer)

Read More

[FIXED] When should us use normal BFS over bidirectional BFS?

Issue

I understand that Bidirectional BFS has a lot of advantage over using normal BFS, as it theoretically halves the time to discover the shortest path between two nodes and the time to find if a node is reachable from another node.

Also I understand that we should use Bidirectional only if we have Uniquely defined both the nodes.

Is there any situation when we should prefer a normal BFS over bidirectional BFS?

Solution

I understand that bidirectional BFS consists of, given start and goal nodes, alternately expanding layers of nodes from start and goal, until a node in the middle has been reached from both ends. The shortest path from start to goal is then understood to be the shortest from start to middle node, continued by the shortest from middle to goal. I can see that less nodes may need to be expanded as compared with a standard BFS approach. However,

• It is easier to implement standard BFS (sBFS) than to implement a bidirectional BFS (bBFS for short). Simple is often good, as it is easier to code and to later verify its correctness.
• If the graph is directed and unweighted, sBFS guarantees that it will find the shortest path from start to goal in minimal steps; bBFS is not guaranteed to work with directed graphs.
• After running sBFS, you can reconstruct shortest paths from the start to all nodes that are at most 1 step before the goal node (that is, before the search was stopped). This may be valuable in and of itself. Running bBFS does not generate such a list.

With this in mind, I would argue the bBFS is only useful for a very narrow case (where, depending on the graph, it is expected to perform better than sBFS), and sBFS is both simpler and useful in a larger range of scenarios.

Answered By - tucuxi

Answer Checked By - Marilyn (PHPFixing Volunteer)

Read More

[FIXED] How to improve Knight's tour with Warnsdorff's rule?

Issue

I know there are several similar threads, but I didn't find a solution even outside of SO. Here's my problem: I implemented Warnsdorff's algorithm for the Knight's Tour problem http://en.wikipedia.org/wiki/Knight%27s_tour , but it doesn't give a solution in some cases. On some places I read it can work much better with some alterations, but nobody specifies which alterations are those. Does somebody know the solution? I know of other algorithms, but they are much more complex.

It sometimes doesn't give a good solution even for a 8x8 chessboard. I think no point in reading through my code, since it's a classical Warnsdorff's: check possible moves, and choose the one with the least possible moves in the next step.

Solution

The link for W+ no longer exist, making the accepted answer not usable.

Improvements to the Warnsdorff algorithm are:

Arnd Roth's proposition: Roth decided that the problem in Warnsdorff's heuristic, lays in the random tiebreak rule. The proposition is to break the ties by choosing the successor with the largest euclidean distance from the center of the board.

The problem here is what happens when more than one successor share the same distance.
Arnd Roth claimed that this improvement first failed on a board with 428 rows and had less than 1% failures on all boards with fewer than 2000 rows.

Ira Pohl's proposition: To break the ties Pohl decided to apply Warnsdorff's rule a second time. To achieve this we must take the sum of the degrees of all unvisited neighbors, of the successors that tied, and choose the square whose sum is minimal.

One of the problems here is that no matter how many times we apply Warnsdorff's rule we will result in a tie (between the two adjacent squares) if we start in the corner square. Furthermore if we apply Warnsdorff's heuristic a large number of times then asymptotically this is equal to an exhaustive search.

Pohl also suggested, if we fail to produce a successor after applying Warnsdorff for the 2nd time, to break ties by using a fixed arbitrary ordering of the squares. His claim is that this successfully produces a solution on a 8*8 board.

By using one of these enhancements we have better chances of creating a solution systematically by preventing possible lock-ins.

Answered By - Panos Kal.

Answer Checked By - Mildred Charles (PHPFixing Admin)

Read More

[FIXED] What is the relaxation condition in graph theory

Issue

I'm trying to understand the main concepts of graph theory and the algorithms within it. Most algorithms seem to contain a "Relaxation Condition" I'm unsure about what this is.

Could some one explain it to me please.

An example of this is dijkstras algorithm, here is the pseudo-code.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph
    // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          if dist[u] = infinity:
 10              break                         // all remaining vertices are inaccessible from source
 11          remove u from Q
 12          for each neighbor v of u:         // where v has not yet been removed from Q.
 13              alt := dist[u] + dist_between(u, v)
 14              if alt < dist[v]:             // Relax (u,v,a)
 15                  dist[v] := alt
 16                  previous[v] := u
 17      return dist[]

Thanks

Solution

Relaxation step:

• You have two nodes, u and v
• For every node, you have a tentative distance from the source node (for all nodes except for the source, it starts at positive infinity and it only decreases up to reaching its minimum).

The relaxation step basically is asking this:

• I already know that I can reach v with some path of distance dist[v]. Could I improve on this by going to v through u instead? (where the distance of the latter would be dist[u] + weight(u, v))

Graphically:

s ~~~~~~~> v
 \         ^
  \        |
   \~~~~~> u

You know some path s~>v which has distance dist[v], and you know some path s~>u which has distance dist[u]. If dist[u] + weight(u, v) < dist[v], then the path s~>u->v is shorter than s~>v, so you'd better use that one!

(I write a~>b to mean a path of any length from a to b, while a->b I mean a direct single edge from a to b).

You may also want to check this lecture: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

Answered By - Dimitris Andreou

Answer Checked By - Candace Johnson (PHPFixing Volunteer)

Read More

[FIXED] How to connect all components of a DiGraph in NetworkX

Issue

I have a directed graph (G), which is made of 65 strongly connected components and 8 weakly connected components. I am aware I can add non-existent edges to connect the entire graph using k-edge-augmentation, but this is only possible with an undirected graph.

Is there any way, within NetworkX, or otherwise to connect the DiGraph to produce one strongly connected component?

Solution

For anyone else coming here in future, one idea I had which I'm probably going to go with is to create both a directed and undirected graph from your data, perform k-edge-augmentation on the undirected graph, and using the edges this returns, add a biconnected component between them in the directed graph.

Answered By - Luca Passariello

Answer Checked By - Clifford M. (PHPFixing Volunteer)

Read More

[FIXED] What is the distinction between sparse and dense graphs?

Issue

I read it is ideal to represent sparse graphs by adjacency lists and dense graphs by an adjacency matrix. But I would like to understand the main difference between sparse and dense graphs.

Solution

Dense graph is a graph in which the number of edges is close to the maximal number of edges. Sparse graph is a graph in which the number of edges is close to the minimal number of edges. Sparse graph can be a disconnected graph.

Answered By - CAMOBAP

Answer Checked By - Marie Seifert (PHPFixing Admin)

Read More

[FIXED] How to find Global Clustering Coefficient of graph?

Issue

I start learning network analysis & its metrics calculation from last week. Don't have enough knowledge. Can anyone check this ?

The formula of finding the global clustering co-efficient is,

C = (3 * Number of Triangles) / (Number of connected triples of vertices)

I calculate the global clustering co-efficient as,

Number of Triangles = 2 
(as there are 2 directly connected triangles in the graph i-e Node4->Node5->Node6 and Node1->Node3->Node4)

Number of connected triples of vertices = 4 
(as Node1, Node2, Node3 & Node6 have three vertices connected)

 C = (3 * 2) / 4 = 1.5

I don't know I do it correctly or not. Can anyone check this ? or correct me If I am wrong

Solution

The denominator must count all triples with 2 or 3 edges. So, the the given graph we have the following triples:
5-4-6
6-5-4, 6-4-2, 6-5-2
4-6-1, 4-5-1, 4-6-3, 4-5-3, 4-1-3, 4-6-5
1-4-3, 1-3-2, 1-4-2
3-4-1, 3-1-7, 3-4-7
7-3-2
2-7-1, 2-1-6, 2-7-6
This gives a total of 20 triples, so the gcc is 2*3/20 = 0.3.

This algorithm is implemented in python's networkx package. The code for this example is:

import networkx as nx
g = nx.Graph()
g.add_edges_from([(5,6), (5,4), (4,6), (4,1), (4,3), (3,1), (3,7), (7,2), (1,2), (6,2)])
print(nx.transitivity(g))

Answered By - Jorge M. Londoño P.

Answer Checked By - Cary Denson (PHPFixing Admin)

Read More