Questions tagged [triangle-count]
33 questions
8
votes
4 answers
Find all cycles in graph, redux
I know there are a quite some answers existing on this question. However, I found none of them really bringing it to the point.
Some argue that a cycle is (almost) the same as a strongly connected components (s. Finding all cycles in a directed…
Shadow
- 1,042
- 2
- 15
- 23
6
votes
2 answers
Number of triangles with N points inside
Given some points in plane (upto 500 points), no 3 collinear. We have to determine the number of triangles whose vertices are from the given points and that contain exactly N points inside them. How to efficiently solve this problem? The naive…
Artur
- 591
- 3
- 14
4
votes
1 answer
Extract All Triangles in Igraph with Labels
I have created an igraph with 1000 edges. My goal is to extract all the triangles found in that igraph but to include the label rather than just then number. I also want it to be in a dataframe form that has 3 columns (one for each node of the…
nak5120
- 4,089
- 4
- 35
- 94
3
votes
0 answers
Number of possible triangles from an integer array in O(NlogN)
Given an array that contains positive integers. The task is to calculate the number of triplets a, b, c such that they can be the sides of a triangle or
max(a, b, c) < a + b + c - max(a, b, c)
the O(N^3) solution is trivial using 3 loops, O(N^2) is…
anand singh
- 103
- 7
3
votes
2 answers
Finding total number of triangles using networkx
I want to count the total number of triangles in a graph using networkx python package.
I have tried the following:
import networkx as nx
g = ## some graph
t = nx.triangles(g)
However, nx.triangles() returns a dictionary denoting the number of…
Ahsan Tarique
- 581
- 1
- 11
- 22
3
votes
1 answer
Printing out a rhombic pattern in java with "for" loop
I am having a hard time doing a school exercise in Java. We are asked to print out this pattern:
+++++++++++++++++++++++++++++++++++++++++++++
+++++++ +++++++ +++++++ +++++++ +++++++
+++++ +++++ +++++ +++++ +++++
+++ …
eroruz
- 83
- 10
2
votes
2 answers
Triangle counting in undirected graph
I got asked this in an interview and was told that O(n^2) is possible. Anyone has a simple approach for that?
Found here a paper telling me that it is as hard as matrix multiplication:
http://kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf
Amtrix
- 338
- 2
- 10
2
votes
3 answers
Divisors of triangle numbers (Euler 12)
I have found a couple of topics related to this very problem, I just want to know why my code returns incorrect data.
So we have to find the first triangle number having more than 500 divisors. Details can be found here:…
fishmong3r
- 1,414
- 4
- 24
- 51
1
vote
2 answers
C For Loop Floyd's Triangle but different?
I need help on how to do a Flyod's Triangle style but instead of input value in rows, the triangle is based on the input value as a whole.
instead of;
Enter a number: 9
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28…
LittleBeginner
- 11
- 3
1
vote
1 answer
Python: count specific subshapes in shape with intersecting lines
I want to count specific subshapes of a bigger shape with python.
For expample:
I draw a Triangle. I draw a diagonal line cutting the triangle in half. Now the program show draw this triangle with the intersecting line and count the amount of…
LeeLii100
- 13
- 3
1
vote
0 answers
Count Triangles in Scala - Spark
i am trying to get into data analytics using Spark with Scala. My question is how do i get the triangles in a graph? And i mean not the Triangle Count that comes with graphx, but the actual nodes that consist the triangle.
Suppose we have a graph…
BubbleBeam
- 256
- 1
- 4
1
vote
4 answers
Printing triangle in C
I am new to C and I have this program where I am trying to print a triangle based on its height as such:
/\
/__\
So if the height is 2, then there are 2 of '/', '\' and '_'.
So I have written these chunk of codes:
#include
int…
Amy
- 15
- 1
- 5
1
vote
1 answer
Number of triangles from a sorted sequence
Given a strictly increasing sequence of n positive integers A(1) < A(2) < ... < A(n). We need to find the number of triangles with side lengths as 3 distinct elements of this sequence.
Since n <= 6000, checking every possible combination is not…
Artur
- 591
- 3
- 14
0
votes
1 answer
How to generate a triangle free graph in Networkx (with randomseed)?
After checking the documentation on triangles of networkx, I've wondered if there is a more efficient way of generating a triangle free graph than to randomly spawn graphs until a triangle free one happens to emerge, (in particular if one would like…
a.t.
- 2,002
- 3
- 26
- 66
0
votes
2 answers
How to find a "triangle of friends" in a graph?
I have names of people that are friends and I am looking for triangles of friends, if there are any.
Example (names next to each other classify as friends, in the first row the first number represents the number of people and the second number…
randommikrovalna
- 3
- 2