Stack Overflow
Stack Overflow

Questions tagged [subgraph]

Use this tag for questions related to a Subgraph, a part of a larger graph.

313 questions
226
votes
4 answers

GraphViz - How to connect subgraphs?

In the DOT language for GraphViz, I'm trying to represent a dependency diagram. I need to be able to have nodes inside a container and to be able to make nodes and/or containers dependent on other nodes and/or containers. I'm using subgraph to…
Winston Smith
  • 21,585
  • 10
  • 60
  • 75
59
votes
8 answers

Finding all disconnected subgraphs in a graph

I have a graph which contains an unknown number of disconnected subgraphs. What's a good algorithm (or Java library) to find them all?
Ollie Glass
  • 19,455
  • 21
  • 76
  • 107
55
votes
5 answers

top-down subgraphs, left-right inside subgraphs

I'd like to have my graph looks like this: But I can only get this: The problem is, rankdir does not work in subgraph. So, how to emulate it? The code: digraph G { node [shape = circle] 0 [style = invis] 0 -> "0A" subgraph…
Pitel
  • 5,334
  • 7
  • 45
  • 72
30
votes
1 answer

group nodes with subgraphs

I'd like to group some nodes with the following code digraph dataflow { subgraph pipeline { relations; synonyms; articles; } subgraph lucene { index; search; } training_data - > index; …
Reactormonk
  • 21,472
  • 14
  • 74
  • 123
27
votes
5 answers

minimum connected subgraph containing a given set of nodes

I have an unweighted, connected graph. I want to find a connected subgraph that definitely includes a certain set of nodes, and as few extras as possible. How could this be accomplished? Just in case, I'll restate the question using more precise…
hyluka
  • 273
  • 3
  • 4
26
votes
2 answers

Find all complete sub-graphs within a graph

Is there a known algorithm or method to find all complete sub-graphs within a graph? I have an undirected, unweighted graph and I need to find all subgraphs within it where each node in the subgraph is connected to each other node in the…
Mantas Vidutis
  • 16,376
  • 20
  • 76
  • 92
18
votes
2 answers

Loading a Neo4j subgraph into Networkx

I have been dealing with Neo4j through python's Bulbflow and now need a way to save/export subgraphs. I have seen Java and even Ruby approaches for doing this, however a simple Python approach seems to be hiding from me.. So far, I have found two…
zanbri
  • 5,958
  • 2
  • 31
  • 41
15
votes
1 answer

How do I get graphviz to generate fixed sized subgraphs?

I've been struggling with this for a while and cannot seem to find a straight answer. I'm working with compound subgraphs in graphviz and cannot seem to find the right combination of settings to force two subgraphs to align with each other. Enclosed…
user1818047
  • 151
  • 1
  • 1
  • 3
14
votes
1 answer

How do I position the label of a graphviz subgraph cluster to be on the left?

How do I position the label for subgraph cluster to appear at it's left instead of being centered? digraph mygraph { test1; subgraph cluster_mysubgraph { label = "This text should be at the left of the subgraph - not centered!"; …
chaimp
  • 16,897
  • 16
  • 53
  • 86
13
votes
4 answers

What's the Difference Between Subgraph Isomorphism and Subgraph Monomorphism?

In one of the projects I've worked on, the subject of isomorphism versus monomorphism came up. A little background: I'm no expert on graph theory and have no formal training in it. But this topic is very important in chemistry, where chemists expect…
Rich Apodaca
  • 28,316
  • 16
  • 103
  • 129
13
votes
2 answers

List of C++ libraries for Graph Theory

I'm going to start a scientific project about automata and graph theory, and I'm searching for a graph library that supports features like: directed/undirected graphs graph isomorphism test (i.e. is graph g1 isomorphic w.r.t. g2?) subgraph…
Riccardo T.
  • 8,907
  • 5
  • 38
  • 78
12
votes
1 answer

How to layout multiple subgraphs inside a master graph in dot?

I am trying to create a graph using dot. The graph I have come up till now is given below and code is also given. Code digraph top { node [shape=record ,penwidth = 2,fontsize=25]; graph [labeljust=l] ratio="fill"; subgraph cluster_1 { …
Kunal Jha
  • 2,102
  • 4
  • 24
  • 34
12
votes
1 answer

graph - How to find maximum induced subgraph H of G such that each vertex in H has degree ≥ k

Here is an excise for graph. Given an undirected graph G with n vertices and m edges, and an integer k, give an O(m + n) algorithm that finds the maximum induced subgraph H of G such that each vertex in H has degree ≥ k, or prove that no such graph…
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
10
votes
3 answers

Pattern matching in graphs

I'm trying to find tool/algorithm for searching sections that corresponds to specified pattern in oriented graph, e.g.: A->B->C or or A<->B->C Please, suggest me direction of my searches. I mean pattern matching. I need to find all group of nodes…
Jamal
  • 365
  • 2
  • 3
  • 10
10
votes
5 answers

sampling subgraphs from different sizes using igraph

I have an igraph object mygraph with ~10,000 nodes and ~145,000 edges, and I need to create a number of subgraphs from this graph but with different sizes. What I need is to create subgraphs from a determined size (from 5 nodes to 500 nodes) where…
user2380782
  • 1,542
  • 4
  • 22
  • 60
1
2 3
…
20 21