How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation. What I did is as follows:

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.

• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.

Pseudocode:

#adjList is the adjacency list given as a dictionary #myQueue is a double-sided queue containing node and its parent node ([Node, parNode]) #visited is a set containing visited nodes  while(myQueue):     currNode, parNode = myQueue.pop() #dequeue operation     visited.add(currNode) #Marking currNode as visited     for childNode in adjList[currNode]: #Traversing through all children of currNode         if currNode not in visited:             myQueue.appendleft([childNode, currNode]) #Enqueue operation         else:             if childNode!=parNode: #Main logic for cycle detection                 print('CYCLE DETECTED')                 break 

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices 0 and 1:

Graph containing cycle

Adjacency list of above graph is: adjList = {0:[1, 2], 1:[0], 2:[0]}. Here we can clearly see that the graph contains a cycle but above algorithm is not able to detect the same because when BFS will reach vertex 1, vertex 0 is already visited but vertex 0 is also the parent of vertex 1 so this cycle will go undetected.

My question is how I can modify above algorithm to detect such cases?

Edit: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex 0 to vertex 1 and another directed edge from vertex 1 to vertex 0

Forward edges in undirected grapth using BFS

Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally appearing?

Given graph with just 2 vertices A and B and 3 edges from A to B!

exploring A adjacent vertices

(1) A->B (tree edge, A is now marked as an ancestor for B and B is A’s descendant)

(2) A->B (forward edge? B is not yet processed (gray) and we found an edge to it from its ancestor(A))

(3) A->B forward edge using the same reasoning as in (2)!

What am I missing here?

Average branching factor of an undirected graph

I’m trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every spanning tree of the graph.

I know that, given a tree of $ n$ nodes, an average branching factor $ b_f$ and $ n_l$ leaf nodes, these three variables are related as follow:

$ $ b_f = \frac{e}{n-n_l} \Rightarrow n_l = n – \frac{e}{b_f}$ $

where $ e = n – 1$ (the number of edges).

However, if instead of an undirected tree you have an undirected graph of $ n$ nodes and $ e = n – 1 + k$ edges (or with $ k$ fundamental cycles), different traversals of the graph would give you different spanning trees, depending on which one of those $ k$ edges are the one being ignored from the graph.

Also, I don’t have a clear picture about how to calculate the “branching factor” of a graph since nodes have not notion of “parent node”, because their outdegrees are not known until some traversal starts, but I need to considered “any” traversal, specifically, a worst case scenario where any not-known-yet traversal have a maximum number of leaves.

Is there any known property of graph’s spanning trees that can offer an upper bound on the number of resulting leaves nodes of any traversal?

My best approximation so far is that, the maximum number of leaves must be bounded by $ $ n_l <= |\{n_{e^1}\}| + 2k$ $ where $ |\{n_{e^1}\}|$ is the number of nodes of the graph with degree 1, and $ k = e – n + 1$ .

That’s a worst case scenario where there exists $ k$ edges in the graph connecting nodes with degree 2 each, because removing them will give $ 2k$ nodes with degree 1 each, and thus $ + 2k$ leaves. If $ k$ is very low that can be an acceptable good approximation, but the biggest the connectivity of the graph, the worst the significance of the approximation.

If someone could give a better approximation based on the average degree of the graph or something similar that can be calculated on a first traversal would be appreciated.

UNDIRECTED HAMCYCLE to HAMPATH reduction

I’ll define the problems

UHAMPATH

Input: A undirected graph G and 2 nodes, s and t

Question: Is there a hamiltonian path from s to t in G?

UHAMCYCLE

Input: A undirected graph G

Question: Is there a hamiltonian cycle in G?

$ $ UHAMCYCLE \leq_p UHAMPATH$ $

my reduction is as followed $ (G) \to (G’, s, t)$

function(G)      for each e = (u, v) in E(G)         G' = G         add nodes u' and v' to G'         add edges (u', u) and (v, v')         s = u'         t = v'         if there is a hamilton path from s to t:             return (G', s, t) 

Basically if there is a hamilton cycle in G then some edge in $ G$ will form a hamilton path in $ G’$ .

An example to further illustrate the reduction:

 Graph G  (a) ---- --(d)  | \        |  |   \      |  |    \     |  |     \    |   |      \   |   |       \  |  |         \|      | (b) ------ (c)  Has a clear Hamilton cycle (a, b, c, d).   If we choose edges (a, d)   Graph G'  (s)--(a) ---- --(d)       | \        |       |   \      |       |    \     |       |     \    |        |      \   |        |       \  |       |         \|            (b) ------ (c)--(t) 

Doesn’t have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

(s)--(a) ---- --(d)--(t)       | \        |       |   \      |       |    \     |       |     \    |        |      \   |        |       \  |       |         \|            (b) ------ (c) 

$ (s \to a \to b \to c \to d \to t)$ . Holds.


I’m confused whether or not I can use this line:

if there is a hamilton path from s to t:     return (G', s, t) 

Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?

Undirected Acyclic Graphs

Given a Tree(Undirected), how can I find the number of triplets (a,b,c) such that b lies on the shortest path from a to c and b is smaller than both a and c? For example :

Edges : a b represents an edge between a and b

1 2 (represents an edge between 1 and 2)

1 3

3 4

3 5

Answer : 4 ((2,1,3) , (2,1,4) ,(2,1,5) ,(4,3,5))

Will decomposition algorithms on trees work or am i thinking in the wrong way? Any help would be appreciated.

Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

I’m looking for an algorithm that gives a smallest sum of ‘travel time’ within the following constraints:

  • a complete, connected, weighted graph,
  • vertices are defined in 3d euclidean space,
  • relatively low number of vertices (less than 500),
  • no limits on how many times a node may be visited,
  • a fixed starting vertex,
  • no requirement for which vertex to end at.

I’ve looked at minimum spanning tree algorithms, but those could create sub-optimal result, because they optimize for lowest summed edge weight.

I’m suspecting this may be a variant of the travelling salesman problem and thus NP-hard. For our use case however, a good approximation will be good enough.

efficiently find connected components in undirected graph considering transitive equivalence

I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By “equal” I mean transitive equivalence: If 1==2 and 2==3 then 1==3 and also: If 1==2 and 1!=4 then 2!=4

When given a set of nodes I can find all connected components in the graph by passing every possible combination of nodes to foo(u,v) function and building the needed edges. Like this:

import networkx as nx import itertools from matplotlib import pyplot as plt  EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}   def foo(u, v):     # this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.     return (u, v) in EQUAL_EDGES   def main():     g = nx.Graph()     g.add_nodes_from(range(1, 5 + 1))     for u, v in itertools.combinations(g.nodes, 2):         are_equal = foo(u, v)         print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')         if are_equal:             g.add_edge(u, v)      conn_comps = nx.connected_components(g)     nx.draw(g, with_labels=True)     plt.show()     return conn_comps   if __name__ == '__main__':     main() 

the problem with this approach is that I get many redundant checks that I would like to avoid:

1==2  # ok 1==3  # ok 1!=4  # ok 1!=5  # ok 2!=3  # redundant check, if 1==2 and 1==3 then 2==3  2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4  2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5 3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4 3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5 4==5  # ok 

I want to avoid running in O(n^2) time complexity. What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?