# Graph algorithm for Lightgraph

**URL:** <https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708>\
**Category:** General Usage\
**Created:** [January 21, 2021, 8:11am UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708 "2021-01-21T08:11:57Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [January 21, 2021, 8:11am UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/1 "2021-01-21T08:11:57Z")

</div>

Hi,

below is a graphical representation of 3 SQL Tables with their corresponding columns. And their intertable connections.

In red circles are four columns of two different tables that are not directly connected with each other.

I am looking for an algorithm that takes a set of vertices as input (red cicles) and then gives me the shortest path possible that links the input vertices. In this case:

**C3.2** -\>T3  
**C3.1** -\>T3  
T3-\>C3.4  
C3.4-\>C2.1  
C2.1-\>T2  
T2-\>C2.3  
C2.3-\>C1.5  
C1.5-\>T1  
T1-\> **C1.1**  
T1-\> **C1.2**

I realize that especially the first 2 and the last 2 are not perse what you would expect because they branch inward (or outward) but any algo that comes reasonably close to this is already a great help!

![image](https://global.discourse-cdn.com/julialang/original/3X/0/0/00890d4374c2e74d146d5dcb24e9e4bfde98dbbb.png)

---

<div class="post-metadata">

**Author:** ![healyp](https://avatars.discourse-cdn.com/v4/letter/h/67e7ee/32.png) [@healyp](https://discourse.julialang.org/u/healyp)\
**Post date:** [January 21, 2021, 10:13am UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/2 "2021-01-21T10:13:53Z")

</div>

I don’t think there are any specialized algorithms for multiple start / end points. Even if there were AFAIK the time complexity of the best _all-pairs shortest path_ algorithm isn’t a whole lot better than the naïve alg of running SP on all C(|V|, 2) start- end-vertex pairings – maybe a log factor in the difference.

How large (relative to the vertex set) do you expect your circled vertices to be? If it’s a small fraction then you would probably be as well off to go with the naïve strategy above.

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [January 21, 2021, 11:08am UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/3 "2021-01-21T11:08:03Z")

</div>

… well that isn’t good news 🙂 .

would it help if I take advantage of the structure itself. e.g. instead of input of 4 columns I only give T3 as start and T1 as end (every column is connected to a Table)? This will of course give me only part of the story but at least something to start out with.

Where can I find information on designing an algorithm for graphs specifically for julia or in python?

thanks,

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [January 21, 2021, 12:39pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/4 "2021-01-21T12:39:17Z")

</div>

It would help to know a little more about the structure of your graph in the worst case.

- is it always a tree or can there be multiple connections between Ts
- are your input vertices always leaves (have only one connection) or could you, if we take your example, start with something like ( C2.1, C1.5 ) as input?
- are there weights associated with anything or is it just (connection or no connection)

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [January 21, 2021, 12:49pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/5 "2021-01-21T12:49:18Z")

</div>

If I understand your problem correctly, the term you should search for is [Steiner Tree](https://en.wikipedia.org/wiki/Steiner_tree_problem).

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [January 21, 2021, 4:12pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/6 "2021-01-21T16:12:44Z")

</div>

Hi,

- is it always a tree or can there be multiple connections between Ts —  
_The table/column structure will always be a `star_graph` meaning 1 point in de middle which is the table and n columns (n\>1). But it could be that 1 table has connections with multiple other tables but it must at least have 1 connection otherwise its disjoined._

- are your input vertices always leaves (have only one connection) or could you, if we take your _example, start with something like ( C2.1, C1.5 ) as input? —_  
_Good question, yes it should be possible to use a leave that is simulatenously also a ‘bridge’ between its own table and another._

- are there weights associated with anything or is it just (connection or no connection)—  
_No, there are no weights and the edges a bidirectional.A weigh could be added but they would all be the same weight since there is no distinction (cost difference) between them_

I hope i understood your question correctly please tell me if i missed the mark!

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [January 21, 2021, 4:16pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/7 "2021-01-21T16:16:17Z")

</div>

Hi @GunnarFarneback ,

The general wikipage of ‘steiner trees’  
did not give me enough to make the connection between my current problem and that concept. Could you explain the connection to me?

best,

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [January 21, 2021, 4:32pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/8 "2021-01-21T16:32:30Z")

</div>

The minimum Steiner tree problem in graphs means to find the smallest tree that connects a given set of terminal nodes, which seemed to be what you wanted to find.

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [January 22, 2021, 12:09am UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/9 "2021-01-22T00:09:42Z")

</div>

> [@AlexanderChen](#):
>
> The table/column structure will always be a `star_graph` meaning 1 point in de middle which is the table and n columns (n\>1). But it could be that 1 table has connections with multiple other tables but it must at least have 1 connection otherwise its disjoined.

Yeah What I meant was rather if circles are possible, like `T1>C1.2>C2.1>T2>C2.2>C3.1>T3>C3.2>C1.1>T1`

Gunnar did point you into the right direction. This also tells you, that this problem is NP-complete in the general case. (if your case is general or sufficiently structured is still under question)

Nontheless, this means nothing but that you don’t want to solve it exactly for big, complex problems. You should be fine with any of the approximaton algorithms for that problem.

So, anyways, what you want to do is (probably) the following (disclaimer: I’m not a graph theorist):

1. reduce your problem size as much as possible:

- you can safely drop all vertices with 1 edge that are not your “starting points”, they can never minimally connect other vertices and thus can not appear in the solution
- think about further reductions: is every connection between tables of the form `T1>C1.x>C2.y>T2` without any side branches? Or can something like this exist:  
 ![q1](https://global.discourse-cdn.com/julialang/original/3X/2/7/27a156cc9e6b0399cd25309be9e54035cec197bf.png)  
And if it did, would this imply:  
 ![q2](https://global.discourse-cdn.com/julialang/original/3X/b/0/b06f4973b09f251af00ea95f4770e5928bd4a511.png)  
And what shall the cost of “traversing” this be? Could be 3, but it may be just as cheap having 3 of the interlinked tables as having 2 or 4. (This depends on your definition, is every edge/link costly or do you just want to minimize the amount of inter-table connections?)  
Depending on that you may find more powerful reductions, e.g. it may be possible to contract each inter-table connection to a single vertex, or a single edge! If you can reduce your problem size sufficiently, the choice of algorithm is probably near-irrelevant, it’s rare that you’ll link 100+ SQL tables after all, so your worst case problem may still be trivially small with a “costly” algorithm.

1. Depending on the topology that is allowed (will those diagramms contain circles or not, that’s really the point), you eitehr pick one of the algorithms from the wikipedia page or a different one from that field and apply it liberally.  
Or - if these are always tree-like (cycle free) - a simple dfs will give you an optimal solution in acceptable time.

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [January 25, 2021, 12:21pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/10 "2021-01-25T12:21:27Z")

</div>

@FPGro & @GunnarFarneback Thank you both for the good feedback just a couple of answers to open questions concering FPGro.

> Yeah What I meant was rather if circles are possible, like `T1>C1.2>C2.1>T2>C2.2>C3.1>T3>C3.2>C1.1>T1`
> 
> Gunnar did point you into the right direction. This also tells you, that this problem is NP-complete in the general case. (if your case is general or sufficiently structured is still under question)

yes a circle path is technically possible.

> 1. reduce your problem size as much as possible:
> 
> - you can safely drop all vertices with 1 edge that are not your “starting points”, they can never minimally connect other vertices and thus can not appear in the solution
> - think about further reductions: is every connection between tables of the form `T1>C1.x>C2.y>T2` without any side branches? Or can something like this exist:
> 
> ![q1](https://global.discourse-cdn.com/julialang/original/3X/2/7/27a156cc9e6b0399cd25309be9e54035cec197bf.png)
> 
> And if it did, would this imply:
> 
> ![q2](https://global.discourse-cdn.com/julialang/original/3X/b/0/b06f4973b09f251af00ea95f4770e5928bd4a511.png)

1. yes, I was thinking along similar lines. Once you know the input nodes that need to connect one could construct a temp graph that only features the tables vertices, the input vertices (both starting and finishing) and the ‘join vertices’. I was thinking that I could go one step further and take out temporarily the input vertices and exchange them for the tables on which the input vertices are connected. This way I only have the ‘tables’ and ‘join’ vertices.

Yes, it is implied that if the first picture is possible then the second picture is possible. But until that edge is made by the “graphista” for a lack of a better term, it is not possible to travel that edge. So there is no knowledge graph kind of reasoning. Its pretty plain in that respect.

> And what shall the cost of “traversing” this be? Could be 3, but it may be just as cheap having 3 of the interlinked tables as having 2 or 4. (This depends on your definition, is every edge/link costly or do you just want to minimize the amount of inter-table connections?)

I want to keep the inter-table connections to a minimum so I will have to start thinking about a weighted graph. Not sure which weight should be given.I have to visualize that better to understand it.

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [February 6, 2021, 9:35am UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/11 "2021-02-06T09:35:02Z")

</div>

Hey, just wanted to ask how far you came with your approach, and if it would be worthwhile to to share it?

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [February 6, 2021, 1:00pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/12 "2021-02-06T13:00:52Z")

</div>

Hi @FPGro,

The approach above is want I am currently pursuing. At the moment I am experimenting how to best transform the input of columns into a list of their tables. So if I give it C2.1 it gives me T2 back. I wanted to see if I can find a pattern in the Matrix() that I can transform into an algorithm. Because of the star\_graph structure there is a clear pattern but I am not convinced i can find an algo that will always work. So I am thinking about using Metagraphs but I need to be able to ‘query’ on Metagraph levl, I will need to know more of the package to understand if that is feasible.

I also have concluded that I need weights on my edges but that is not a big challenge.

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [February 6, 2021, 1:15pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/13 "2021-02-06T13:15:57Z")

</div>

Sounds good. I just searched out of curiosity, and there appears to be an approximate minimal steiner tree algorithm in the `LightGraphs` package already 🙂 so if you can transform your graph in a suitable way and determine the weights properly, you can probably use that. Good luck!

> <https://github.com/sbromberger/LightGraphs.jl/blob/ce533729381a6c0b0d8a1eb5f0c3e058833cb55b/src/steinertree13/steiner_tree.jl#L43>

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [February 6, 2021, 2:41pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/14 "2021-02-06T14:41:05Z")

</div>

thanks! I thought it did not exist so i sortof resigned myself in having to figure it out on my own 🙂

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [February 6, 2021, 3:22pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/15 "2021-02-06T15:22:02Z")

</div>

Sorry then for not pointing that out earlier 😅 I thought you did but it makes sense that you didn’t find much, as Gunnar just pointed out the correct name for that problem. Anyways, hope this helps!

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [February 6, 2021, 7:02pm UTC](https://discourse.julialang.org/t/graph-algorithm-for-lightgraph/53708/16 "2021-02-06T19:02:24Z")

</div>

no worries, I was reading de docs there was no mention of steiner algo but in the `help?>` i see it.

just for refence, this is the graph that i think is complex enough to start with:

![image](https://global.discourse-cdn.com/julialang/original/3X/9/0/902c7b6eea595e80407bff0d16089dbe0362f407.png)

and this is the pattern in the matrix of this same graph:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/c/c/cc65ad42f1ce910917ff85bae405f127a40b2608.png)