Verifying connectivity of a graph in O(n^2)

I solved the following problem:

We have vertices which represents cities and a textfile with edges between vertices representing roads. How many roads do we need to build to make the graph connected – you can travel by road to each city?

Using the BFS algorithm. Basically, I’m calling the BFS algorithm after adding each edge to the graph until the graph is connected and counting the number of BFS calls. However, since the BFS itself has a time complexity of O(n^2) and I’m calling it n-times, I have a worstcase time complexity near O(n^3).

How would I solve this issue in O(n^2)?

Thanks!

How to transform an arbitrary graph into a fixed vector representation?

Actuality I work in computer vision, specifically on a problem known as “scene graph modeling.” This problem aims to convert an image $ I$ in a graph $ G=(V,E)$ where the nodes $ V$ represent the objects (and the features) in scene and the edges $ E$ the relationships between objects. An interesting paper on this topic is Graph R-CNN for Scene Graph Generation (Note that unlike of only to detect the objects in an image, the scene graph aims to capture the contextual information of image). A graph is a mathematics structure rich in information, and it would be very interesting to integrate graphs in a machine learn approach. In order to achieve this task is necessary to transform a graph in a vector representation. Some works that intend solve this problem are the following:

  • SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS: The problem with this algorithm is that assumes a fix number of nodes. After training, this algorithm take a graph $ G=(V,E)$ as input  (whit $ N$ nodes, that is, $ |V|=N$ ) and outputs a fixed vector representation.
  • graph2vec: Learning Distributed Representations of Graphs: This algorithm is flexible due to permit build a vector representation from a graph $ G$ without restrict the number of nodes. However, it needs to know the whole space graph. That is, given a set $ G=\{g_{1},g_{2},\dots,g_{i},\dots,g_{m}\}$ , where $ g_{i}$ is the i-th graph, this algorithm builds a vectorial representation $ V=\{v_{1},v_{2},\dots,v_{i},\dots,v_{m}\}$ , where $ v_{i}$ is the i-th vector associated with the graph $ g_{i}$ . This algorithm is originally proposed to text analysis, where the features in nodes are of low dimension, I do not know if it can work using high dimension features in nodes. 

I would like to know if there is another simple algorithm that allows me to convert any graph into a fixed vector representation.

Number of distinct BFS, DFS trees in a complete graph

What is the number of distinct BFS, DFS in a complete graph?


My approach is like this–>

For DFS take a node, we have (n-1) possible tree edges, next we have all possible (n-2) tree edges,…….finally 1 possible tree edge. and we can choos any of n nodes as rooot node. hence no of distinct DFS trees= n*(n-1)(n-2)….1= n!

For BFS tree if we take a node as root, we have to explore all its neighbors , so the number distinct of BFS trees =no of nodes we can choose as root ie. n .

Is this approach correct?

Constructing a directed graph for O(1) queries

I need help to design a data structure for a directed graph with the following properties:

  1. Initialization should be done in O(1) time.
  2. AddVertex(id1,id2,…idK) – Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices. id1…idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK. This should be done in O(1) time.
  3. GetNumberOfNeighbors(id) – Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time. All O(1) times are for worse case.

Thanks allot

How to draw a graph whose vertices are elements of permuation group

How to write the following program in C++:

Consider the Permutation Group $ S_3$ .

The elements of $ S_3$ are $ e,(12),(13),(23),(123),(132)$ .

I want to draw a graph $ G$ whose members are the elements of $ S_3$ and two vertices $ x,y$ are adjacent if and only if $ xy\neq yx$ .

I am stuck in doing the following things:

  1. How to call the elements of $ S_3$ through a loop?
  2. How to draw the graph $ G$ ?
  3. How to check whether they commute or not

    I am stuck in the three things. Is there any way to write the code in C++?

As an example if I input $ S_3$ I want to get the following graph

$ G=Graph({1:[2,3,4,5],2:[1,3,4,5],3:[1,2,4,5],4:[1,2,3],5:[1,2,3]})

Any help will be highly appreciated.

Should I use Microsoft Graph or CSOM when integrating .NET with O365?

I have an existing integration based on CSOM, which I need to move from one .NET solution to another. In the process, I was made aware that Microsoft now has a graph API. I’ve tried to research recommendations about whether to use the Graph API or CSOM, but I haven’t found documentation that I’d thought was quite definitive enough on the issue.

The use case is fetching calendar events from O365.

Should we opt to use the Microsoft Graph API or the CSOM NuGet package? Or is there some other alternative that should be used to do the integration? I don’t want to just use CSOM because we have it, if it is considered a somewhat outdated approach.

I am inexperienced when it comes to integrations with Sharepoint/O365.

Why does the listeners increase in my graph? and what does it say about my web application?

i am trying to find out if there are any memory leaks in my web app. by reading some blog i have reached to a point where i can use performance tab in google chrome and record it. It created the following graph. Performance tab of my web app now i am seeing that there is limit to the rise of Js heap graph and others except the listeners. What does that listeners part of the graph suggest? and what type of code can cause it to increase it like that? PS:- every 5 seconds i call a function , it sends a http get request and shows the response to the users.

Does the Microsoft Graph support driveItem change notifications for SharePoint Online?

In the documentation Use the Microsoft Graph API to get change notifications, it says:

Using the Microsoft Graph API, an app can subscribe to changes on the following resources:

  • Content within the hierarchy of the root folder driveItem on OneDrive for Business

There is no explicit mention of SharePoint Online support for file notifications in the documentation, but because the OneDrive for Business and SharePoint Online APIs within the Microsoft Graph are essentially the same, should this infer that the same functionality is supported for SharePoint Online too?

Finding minimum spanning tree of a special form graph

I’m trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form:

enter image description here

My idea was a recursive solution: Suppose the algorithm recieve the graph with n as a parameter,

if n==2 then:     take the lower cost path between vo-->v1-->v2 and v0-->v2 if n==1 then:     take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1 else:     - recursivly call the algorithm for n-1     - take the lower cost edge between v0-->vn and v(n-1)-->vn 

I’m really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.

Any suggestions would be much appreciated.

Empty intersection of longest path in connected graph


Do all longest paths share a common point? (Gallai 1966)

A few years later, Walther produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu independently and has 12 vertices (b).

Counterexamples

I found this examples in numerous study, but i couldn’t find a vertex that does not appear in all longest paths.

Could you explain how should i see these graphs? Where are paths which intersection are empty?