What does **`relaxation of an edge`** mean in the context of graph theory ? I came across this while studying up on Dijkstra&#39;s algorithm for single source shortest path.

Relaxation of an edge in Dijkstra&#39;s algorithm

Say I have two networkx graphs, `G` and `H`:

    G=nx.Graph()
    fromnodes=[0,1,1,1,1,1,2]
    tonodes=[1,2,3,4,5,6,7]
    for x,y in zip(fromnodes,tonodes):
        G.add_edge(x,y)

    H=nx.Graph()
    fromnodes=range(2,8)
    tonodes=range(8,14)
    for x,y in zip(fromnodes,tonodes):
        H.add_edge(x,y)

**What is the best way to join the two networkx graphs?**  

I&#39;d like to preserve the node names (note the common nodes, 2 to 7). When I used `nx.disjoint_union(G,H)`, this did not happen:

    &gt;&gt;&gt; G.nodes()
    [0, 1, 2, 3, 4, 5, 6, 7]
    &gt;&gt;&gt; H.nodes()
    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
    &gt;&gt;&gt; Un= nx.disjoint_union(G,H)
    &gt;&gt;&gt; Un.nodes()
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    # 
The `H` node labels were changed (not what I want). I want to join the graphs at the nodes with the same number.

*Note. This is not a duplicate of https://stackoverflow.com/questions/21806751/combine-two-weighted-graphs-in-networkx.* 

Combine (join) networkx Graphs

Just wondering if there is convenient networkx function that returns a list of edges connected to a given node (or nodes) (e.g. `my_node_name`) in a graph (e.g. `G`).

I can do it this way:

    edlist=[]
    for ed in G.edges():
         if &#39;my_node_name&#39; in ed:
                edlist.append(ed)

but expect there might be a better way?

Get all edges linked to a given node in a networkx graph

I&#39;m looking for a (free) library which allows me to draw a [CFG][1] (control flow graph). Something like [yFiles][2], but free or preferably open source? Ideally this library would allow the user to navigate the graph (and modify it), i.e. the graph isn&#39;t just a static a priori rendered bitmap.
Ideas?


**Update:**  
[Glee][3] in combination with the mentioned QuickGraph library seems to work pretty nice. thx

**Update2:**
[Graph#][4] seems to be the most powerful library currently. There is also a nice [tutorial][5] on how to use it.

  [1]: http://en.wikipedia.org/wiki/Control_flow_graph
  [2]: http://yworks.com/
  [3]: http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/default.aspx
  [4]: http://graphsharp.codeplex.com/
  [5]: http://sachabarber.net/?p=815

C# graph drawing library?

I have a large, connected, sparse graph in adjacency-list form.  I would like to find two vertices that are as far apart as possible, that is, the [diameter of the graph](http://en.wikipedia.org/wiki/Graph_diameter) and two vertices achieving it.

I am interested in this problem in both the undirected and directed cases, for different applications.  In the directed case, I of course care about directed distance (the shortest directed path from one vertex to another).

**Is there a better approach than computing all-pairs shortest paths?**

*Edit*: By &quot;as far apart as possible&quot;, I of course mean the &quot;longest shortest path&quot; -- that is, the maximum over all pairs of vertices of the shortest distance from one to the other.

Good algorithm for finding the diameter of a (sparse) graph?

After reading Stevey Yegge&#39;s [Get That Job At Google][1] article, I found this little quote interesting:

&gt; Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it&#39;s about a 50–50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can&#39;t think of a way to solve it using graphs before moving on to other solution types. This tip is important!

What are some examples of problems that are best represented and/or solved by graph data structures/algorithms?

One example I can think of: navigation units (ala Garmin, TomTom), that supply road directions from your current location to another, utilize graphs and advanced pathing algorithms.

What are some others?

  [1]: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

What are good examples of problems that graphs can solve better than the alternative?

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. 

What is the distinction between sparse and dense graphs?

I was wondering when one should use [Prim&#39;s algorithm][1] and when [Kruskal&#39;s][2] to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which might involve a bit different data structures. So what is the deciding factor?

  [1]: http://en.wikipedia.org/wiki/Prim%27s_algorithm
  [2]: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

When should I use Kruskal as opposed to Prim (and vice versa)?

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?

For example, I want something like this:

    A-&gt;B-&gt;A
    A-&gt;B-&gt;C-&gt;A
but not:
    B-&gt;C-&gt;B



Finding all cycles in a directed graph

Can somebody tell me why Dijkstra&#39;s algorithm for single source shortest path assumes that the edges must be non-negative. 

I am talking about only edges not the negative weight cycles.

Why doesn&#39;t Dijkstra&#39;s algorithm work for negative weight edges?

The basic algorithm for BFS:

    set start vertex to visited
    
    load it into queue
        
    while queue not empty
        
       for each edge incident to vertex
                  
            if its not visited
                
                load into queue
                      
                mark vertex


So I would think the time complexity would be:  

    v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 


where `v` is vertex `1` to `n`


Firstly, is what I&#39;ve said correct?  Secondly, how is this `O(N + E)`, and intuition as to why would be really nice.  Thanks


Why is the time complexity of both DFS and BFS O( V + E )

I am trying to determine the best time efficient algorithm to accomplish the task described below.

I have a set of records. For this set of records I have connection data which indicates how pairs of records from this set connect to one another. This basically represents an undirected graph, with the records being the vertices and the connection data the edges.

All of the records in the set have connection information (i.e. no orphan records are present; each record in the set connects to one or more other records in the set).

I want to choose any two records from the set and be able to show all simple paths between the chosen records. By &quot;simple paths&quot; I mean the paths which do not have repeated records in the path (i.e. finite paths only).

Note: The two chosen records will always be different (i.e. start and end vertex will never be the same; no cycles).

For example:
&lt;pre&gt;
    If I have the following records:
        A, B, C, D, E

    and the following represents the connections: 
        (A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
        (C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

        [where (A,B) means record A connects to record B]
&lt;/pre&gt;

If I chose B as my starting record and E as my ending record, I would want to find all simple paths through the record connections that would connect record B to record E.

&lt;pre&gt;
   All paths connecting B to E:
      B-&gt;E
      B-&gt;F-&gt;E
      B-&gt;F-&gt;C-&gt;E
      B-&gt;A-&gt;C-&gt;E
      B-&gt;A-&gt;C-&gt;F-&gt;E
&lt;/pre&gt;

This is an example, in practice I may have sets containing hundreds of thousands of records.

Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been
visited while traversing the tree/graph.

Why DFS and not BFS for finding cycle in graphs

I have a undirected graph with about 100 nodes and about 200 edges.  One node is labelled &#39;start&#39;, one is &#39;end&#39;, and there&#39;s about a dozen labelled &#39;mustpass&#39;.

I need to find the shortest path through this graph that starts at &#39;start&#39;, ends at &#39;end&#39;, **and passes through all of the &#39;mustpass&#39; nodes (in any order).**

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt is the graph in question - it represents a corn maze in Lancaster, PA)

Find the shortest path in a graph which visits certain nodes


Background
---

This picture illustrates the problem:
![square_grid_with_arrows_giving_directions][1]

I can control the red circle.  The targets are the blue triangles.  The black arrows indicate the direction that the targets will move.

I want to collect all targets in the minimum number of steps.

Each turn I must move 1 step either left/right/up or down.

Each turn the targets will also move 1 step according to the directions shown on the board.


Demo
---

I&#39;ve put up a playable demo of the problem [here on Google appengine](http://penguinspuzzle.appspot.com/a_fishy_problem.html).

I would be very interested if anyone can beat the target score as this would show that my current algorithm is suboptimal.  (A congratulations message should be printed if you manage this!)

Problem
---

My current algorithm scales really badly with the number of targets.  The time goes up exponentially and for 16 fish it is already several seconds. 

I would like to compute the answer for board sizes of 32*32 and with 100 moving targets.


Question
---

What is an efficient algorithm (ideally in Javascript) for computing the minimum number of steps to collect all targets?

What I&#39;ve tried
-----

My current approach is based on memoisation but it is very slow and I don&#39;t know whether it will always generate the best solution.

I solve the subproblem of &quot;what is the minimum number of steps to collect a given set of targets and end up at a particular target?&quot;.

The subproblem is solved recursively by examining each choice for the previous target to have visited.
I assume that it is always optimal to collect the previous subset of targets as quickly as possible and then move from the position you ended up to the current target as quickly as possible (although I don&#39;t know whether this is a valid assumption).

This results in n*2^n states to be computed which grows very rapidly.

The current code is shown below:

    var DX=[1,0,-1,0];
    var DY=[0,1,0,-1]; 
    
    // Return the location of the given fish at time t
    function getPt(fish,t) {
      var i;
      var x=pts[fish][0];
      var y=pts[fish][1];
      for(i=0;i&lt;t;i++) {
        var b=board[x][y];
        x+=DX[b];
        y+=DY[b];
      }
      return [x,y];
    }
    
    // Return the number of steps to track down the given fish
    // Work by iterating and selecting first time when Manhattan distance matches time
    function fastest_route(peng,dest) {
      var myx=peng[0];
      var myy=peng[1];
      var x=dest[0];
      var y=dest[1];
      var t=0;
      while ((Math.abs(x-myx)+Math.abs(y-myy))!=t) {
        var b=board[x][y];
        x+=DX[b];
        y+=DY[b];
        t+=1;
      }
      return t;
    }
    
    // Try to compute the shortest path to reach each fish and a certain subset of the others
    // key is current fish followed by N bits of bitmask
    // value is shortest time
    function computeTarget(start_x,start_y) {
      cache={};
      // Compute the shortest steps to have visited all fish in bitmask
      // and with the last visit being to the fish with index equal to last
      function go(bitmask,last) {
        var i;
        var best=100000000;
        var key=(last&lt;&lt;num_fish)+bitmask;
        if (key in cache) {
          return cache[key];
        }
        // Consider all previous positions
        bitmask -= 1&lt;&lt;last;
        if (bitmask==0) {
          best = fastest_route([start_x,start_y],pts[last]);
        } else {
          for(i=0;i&lt;pts.length;i++) {
            var bit = 1&lt;&lt;i;
            if (bitmask&amp;bit) {
              var s = go(bitmask,i);   // least cost if our previous fish was i
              s+=fastest_route(getPt(i,s),getPt(last,s));
              if (s&lt;best) best=s;
            }
          }
        }
        cache[key]=best;
        return best;
      }
      var t = 100000000;
      for(var i=0;i&lt;pts.length;i++) {
        t = Math.min(t,go((1&lt;&lt;pts.length)-1,i));
      }
      return t;
    }


What I&#39;ve considered
---

Some options that I&#39;ve wondered about are:

1. Caching of intermediate results.  The distance calculation repeats a lot of simulation and intermediate results could be cached.  
However, I don&#39;t think this would stop it having exponential complexity.

2. An A* search algorithm although it is not clear to me what an appropriate admissible heuristic would be and how effective this would be in practice.

3. Investigating good algorithms for the travelling salesman problem and see if they apply to this problem.

4. Trying to prove that the problem is NP-hard and hence unreasonable to be seeking an optimal answer for it.


  [1]: http://i.stack.imgur.com/dNVaO.png

How can I find the shortest path between 100 moving targets? (Live demo included.)

Is there an efficient algorithm for detecting cycles within a directed graph?

I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency being an edge. I need to detect the error case of a cycle within this graph leading to cyclic dependencies.

Best algorithm for detecting cycles in a directed graph

I understand the differences between DFS and BFS, but I&#39;m interested to know when it&#39;s more practical to use one over the other? 

Could anyone give any examples of how DFS would trump BFS and vice versa?

When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

I am working on an implementation of Dijkstra&#39;s Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implementation working. It returns all the shortest paths to all the nodes when I pass the start node into the algorithm.

My question: 
How does one go about retrieving all possible paths from Node A to, say, Node G or even all possible paths from Node A and back to Node A?


Find all paths between two graph nodes

I need advice for rendering an undirected graph with 178,000 nodes and 500,000 edges.  I&#39;ve tried Neato, Tulip, and Cytoscape.  Neato doesn&#39;t even come remotely close, and Tulip and Cytoscape claim they can handle it but don&#39;t seem to be able to.  (Tulip does nothing and Cytoscape claims to be working, and then just stops.)

I&#39;d just like a vector format file (ps or pdf) with a remotely reasonable layout of the nodes.

Visualizing Undirected Graph That&#39;s Too Large for GraphViz?

First of all, let me say I&#39;m using LyX, though I have no problem using ERT.

Secondly, what is the most simplest way to draw a simple graph like this in Latex?
![alt text][1]

I&#39;ve seen some documents with graphs and I&#39;ve seen some examples, but I couldn&#39;t figure out how to just draw a simple graph - what packages do I need, etc?

  [1]: https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg

How to draw a graph in LaTeX?

I have a graph I&#39;ve created in graphviz, but the problem is that edges overlap each other (I have 5-7 nodes in each row), so it is hard to tell for each node which are the nodes it connects.

How can I make the edges not to overlap each other? Have them cross each other is OK.

How to prevent edges in graphviz to overlap each other

I need to be able to manipulate a large (10^7 nodes) graph in python. The data corresponding to each node/edge is minimal, say, a small number of strings. What is the most efficient, in terms of ***memory and speed***, way of doing this? 

A dict of dicts is more flexible and simpler to implement, but I intuitively expect a list of lists to be faster. The list option would also require that I keep the data separate from the structure, while dicts would allow for something of the sort:

    graph[I][J][&quot;Property&quot;]=&quot;value&quot;

 What would you suggest?

---

Yes, I should have been a bit clearer on what I mean by efficiency. In this particular case I mean it in terms of random access retrieval.

Loading the data in to memory isn&#39;t a huge problem. That&#39;s done once and for all. The time consuming part is visiting the nodes so I can extract the information and measure the metrics I&#39;m interested in.

I hadn&#39;t considered making each node a class (properties are the same for all nodes) but it seems like that would add an extra layer of overhead? I was hoping someone would have some direct experience with a similar case that they could share. After all, graphs are one of the most common abstractions in CS.

What is the most efficient graph data structure in Python?

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Difference between hamiltonian path and euler path

Given an undirected graph *G*=(*V*, *E*) with *n* vertices (|*V*| = *n*), how do you find if it contains a cycle in *O*(*n*)?

Cycles in an Undirected Graph

if given a graph problem how do we know whether we need to use bfs or dfs algorithm???
or when do we use dfs algorithm or bfs algorithm.
What are the differences and advantages of one over other?

Graphs data structure: DFS vs BFS?

I tried to find a graph data structure to reuse in C# without any success. Of course, I can borrow from data structure books but I want it to be more commercially practical(?) Also I would appreciate if you can tell me what the best way of implementing a graph is. Thanks 

Is there any graph data structure implemented for C#

I am trying to force position of nodes. I have x and y coordinates of my nodes and its also directed graph. I can use the rank=same to handle row (y coordinate), but can&#39;t figure out how I can handle column (x coordinate). 

How to force node position (x and y) in graphviz

I need to find the minimum cut on a graph. I&#39;ve been reading about flow networks, but all I can find are maximum flow algorithms such as Ford-Fulkerson, push-relabel, etc. Given the max flow-min cut theorem, is it possible to use one of those algorithms to find the minimum cut on a graph using a maximum flow algorithm? How?

The best information I have found so far is that if I find &quot;saturated&quot; edges i.e. edges where flow equals capacity, those edges correspond to the minimum cut. Is that true? It doesn&#39;t sound 100% right to me. It is true that all edges on the minimum cut will be saturated, but I believe there might also be saturated edges which are out of the minimum cut &quot;path&quot;.

All Graph Theory Solutions on Gang of Coders

Total of 28 Graph Theory Solutions

Relaxation of an edge in Dijkstra's algorithm