diff --git a/dvc/dependency/base.py b/dvc/dependency/base.py
index ba993b21d..9290389d1 100644
--- a/dvc/dependency/base.py
+++ b/dvc/dependency/base.py
@@ -39,6 +39,10 @@ class DependencyBase(object):
     def supported(cls, url):
         return cls.match(url) != None
 
+    @property
+    def sep(self):
+        return '/'
+
     def changed(self):
         raise NotImplementedError
 
diff --git a/dvc/dependency/local.py b/dvc/dependency/local.py
index 081ae81e6..7336f9298 100644
--- a/dvc/dependency/local.py
+++ b/dvc/dependency/local.py
@@ -39,6 +39,10 @@ class DependencyLOCAL(DependencyBase):
         self.path_info = {'scheme': 'local',
                           'path': self.path}
 
+    @property
+    def sep(self):
+        return os.sep
+
     @property
     def rel_path(self):
         return os.path.relpath(self.path)
diff --git a/dvc/project.py b/dvc/project.py
index 1cea1725b..98c17d286 100644
--- a/dvc/project.py
+++ b/dvc/project.py
@@ -399,22 +399,20 @@ class Project(object):
     def graph(self):
         G = nx.DiGraph()
         stages = self.stages()
-
-        outs_map = {}
-        for stage in stages:
-            for o in stage.outs:
-                outs_map[o.path] = stage
+        outs = self.outs()
 
         for stage in stages:
             node = os.path.relpath(stage.path, self.root_dir)
             G.add_node(node, stage=stage)
             for dep in stage.deps:
-                dep_stage = outs_map.get(dep.path, None)
-                if not dep_stage:
-                    continue
-                dep_node = os.path.relpath(dep_stage.path, self.root_dir)
-                G.add_node(dep_node, stage=dep_stage)
-                G.add_edge(node, dep_node)
+                for out in outs:
+                    if out.path != dep.path and not dep.path.startswith(out.path + out.sep):
+                        continue
+
+                    dep_stage = out.stage
+                    dep_node = os.path.relpath(dep_stage.path, self.root_dir)
+                    G.add_node(dep_node, stage=dep_stage)
+                    G.add_edge(node, dep_node)
 
         return G
 

Dependency files under output directory
i.e.
```
dvc run -c . -f unarchive.dvc -d data/Posts.xml.tgz -o data/xml/ tar zxf data/Posts.xml.tgz  -C data/xml/
dvc run -c . -f tsv.dvc -d data/xml/ -d code/xml_to_tsv.py -d code/conf.py -o data/tsv/ python code/xml_to_tsv.py
dvc run -c . -f split.dvc -d data/tsv/ -d code/split_train_test.py -d code/conf.py -o data/tt/  python code/split_train_test.py 0.33 20180319
dvc run -c . -f feature.dvc -d code/featurization.py -d code/conf.py -d data/tt -o data/matrix/ python code/featurization.py
dvc run -c . -f model.dvc -d data/matrix/matrix-train.p -d code/train_model.py -d code/conf.py -o data/model/model.p python code/train_model.py 20180319
dvc run -c . -f Dvcfile -d data/model/model.p -d data/matrix/matrix-test.p -d code/evaluate.py -d code/conf.py -o data/eval.txt python code/evaluate.py
```
Kudos @Nicolabo !
diff --git a/tests/test_repro.py b/tests/test_repro.py
index 64129fe22..7bc5b4b14 100644
--- a/tests/test_repro.py
+++ b/tests/test_repro.py
@@ -36,6 +36,27 @@ class TestRepro(TestDvc):
                      cmd='python {} {} {}'.format(self.CODE, self.FOO, self.file1))
 
 
+class TestReproDepUnderDir(TestDvc):
+    def test(self):
+        self.dir_stage = self.dvc.add(self.DATA_DIR)
+
+        self.file1 = 'file1'
+        self.file1_stage = self.file1 + '.dvc'
+        self.dvc.run(fname=self.file1_stage,
+                     outs=[self.file1],
+                     deps=[self.DATA, self.CODE],
+                     cmd='python {} {} {}'.format(self.CODE, self.DATA, self.file1))
+
+        self.assertTrue(filecmp.cmp(self.file1, self.DATA))
+
+        os.unlink(self.DATA)
+        shutil.copyfile(self.FOO, self.DATA)
+
+        stages = self.dvc.reproduce(self.file1_stage)
+        self.assertEqual(len(stages), 2)
+        self.assertTrue(filecmp.cmp(self.file1, self.FOO))
+
+
 class TestReproNoDeps(TestRepro):
     def test(self):
         out = 'out'

pip install -e .
parse_log_pytest
requirements.txt
pytest pytest-cov pytest-xdist pytest-mock pytest-asyncio
apt-get update apt-get install -y gcc
3.9
requirements.txt
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
altgraph==0.17.4
bcrypt==4.3.0
binaryornot==0.4.4
boto3==1.7.4
botocore==1.10.84
cachetools==4.2.4
certifi==2025.1.31
cffi==1.17.1
chardet==5.2.0
charset-normalizer==3.4.1
colorama==0.4.6
configobj==5.0.9
configparser==7.2.0
coverage==7.8.0
cryptography==44.0.2
decorator==5.2.1
dill==0.2.9
docutils==0.21.2
-e git+https://github.com/iterative/dvc.git@436a9fc81776a383296c72f5e418a1b7726e6db8#egg=dvc
exceptiongroup==1.2.2
execnet==2.1.1
future==0.16.0
gapic-google-cloud-datastore-v1==0.15.3
gapic-google-cloud-error-reporting-v1beta1==0.15.3
gapic-google-cloud-logging-v2==0.91.3
gitdb==4.0.12
GitPython==3.1.44
google-api-core==0.1.4
google-auth==1.35.0
google-cloud==0.32.0
google-cloud-bigquery==0.28.0
google-cloud-bigquery-datatransfer==0.1.1
google-cloud-bigtable==0.28.1
google-cloud-container==0.1.1
google-cloud-core==0.28.1
google-cloud-datastore==1.4.0
google-cloud-dns==0.28.0
google-cloud-error-reporting==0.28.0
google-cloud-firestore==0.28.0
google-cloud-language==1.0.2
google-cloud-logging==1.4.0
google-cloud-monitoring==0.28.1
google-cloud-pubsub==0.30.1
google-cloud-resource-manager==0.28.1
google-cloud-runtimeconfig==0.28.1
google-cloud-spanner==0.29.0
google-cloud-speech==0.30.0
google-cloud-storage==1.6.0
google-cloud-trace==0.17.0
google-cloud-translate==1.3.1
google-cloud-videointelligence==1.0.1
google-cloud-vision==0.29.0
google-crc32c==1.7.1
google-gax==0.15.16
google-resumable-media==2.7.2
googleapis-common-protos==1.69.2
grpc-google-iam-v1==0.11.4
grpcio==1.71.0
httplib2==0.22.0
idna==3.10
iniconfig==2.1.0
jmespath==0.10.0
jsonpath-rw==1.4.0
macholib==1.16.3
nanotime==0.5.2
networkx==3.2.1
ntfsutils==0.1.5
oauth2client==3.0.0
packaging==24.2
paramiko==3.5.1
pefile==2024.8.26
pluggy==1.5.0
ply==3.8
proto-google-cloud-datastore-v1==0.90.4
proto-google-cloud-error-reporting-v1beta1==0.15.3
proto-google-cloud-logging-v2==0.91.3
protobuf==3.20.3
psutil==5.9.8
pyasn1==0.6.1
pyasn1_modules==0.4.2
pycparser==2.22
PyInstaller==3.3.1
PyNaCl==1.5.0
pyparsing==3.2.3
pytest==8.3.5
pytest-asyncio==0.26.0
pytest-cov==6.0.0
pytest-mock==3.14.0
pytest-xdist==3.6.1
python-dateutil==2.9.0.post0
pytz==2025.2
PyYAML==6.0.2
reflink==0.2.0
requests==2.32.3
rsa==4.9
s3transfer==0.1.13
schema==0.7.7
six==1.17.0
smmap==5.0.2
tomli==2.2.1
typing_extensions==4.13.0
urllib3==2.3.0
zc.lockfile==3.0.post1

name: dvc
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.4.4=h6a678d5_1
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=3.0.16=h5eee18b_0
  - pip=25.0=py39h06a4308_0
  - python=3.9.21=he870216_1
  - readline=8.2=h5eee18b_0
  - setuptools=75.8.0=py39h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - tzdata=2025a=h04d1e81_0
  - wheel=0.45.1=py39h06a4308_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - altgraph==0.17.4
      - bcrypt==4.3.0
      - binaryornot==0.4.4
      - boto3==1.7.4
      - botocore==1.10.84
      - cachetools==4.2.4
      - certifi==2025.1.31
      - cffi==1.17.1
      - chardet==5.2.0
      - charset-normalizer==3.4.1
      - colorama==0.4.6
      - configobj==5.0.9
      - configparser==7.2.0
      - coverage==7.8.0
      - cryptography==44.0.2
      - decorator==5.2.1
      - dill==0.2.9
      - docutils==0.21.2
      - exceptiongroup==1.2.2
      - execnet==2.1.1
      - future==0.16.0
      - gapic-google-cloud-datastore-v1==0.15.3
      - gapic-google-cloud-error-reporting-v1beta1==0.15.3
      - gapic-google-cloud-logging-v2==0.91.3
      - gitdb==4.0.12
      - gitpython==3.1.44
      - google-api-core==0.1.4
      - google-auth==1.35.0
      - google-cloud==0.32.0
      - google-cloud-bigquery==0.28.0
      - google-cloud-bigquery-datatransfer==0.1.1
      - google-cloud-bigtable==0.28.1
      - google-cloud-container==0.1.1
      - google-cloud-core==0.28.1
      - google-cloud-datastore==1.4.0
      - google-cloud-dns==0.28.0
      - google-cloud-error-reporting==0.28.0
      - google-cloud-firestore==0.28.0
      - google-cloud-language==1.0.2
      - google-cloud-logging==1.4.0
      - google-cloud-monitoring==0.28.1
      - google-cloud-pubsub==0.30.1
      - google-cloud-resource-manager==0.28.1
      - google-cloud-runtimeconfig==0.28.1
      - google-cloud-spanner==0.29.0
      - google-cloud-speech==0.30.0
      - google-cloud-storage==1.6.0
      - google-cloud-trace==0.17.0
      - google-cloud-translate==1.3.1
      - google-cloud-videointelligence==1.0.1
      - google-cloud-vision==0.29.0
      - google-crc32c==1.7.1
      - google-gax==0.15.16
      - google-resumable-media==2.7.2
      - googleapis-common-protos==1.69.2
      - grpc-google-iam-v1==0.11.4
      - grpcio==1.71.0
      - httplib2==0.22.0
      - idna==3.10
      - iniconfig==2.1.0
      - jmespath==0.10.0
      - jsonpath-rw==1.4.0
      - macholib==1.16.3
      - nanotime==0.5.2
      - networkx==3.2.1
      - ntfsutils==0.1.5
      - oauth2client==3.0.0
      - packaging==24.2
      - paramiko==3.5.1
      - pefile==2024.8.26
      - pluggy==1.5.0
      - ply==3.8
      - proto-google-cloud-datastore-v1==0.90.4
      - proto-google-cloud-error-reporting-v1beta1==0.15.3
      - proto-google-cloud-logging-v2==0.91.3
      - protobuf==3.20.3
      - psutil==5.9.8
      - pyasn1==0.6.1
      - pyasn1-modules==0.4.2
      - pycparser==2.22
      - pyinstaller==3.3.1
      - pynacl==1.5.0
      - pyparsing==3.2.3
      - pytest==8.3.5
      - pytest-asyncio==0.26.0
      - pytest-cov==6.0.0
      - pytest-mock==3.14.0
      - pytest-xdist==3.6.1
      - python-dateutil==2.9.0.post0
      - pytz==2025.2
      - pyyaml==6.0.2
      - reflink==0.2.0
      - requests==2.32.3
      - rsa==4.9
      - s3transfer==0.1.13
      - schema==0.7.7
      - six==1.17.0
      - smmap==5.0.2
      - tomli==2.2.1
      - typing-extensions==4.13.0
      - urllib3==2.3.0
      - zc-lockfile==3.0.post1
prefix: /opt/conda/envs/dvc

tests/test_repro.py::TestReproDepUnderDir::test
tests/test_repro.py::TestReproMissingMd5InStageFile::test tests/test_repro.py::TestReproShell::test
tests/test_repro.py::TestReproNoDeps::test tests/test_repro.py::TestReproForce::test tests/test_repro.py::TestReproChangedCode::test tests/test_repro.py::TestReproChangedData::test tests/test_repro.py::TestReproChangedDeepData::test tests/test_repro.py::TestReproPhony::test tests/test_repro.py::TestNonExistingOutput::test tests/test_repro.py::TestReproDataSource::test tests/test_repro.py::TestReproChangedDir::test tests/test_repro.py::TestCmdRepro::test tests/test_repro.py::TestCmdReproChdir::test tests/test_repro.py::TestReproExternalBase::test tests/test_repro.py::TestReproExternalS3::test tests/test_repro.py::TestReproExternalGS::test tests/test_repro.py::TestReproExternalHDFS::test tests/test_repro.py::TestReproExternalLOCAL::test
dvc/dependency/local.py dvc/dependency/base.py dvc/project.py
dvc/dependency/local.py dvc/dependency/base.py dvc/project.py