Skip to content

Latest commit

 

History

History
64 lines (43 loc) · 2.59 KB

README.md

File metadata and controls

64 lines (43 loc) · 2.59 KB
Raw

Graph

The aim of this project is to implement a kind a framework to manage graph data structure and some algorithms using Scala.

This project is based on "Graphs and algorithms" lesson at "École des Mines de Nantes".

This project will probably use this resource : http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf

Graph generation implementation

I created a function that generates an adjacency matrix to represent the graph. This function takes the graph order (number of nodes), the number of edges (or arcs) and whether the graph is directed or not.

I tried to figure out the efficient algorithm to generate a directed graph.

The matrix is generated using this piece of code :

(0 until graphOrder).toList.map { i =>
  (0 until graphOrder).toList.map { j =>
    arcs.shouldIKeepTheArc((i, j))
      .toInt // trick : true => 1 ; false => 0
  }
}

I created a matrix using a double nested ranges (0 until graphOrder).

But, the question is : how to implement shouldIKeepTheArc ?

2 algorithms : top-bottom and bottom-top

These two algorithms have to generate an exact number of arcs. I mean they have to answer yes to the question shouldIKeepTheArc a given number of times.

The graph is a simple one (must have no loop)

Top-bottom

The idea of this algorithm is to generate arcs of the graph.

This algorithm is efficient when there is only "few" arcs to generate because the more arcs we need more the probability to get a arc that does not already exists falls.

Bottom-top

The idea of this algorithm is to generate arcs "to remove" from the graph.

This algorithm is efficient when there is only "few" arcs to remove for the same reason.

Where is the threshold ?

For now I have set the threshold at numberOfArcs < (graphOrder * graphOrder) / 2.

This logically send more time when numberOfArcs is not far than (graphOrder * graphOrder) / 2.

Number of nodes Number of arcs Time (ms)
1000 1000 * 0 127,15
1000 1000 * 100 749,41
1000 1000 * 200 746,81
1000 1000 * 300 1108,87
1000 1000 * 400 1473,48
1000 1000 * 500 1688,84
1000 1000 * 600 1274,71
1000 1000 * 700 971,43
1000 1000 * 800 667,84
1000 1000 * 900 357,07

I think that there are better algorithm and better threshold.