Feature: Add DiGraph, MultiGraph and MultiDiGraph graph types in Python bindings

[davvard]

Describe what you are looking for

I am looking for DiGraph, MultiGraph and MultiDiGraph graph types in Python bindings

Can you contribute to the implementation?

• I can contribute

Is your feature request specific to a certain interface?

Official Python bindings

Contact Details

[email protected]

Is there an existing issue for this?

• I have searched the existing issues

Code of Conduct

• I agree to follow this project's Code of Conduct

[ashvardanian]

@davvard, can you please share the table describing expected behavior for edge ID generation here?

[davvard]

Graph (node_ids, edge_ids)	Edge Ids
Graph (false, false)	None
Graph (true, false)	None
Graph (false, true)	Auto Generated
Graph (true, true)	Auto Generated
DiGraph (false, false)	None
DiGraph (true, false)	None
DiGraph (false, true)	Auto Generated
DiGraph (true, true)	Auto Generated
MultiGraph (false, false)	User Defined (Auto Generated)
MultiGraph (true, false)	User Defined (Auto Generated)
MultiGraph (false, true)	User Defined (Auto Generated)
MultiGraph (true, true)	User Defined (Auto Generated)
MultiDiGraph (false, false)	User Defined (Auto Generated)
MultiDiGraph (true, false)	User Defined (Auto Generated)
MultiDiGraph (false, true)	User Defined (Auto Generated)
MultiDiGraph (true, true)	User Defined (Auto Generated)

[ashvardanian]

So node_ids means "labeled nodes" and edge_ids means "labeled edges"? And Edge Ids means "how to generate edge IDs"?

[davvard]

@ashvardanian Yes, that's correct.

[ashvardanian]

Gotcha, @davvard . Can you please patch it into a more readable form with 4 columns, so that its easier to reason about it.

---

Is it a good idea to have both auto-generation and user-defined IDs in the same class? In that case the user may end up accidentally overwriting and edge we have created... isn't that the case? Is this how NetworkX works?

[davvard]

@ashvardanian Yes I think it is good idea...if you create edges with attributes with auto-generation and after it you add edge with ID that already exists the program will merge edge attributes...This is how NetworkX works.
Example

 db = ustore.DataBase()
 graph = ustore.MultiGraph(db, 'multigraph', relations='edges')
 graph.add_edge(1, 2, name='edge1', weight = 2)
 graph.add_edge(1, 2, key=0, weight=3)
 print(list(graph.edges(data=True))) # [(1, 2, {'name': 'edge1', 'weight': 3})]

[ashvardanian]

Gotcha! Full compatibility is great! And how do they generate the IDs, @davvard ?

[davvard]

@ashvardanian They start from 0 for every (source, target)

[davvard]

Class Name	Labeled Edges	How to generate IDs?
Graph	❌	None
Graph	✅	Auto Generated
DiGraph	❌	None
DiGraph	✅	Auto Generated
MultiGraph	❌	User Defined (Auto Generated)
MultiGraph	✅	User Defined (Auto Generated)
MultiDiGraph	❌	User Defined (Auto Generated)
MultiDiGraph	✅	User Defined (Auto Generated)

[ashvardanian]

@davvard That sounds ugly... as we would either need to store a counter for every pair... or retrieve the list of all the neighbors every time. Which IDs will NetworkX generate for the edge between nodes A and B ?

1. add A-B, add A-B, remove last, add A-B
2. add A-B, add A-B, remove first, add A-B

[davvard]

@ashvardanian NetworkX will generate this IDs

1. 0, 1, 1
2. 0, 1, 2